-3
$\begingroup$

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.

$\endgroup$

closed as unclear what you're asking by Noah Schweber, Asaf Karagila, Stella Biderman, pjs36, Paul Plummer Jan 31 '16 at 9:02

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

locked by Daniel Fischer Feb 1 '16 at 14:53

This post has been locked while disputes about its content are being resolved. You may discuss this on meta if you have concerns.

Read more about locked posts here.

  • 4
    $\begingroup$ It isn't a sentence of the metalanguage. It's a sentence of ZF — anyway, an abbreviation of a ZF sentence. It uses many defined terms, introduced as shorthands, which can actually all be eliminated to yield a formula involving only $\in$ and the standard symbols of first order logic. $\endgroup$ – BrianO Jan 28 '16 at 22:51
  • 4
    $\begingroup$ Your edit is wrong in many ways. First, axioms do not prove that something is expressible - that's done on the level of language. (Even if we don't have the powerset axiom, "being a powerset" is expressible in the language of set theory.) And certainly there's no relationship at all between saying that two sets are bijectable, and the axiom of choice. More to the point, your formalization of CH is incorrect - e.g. it's consistent with CH that $\aleph_{16}$ isn't the cardinality of any powerset. Finally, you have no grounds to call the many answers below "cranky." $\endgroup$ – Noah Schweber Jan 30 '16 at 23:09
  • 4
    $\begingroup$ At this point, based on your responses I think it is clear that you are not acting in good faith here. I have voted to close for now, pending more serious engagement with the answers you have been provided. $\endgroup$ – Noah Schweber Jan 30 '16 at 23:10
  • 5
    $\begingroup$ @AbelPeralta I did not delete your previous comment; presumably, a moderator did. And I'm not really sure what you mean about my qualifications, but certainly I am qualified to answer questions in basic set theory. You still have not addressed any of the answers or comments in a substantive way, so I will not comment here anymore as it seems to be a waste of my time. However, I really do encourage you to read carefully the responses you have gotten here, from me and others. $\endgroup$ – Noah Schweber Jan 31 '16 at 23:13
  • 3
    $\begingroup$ Please avoid making comments about the status of the question in the question body (and certainly not at the top of the post). $\endgroup$ – Asaf Karagila Feb 1 '16 at 0:30
12
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ No. If you really try you can probably fit it in a single A4 page. Probably less (depending on your font size and margins, but let's assume standard fullpage LaTeX in 10pt TeX Gyre font). But not something I'd care to write explicitly on this site, and not something I think is worth being written explicitly on this site either. $\endgroup$ – Asaf Karagila Jan 29 '16 at 0:17
  • 2
    $\begingroup$ @Abel Ordinals are sets. $\endgroup$ – Unit Jan 30 '16 at 4:40
  • 2
    $\begingroup$ @AbelPeralta Transfinite ordinals are sets - in fact, the collection of transfinite ordinals is first-order definable! There is no problem here. $\endgroup$ – Noah Schweber Jan 30 '16 at 5:09
  • 3
    $\begingroup$ @Abel: Perhaps it would be a good idea to actually learn some set theory first. $\endgroup$ – Asaf Karagila Jan 30 '16 at 8:17
  • 3
    $\begingroup$ @Abel: I agree that there are delicate points there, and that you're probably missing them with that simplified declaration. $\endgroup$ – Asaf Karagila Jan 30 '16 at 13:24
6
$\begingroup$

"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$.)

$\endgroup$
  • $\begingroup$ I wonder if $omega$ is a set. I guess it is a transfinite ordinal. In first order language all values of variables must be sets and only sets, no matter if your formula is an abreviation of many other formulae. Thanks for your answer. $\endgroup$ – Kaspar Hauser Jan 30 '16 at 4:22
  • $\begingroup$ @AbelPeralta See my answer. $\endgroup$ – Noah Schweber Jan 30 '16 at 5:18
5
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I guess it's a good answer, but I will try to rebuild it without use of transfinite ordinals. Very grateful. $\endgroup$ – Kaspar Hauser Jan 30 '16 at 12:55
  • 1
    $\begingroup$ @AbelPeralta Why? Do you not like ordinals or something? I really don't understand . . . $\endgroup$ – Noah Schweber Jan 30 '16 at 16:16
  • $\begingroup$ Nothing to do personal tastes. The stated goal was to build a formula with ZFC symbols that are in the link, only, and if necessary for short, provide a method to build the formula. Only that. $\endgroup$ – Kaspar Hauser Jan 30 '16 at 17:25
  • 1
    $\begingroup$ @AbelPeralta I think there's something you don't understand here, but I'm not sure what it is exactly. $\endgroup$ – Stella Biderman Jan 30 '16 at 20:13
  • 1
    $\begingroup$ I wouldn't say that it's "really, really tedious". I would have said that it's "really really really, REALLY tedious". $\endgroup$ – Asaf Karagila Jan 30 '16 at 21:11
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I guess that $\mathbb{N}$ nor $\mathbb{R}$ can be the value of a variable of first order language of ZF/ZFC. Thanks for your kind answer. $\endgroup$ – Kaspar Hauser Jan 30 '16 at 4:27
  • 1
    $\begingroup$ @AbelPeralta See my answer. $\endgroup$ – Noah Schweber Jan 30 '16 at 5:18
  • 2
    $\begingroup$ @AbelPeralta what do you mean by that? $\endgroup$ – Stella Biderman Jan 30 '16 at 15:30
  • $\begingroup$ "There is a bijection from $ S$ to itself does not suffice to say that $ S $ is infinite. $\endgroup$ – Andrés E. Caicedo Jan 31 '16 at 2:07
  • $\begingroup$ @AndrésCaicedo you're right, I modified my sentence. Must have just left the extra element out by accident. $\endgroup$ – Stella Biderman Jan 31 '16 at 2:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.