Continuum Hypothesis in formalized language.

Question

The Continuum Hypothesis was advanced by Georg Cantor in 1878, before that Zermelo–Fraenkel set theory was stablished.

"There is no set whose cardinality is strictly between that of the integers and the real numbers".

$$ 2^{\aleph_0} = \aleph_1 $$

But in the formal language of that theory (see http://mathworld.wolfram.com/Zermelo-FraenkelAxioms.html) it is not possible to directly express that judgment, and there seems not to be an issue of "abbreviations" only, because the concept of transfinite cardinal transcend to theories of first order.

Therefore, it is necessary to express the concepts born in natural language, formalizable in second order logic, in the first-order language, which is not trivial.

How you would express it with a formula in the formal language of ZF or ZFC?

---

Since formal language is needed, I explain the requirements.

If you write an abreviation of many formulae of first order, the type of it must be a set definable in first order (not numbers, nor other formula. In this case, please sketch the procedure for to translate it to first order.

A property or relationship is expressible in the ZF/C system, iff when checked in the theory of reference (in this case, not formalized set theory) is a theorem in ZF/C. A function is representable ssi the relationship F (x) = y is expressible.

If you use some everyday set theory property/function/relation, please sketch why it is expresible/representable. Please do not use limit ordinals because they are of second order (if $\omega$ would be definable in first order, so it would be $\aleph_0$). In any case, even if you think the limit ordinals are of first order, it is not what we need. Just as an example of the type of requested language, I add an tipical answer within the requirements:

Being a Power set is expressible in ZFC, by the axiom 5.

By the axiom of choice, bijection between A and B is representable, say by $\varphi(A,B)$.

Being an infinite set is expressible, by the axiom 6.

So:

If W is an infinite set (countable or not); and there is no set of which W is the power set:

(Z) W ~= $\mathscr{P}(Z)$

For all sets that are'nt power of any power set, they are biyectable with W or with Pow (W)

(X)(W) [ ~(EY) X = $\mathscr{P}$ ($\mathscr{P}(Y)$) ] $\implies$ [ $\varphi(W,X)$ \/ $\varphi(X,\mathscr{P}(W))$ ]

Thank for your respect to this format.

Answer 1

This is a very very very dull and long exercise in writing formulas.

1. $\varphi_o(x)$ states that $x$ is a limit ordinal.
2. $\varphi_c(x)$ states that $x$ is countable.
3. $\varphi_p(x,y)$ states that $y$ is the power set of $x$.
4. $\varphi_b(x,y)$ states that there exists a function with domain $x$ and range $y$ which is injective (and surjective, by definition).
5. Write a "template" for $x$ is the least ordinal such that $\varphi(x)$ is true, whatever $\varphi$ is (and it will be $\varphi_c$ and $\lnot\varphi_c$ so there are just two instances of this template being used here).

Now we combine these to say that there is $x$ which is the least countable limit ordinal, and $y$ which is the least limit ordinal that is not countable, and there exists $z$ which is the power set of $x$, and there exists a bijection between $z$ and $y$.

All this becomes a long long long formula. But since $2^{\aleph_0}$ is the cardinality of the power set of the least countable limit ordinal; and $\aleph_1$ is the cardinality of the least uncountable ordinal; and equipotency is defined using bijections... this is what it means.

Answer 2

It is formalized as: For all $S$, if there exists an $a\not\in S$ such that there exists a bijection from $S$ to $S\cup\{a\}$, and there is no injection from $P(\mathbb{N})$ to $S$, then there is a bijection from $\mathbb{N}$ to $S$.

This asserts that if $S$ is infinite and not as big as $\mathbb{R}$ then it is the case that $S$ is countable, i.e. Every smaller infinity is countable.

Each of these words has a way to express it formally, which is quite long, but I can write out of you like.

Answer 3

"Every subset of $\mathscr{P}(\omega)$ is either at most countable or in bijection with $\mathscr{P}(\omega)$ itself."

Of course, you can replace "at most countable" with "in bijection with a subset of $\omega$". And you can replace "$X$ is in bijection with $Y$" by "there exists a set of ordered pairs $(x,y)$ such that the first coordinate of each is in $X$ and the second is in $Y$, and each element of $X$ occurs as first coordinate of a unique air and each element of $Y$ occurs as first coordinate of a unique pair".

And you can replace $\omega$ by "a set $S$ such that $\varnothing\in S$ and $\forall x\in S(x\cup\{x\}\in S)$ and such that any $S'$ which satisfies those two properties is a subset of $S$". And of course, you can replace ordered pairs (and their coordinates), singletons, unions, and powersets in all of the above by the fairly obvious codings.

In the end, it should be rather long. It might be interesting to write it in full with the help of a computer.

(Edit/clarification: This is all assuming $\mathsf{ZFC}$. In $\mathsf{ZF}$ alone, if CH is the statement that $\mathscr{P}(\omega)$ is well-orderable with order-type $\omega_1$, we need to really write the fact that there is a bijection between $\mathscr{P}(\omega)$ and $\omega_1$, so define $\omega_1$.)

Answer 4

Based on the OP's comments, I think I see their problem.

In ZF, everything is a set. This includes transfinite ordinals such as $\omega$ and $\omega_1$, real numbers, natural numbers, etc. So when we write "$\forall x$", we are indeed quantifying over all ordinals (and much more).

Perhaps surprisingly, not only is every ordinal a set, but the collection of ordinals is definable! We can write down a formula in first-order logic whose meaning is "$x$ is an ordinal". Similarly for the infinite ordinals, or the ordinals bigger than 17. The most convenient definition of ordinal (in my opinion) is "hereditarily transitive set": a set $x$ is an ordinal if it satisfies $$\forall y\in x(\forall z\in y(z\in x)\wedge\forall z\in y, w\in z(w\in y)).$$ Specific ordinals such as $\omega$ and $\omega_1$ also can be defined, although these definitions are a bit long (note that although they talk about functions, functions are just special kinds of sets, so this is still first-order in ZF or ZFC):

• We can define $\omega$ as the unique ordinal (defined above) $x$ such that for every ordinal $y$, if there is a bijection from $y$ to a proper subset of $y$, then $x$ is a subset of $y$. (That is, $\omega$ is the smallest infinite ordinal.)

• $\omega_1$ is then defined as the unique ordinal (defined above) such that for every ordinal $\alpha$ which has no injection into $\omega$, $\omega_1$ is a subset of $\alpha$. (That is, $\omega_1$ is the smallest uncountable ordinal.)

To refer to a defined set inside a larger statement, we use a kind of dummy quantifier: e.g. to say "$\alpha\in\omega_1$" we could write $$\forall x(\varphi(x)\implies \alpha\in x),$$ where $\varphi$ is the formula defining $\omega_1$.

The continuum hypothesis is then the statement that there is a bijection between $\omega_1$ and the powerset of $\omega$.

---

Just for kicks, here is the continuum hypothesis written almost entirely in the language of ZF (the one exception is that I'm using an abbreviation "$\mathfrak{B}(a, b, c)$" for "$a$ is a bijection between $b$ and $c$", since this is easy but extremely tedious to write out in the language of ZF):

$\exists x\forall y\forall z\forall w[([\forall t\in y(\forall u(u\in t\implies u\in y)\wedge\forall u\forall v(u\in t\wedge v\in u\implies v\in t))] \wedge \exists h[\forall j(j\in h\implies j\in y)\wedge \exists l(l\in y\wedge \neg l\in h)\wedge \exists i(\mathfrak{B}(i, y, h))]\wedge\forall q([\forall t(t\in q\implies \forall u(u\in t\implies u\in q)\wedge\forall u \forall v(u\in t\wedge v\in u\implies v\in t))]\wedge \exists h[\forall j(j\in h\implies j\in q)\wedge \exists l(l\in q\wedge \neg l\in h)\wedge \exists i(\mathfrak{B}(i, q, h))] \implies \forall p(p\in y\implies p\in q))) \wedge \forall y(y\in z\implies \forall n(n\in y\implies n\in z)\wedge\forall n\forall w(n\in y\wedge w\in n\implies w\in y))\wedge\forall k[\forall y\in k(\forall z(z\in y\implies z\in k)\wedge\forall z\forall w(z\in y\wedge w\in z\implies w\in y))\wedge \exists f[\mathfrak{B}(f, k, y)]\implies \forall r(r\in k\implies r\in z)] \wedge \forall j(\forall k[\forall y(y\in k\implies\forall z(z\in y\implies z\in k)\wedge\forall z\forall w(z\in y\wedge w\in z\implies w\in y))\wedge \exists f[\mathfrak{B}(f, k, y)]\implies \forall r(r\in k\implies r\in j)] \implies \forall r(r\in z\implies r\in j)) \wedge [\forall c[c\in w\iff \forall d(d\in c\implies d\in y)]] \implies \mathfrak{B}(x, w, z)].$

Clear, right? :P

What this sentence says, if you unpack it, is: "There is an $x$ such that for all $y, z, w$, if $y$ is the first infinite ordinal, $z$ is the first uncountable ordinal, and $w$ is the powerset of $y$, then $x$ is a bijection between $z$ and $w$." That is, "The powerset of $\omega$ is in bijection with $\omega_1$."

Hopefully you can see both how a sentence like this can be constructed from the recipes the answers have given, and also why we're all reluctant to actually do it: it's really, really tedious!