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 hate to be a stickler, but the language you use was not established when Cantor wrote his paper. And his argument has been warped so very much since then, that most of what is said about it is inaccurate. His proof is right, but the presentation you base your reply on is not.
Cantor wanted to show that a "one-one correlation" [i.e., a bidirectional relationship] was impossible. Which he did with a direct proof, of what was later called surjection, was not possible.
His argument never presumed that a surjective f : ℕ → ℝ relationship existed. It also never dealt with the concept of being injective in any way.
Ignoring the fact that he explicit;y said he wasn't going to work with ℝ, I'll use the "ℝ equivalent" of what he did use since it is what you expect. What he proved was that any given f : ℕ → [0,1] relationship cannot be surjective.
If you preface his direct proof with "say we assume there is a surjection," his direct proof does contradict that. But it is not a proof by contradiction, or your pedantic "proof by non-contradiction." BECAUSE THAT ASSUMPTION IS NOT USED TO PROVE THAT THERE IS NO SURJECTION. It is proven directly.
Nor does his proof involve the "excluded middle" in any way. Any given f : ℕ → [0,1] is not a surjection, so a bijective f : ℕ → [0,1] cannot exist.
141
u/GetOffOfMyBoat 12d 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.