Logic related to Cantor's argument [closed]

Question

Suppose we construct a choice function that separates R/{0} in the interval (0,1) (viewed in base 2) into two sets A and B each consisting of an arbitrary element chosen from every pair of complements. Suppose then that we map all the elements of B to 0, while each element of the other set A are mapped to an element of 1,2,3,…. Members of R/{0} sent to 0 are identified with an element not in the set R/{0}, hence not in 1,2,3,…while those in A are mapped to elements of 1,2,3... Can we formally decide whether set A is diagonalizable or not?

Answer 1

The diagonalization is a way of finding a real number that is not on a given ordered list of real numbers. In your example, given your A, we can find a real number that is not on the list of A. We don't know if it's in B, and it doesn't matter. The theorem is that we can find a real number not on any ordered/countable list of real numbers. It doesn't say that, given a list A of real numbers, that we can produce a real that isn't in list A or B. If there were a 1-1 correspondence between reals and natural numbers, we could produce an ordered list of all reals, but there is at least one real number not on the list. This is a constructive proof that leads to a proof by contradiction.

Also, Sets A and B are not equinumerous with R. Since the reals in set A can be put into 1-1 correspondence with the natural numbers, and also can be put into 1-1 correspondence with members of set B, then they're countable, and R isn't. If A is equinumerous with R, it's not possible to have a 1-1 correspondence with the natural numbers. You have chosen a countable subset of R, and are trying to prove it's countable, which doesn't prove anything.

Answer 2

Wikipedia outlines Cantor's diagonal argument. Cantor used binary digits in his 1891 proof so using "base 2 representations of the Reals" work in the argument:

In his 1891 article, Cantor considered the set T of all infinite sequences of binary digits (i.e. each digit is zero or one). He begins with a constructive proof of the following theorem:

If s₁, s₂, … , s_n, … is any enumeration of elements from T, then there is always an element s of T which corresponds to no s_n in the enumeration.

Note that the proof starts by considering any enumeration of these sequences of binary digits which can represent the real numbers. In particular this would include the specific enumeration suggested by the OP:

Form two subsets of R[0,1] by choosing arbitrary members of each class, sending one such member of each class to set A and the other to set B. Pair set B with 0 and list the members of set A paired with the natural numbers. Do we not get an arrangement of A and N for which the diagonal argument does not lead to contradiction? For when we try to argue that if we take the diagonal of the N vs. A arrangement and attempt to argue that its complement is not accounted for...it cannot be proved that it is not in B.

Although there are two lists, A and B, one containing the complement of the other, these two lists could be interleaved so that one has one list. An easy way to get this interleaving is to use odd natural numbers for list A and even natural numbers for list B.

That one list is all we would need to create a sequence of binary digits that could not be in either of the two lists using the diagonal method. Hence the diagonal argument would work with this enumeration as well.

Also one is not taking the complement of all of the binary digits in each sequence associated with a natural number, but only the single binary digit on the diagonal. Only one digit is changed in each sequence of binary digits. That's what makes this argument work. That sequence of binary digits from the diagonal is different from any of the sequences paired with the natural numbers by at least one digit, the one on the diagonal.

The existence of that diagonal sequence of binary digits (or digits in any base) would be evidence that the assumed one-to-one mapping of the reals with the natural numbers is not complete. And so there are more real numbers than the natural numbers can enumerate.

---

The following represents edits to the original question as of 10/20/2018.

The question is:

I argue that it is necessary that the author of the diagonal argument show how any and all assumed maps lead to contradiction (without changing the assumed mapping) or the argument fails to be decidable...is this logic incorrect, if so, how?

The particular map is the following:

So I asked can we construct within ZFC a choice function that separates R/{0} in the interval (0,1) (viewed in base 2) into two sets A and B each consisting of an arbitrary element chosen from every pair of complements where information about one of them is completely inaccessible. I thought in this way: by the Axiom of Regularity every non-empty set S contains an element y disjoint from S (essentially a least element). So let’s identify one arbitrary element of each complementary pair of R/{0} in the interval (0,1) with one such element y from outside the set R/{0} …as in sending every element of set B to 0, and elements of the other set A to an element of 1,2,3,…. Then we get an arrangement where those members of R/{0} sent to 0 are identified with an element not in the set R/{0}, hence not in 1,2,3,…while those in A are mapped to elements of 1,2,3...yet the two sets A and B are separately equinumerous with R/{0}. So even though we can view R/{0} as representing the power set of N (aside from the empty set which logically could be paired with the excluded 0), do we get a contradiction via a diagonal argument?

To summarize, assume there exists a choice function that splits the set of real numbers into two sets A and B. The elements in B are the binary complements of the elements in A. Assume there is an enumeration, that is, a one-to-one map, between A and the natural numbers N. Make no assumption about B and N. The diagonal argument will produce a real number, call it r, that is not in A by Cantor's argument. However, we have no guarantee that r is not somewhere in B.

The claim is this provides an example showing that not all mappings between the reals and natural numbers lead to a contradiction.

Let's review the theorem Cantor was trying to prove from Wikipedia:

If s₁, s₂, … , s_n, … is any enumeration of elements from T, then there is always an element s of T which corresponds to no s_n in the enumeration.

Note that T is the set "of all infinite sequences of binary digits (i.e. each digit is zero or one)". T is the set of real numbers.

Note that an "enumeration of elements from T" is a one-to-one mapping of the elements of T to the natural numbers.

Note that the theorem Cantor is attempting to prove applies to "any enumeration". It does not apply to any mapping whatsoever.

Since the example of the map of the set A of real numbers to N is not an enumeration of all the reals, that is, it is not a one-to-one mapping of the real numbers to the natural numbers, it is not one of the mappings that Cantor's theorem is considering.

There are many mappings that Cantor's theorem is not interested in considering. For example, consider the mapping that takes all of the real numbers to the set {1}, the set containing only the natural number 1. This mapping does not usefully help compare the number of real numbers with the number of elements in {1}. Since Cantor is interested in mappings that allow him to compare the number of elements between two sets he would only use one-to-one mappings, enumerations, assuming they exist, not any mappings whatsoever.

---

The OP's question asks: "is this logic incorrect, if so, how?"

The logic is incorrect because it replaces Cantor's original premise about "any enumeration" with "any mapping" and then argues against the new premise as if it were Cantor's. This would be similar to setting up a straw man argument.

---

Reference

Wikipedia, "Cantor's diagonal argument" https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument