7 ms·

I feel like the axiom of choice can't be used here. Let's say we have a infinitely long bit string, b. This equivalence class has an infinite number of element

I feel like the axiom of choice can't be used here. Let's say we have a infinitely long bit string, b. This equivalence class has an infinite number of elements in it! That is, there is an infinite number of strings with suffix b. b, 0b, 1b, 00b, 01b, 10b, 11b, etc. Can you use the axiom of choice in this case? I think it is required that each bin has a finite number of objects, even though there are infinite bins.

ggchappell 17y ago
> Can you use the axiom of choice in this case? Yes, you can. > I think it is required that each bin has a finite number of objects, even though there are infinite bins. No, the axiom says only that the product of nonempty sets is nonempty. It doesn't say anything about the number of sets or their sizes. For those who don't see the connection: Each element of a product of sets consists of a choice of one item from each set. Saying the product is nonempty is saying there is a way to make such choices. For example, the product of {1,2} and {a,b} contains, among other things, the pair (1, b), which can be thought of as choosing 1 from the first set and b from the second. There are restricted versions of the Axiom of Choice (e.g., Countable Choice, Dependent Choice); however, none of these are called "the Axiom of Choice".
- jganetsk 17y ago
  Ok. My other gripe with his argument is that these aren't equivalence classes. Let the string be 01b, where b is an infinitely long bit string. Then the string 01b belongs to equivalence class b, and also equivalence class 1b... and an element cannot belong to multiple equivalence classes at once. The only way out of this is for 1b and b to actually be the same equivalence class, that is, that of b. But, can we do that? I feel like that is wrong.
  - deleted 17y ago
    [deleted]
  - thisrod 17y ago
    It's like saying 128x and 28x, considered as finite sequences of digits followed by a letter, are in the class of sequences that end in x. Except in the infinite case, there are a lot more than 26 letters.
    - jganetsk 17y ago
      They also happen to be in the class of sequences that end in 8x and 28x... also definitely their own classes. So 128x is in at least 4 classes, 28x is in at least 3. Therefore it's not an equivalence relation.
      - ggchappell 17y ago
        Ah, but 8x and 28x are not different classes; they are all the same class. I think it's clearer if you describe things the way the article does. Don't say "these are the classes"; say "here is the relation". As the article says: > Call two such sequences ‘equivalent’ if they are equal after a finite number of entries. To see whether this is an equivalence relation, you only need to check whether it is reflexive, symmetric, and transitive. Figuring out what the classes are, might be interesting, but it is not necessary.
        jganetsk 17y ago
        If an item belongs to multiple equivalence classes, then transitivity does not hold. In other words, if you show that the classes are not disjoint, then it's not an equivalence relation. 18x belongs in the 8x class, but 28x belongs in both the 28x and 8x classes.
        jibiki 17y ago
        And 8x belongs in 28x's class, since 8x and 28x share a tail. I think the author meant for you to interpret "equal after a finite number of entries" in the more normal fashion (e.g., 123x = 456x but 1x != 111x, the prefixes have to have equal length.) But your way seems to work fine too.

ggchappell 17y ago

> Can you use the axiom of choice in this case? Yes, you can. > I think it is required that each bin has a finite number of objects, even though there are infinite bins. No, the axiom says only that the product of nonempty sets is nonempty. It doesn't say anything about the number of sets or their sizes. For those who don't see the connection: Each element of a product of sets consists of a choice of one item from each set. Saying the product is nonempty is saying there is a way to make such choices. For example, the product of {1,2} and {a,b} contains, among other things, the pair (1, b), which can be thought of as choosing 1 from the first set and b from the second. There are restricted versions of the Axiom of Choice (e.g., Countable Choice, Dependent Choice); however, none of these are called "the Axiom of Choice".

jganetsk 17y ago
Ok. My other gripe with his argument is that these aren't equivalence classes. Let the string be 01b, where b is an infinitely long bit string. Then the string 01b belongs to equivalence class b, and also equivalence class 1b... and an element cannot belong to multiple equivalence classes at once. The only way out of this is for 1b and b to actually be the same equivalence class, that is, that of b. But, can we do that? I feel like that is wrong.
- deleted 17y ago
  [deleted]
- thisrod 17y ago
  It's like saying 128x and 28x, considered as finite sequences of digits followed by a letter, are in the class of sequences that end in x. Except in the infinite case, there are a lot more than 26 letters.
  - jganetsk 17y ago
    They also happen to be in the class of sequences that end in 8x and 28x... also definitely their own classes. So 128x is in at least 4 classes, 28x is in at least 3. Therefore it's not an equivalence relation.
    - ggchappell 17y ago
      Ah, but 8x and 28x are not different classes; they are all the same class. I think it's clearer if you describe things the way the article does. Don't say "these are the classes"; say "here is the relation". As the article says: > Call two such sequences ‘equivalent’ if they are equal after a finite number of entries. To see whether this is an equivalence relation, you only need to check whether it is reflexive, symmetric, and transitive. Figuring out what the classes are, might be interesting, but it is not necessary.
      - jganetsk 17y ago
        If an item belongs to multiple equivalence classes, then transitivity does not hold. In other words, if you show that the classes are not disjoint, then it's not an equivalence relation. 18x belongs in the 8x class, but 28x belongs in both the 28x and 8x classes.
        jibiki 17y ago
        And 8x belongs in 28x's class, since 8x and 28x share a tail. I think the author meant for you to interpret "equal after a finite number of entries" in the more normal fashion (e.g., 123x = 456x but 1x != 111x, the prefixes have to have equal length.) But your way seems to work fine too.