# Can uncountability of reals be proved only from the axioms?

If we define real numbers, as is sometimes done, with field axioms, and order axioms, and completeness (or continuity) axiom, then, rational numbers fulfill field axioms and order axioms, but they do not fulfill completeness axiom.

So, completeness axiom helps us, in a sense, to distinguish between rational and real numbers.

Moreover, axioms for the real numbers characterize real numbers up to isomorphism, so, in a sense, there is only one structure that fulfills axioms for the real numbers, and that structure is a system of real numbers.

Because both real numbers and rational numbers fulfill field and order axioms, the field and order axioms do not characterize only one structure (up to isomorphism).

It is written somewhere that, for example, we can prove existence of $$n$$-th (for every $$n$$) roots of nonnegative real numbers in the set of real numbers, by taking as our starting point the set of axioms for the real numbers.

Also, there is a set-theoretic result that there is no bijection between the set of real numbers and the set of rational numbers, and the one which states that there is a bijection from naturals onto rationals, so, rationals are countable and reals are uncountable.

But, as axioms for the real number system characterize reals up to isomorphism, I started to think that we could be able to prove that there is no bijection between rationals and reals by using only these two premises:

1) rationals and reals satisfy field and order axioms

2) reals satisfy the completeness axiom but rationals do not

and by using the concept of bijection.

What I mean is, that representation of reals and rationals as infinite sums in some base would not be allowed in such a proof.

If something is not clear, you can ask in comments, and if you have an idea on how to improve this question, ideas are welcomed.

• Can you use Cantor theorem? It is equivalent to the axiom of completeness – miraunpajaro Jun 13 at 20:34
• A (possible) sketch of an idea (not even a sketch of a proof!): suppose that there is a bijection between $\mathbb{Q}$ and $\mathbb{R}$, then there is a bijection that preserve order (aka "limits"), but there are things that converge in $\mathbb{R}$ and not in $\mathbb{Q}$, contradiction. – dcolazin Jun 13 at 20:34
• @dcolazin Why there must necessarily be a bijection that preserves order? – Grešnik Jun 13 at 20:38
• @miraunpajaro Which one? The one with nested intervals? – Grešnik Jun 13 at 20:40
• There are incomplete ordered fields that are the same cardinality as $\mathbb{R}$, so if you want to prove there is no bijection between $\mathbb{Q}$ and $\mathbb{R}$ you need to use more about $\mathbb{Q}$ than just that it is incomplete. – Eric Wofsey Jun 13 at 21:02

Since you're introducing non-first-order axioms (such as completeness - and the compactness and Lowenheim-Skolem theorems say you really need to in this context), there is no really satisfying notion of "proof." Instead, we need to go "fully semantic" - the right notion here instead of "$$\Gamma$$ proves $$\varphi$$" is "Every model of $$\Gamma$$ is a model of $$\varphi$$, and in jargon this would be phrased as "$$\Gamma$$ entails $$\varphi$$." The logic you're working in here is second-order logic.

The axioms you listed are not enough to entail that $$\mathbb{Q}$$ is countable, or indeed that $$\vert\mathbb{Q}\vert<\vert\mathbb{R}\vert$$, since - as noted in the comments - there are proper (hence incomplete) subfields of $$\mathbb{R}$$ which have cardinality continuum.

• Incidentally, there's an interesting question here: when does an algebraic structure have a proper substructure of the same cardinality? Structures which don't are called "Jonsson" - see e.g. here - and their study is important in set theory.

So what do we need here?

A sufficient axiom - and in my opinion, the right choice here - is that the rationals form the smallest ordered field. Another way to phrase this, which you may find more palatable, is "Every subfield of $$\mathbb{R}$$ contains $$\mathbb{Q}$$." This does indeed pin down $$\mathbb{Q}$$ exactly, and hence is enough to entail countability.

If you'd rather use ideas about bijections, you can do that too: a set $$S$$ is countably infinite iff

• $$S$$ is Dedekind infinite (= there is a bijection between $$S$$ and some proper subset of $$S$$), and

• for each Dedekind-infinite $$T\subseteq S$$, there is a bijection between $$T$$ and $$S$$.

So we can write axioms entailing the countability of $$\mathbb{Q}$$ in this way, too. And all of this can be expressed in second-order logic.

A couple further remarks:

• Re: the need for second-order logic here, it's important to note that there are other logics stronger than first-order, perhaps the most important one being $$\mathcal{L}_{\omega_1,\omega}$$, which is the simplest infinitary logic (and is much better behaved than second-order logic in many ways). The general study of logics stronger than first-order logic is called abstract model theory, and there is a fantastic (if difficult) collection on the subject edited by Barwise and Feferman.

• Re: the above demonstration of the insufficiency of your proposed axioms, an interesting question here: when does an algebraic structure have a proper substructure of the same cardinality? Structures which don't are called "Jonsson" - see e.g. here - and their study is important in set theory.

• Yes, my thoughts were mostly on can we prove that Q is countable from all the axioms except continuity axiom. – Grešnik Jun 26 at 17:06
• @Grešnik Do you mean "completeness" axiom? I'm not sure what the "continuity" axiom is. (And to reiterate: no, per my answer and the comments to the OP those axioms do not suffice.) – Noah Schweber Jun 26 at 17:08
• Yes, completeness axiom, sometimes called continuity axiom because we suppose sometimes that a line is continuous in such a way that there is a bijection of real numbers with the points of a line, that is the reason for that different name. – Grešnik Jun 26 at 17:10