Can you elaborate? It all seems really straightforward to me. There is no bijection between a set and its power set, via diagonalization. Thus, there is no bijection from the natural numbers to the power set of natural numbers. By definition, that means the power set of natural numbers is uncountable.
Not the parent, but the argument uses quite a few assumptions (axioms) that may not be intuitive to everyone, but which are quite relevant when studying mathematics at the foundational level.
For example, why would one be able to create the diagonal set (those indices of the power set elements that do not contain that index as an element) and the enumeration of the power set (i.e. the entire list of possible sets of numbers) at the same time? The theorem proves that an enumeration of the power set cannot be made. Perhaps some sets cannot be constructed at will just by writing down its properties either?
In computer land, one would quickly run into self-referential problems when constructing sets like these. For mathematics of this kind, most people agree that this is all fine, and one can derive interesting things from it. But one can also reject the approach and still do some elementary fun stuff.
Then again, I might be completely misunderstanding all of this, and I love to be corrected.
I’m not sure there’s many axioms used. Given any set A, and a function from A to the power set, P(A), construct the set X = {a in A | a is not in f(a) }. Here all we’re using is the power set axiom to define the power set and the subset axiom schema to construct X. We claim there is no a such that f(a) = X. If there was such an a, is a in X? By construction, a is in X if and only if a is not in X, just by first order logic, which is a contradiction. Thus, X is not in the image of f, so f is not a bijection. Thus, there is no bijection from A to P(A). And that’s it. We don’t even need the axiom of choice
You can't prove such a thing in ZFC [1]. ZFC's "power set axiom" is a misnomer. It doesn't imply the existence of infinite power sets. It just says if any set S exists and is a subset of an infinite set A, then S is element of a set P (the supposed "power set"). But the axiom doesn't imply the existence of "all" subsets of A. There is no way for first-order logic to state "every possible combination of elements of A forms a set". And Cantor's theorem stating that there is no mapping f from A onto P merely means that the mapping f itself can't exist inside a model of ZFC. [2]
[1] Or any other theory of first-order logic.
[2] This is explained in more detail in Stewart Shapiro's book "Foundation without Foundationalism" p. 114f.
At the moment I don't remember enough of the axiom of choice to comment on it in detail, but we can infer from the Downward Löwenheim-Skolem theorem (roughly, every first-order theory, including ZFC, has a countable model) that the Choice axiom can't imply uncountable sets.
The main reason people like first-order logic is Gödel's completeness theorem. It says that for first-order logic there is a proof system such that it proves a sentence if and only if it is true in every model. That is, the proof system is both sound and complete. This doesn't work for second or higher order logic. If we want a second-order proof system to be sound (proves no false things), it must be incomplete, i.e. not prove some true statements.
On the other hand, the main advantage of second (and higher) order logic is that it allows for "categorical" theories. A theory, like second-order Peano arithmetic, is categorical when it only has one model up to isomorphism. For second-order PA this model is the natural numbers. First-order logic doesn't allow categorical theories, so the axiom of first-order PA can't rule out the existence of weird non-standard numbers. Categoricity of a theory means that the axioms of the theory "define" ("pin down") some model. First-order theories can't do that.
So naturally, first-order ZFC isn't categorical. It even allows for countable and uncountable models. It's interpretation (model) is highly indeterminate. However, second-order ZFC (unlike, say, second-order PA or second-order analysis) is also not categorical. It doesn't have a countable model anymore, but it is still has many non-isomorphic models. (Though I think it has some weaker property which means that it is at least "more categorical" in some sense.)
So second-order ZFC doesn't give us the main advantage that second-order logic allows (the possibility of categorical theories), while also not having the complete proof system of first-order logic.
However, we could simply not use ZFC at all and only use second (or rather: higher) order logic. Higher-order logic is powerful on its own to (often categorically) formalize mathematical theories, like PA, without the need of any set theory. Instead of sets we have properties ("being a real number" instead of the set of real numbers), relations, properties of properties etc.
Formal proof checkers like Isabelle actually use higher-order logic instead of first-order ZFC as a basis.
There is also some argument to be made that categoricity is more important than completeness, since completeness of a proof system turns out to be not a plausible property anymore once self-referential statements, like the Gödel sentence, get involved. But that would lead me too far afield, and it isn't the standard opinion, which favors completeness over categoricity.
I’m uncertain what your point is. Like I said, in ZFC, there is no bijection from A to its power set. I don’t think anything you’ve stated contradicts that. Are there alternative axiom systems in which you can construct such a bijection?
There is no bijection (surjection, to be more general) from A to P inside your ZFC model even if both A and P are assumed to be countable. The bijection we talk about here would be just another object inside the model. So you can't infer from the lack of such an object that P is uncountable.
Yeah, Cantors theorem is a theorem written in the language of ZFC set theory. In other axiom systems it may not be true. But you can also say that about literally every theorem beyond, like, modus ponens. Is that the point you are trying to make?
The point is simply that it doesn't imply the existence of uncountable sets in ZFC. Modus ponens is different. The semantic entailment relation ⊨ between (P→Q, P) and Q is valid iff there is no model such that the former is true and the latter is false. Which is a sentence in plain English. It doesn't require the existence of some object that is mapping the premises to the conclusion inside the model. It doesn't even require the existence of a syntactic deduction rule (⊢) that tells you from (P→Q, P) to infer Q.
It is a theorem of ZFC that uncountable sets exist and every model of ZFC will have a set that the model believes to be uncountable. It doesn't matter than the metatheory might believe that model to be countable (why should the metatheory have the correct notion of what it means to be countable anyway?).
> It is a theorem of ZFC that uncountable sets exist
This is simply false, as I already explained.
> and every model of ZFC will have a set that the model believes to be uncountable.
That is something else. (And I wouldn't use the nebulous term "believes" here, it's just that the model lacks an object which maps A to P.)
> It doesn't matter than the metatheory might believe that model to be countable (why should the metatheory have the correct notion of what it means to be countable anyway?).
"The meta theory" here is simply sentences expressed in natural language, or beliefs held by people expressing those sentences. It is the language in terms of which everything formal is ultimately defined. It's the only thing that ultimately matters.
It is absolutely not false! This is taught in every undergraduate set theory course. Please point to me the step in the above proof where there is an error.
Certainly not in every undergraduate class, though I don't doubt that the subtleties around these issues may often be taught wrong. I already did point you to the errors, and I included the reference to Shapiro's book.
You keep making vague references to concepts without showing how they even remotely contradict Cantors theorem. You explained to me the power set axiom, which, thanks, I guess? But I don’t understand what your point is. Are you claiming X is not in the power set of the natural numbers? X is, unambiguously, a set. And it is clearly a subset of A. Therefore, it is in the power set. If you don’t understand that, I think you need to review the power set axiom in ZFC. Then you said “Cantor's theorem stating that there is no mapping f from A onto P merely means that the mapping f itself can't exist inside a model of ZFC”. Which is literally identical to saying “under ZFC, there are uncountable sets”. You just don’t like it because that statement isn’t wrapped in eight layers of indirection with model theory.
I don't exactly understand your construction of X. But note that you are relying on the existence of ZFC's so-called "powerset", which, as we already know, can be countable. ZFC has no ability to talk about infinite powersets, since it can't and doesn't state that all subsets exist, and thus it doesn't imply the existence of a powerset. Accordingly, both f and X may not be what you want.
> Then you said “Cantor's theorem stating that there is no mapping f from A onto P merely means that the mapping f itself can't exist inside a model of ZFC”. Which is literally identical to saying “under ZFC, there are uncountable sets”.
No, it only means that ZFC can't contain a function f from A to P in its model, which doesn't make P uncountable. (Things can be true even if the theory itself can't express them. E.g. Gödel's second incompleteness theorem says that a theory can't prove its own consistency, but that doesn't mean that the theory is inconsistent.)
For any f and A, we can define X as { a in A | a is not in f(a) } . That set exists in ZFC by the axiom of separation, also known as the axiom of subsets or the axiom of comprehension.
I recommend you pick up a book on ZFC if you are interested in understanding set theory. I found Enderton’s “Elements of Set Theory” to be a really good introductory text.
I'm sorry but this is just wrong. Since you seem to like Shapiro's book more than traditional set theory books let me quote from page 144 that the existence of an uncountable set is a theorem of ZFC: "Let C be the statement of Cantor's theorem. It entails that the powerset
of the collection of finite ordinals is not countable. Since C is a theorem of
first-order ZFC..."
Also this is not how the metatheory is understood in mathematics, not even in Shapiro's book, who dedicates two whole chapters to the metatheory
> Since you seem to like Shapiro's book more than traditional set theory books let me quote from page 144 that the existence of an uncountable set is a theorem of ZFC: "Let C be the statement of Cantor's theorem. It entails that the powerset of the collection of finite ordinals is not countable. Since C is a theorem of first-order ZFC..."
You didn't finish reading the quote. It continues:
> "... Since C is a theorem of first-order ZFC, m ⊨ C, but, as just stated, m is itself countable and so are its elements. This, again, is the so-called Skolem paradox."
That is, he was making an (informal) contradictory statement in order to illustrate the paradox. But there is actually no contradiction (otherwise ZFC would have been proven inconsistent), so we already know the statement of the paradox must have been inaccurate. He then goes on to explain where the inaccuracy was. It turns out that it was mainly in the mistaken, but common, assumption that the "powerset axiom" implies the existence of a powerset:
> [The powerset axiom] is supposed[!] to assert the existence of the set of all subsets of each set. But the variables (like all first-order variables) range over the elements of the model. So the powerset axiom only guarantees the existence of a set of all subsets of (say) ω that are in the model. The subsets of ω that are 'guaranteed by the axioms' to exist in a given model m are those that are first-order m-definable, and only those. In some cases there are only countably many of them.
As I explained in a previous comment, you can't say in first-order logic "every possible combination of elements of this infinite set forms a set" (more precise expression of "all possible subsets exist"). ZFC's powerset axiom only states that all existing subsets are element of some set P, but it doesn't imply they exist in the first place. So it doesn't imply the existence of infinite powersets (finite powersets wouldn't require the axiom anyway). Indeed, only those subsets are implied to exist that are implied by the other axioms, which isn't very many. (See the Löwenheim-Skolem theorem.)
And Cantors theorem only states that inside the model no function f (which would be just another set) exists that maps A to its supposed powerset P, even if both A and P are countable. So there no contradiction between Cantor's theorem and the countability of P in ZFC.
> Also this is not how the metatheory is understood in mathematics, not even in Shapiro's book, who dedicates two whole chapters to the metatheory
See this (well-known) quote on page 254 where he talks about the metatheory of second-order logic:
> The language of set theory is employed, without apology, and no anti-realist interpretation or reduction its envisaged. Indeed, no explicit interpretation is envisaged at all. There is no perspective outside this language from which to discuss its interpretations, or its models, or at least none is contemplated. The set-theoretic universal quantifier reads 'for all sets' and the existential quantifier reads 'there is a set'. Thus sets are in the ontology of the background theory. If asked 'which sets?' or 'how many?', there is only one answer: 'all of them'. This is what it is to take the language literally.
Alternatively, one could already take the axioms of second-order logic as "rock bottom", insofar they are grounded in natural language (which he also offers arguments for). In any case, using other formal theories as a tower of meta- and meta-meta-theories only leads to an infinite regress. Everything bottoms out in natural language. Normal mathematicians don't bother with formal languages in the first place, it's only logicians which make this excursion, but even they resort to natural language on the (meta) meta level.
