5
$\begingroup$

Cantor's Theorem seems pretty airtight to me. So what is wrong with the following reasoning?

Consider $X = \mathcal{P}(\mathbb{N})$. We say $X$ contains uncountably many sets. But the only sets that exist are those asserted to exist by the axioms. So if we consider each of the axioms that assert more sets, starting with $\emptyset$, we have one set. The pairing axiom can only produce countably many more. Union gives us up to one more set per set in existence. Powerset also gives us up to one more set per set in existence. Separation and replacement gives us countably many more sets per set in existence. Infinity gives us more more set. Foundation gives us one more set per set in existence. Choice also only gives us one more set per set in existence.

It seems to me that the axioms only ever define countably many sets. So when we consider all the subsets of a set, there might be uncountably many things that satisfy the condition of being a subset, but only countably many of them are possibly sets. If sets can only contain sets, $\mathcal{P}(\mathbb{N})$ must be countable.

I'm still not getting the argument about parameters coming from somewhere. I understand the notion of parameters in the context of definability in a structure, but this question is about a theory (ZFC), whose axioms are well formed formulas in the language of set theory ($\forall,\land,\neg,\in$). Thus technically all the separation and replacement axioms do not contain any parameters, right?

Considering the example set:

$$ X = \{ (n,k) | 2^{\aleph_n} = \aleph_k \} $$

When all the subsets of $\mathbb{N}^2$ are added, surely $X$ is among them? We can say with certainty is that $X$ exists at this stage (because it is definable...or perhaps we can only say there is a plethora of possibilities for $X$ in existance?), but we would be unable to enumerate the pairs (ie say which subset of $\mathbb{N}^2$ it is) without making more assertions about the continuum.

I like this idea that there can exist subsets of $\mathbb{N}$ that are undefinable without parameters that come from sets of a higher rank. Perhaps there is a forcing notion that makes $X$ one of these in a particular model. But are there uncountably many of them?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Jonny, the point of my comment about this $X$ is that it is that you suggested that only sets which are definable from previously defined sets exist. And while this $X$ is indeed definable, it isn't necessarily definable as a subset of $\Bbb N$, just from what we have accumulated by the time we generated $\Bbb N$. $\endgroup$ – Asaf Karagila♦ Dec 12 '14 at 4:28
  • $\begingroup$ Additionally, look at the formulation of separation and replacement. Separation begins with $\varphi(x,p_1,\ldots,p_n)$ and it says that for every choice of parameters $p_1,\ldots,p_n$, and every set $w$ there is a unique set $y$ such that $x\in y$ if and only if $x\in w$ and $\varphi(x,p_1,\ldots,p_n)$. These are the parameters and they can come from wherever you want them to come in the set theoretic universe. $\endgroup$ – Asaf Karagila♦ Dec 12 '14 at 4:30
  • $\begingroup$ Surely the rank of $X$ is $\omega$, and therefore it gets added at this stage? If I have a theory with the property that every model contains the elements 1 and 2, but it is not provable in the theory whether $x$ is equal to 1 or 2 (but has to be one of them), I'd say the set containing $x$ is definable and exists. It just happens to be the case that in some models, the set containing $x$ is the set containing 1, and in other models it is the set containing 2. But the set containing $x$ is definitely not a new, unique set that increases the total number of sets in my model. $\endgroup$ – Jonny Dec 12 '14 at 18:50
  • $\begingroup$ Let me say that again. The set of $n$ such that $\aleph_n$ violates the continuum hypothesis (for that specific cardinal) can be undefinable as a subset of $\Bbb N$ along with addition, multiplication, whatever. It is added at rank $\omega+1$ but it is UNDEFINABLE as such subset. But it (1) might be definable using set theoretic formulas which are not bounded by addition and multiplication and whatnot; and (2) might be definable using parameters from the universe (trivially or less trivially). Your question makes it seem as if the only sets added are those definable from [...] $\endgroup$ – Asaf Karagila♦ Dec 12 '14 at 19:00
  • $\begingroup$ [...] the basic structure of the natural numbers, whatever it might be. But this is not true. There are sets definable using formulas and using parameters, and sometimes sets might be definable, essentially only by the formula $\varphi(x,A)=x\in A$ where $A$ is the parameter (so the definition is trivial). $\endgroup$ – Asaf Karagila♦ Dec 12 '14 at 19:01
3
$\begingroup$

You hit some sort of circularity with separation.

While there are only countably many formulas (and that countable collection is not really countable from the standpoint of set theory. It's nonexistent, since it's a part of the meta-theory); these formulas are allowed to have parameters.

All you really show here is that a lot of the subsets of $\Bbb N$ will be definable using separation axioms of the form $\varphi(x,p):= x\in p$ where $p$ is a parameter, and $A=\{x\in\Bbb N\mid\varphi(x,A)\}$. It's a bit of circular, but not if you really think about it.

But there is another issue here. Separation axioms don't rely on "previously added sets" in the hierarchal order of things. Note that $\{(n,k)\mid 2^{\aleph_n}=\aleph_k\}$ is a definable subset of $\Bbb N^2$ (and so by encoding it defines a subset of $\Bbb N$), but it's not really added after adding $\Bbb N$. It will only be added after we've added a lot more, namely all the $\aleph_n$'s and all their power sets.

And we can add all sort of crazy definitions like that. The freedom to use parameters, and to use formulas which address the entire set theoretical universe and not just $\Bbb N$, show that there are uncountably many subsets. The power set axiom just ensures that there is just "set many" of them.

What's even more important is to understand that the axioms don't "define" the structure". Instead the structure is given and we check that it satisfies the axioms. Does your argument mean that any model of a countable language is countable, just because? Not really. It just shows that a countable language can define only countably many elements in a model (unless you allow parameters).

Let me point a similarity with the von Neumann construction of $V$ (or really, any other hierarchal construction). The sets come from somewhere. They already exist. We just show that we can write the universe as a limit of a hierarchy of sets. Similarly in your question, the sets already exist, the axioms don't bring them to life, they just allow us to show that particular sets exist.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I love the example you give of a definable subset of $ \mathbb N^2 $. However, is it not possible that such a subset may have an alternative extension that relied only on, say, the arithmetic of $ \mathbb N $. It seems unlikely perhaps, but how can one claim uniqueness for this definition. Is this a well known subset whose properties are well understood so that no arithmetic relation between $ n $ and $ k $ will suffice. $\endgroup$ – Nick Sep 18 '14 at 20:43
  • $\begingroup$ Sorry, I see my stupidity now. Obviously this relates to the continuum hypothesis. $\endgroup$ – Nick Sep 18 '14 at 20:47
  • $\begingroup$ Nick, of course I can't. In a model where $\sf GCH$ holds this set is simply $\{(n,n+1)\mid n\in\Bbb N\}$, and in a model where $2^{\aleph_0}>\aleph_\omega$ this is an empty set. So since I can't tell what is the explicit content of this set, I can't tell you that it has another definition as an arithmetical set. But I know that it can not have such definition. Begin by forcing $\sf GCH$ (below $\aleph_\omega$ is enough), add a Cohen real and use it to force the values of the continuum of the $\aleph_n$'s, the Cohen real is not arithmetical, so in the last model it's not an arithmetical set $\endgroup$ – Asaf Karagila♦ Sep 18 '14 at 20:48
  • 1
    $\begingroup$ How is that true if the only sets that exist belong to the model? The only 'parameters' available are constant symbols and variables. It seems to me that your uncountable collection only exists in an uncountable language. $\endgroup$ – Jonny Sep 20 '14 at 1:31
  • 1
    $\begingroup$ I don't see any previous explicit reference to the fact that "uncountable" is an internal term, which is apparently the critical fact in question. All the examples here seem to reference a particular model which is already assumed to be uncountable. $\endgroup$ – Jonny Sep 24 '14 at 0:18
2
$\begingroup$

I believe the crux of the issue is grasping that Cantor's theorem requires the bijection to exists in the model.

When we say $X = \mathcal{P}(\mathbb{N})$ is "uncountable", it simply means that there does not exist a bijection from $\mathbb{N}$ to $X$ in whatever model. So, if we let $M$ be a countable model of ZFC, the cardinality of $\mathcal{P}(\mathbb{N})$ is"countable" in a metalanguage sense of the term -- each of the subsets are in a one to one correspondence with the "countable" $\varphi$ that define them. However, there exists an injective function $f_i$ from $\mathbb{N}$ to $X$ such that $f_i \in M$, but there does not exist a bijective function $f_b$ from $\mathbb{N}$ to $X$ such that $f_b \in M$ (else $M$ would not be a model of ZFC).

I see now that my question was, in fact, equivalent to the Skolem Paradox. In my question I assert that the only sets that exist are those that provably exist from the axioms, but this assertion is not provable from ZFC. However, it is true in a model constructed by the downward Lowenheim-Skolem theorem. Inside such a model, the powerset of the natural numbers is uncountable, even though it is countable in whatever meta-model the construction of this model took place.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Suppose that you have an uncountable model of $\sf ZFC$ which includes all the subsets of $\Bbb N$. For example some $V_\kappa$ with $\kappa$ inaccessible. Skolem's paradox does not apply here sine the model and the universe agree on the power set operation. How do you resolve the problem that you asked about using your answer here? $\endgroup$ – Asaf Karagila♦ Nov 16 '14 at 6:28
  • $\begingroup$ What do you mean by the model and the universe? Why doesn't Skolem's paradox apply? Inside your $V_{\kappa}$ (and every other model), by downward LST there exists a countable model $M$ that thinks ZFC. $M$ also thinks the powerset of the natural numbers is uncountable even though $V_{\kappa}$ thinks this set is countable. The argument in my question fails because the notion of being "countable" is not absolute. I think it would be interesting to try coding/enumerating the axioms of ZFC in your $V_{\kappa}$, constructing a countable $M$, and then coding/enumerating the axioms of ZFC in $M$. $\endgroup$ – Jonny Nov 17 '14 at 17:42
  • 1
    $\begingroup$ You're not answering my question. Nor your original question either. You asked, if there are only countably many formulas, how can the power set of the natural numbers be uncountable. In this answer of yours you say "Oh, that's the Skolem paradox", but the Skolem paradox is when you talk about a countable model of set theory. But of course a countable model of set theory has only countably many sets, in particular countably many subsets of $\Bbb N$. But as I said, your question doesn't have "countable model" in it. So how does this answer resolves the case when the model is $V_\kappa$? $\endgroup$ – Asaf Karagila♦ Nov 17 '14 at 17:46
  • 2
    $\begingroup$ It's an important point, the parameters, and many people fail to remember it. Not to mention that just because the axioms govern the universe doesn't mean that every element of the universe is definable. Sometimes things just exist, and we have no "reasonable" explanation why. $\endgroup$ – Asaf Karagila♦ Nov 17 '14 at 18:44
  • 1
    $\begingroup$ Your edit is not quite true either. If $M$ is a model which is a generic extension by some real number $x$ of the model $N$, it is not necessarily the case that a particular $x$ can be defined using a formula (especially since you ignore the fact that the parameters can vary all over the model, trivializing a lot of the definitions). But the statement "$M$ is a generic extension of $N$ by adding a generic real of this type" is expressible in the language of set theory, so it will be true in the countable model. So the countable model will have "not provably existing sets" as well. $\endgroup$ – Asaf Karagila♦ Nov 17 '14 at 18:53

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.