In a formal axiomatic system with both the law of the excluded middle and the axiom of infinity does an uncountable set have to exist?

Question

This was something I have been thinking around when examining writings of some “philosophers” who seemingly argue against the existence of a continuation but at the same time accept the law of the excluded middle and also the axiom of infinity.

I know from cantor’s proof of the unaccountability of the reals if you have something that obeys the real number axions then the set of all of them will be uncountable (if you have LEM). However what I am interested in is if you just have the natural numbers and LEM does that entail the existence of some sort of uncountable set.

Clearly introducing the power set axiom would also entail an uncountable set so that isn’t the type of FAS I am interested in.

Answer 1

No. For instance, if you omit the power set axiom from ZFC, you get a theory that is consistent with the non-existence of uncountable sets. In particular, working in ZFC, consider the set of hereditarily countable sets. This is a model of every axiom of ZFC except for the power set axiom, and in this model every set is countable.

(This theory is also quite a bit more powerful than you might think and is strong enough for most of mathematics. For instance, you don't have a set of real numbers, but you can still do basically all of real analysis by treating the real numbers as a class, and describing sufficiently nice functions $\mathbb{R}\to\mathbb{R}$ using a countable amount of data.)

Answer 2

Certainly not: consider (in the setting of classical logic) any structure in which there is an infinite set but no countable set, such as $L_{\omega+1}$, and then just consider the theory of that structure.

(Note that in the case of $L_{\omega+1}$ we have something even better - a definable bijection with $\omega$. By contrast, something like $L_{\omega_1}$ is "locally countable" but not "internally globally countable.")

I suspect that you want some additional properties of the theory in question, but I'm not sure what.

Answer 3

Note that ACA0 (one of the common base theories in reverse mathematics) is conservative over PA for arithmetical sentences and yet powerful enough to handle essentially all applied real analysis. And ACA0 has a nice countable model where its sets are simply the arithmetical subsets of $ℕ$. There is no set-theoretic infinity axiom in ACA0, but any model of ACA0 obviously has an infinite set (i.e. the model of the first-order subtheory, which is a model of PA). Of course ACA0 has no uncountable sets; it has just two levels after all.

But I don't know whether you realize that even with no set-theoretic axioms, not to say power-set kind of axiom, Cantor's theorem still holds in the following form:

For every binary arithmetical predicate $Q$ there is some unary arithmetical predicate $R$ such that $∀k{∈}ℕ\ ∃m{∈}ℕ\ ¬( \ Q(k,m) ⇔ R(m) \ )$.

Why is this like Cantor's theorem? It says that for every arithmetically definable function $f$ from $ℕ$ to subsets of $ℕ$ (i.e. $f(k) = \{ m : m{∈}ℕ ∧ Q(k,m) \}$ for each $k∈ℕ$) there is some arithmetically definable subset $S$ of $ℕ$ (i.e. $S = \{ m : m{∈}ℕ ∧ R(m) \}$) that is not in the range of $f$. So, clearly, the arithmetically definable subsets of $ℕ$ are 'uncountable' in the sense of being not enumerable by any arithmetically definable function.

The proof mirrors that of the usual Cantor's theorem, which I shall leave as an easy exercise.