According to Thomas Jech (Set Theory, p. 4-5): "We develop axiomatic set theory in the framework of the first order predicate calculus. Apart from the equality predicate =, the language of set theory consists of the binary predicate $\in$, the membership relation ... In practice, we shall use in formulas other symbols, namely defined predicates, operations, and constants, and even use formulas informally; but it will be tacitly understood that each such formula can be written in a form that only involves $\in$ and = as nonlogical symbols."

Let's call this language $L_{\in}$. Is this the language of ZFC? If so, any formula of ZFC has to be reducible to a $\Pi^0_n$ or $\Sigma^0_n$, formula on the language $L_{\in}$. Am I correct up to here?

Queston 1: The continnum hipothesis is said to be a $\Sigma^2_1$ statement. In what language? What about the GCH? if they are not reducible to $\Pi^0_n$ or $\Sigma^0_n$, why do they belong to ZFC?.

Question 2: Similar with the definition of totally indescribable cardinal, is this definition within $L_{\in}$? if so, is it reducible to a $\Pi^0_n$ or $\Sigma^0_n$ formula in the language $L_{\in}$?

  • $\begingroup$ It took me nearly 25 minutes to write that answer. I didn't even see the edit! $\endgroup$
    – Asaf Karagila
    Apr 22 '13 at 0:02
  • $\begingroup$ The continuum hypothesis was proven independent of zfc. This means there is not contradiction regardless of the truth of the continuum hypothesis. Also indescribable cardinal. Those things are not decidable in zfc. See en.wikipedia.org/wiki/List_of_statements_undecidable_in_ZFC $\endgroup$ Jun 13 '15 at 11:38

There is a fine line between the language of the theory, and the expressible powers of the theory.

Note that $\sf ZFC$ has a language with a single binary relation. The same language would be sufficient for $\Bbb Q$ or $\Bbb N$ with their linear orders; or even any other binary relation. That's just the language.

The theory itself, however, can prove that certain formulas define very particular functions or relations. And we can use these to express more. For example $\subseteq$. Think about it, $A\subseteq B\iff\forall x(x\in A\rightarrow x\in B)$. In a theory where $\in$ is interpreted as any old partial order, this would trivially be satisfied by any $A\in B$. But since we have a particular idea about what is going to be the interpretation, and what axioms would be true in such interpretation we know that $A\subseteq B$ has a lot more information.

When you were told that $\sf CH$ is $\Sigma^2_1$ the meaning was as a statement of third-order arithmetics. That is we talk about sets of sets of natural numbers. This is not in the language of $\{\in\}$ and the axioms which are for our disposal are not those of $\sf ZFC$ (or $\sf ZF$). No, that $\Sigma^2_1$ would be to formulate $\sf CH$ as a statement about the integers, or rather sets of sets of integers.

So how can we describe $\sf GCH$ in the language of set theory? Well, easily. First we write the following formulas:

  1. $\varphi_f(x,y,z)$ the set $z$ is a subset of $x\times y$ and it is a function, whose domain is $x$ and whose range is a subset of $y$, and it is injective.

    Note that all these things can be easily expressed. We can say when something is an ordered pair, so we can say when $z$ is a set of ordered pairs from $x\times y$, and we can express being a function and so on, and we can certainly express being injective.

  2. $\varphi_p(x,y)$ is the definable power set function, i.e. $y=\mathcal P(x)$.

  3. $\varphi_I(x)$ is a predicate saying that $x$ is infinite, that is to say that there is no function from $x$ into $\omega$ which is injective and whose range is bounded. Note that $\omega$ itself is a definable element in the axioms of $\sf ZFC$, it is the unique ordinal that is not zero, not a successor and all its elements are either zero or successor ordinals.

  4. Now we can easily write $\sf GCH$. Because $\sf GCH$ says that for every $x,y,z$ if $\varphi_p(x,y)$ and $z\subseteq y$ then exists $f$ such that $\varphi_f(z,x,f)$ or $\varphi_f(y,z,f)$.

    That is to say, whenever $z$ is a subset of $\mathcal P(x)$ either $z$ injects into $x$ or $\mathcal P(x)$ injects into $z$.

Now to compute the complexity of $\sf GCH$ as stated above, note that power set definitions are $\Pi^0_1$ (every $z$ is in $\mathcal P(x)$ if and only if $z\subseteq x$ (which is bounded)); so $\varphi_f$ is probably $\Delta^0_0$ (note that any quantification we have in that formula can be bounded by $x,y$ or $z$), and $\varphi_p$ is certainly $\Pi^0_1$, being infinite is easily $\Delta^0_1$.

So we have that $\sf GCH$ itself is also $\Pi^0_3$. Because it starts with universal quantifiers, and inside we have a disjunction of $\Sigma^0_2$ with another $\Sigma^0_2$ (recall that implication can be replaced by a disjunction, and calculate that indeed the formulas inside the implication turn to $\Sigma^0_2$ when we replace the $\rightarrow$ by $\lor$).

So all in all $\sf GCH$ is $\Pi^0_3$ in the language of $\{\in\}$. It might be even less, but I'm not sure.

You should convince yourself like my students this semester do, that these things are correct. Start by writing formulas which state that something is a function, define ordinals, then define $\omega$, and so on and so forth. It's a great exercise and you realize how much you can express in $\sf ZFC$.

Now to the indescribable cardinals, the point of these is that you don't use $\sf ZFC$ in its full power (i.e. quantify somewhere in the universe), but you consider the structure $\langle V_\kappa,\in,R\rangle$, and now you consider whether or not you can find a formula separating this structure from substructure of the form $\langle V_\alpha,\in,R\cap V_\alpha\rangle$ for some $\alpha<\kappa$.

It might be the case that you can with a very simple formula, but it might be the case that you really need a second- or third- or even higher-order formula for this. But this property as a whole is still a first-order property in $\sf ZFC$, because in the full universe we have power sets of $V_\kappa$ to bound the things which are higher-order in the structure $\langle V_\kappa,\in,R\rangle$.

This is not an obvious distinction, and it takes a lot of time to full digest these arguments, which is why I suggest you start with something gentle such as verifying that $\sf GCH$ is really $\Pi^0_3$ (or lower) in the language of $\{\in\}$ (by verifying all these things I wrote above).

  • $\begingroup$ thanks a lot Asaf, I just got a few books on set theory, I am gonna try! $\endgroup$ Apr 22 '13 at 0:17
  • $\begingroup$ My pleasure. It was a fun answer to write. You're making me revise basic large cardinals material in my head which is great, too. I understand a lot of things I didn't pay attention (or couldn't understand) when I took a course about this stuff two years ago. $\endgroup$
    – Asaf Karagila
    Apr 22 '13 at 0:18
  • $\begingroup$ Julian, you may want to write $\sf CH$ as well, and see if you can get it for cheaper than $\Pi^0_3$, it could be a fun exercise I think. $\endgroup$
    – Asaf Karagila
    Apr 22 '13 at 0:38
  • $\begingroup$ ok, I'll try!... $\endgroup$ Apr 22 '13 at 0:42

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.