Why is Cantor's diagonal argument not a paradox?

The "diagonal of $T$" is meaningless.

$T$ is an un-ordered set.

What Cantor says is that any map $\phi:\mathbb N\to T$ misses an element of $T$, and uses the diagonal of $\phi$, not $T$ - that is, he defines the sequence $\{t_n\}$ where $t_n$ is some value other than $\phi(n)_n$.

You can't define the "diagonal of $T$" in general.

Your update to the question simply removes the problematic phrase, "diagonal of $T$", replacing it with the phrase, "As per Cantor,..." But Cantor doesn't construct $s$ from $T$, he constructs $s$ from a map $\mathbb N\to T$.

So your argument is still meaningless. How are you construction $s$ from $T$? It is certainly not possible for it to be the same as the way that Cantor constructs $s$ from $\mathbb N\to T$.

Regardless of whether or not we assume the set is countable, one statement must be true: The set T contains every possible sequence. This has to be true; it's an infinite set of infinite sequences - so every combination is included.

This is simply not correct. Just because a list is infinite does not mean it is complete. For instance, here is an infinite list of integers: $$0,2,4,6,8,10,\dots$$ This list, despite being infinite, does not contain all the integers: it is missing all of the odd integers, as well as the negative integers.

As a result, even though it is easy to come up with a countably infinite set $T$ of sequences, there is no contradiction from the conclusion that such a set does not contain all the sequences.

If you intend to assume that your initial set $T$ contains all sequences, then you get no paradox because you have not justified that assumption! How do you know that there exists a countable set $T$ that contains all sequences? There does exist a set of all sequences, but performing Cantor's diagonal argument to obtain the sequence $s$ requires you to know that $T$ is countable (since it makes use of a specific enumeration of the elements of $T$).

If you don't justify this assumption, then all you have proven is that if you make the assumption, you reach a contradiction. This is a proof by contradiction that the assumption is actually false! That is, the set of all sequences is not countable.

So now we define the infinite sequence s of complementary numbers to the diagonal of $T$.

This step only works if $T$ is countable. By definition, a sequence can only contain countably many elements.

Cantor's diagonalization argument was taken as a symptom of underlying inconsistencies - this is what debunked the assumption that all infinite sets are the same size. The other option was to assert that the constructed sequence isn't a sequence for some reason; but that seems like a much more fundamental notion. Cantor's argument explicitly constructs a mapping from $\mathbb{N}$ to whatever set the sequences are in; this is what we mean by a "sequence", so it seems bizarre to question whether it exists.

In general, we prefer to question axioms rather than definitions, wherever possible, because definitions are far more fundamental. For example, suppose you believed that all prime numbers were odd, and one day I showed you the number $2$. Would it be more reasonable to decide that (a) for some reason $2$ is either not prime or not a number at all, even though it satisfies the definitions for both, or (b) the axiom "all prime numbers are odd" is just wrong?

Also, nothing becomes a "paradox". Russell's paradox prompted the creation of modern set theory, in which the "paradox" is just a theorem. The "twin paradox" in relativity is just a thought experiment that informs the experimenter about the effects of relativity. Schrodinger's Cat, originally intended as a paradox, is now taken as an illustration of the effects of quantum mechanics. Given the option, no scientist in any field will take an example as an actual paradox; they will alter their assumptions just enough to make it no longer a paradox, rather than throwing everything out and starting fresh. In this case, the solutions to Cantor's "paradox" were to either conclude that some infinities are bigger than others, or that the definition of a "sequence" is inherently flawed in some unknown way. The first option was clearly simpler, so we chose that.

Of course you can define such an infinite set T. As you said

Regardless of whether or not we assume the set is countable, one statement must be true: The set T contains every possible sequence.: The set T contains every possible sequence.

However if it is not countable then you CANNOT use the Cantor's arguments on this set. Therefore the problem arises.

If you look into the Cantor's theorem you will see that the numbering of the sequences matters. Therefore the countability of the set T is first assumed and then after the contradiction is reached, all the blame is put in on our single assumption which is the countability.

Regardless of whether or not we assume the set is countable, one statement must be true: The set T contains every possible sequence. This has to be true; it's an infinite set of infinite sequences - so every combination is included.

I know that others have already given counterexamples to this, you could actually come up with counterexamples for quite a few infinite sets. For example, the set of all real numbers between 5 and 10 is clearly uncountably infinite, but it's still a proper subset of the real numbers.

You may want to research the Infinite Hotel Paradox. Suppose that you have a hotel with a countably infinite number of rooms, all of which are booked. One night, a bus pulls up with an infinite number of numbers looking for rooms. The paradoxical thing: the hotel can accommodate all of them in spite of being at "full occupancy." All you have to do is move everyone to even-number rooms (i.e. if you occupy room $n$, you would have to move to room $2n$).

Let's put it this way.

Let $T = \{\text{the set of all sequences}\}$.

Let $S \subset T$ so that $S$ can be sequenced.

Let $s_S$ be the "impossible sequence" so that $s_S \not \in S$.

As $s_S \not \in S$ but $s_S \in T$, we know $S \subsetneq T$.

But $S$ was any arbitrary subset of $T$ that could be sequenced. But $S$ can not be $T$. So $T$ can not be sequenced.

So $T$ is uncountable.

Q.E.D.

That's all there is to it. No paradox.

======

"Regardless of whether or not we assume the set is countable, one statement must be true: The set T contains every possible sequence. This has to be true;"

It has to be true because that is how we defined it; not for the arguments you give (which are naively wrong). But that's irrelevant.

"As per Cantor's argument, now we define the sequence s - and as a result"

Whoa!!!!! Hold on! HOW did we define the sequence $s$ on the set $T$? We can only use the Cantor diagonal argument on $T$ if $T$ is a sequence. We don't know that $T$ is a sequence; only that $T$ is a set.

And that is the entire point. IF $T$ could be made into a sequence, THEN we could create a sequence $s$, that is not in $T$ which would be a contradiction. So we must conclude our hypothesis, that $T$ can be made into a sequence, is false.

So now we know that $T$ can not be made into a sequence. And if we can't make $T$ into a sequence, we have no way of creating $s$. And we have failed to create a sequence not in $T$.

So there is not paradox because we didn't do anything. We know $T$ can not be sequenced. Since $T$ can not be sequenced we can't and didn't create an $s$.

If we tried to create $s$ we'd have to take a sub set of $T$, $S \subsetneq T$ that can be sequenced. We construct $s$. We conclude $s \not \in S$ and therefore $s \in S^c \cap T$. Which is .... just honky-dory.

What we did conclude was this statement: $T = \{\text{ all infinite sequences}\}$ can not be ordered into a sequence.

And that is the core of the diagonal argument.

========

You already got a lot of answers about your errors. But let me add what Cantor's argument actually says.

Ultimately it is about functions from a set $X$ to a set $Y$, where $Y$ has more than one element. And it says that there are more functions from $X$ to $Y$ than there are elements in $X$. Or, more formally, the set of functions from $X$ to $Y$ has greater cardinality than $X$.

The most famous application of Cantor's diagonal element, showing that there are more reals than natural numbers, works by representing the real numbers as digit strings, that is, maps from the natural numbers to the set of digits. And the probably most important case, the proof that the powerset of a set has larger cardinality than the set itself, is brought to that form by identifying a subset with a function from the set to $\{0,1\}$, with $0$ meaning "this element is not in the subset" and $1$ meaning "this element is in the subset".

Note that there are always two sets involved in Cantor's diagonal element. The first one is the set I called $X$ above, and the second one is the set of functions from $X$ to $Y$ (or a set that can be described by such functions).

You are talking about sequences. Sequences are, bu definition, functions from the natural numbers to whatever objects you form sequences of. So here $X=\mathbb N$. It doesn't matter what $Y$ is, as long as it has at least two elements. Since you assert that $T$ is an infinite set, we can assume that this is indeed the case, as if $Y$ had only one element, there would be only one sequence, and from one sequence you cannot make an infinite set. And obviously with empty $Y$ you cannot form any sequence at all, and the empty set is finite.

So what you would prove with Cantor's diagonal proof is not that $T$ is incomplete. Rather, you prove that if you have a bijection $\mathbb N\to T$, then there's a sequence that's not in $T$. Which in reverse means that if $T$ does contain all sequences (that is, there's no sequence that's not in $T$), then there is no bijection $\mathbb N\to T$, which in turn means that $\mathbb N$ and $T$ don't have the same number of elements. Since it is easy to see that the set of all sequences must be at least as large as $\mathbb N$ (simply consider the sequences which are almost constant, but have exactly one element different), this implies there are more sequences than natural numbers.

These two sentences are not related the way you think:

Regardless of whether or not we assume the set is countable, one statement must be true: The set $T$ contains every possible sequence.

As per Cantor's argument, now we define the sequence $s$ - and as a result, we have constructed a sequence that cannot possibly be in the set $T$.

As per Cantor's argument, you define the sequence $s$ term-by-term (digit-by-digit in Cantor's proof), chosing each single term against some sequence chosen from the set $T$. And as $s$ is a sequence, it has only countably infinite set of terms, so you used at most countably infinite set $S$ of sequences.

Of course, $S \subseteq T$, but you have not shown $S = T$, even for countable $T$ (note that infinite $T$ can have, and even has, proper subsets equipollent with itself, so equipollency of $S$ and $T$ does not imply their equality).

The more, you have not shown (and in fact, you're unable to show), that countable $S$ exhausts $T$, if $T$ is uncountable.

You can conclude, as Cantor did before, that your newly constructed $s$ certainly does not appear in $S$, but it's not enough to infer $s\notin T$.

The whole 'paradox' is just a result of a mistake in your reasoning.

Cantor's argument says that you can't enumerate the elements in $T$, i.e. define a bijection between $\mathbb N$ and $T$. He does so by showing that whatever the enumeration, let $E$ (such that there is a bijection between $\mathbb N$ and $E$), you will miss some element.

You have two nonconflicting claims:

• $T$ contains all sequences,

• for any enumeration $E$, one can build a sequence $s$ such that $s\in T$ but $s\notin E$.

Hence, $E$ is a proper subset of $T$.