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?

  • I made an edit to focus the question on Gaifman's argument. You may roll this back or continue editing it. Hopefully the reference to Gaifman will focus the question you are asking. Welcome to this SE! – Frank Hubeny Oct 18 '18 at 17:52
  • 2
    It's not a proof by contradiction. Period. Given an arbitrary list of real numbers, there is some real number not on it. That's stated and proved directly. Not contradiction. Not contradiction. Happy to debunk this common misunderstanding. Did I mention it's not a proof by contradiction? – user4894 Oct 18 '18 at 18:01
  • If I understand your question correctly, you are asking "IF" we could construct a set with the property that we could not formally decide whether it is diagonalisable or not, then would this invalidate the diagonal argument as applied by Cantor. Yes. It would say that the predicate "is diagonalisable" is not a classical predicate since it would not obey the law of the excluded middle and therefore it has no place in any argument using classical logic. – Nick Oct 18 '18 at 18:06
  • 3
    I would suggest completely rewriting the question, making what you are actually asking concise instead of just adding more and more extra points to address what was said in the comments. I can't look at what you wrote and easily figure out what your main question is, and questions on this site are supposed to be one single question per post, so that is a huge issue. I understand what you're asking is technical, but right now this question needs to be salvaged by editing and pruning unnecessary information that is muddling the main question. – Not_Here Oct 19 '18 at 14:06
  • 2
    This question is still disorganized and muddled, I am really disappointed that it was reopened and I am going to open up a discussion about it on meta. As an example of how it's still failing, first of all, the first sentence of the last giant block of a paragraph is missing a closed parenthesis so the sentence makes no sense. Second of all, you still do not have a clear and concise statement of your question. You spend the first four paragraphs going into irrelevant background information without having introduced the topic of your question, that is not good for readability. – Not_Here Oct 20 '18 at 12:27

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.

  • Thank you Mr. Thornley. If we have a 1-to-1 mapping from set A to R and list the elements of A, yet cannot show we arrive at a contradiction, then there exists a possible mapping that has not been shown to lead to contradiction. The fact that it has not been shown to be impossible to go from N to A to R indicates that we have not eliminated the possibility of the existence of such a map. Such a map would provide a case of N being equinumerous with R. I am not saying this proves there is such a map, just that we do not have a proof that there is not....that is what Cantor's purports to be. – 21stCenturyParadox Oct 18 '18 at 23:51
  • Mr Thornley...regarding your second paragraph: how do we know sets A and B are not equinumerous with R? Please explain. You also claim they can be put into a 1-1 correspondence with N, is there a proof of that? – 21stCenturyParadox Oct 19 '18 at 0:00
  • It may be possible to go from N to A or A to R with 1-1 maps, but Cantor's original proof (which you have not shown invalid) shows that it's not possible to go from N to R. Your statement "the other complement to an element of N" suggests 1-1, and, in any case, if no element of N is mapped to an uncountable number of reals we can make a mapping 1-1. If the mapping isn't 1-1 to N (or at least can't be made to be) then we can't do the diagonalization in the first place. – David Thornley Oct 19 '18 at 15:53

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 s1, s2, … , sn, … is any enumeration of elements from T, then there is always an element s of T which corresponds to no sn 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 s1, s2, … , sn, … is any enumeration of elements from T, then there is always an element s of T which corresponds to no sn 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.


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

  • Thank you Mr Hubeny...yes, I see, a pair of equinumerous subsets of N will defeat any effort to challenge Cantor's argument via equinumerous subsets of R. Perhaps that is why I have never seen such a challenge in anything I have read. As you say it is easy to get an interleaving. – 21stCenturyParadox Oct 19 '18 at 2:44
  • I added an edit to my original post...I would be interested in hearing your thoughts. – 21stCenturyParadox Oct 19 '18 at 12:51
  • @21stCenturyParadox There may be other approaches to the real numbers worth considering. Regarding the Liar paradox, I am interested in logical systems that do not permit the law of the excluded middle except for propositions where one can derive the proposition. See Fitch's Symbolic Logic. The linked papers by Bohm and others look interesting. I hope you keep bringing up questions here. Make them very specific, perhaps ones you almost have an answer for. Many questions may lead to a better overall insight after they have been asked. Best wishes. – Frank Hubeny Oct 19 '18 at 14:02
  • Thank you Mr Hubeny...unfortunately the question has been put on hold...I reworked it to give it a better focus. After consideration I have a reply to your idea regarding changing the mapping sending A to odds and B to evens...that idea misses my point. I claim we can exhibit a mapping that is undecidable...changing the mapping does not address that claim. Please see Nick R's comment at the top. – 21stCenturyParadox Oct 19 '18 at 16:58
  • 1
    @21stCenturyParadox You can always ask a different, more specific question. Don't worry that it has been closed. I agree with Nick R's comment. However, I don't think you have a mapping that shows we cannot answer the question whether the diagonal approach works. The assumption is that the reals are countable. So, they can be placed in a 1-1 mapping with the natural numbers. Whatever mapping you come up with has to be a 1-1 mapping with the natural numbers. If many reals can be mapped to 0 in set B, that would not be a 1-1 mapping, but a many to 1 mapping. So it would not work. – Frank Hubeny Oct 19 '18 at 17:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.