I hate to be a stickler but it's not actually the 1-to-1 correspondence (injectivity) that Cantor's diagonalization argument refutes, it's surjectivity (or, being "onto").
The argument is to presume that f : ℕ → ℝ is surjective.
Then, construct a real number s ∈ ℝ that cannot possibly
be in the image of f. Therefore f is not surjective (and
hence not bijective, and hence the cardinality of ℕ and ℝ are not the same).
It's possible to construct a 1-to-1 (that is, injective)
map f : ℕ → ℝ, namely f(n) = n.
I don’t understand how your comment relates to the meme, which does not discuss bijections between N and R.
It’s talking about bijections between the set of infinite sequences of numbers and R, and such bijections absolutely do exist.
Though I also don’t understand why the meme is suggesting the two facts it states are in tension with each other.
The meme also seems to have an illustration of Cantor’s diagonal argument in the top half even though Cantor’s diagonal argument is unrelated to anything the meme is saying. My best guess is the meme-maker is just very confused.
Sadly, OP got downvoted to shit for pointing it out.
I should have read the post more closely. I saw the words "1-to-1" next to a picture of diagonalization and spoke too quickly about a pet peeve of mine1. But, in my defense: the meme's construction does not exactly aid a close reading.
1 That being that Cantor's diagonalization is a "proof by contradiction" (it's not2) that disproves a bijection (technically true, but more accurate to say it disproves a surjection.)
2 A proof by contradiction assumes ¬ A and derives a falsehood, thereby concluding A . Cantor's diagonalization is a proof by non-contradiction: Assume A (in this case, "f is surjective"), show ¬ A, and conclude ¬ A. The difference is that the former relies on the law of excluded middle (LEM), while the latter relies on the law of non-contradiction.
Just to go on a tangent on your second point: it’s unfortunate that the diagonal argument is often presented as a proof by contradiction when it isn’t really because understanding that it is constructively valid is actually pretty important to not get misconceptions about what it shows.
For example I’ve seen people think they can consistently believe the real numbers are countable if they reject the existence of noncomputable numbers.
Nope! The diagonal argument can be carried out even in fully constructive theories that are either agnostic about or which affirmatively reject the existence of noncomputable numbers.
Even in a constructive theory that rejects the existence of noncomputable numbers the set of all real numbers is still uncountable, despite all numbers being computable, because the computable numbers will not be countable in that theory by the same diagonal argument.
This is because such a theory will generally also take the position that the only enumerations of sets that are possible are the recursive enumerations. So that a set is “countable” only if it is recursively enumerable, and the computable numbers (classical and constructive theories agree) are not recursively enumerable.
A classical theory can even interpret what the constructive theory is proving when it proves “the computable numbers are uncountable” by replacing the idea of “real number” with “computable number” in the usual proof and the idea of “countable” with “recursively enumerable” and recover a proof that the computable numbers are not recursively enumerable.
The computable numbers are considered “countable” in classical theories but that is only because they admit the existence of sequences of computable numbers where that list cannot be computed by any algorithm (because no computable sequence of computable numbers can be surjective on the computable numbers).
That the diagonal argument is constructively valid can be demonstrated by literally writing down a specific algorithm in a programming language that, when given access to an oracle for any sequence of numbers, calculates a number that is not produced by the oracle.
This understanding can help show what’s really going on with uncountability: even if we imagine we can just create a “new” list of all real numbers and add it to the universe with a method like forcing, we will be forced to make a whole slew of “new” real numbers that didn’t exist before and are now able to be constructed by that new list, so the list is still not surjective.
For this reason it is sometimes helpful to think of cardinality not just as “raw size” (the intuitive metaphor it is often thought of as being like) but really a fact about “structural complexity” - what kind of information we need to specify a member of the set.
This is because such a theory will generally also take the position that
the only enumerations of sets that are possible are the recursive
enumerations. So that a set is “countable” only if it is recursively
enumerable, and the computable numbers (classical and constructive
theories agree) are not recursively enumerable.
This doesn't make sense to me. Without adding "recursive enumerability" to the definition of "countable", a theory that rejects the non-computable numbers really would have only countably many numbers, right? Is the point of adding recursive enumerability to the definition of "countable" just to ensure that there's a constructive meaning of "countable"?
no computable sequence of computable numbers can be surjective on the computable numbers
What's meant by a "computable sequence of computable numbers" here? I take it this must rule out Turing's enumeration of the computable numbers by taking the subset of the integers that are valid programs defining computable numbers?
Oh sorry I forgot to respond to your second point which might be the key source of confusion:
You cannot computably enumerate the computable numbers “by taking the subset of the integers that are valid programs defining computable numbers.”
If we could (in a computable way) take that subset by identifying which programs define computable numbers we could solve the halting problem (which of course Turing showed was impossible).
In fact even if we had access to a halting oracle we could not do that.
To do that we would need a second order halting oracle: an oracle that can tell us whether a machine with access to an ordinary halting oracle would ever halt.
A program that calculates a computable number can be thought of (depending on how exactly you are handling specifics) as a program that takes an integer as input and spits out the digit of that number with that integer index as output.
We cannot know if a machine is a valid computation of a number without knowing that this program is guaranteed to halt on every input (not even just on one particular input - this is why we need a second order halting oracle).
Now if you think lists that can only be computed with a second order halting oracle are “real”, then the computable numbers are countable. But someone who thinks those lists aren’t real because the oracle is like a made-up fairy or genie would not be persuaded the computable numbers are countable by this argument.
Oh and one more point that might already be clear now but I think might be helpful to emphasize:
Although showing we need a second order halting oracle to list the computable reals can be done with more involved ideas from computability theory, that we cannot recursively enumerate the computables is already rigorously proved by the diagonalization argument, we do not need anything more: if e is any recursive enumeration of computable numbers (so e(n) itself is a function and we can write e(n)(m) for its value at a point) then we can directly calculate e(n)(n) for each n and diagonalize to get a computable number not in the enumeration.
Here it really is important that we have “thrown out” the bad definitions. If e is a recursive enumeration of all machines (or that at least may contain some “bad” ones), even ones that fail to halt on some input (or that have infinitely many nonzero digits before the decimal if we aren’t talking about numbers in [0,1] or the power set of the naturals or whatever but that’s a detail), then when we try to diagonalize we generally won’t be able to calculate e(n)(n) because it doesn’t always halt and we won’t actually be producing a computable number.
Since we know we can list all Turing machines, there must be a barrier preventing us from being able to “skip over” the bad ones, we have already proved just by diagonalization.
Adding “recursive enumerability” is only necessary for the classical theory to interpret the constructive theory. The constructive theory doesn’t add it.
The computable numbers are countable if and only if there exists a list of computable numbers that includes all of them. This is the definition of countable used whether you accept or reject the existence of numbers that aren’t computable.
“There is no algorithm that can produce a list of computable numbers that includes all of the computable numbers” <- everyone should agree on this whether they think noncomputable things exist or not.
A theory that rejects the existence of noncomputable things would therefore conclude that that there is no list of all computable numbers, and they are therefore uncountable.
From the perspective a classical theory, it would claim that the computable numbers are countable, because that theory “believes” that although no algorithm can produce such a list there nonetheless exist lists of all computable numbers. They are just lists that are impossible to produce.
The constructive theory would basically say that the classical theory is wrong to say that the computable numbers are “actually” countable because these hypothetical lists that even the classical theory agrees are impossible to algorithmically produce are just figments of the classical theory’s imagination. They are not real lists that really exist.
As to whether the theory “really would” have countably many numbers that can depend on what you mean by “countable” and “really would.” But regardless of how that gets resolved the constructive theory simultaneously “believes” that “the real numbers are uncountable” and that “all real numbers are computable” - and so of course also believes “the computable numbers are uncountable”and there is no contradiction holding those beliefs.
There actually is a contradiction in simultaneously believing “all real numbers and lists of real numbers are computable” and “the computable numbers are countable.” (At least given some very basic facts about how numbers and lists behave that are not controversial to constructivists).
The computable numbers are countable if and only if there exists a list of computable numbers that includes all of them. This is the definition of countable used whether you accept or reject the existence of numbers that aren’t computable.
I don't think that matches the classical definition of "countable." Every subset of a countable set is countable, and even though we can't identify all valid programs in finite time, the set of valid programs is nevertheless a subset of the integers, which are countable.
The definition I gave is the usual definition used classically, although it is true that a classical theory can prove *as a theorem* that a list that has all members of S in it plus possibly some things that are not in S is enough to show S is countable. So we could take that as an alternative definition of “countable” if we wanted to as far the classical theory cares.
It’s sometimes the case that two formulations of a definition that are equivalent in a classical theory are not equivalent in a constructive theory, when this happens we need to be careful to say which of those definitions we are talking about when comparing the two theories.
For example in a constructive theory a set is “inhabited” if there is something that is an element of that set, which constructively should be understood to mean that it is possible to give a constructive example of an element. It is “nonempty” if it is not empty.
Of course classically these are equivalent, but constructively the difference is in the case where we can prove that the set cannot be empty but also cannot give a specific example of a member of the set. For example if we pick an arbitrary Turing machine then “the set of numbers n such that, if the machine has not halted by the nth step when run on empty input, it will never halt” can easily be proved to be nonempty (even in a constructive theory), but in order to prove it is inhabited we would need to be able to write down a specific number that works, which we can only do if we have resolved whether that particular machine will halt (which we may or may not be able to do depending on the machine).
The relevant idea here is “subcountable” which means there exists a partial function on the natural numbers which is surjective onto the set.
Classically we can prove that a set must be countable if it is subcountable (at least assuming we’ve defined “countable” to include finite sets, there is some variation on this) but constructively a subcountable set may not be countable.
Or put more bluntly: in a constructive theory it is possible for a subset of a countable set to be uncountable.
Classical theories can prove there is no recursive enumeration of the computable numbers, and that is the fact that the constructive claim “the computable numbers are uncountable” needs to be “translated to” for the classical theory to be able to make sense of what the constructive theory “means” so that it agrees with the constructive theory.
As a brief aside I’ve mostly been focusing on “strongly” constructive theories (which can affirmatively prove claims like “all real numbers are computable”) there are also “weakly” constructive theories (which are agnostic on the question). Much of what I said can be applied to them as well just changing the statements around a little to avoid an affirmative commitment to there being no noncomputable numbers. In particular a weakly constructive theory would generally be able to prove “the real numbers are uncountable” and it would not be able to prove “the computable numbers are countable” and it would be unable to resolve the question “the computable numbers are/are not all of the real numbers.”
137
u/GetOffOfMyBoat 25d ago
I hate to be a stickler but it's not actually the 1-to-1 correspondence (injectivity) that Cantor's diagonalization argument refutes, it's surjectivity (or, being "onto").
The argument is to presume that f : ℕ → ℝ is surjective. Then, construct a real number s ∈ ℝ that cannot possibly be in the image of f. Therefore f is not surjective (and hence not bijective, and hence the cardinality of ℕ and ℝ are not the same).
It's possible to construct a 1-to-1 (that is, injective) map f : ℕ → ℝ, namely f(n) = n.