(I actually thought this up while listening to a lecture on Goedel's [first] Incompleteness Theorem.)

A rudimentary presentation of the diagonal argument:

(I used the set of all binary sequences, but feel free to use any other uncountable set)

Let $\mathbf{f}:\Bbb{N}\to\bigoplus_{n\in N}\{0,1\}$. Order each binary sequence $\mathbf{f}(n)$ into a list according to $n$...

$$\begin{matrix} &1&2&3&4&\cdots\\1\mapsto&0&\cdots&\cdots&\cdots&\cdots\\2\mapsto&0&1&\cdots&\cdots&\cdots\\3\mapsto&1&0&1&\cdots&\cdots\\4\mapsto&0&1&1&0&\cdots\\\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{matrix}$$

Let $h:\Bbb{N}\to\{0,1\}$, where $h(n)=1-f_n(n)$. Let $v$ be the sequence $\bigoplus_{n=1}^\infty h(n)$. It follows that $v$ is not in the above list (diagonal argument). From this, we may conclude that the set of binary sequences $\bigoplus_{n\in\Bbb{N}}\{0,1\}$ is uncountable.


What if we place $v$ before the first entry in our list? The list is still countable, and now it contains $v$. We can then map each element of our new list to a natural number indicating its position in the list...

$$\begin{matrix} &1&2&3&4&\cdots\\1\mapsto&0&\cdots&\cdots&\cdots&\cdots\\2\mapsto&0&1&\cdots&\cdots&\cdots\\3\mapsto&1&0&1&\cdots&\cdots\\4\mapsto&0&1&1&0&\cdots\\\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\\?\mapsto&1&0&0&1&\cdots\end{matrix}\quad{\Huge\to}\quad\begin{matrix} &1&2&3&4&\cdots&\cdots\\?\mapsto&1&0&0&1&\cdots&\mapsto1\\1\mapsto&0&\cdots&\cdots&\cdots&\cdots&\mapsto2\\2\mapsto&0&1&\cdots&\cdots&\cdots&\mapsto3\\3\mapsto&1&0&1&\cdots&\cdots&\mapsto4\\4\mapsto&0&1&1&0&\cdots&\mapsto5\\\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\end{matrix}\quad\text{(still countable)}$$

As long as we do not allow self referential statements (e.g. we do not regard $\bigoplus_{n=1}^\infty h(n)$ as referring to the new ordering of the list - which would effectively reduce to an elaborate form of the liar's paradox), this seems like a perfectly valid argument. From a technical standpoint, all that I've really done is shown that $|\omega|=|\omega+1|=\aleph_0$. So, why isn't this a counterexample to Cantor's diagonal argument? (I don't believe that it is, but I want to know why it isn't.)

I'm sure the answer is obvious, but I can't seem to figure it out for the life of me.

  • 5
    $\begingroup$ Ok, but after you add $v$, you can construct another sequence not on the list. The idea is, that we began by assuming there was a way to list all of the binary sequences, but after we looked at this list, we realized it was incomplete. This is true regardless of what list of binary sequences we take. That's the contradiction. $\endgroup$ – Don Thousand May 31 at 1:28
  • $\begingroup$ The main confusion you are having here is not understanding the idea of the proof. It's a proof by contradiction, and in that purpose, it works perfectly. $\endgroup$ – Don Thousand May 31 at 1:29
  • 1
    $\begingroup$ If I claim to have a way of counting all possible binary sequences, you can find a sequence that I must have missed. I can't then say, "wait a second, ok I missed that one, but let me fix my attempt." If I go back to the drawing board and then return with a new attempt, you will find a new sequence that I must have missed. There's no way I could ever succeed. $\endgroup$ – littleO May 31 at 1:30
  • $\begingroup$ @littleO agreed, but there doesn't seem to be any way to show this without it resulting in infinite regress. $\endgroup$ – R. Burton May 31 at 1:33
  • 2
    $\begingroup$ @R.Burton No, you don't get into an infinite regress: the proof is a proof by contradiction that starts out by assuming that there exists a complete enumeration ... and it then shows that this supposed complete enumeration is in fact not a complete enumeration. So that is a contradiction, and thus the end of the proof. Period. $\endgroup$ – Bram28 May 31 at 2:14

EDIT: the OP has clarified their stance, which is actually self-consistent and interesting; I've significantly edited my answer to address this.

The context

The "first response" to any argument against Cantor is generally to point out that it's fundamentally no different from how we establish any other universal proposition: by showing that the property in question (here, non-surjectivity) holds for an "arbitrary" witness of the appropriate type (here, function from $\omega$ to $2^\omega$). For example, the irrationality of $\sqrt{2}$ and the non-existence of a largest natural number both fit this pattern.

Generally this is a good point to push back on - many people who take issue with Cantor's argument perceive a difference between it and these basic nonexistence proofs, and so defending the analogy is helpful. The original version of my answer did this, and can be read in the edit history. The key point here is that ultimately any self-consistent approach which accepts the logical rules leading to such basic facts as the above - together with very basic set existence axioms (forming the antidiagonal sequence from a given list only needs quantifier-free comprehension) - must accept Cantor.

So those are the four options: accept Cantor, defang the concept of set to the point of near-meaninglessness, weaken the underlying logic of all of mathematics, or be self-inconsistent. The first is the standard one, and in my experience the second and fourth are what the die-hard anti-Cantorians generally choose between.

However, the OP's response is in my opinion far more interesting. For whatever reason I think some genuinely cool stuff - both mathematical and philosophical - happens if we look at alternative logical systems. And from the comments below, it seems that this is what the OP is doing. So let me forget Cantor entirely and address that: what logical rule underlies non-existence arguments of the "arbitrary candidate" type, and why might we want to consider rejecting it (this could be an argument against it or just an observation that rejecting it opens the door to something cool)?

The rule

Let's recall the type of argument. I want to prove "No object has property $P$." So I consider an arbitrary object $a$. I show that $a$ does not have property $P$. From this, I conclude that no object has property $P$.

The key logical step here, from the OP's perspective (and I agree), is (2) (in particular, (4) is really "dual" to (2)): to critique it is to take the question "What can an 'arbitrary' object be?" seriously. Now the reaction of the vast majority of the mathematical community, including me, is that (2)/(4) are completely valid. However, it is possible to react differently (and there are those who have), and this begins with the following position:

Quantification has to be scoped.

This is the position that we can only bring in objects from some pre-existing set (indeed, that this is what sets do), and so we can only prove nonexistence results within already-established sets. If we don't accept the set-hood of the class $C$ of maps $\omega\rightarrow 2^\omega$, we can't fully instantiate from it. (Note that rejecting the set-hood of $C$ but keeping our underlying logic classical doesn't save us from Cantor since classical logic doesn't care about quantifier scope; so even though there's an 'axioms of set theory' flavor here, this really is an underlying-logic issue.)

But this doesn't fully save the OP - it prevents us from proving un-scoped propositions in the level of syntax, but we still have "existence failure" semantically unless we accept the possibility of some objects which belong to no set at all - that is, fundamentally non-instantiable objects.

(In the comments below the OP brings definability (and NBG) into the picture, but this is really a red herring. Definability and instantiability need not be related directly in any way - if we're being so skeptical, I see no reason to be surprised by definable non-instantiable objects or instantiable non-definable objects, and definability is a technical concept which should not be abused.)

At this point it's hard to avoid similarities with existing ideas: paraconsistency, relevance logic, dialetheism, Meinongianism, etc. These provide mathematical and philosophical treatments of impossible objects and impossible worlds - and there's definitely going to be a tight connection between impossibility and non-instantiability (the same ideas should be useful for analyzing each). Indeed, I think there is already some literature around non-instantiability but I'm not familiar with it at all.

The rejection

In my opinion, the best justification for taking a weak logical system seriously isn't philosophical but rather mathematical: show me that there are genuinely interesting mathematical objects/situations which that system permits but which classical logic rejects. So: what might an active rejection of $(\forall R)$ look like?

Well, many nonexistence proofs implicitly introduce an idea of an "improvement process." E.g. given an $f:\omega\rightarrow 2^\omega$, we get a $r_f\in 2^\omega\setminus ran(f)$ ... and this suggests to us that we append $r_f$ to $f$ (either at the beginning to get a new genuine list, or at the end and think about maps to arbitrary countable ordinals; it doesn't really matter here).

There's a natural (extremely informal) principle which suggests itself now:

$(F)\quad$ Every process has a fixed point.

(I could have set "completed object," but I think that's overloading the idea - the point isn't that it's not further alterable, but that the particular process we're looking at doesn't do anything. But this is a bit of a technical object.)

This principle is strongly anti-classical: taken naively, it says for example that every real number is rational (since real numbers can be approximated by rational numbers), that there is a largest natural number (since we can always make a given natural number bigger), and - yes - that the reals are countable (since we can always make better countings). Serious work would have to be done to express it precisely and in such a way that it didn't yield a completely trivial or uninteresting mathematics. In fact, I don't think I've ever seen work treating it seriously, precisely because of how overwhelmingly ridiculous it is. But there might indeed be something interesting there. Of course, this is still not the standard approach, and the OP does need to recognize that.

The summary

  • Cantor's argument relies on a logical rule about quantification; this rule is implicitly assumed by basically every mathematical theory, so the OP's claim that "most axiomatic systems fail to prevent the existence of certain objects, it is possible, through careful exploitation of axioms, to show that [such] a proof ... does not exist" is incorrect.

    • In particular, there is no objection to Cantor's argument here which is valid in any of the commonly-used mathematical frameworks. The response to the OP's title question is "Because it doesn't follow the standard rules of logic" - the OP can argue that those rules should be different, but that's a separate issue.
  • Moreover, rejecting that logical rule throws into doubt every non-existence argument.

  • But this is something the OP recognizes and accepts. So while the OP's claims about classical systems are incorrect, their general stance is self-consistent.

    • However, the "counter-argument" they make is still unjustified: removing a rule which allows one argument to go through only makes it harder, not easier, for other arguments to go through. So the OP's construction is only relevant inasmuch as it suggests a new rule to adopt in place of, or actively counter to, the old rule (which it arguably does).
  • Finally, it's worth noting that rejecting that rule does not take us fully into terra incognita, although it does take us well outside the realm of classical logic. This isn't an issue ignored by mathematics; it's simply one where the mathematical community has adopted, for better or for worse (and personally I'd argue for better), a logical system in which it is resolved in a particular way.

  • $\begingroup$ Great. But I'm confused by the title "How do you prove that a certain thing doesn't exist?" - surely every thing exists! $\endgroup$ – David C. Ullrich May 31 at 13:57
  • $\begingroup$ In my current working theory, I try to distinguish between a 'global' universe and an 'observable' universe (borrowing some terminology from physics). With this in mind, I would object to every statement "there is no $a$ such that $B$" wherein $a$ ranges over the global universe, on ontological grounds - because such statements tend to lead to... problems. The global universe also provides a place to put things which exist but cannot be shown to exist. $\endgroup$ – R. Burton May 31 at 14:52
  • $\begingroup$ Bearing in mind the difference between "there is no $x$ such that" and "the object $x$ such that... is not an object in $Y$," proofs of non-existence depend heavily on the axioms used. You mentioned comparable examples "there is no largest natural number" and "$\sqrt{2}$ is not rational"; I've encountered this exact problem with these examples. Because most axiomatic systems fail to prevent the existence of certain objects, it is possible, through careful exploitation of axioms, to show that a proof that there is no largest natural number and that $\sqrt{2}$ is irrational, does not exist. $\endgroup$ – R. Burton May 31 at 15:04
  • $\begingroup$ Correction: Does not exist within the language of the theory being used. $\endgroup$ – R. Burton May 31 at 15:07
  • 1
    $\begingroup$ Wow this is a very interesting and excellent answer! I found the section "The rejection" and talk about principle $(F)$ convincing. $\endgroup$ – palmpo Jun 3 at 4:01

The point of the diagonal argument is to show that, given an enumeration of an uncountable set $T$, there exists an element in $T$ which is not in the enumeration (and thus, you cannot be given such an enumeration). Adding your $h$ sequence to the top of the enumeration just makes a new enumeration. The proof still shows that the sequence $h$ is not in the original enumeration, contrary to assumption, since it differs from every element in one position.


After adding $v$, you just constructed a new diagonal so you can use the same argument again for this diagonal and get another contradiction if you assume that the new one is complete.


Two ways of thinking about it.

First, you say you want to exclude self-referential constructions, but this is beside the point. The structure of the diagonal argument is "by contradiction". The assumption is that there is a complete list. The conclusion is that the list that you thought was complete is incomplete. Since the argument applies to any list, no list is complete. The argument applies to the second list (which is a list, after all, which purports to be complete) as it did to the first. There is no self-reference involved.

Second, try applying your construction to the even numbers starting with $$2,4,6,8 \dots$$

You notice the number $1$ is missing and add it at the beginning $$1, 2,4,6,8 \dots$$

Now $3$ is missing $$3,1,2,4,6,8 \dots$$and continuing in this way you evidently never have a complete list. There were ("only") a countably infinite number of omissions, and you can't fit them all at the beginning to complete the list.

  • $\begingroup$ Would it then be correct to say that the diagonal argument is unique for each countable ordinal. I can see that working, but I do wonder if any problems might be incurred by having a 'set of all lists'. $\endgroup$ – R. Burton May 31 at 1:43
  • $\begingroup$ @R.Burton No to both - there is no problem with having a set of all lists, but ordinals other than $\omega$ aren't relevant at all. If I want to prove that there exists a list of ordertype $\omega$ with a certain property, but you (Cantor) can prove that an arbitrary list of ordertype $\omega$ doesn't have that property, then I've lost. This is no different from any other proof of a universal statement. (It may help to remember that "No $x$ is $y$" is the same as "Every $x$ is not $y$.") $\endgroup$ – Noah Schweber May 31 at 2:25
  • 1
    $\begingroup$ @R.Burton I think you are overthinking. The definition of countably infinite sets essentially implies that they can be put in a form with order type $\omega$. Also adding a finite number of elements at the beginning of an infinite ordinal does not change the order type. There is no essential problem with the set $B$ of all injective functions $f:S\to \mathbb N$ (or however you define countable). The functions $f:\mathbb N \to S$ are simply lists of members of $S$ possibly with repetition and possibly missing elements of $S$. You start with a set before you construct the list of elements $\endgroup$ – Mark Bennet May 31 at 7:45

Cantor's proof shows that any enumeration is incomplete. ... which immediately means that there cannot be a complete enumeration. Period.

All that you manage to show is that, starting with any enumeration, you can obtain an infinite regress of other enumerations, each of which is adding a binary sequence that the previous one is missing. So? All you end up showing is there will be infinitely many enumerations that are all incomplete (we know they are all incomplete, since we already proved that every enumeration is incomplete). Indeed, adding one missing binary sequence to the old enumeration does not mean that the new enumeration is complete, since the old enumeration could be missing binary sequences other than the one pointed out by the diagonalization. In fact, since all of the enumerations in the infinite regress of enumerations will be incomplete, we know that any starting enumeration must be missing infinitely many binary sequences from the get-go. So ... if your argument shows anything of interest, it is merely that.

As an analogy as to what is going here, consider this.

Suppose we prove that there is no finite list of all the numbers. Ok, suppose I take any finite list of natural numbers. Well, then I can point to a number that cannot be on that list: namely, the number that is the highest number on that list plus $1$. This has to be a number ... but clearly it cannot be on the list. So, the list is not complete. So, any finite list of natural numbers cannot be a complete list of all natural numbers.

Now, you say: But wait! Now that you have number identified to not be one the original list, you can add it to that original list, and so it will have that number (and still be a finite list too!) ... and while that new list will be missing some other number, I could add that number too. So ... at the very least don't you get an infinite regress, with one person pointing out missing numbers, but with a second person that just keeps adding those missing numbers? And so why would the former person 'win' in claiming that there will never be a complete listing? Why couldn't the second person claim that any missing number, as claimed to be missing by the first person, can always be added?

Well, again, here's the thing: yes, the process of trying to get a complete listing and adding any missing numbers can indeed go on indefinitely. But, since we already showed (with one simple proof) that any finite list will be missing certain numbers, all of the lists in this infinitely regress of ever-growing (but always-finite) lists will be incomplete. So, all that you are showing with this infinite regress is:

  1. That there are infinitely many finite lists that do not all numbers ... but that is not surprising: of course there are infinitely many incomplete finite lists: $1$ is not complete, $1,2$ is not complete, $1,2,3$ is not complete, etc.

  2. That any incomplete list must be missing not just one, but in fact an infinite number of numbers (since the infinite regress is indefinitely adding numbers to the original list and yet never coming to a complete listing ... but again, that is not surprising: any finite list of natural numbers is indeed missing infinite many numbers.

  • $\begingroup$ I object to (2) on the grounds that the statement "any finite list of natural numbers... is missing infinitely many numbers" cannot be proven without axiomatic declaration. If we are constructing the natural numbers according to "1 is a natural number" and "any natural number plus 1 is a natural number", then there is no way of knowing whether finitely many or infinitely many natural numbers remain after we add a new member to the list. All we can know for sure is that there is at least one more natural number. $\endgroup$ – R. Burton May 31 at 21:24
  • 1
    $\begingroup$ @R.Burton It must be infinite, because of the infinite regress. That is, starting with the first list, we point out a first element that is not on it. When we add that to the list to create a second list, we find a different element that is not on the list. Since the second list contains all elements from the first list, that means that the second missing element was also not on the first list. Etc. Hence, all subsequent elements (and there will be infinitely many, because we can repeat this process indefinitely) found to be missing were never in the first list in the first place. $\endgroup$ – Bram28 May 31 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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