7

What I mean by the title is whether, given that there is a class $\Bbb R$ and operations $+,\cdot,<$ that satisfy the ordered field axioms and the least upper bound axiom, you can prove the existence of an infinite set in $\sf ZF-Inf$. My intuition says this is possible, because those axioms are sufficient to prove that $|\Bbb R|=|2^\Bbb N|$ in $\sf ZF$, and most (all?) models that satisfy the negation of infinity are countable, which means that classes like this $\Bbb R$ cannot possibly fit in the model. (Note that I am not assuming that $\Bbb R\in V$, which would make the question trivial.)

Mario Carneiro
  • 27,438
  • This may seem like an unintelligent comment, but how does one prove an axiom? –  May 03 '14 at 00:10
  • 2
    Derive that the axiom is true as a theorem without using it in the proof. – Mario Carneiro May 03 '14 at 00:12
  • 1
    If a first-order theory over a countable language has an infinite model, or even arbitrarily large finite models, then for any infinite cardinal $\kappa$ it has a model of cardinality $\kappa$. – André Nicolas May 03 '14 at 00:17
  • @AndréNicolas So I guess that means that my argument from cardinality is no good. Note that the least upper bound axiom is in this context a schema over classes that are subsets of $\Bbb R$, so it is nontrivial even without infinity. – Mario Carneiro May 03 '14 at 00:21
  • 2
    The assertion that the Axiom of Infinity follows seems highly plausible, and interesting. – André Nicolas May 03 '14 at 00:24
  • Note that I am also assuming the axioms of $\sf ZF-Inf$ in any derivation (so it is perfectly alright to talk about sets here). $\Bbb R$ is a concrete class in the universe, we just don't know anything about it beyond that given to us from the real number axioms. – Mario Carneiro May 03 '14 at 01:30
  • It's worth noting that any real closed field (including the countable ones, like the field of real algebraic numbers) satisfies the least upper bound axiom schema if we only consider the subclasses that can be defined in terms of the ordered field structure. If we equip the class of hereditarily finite sets with a real closed field structure, it's nonobvious to me that we can use $\in$ along with $+,\cdot,<$ to define a bounded class that doesn't have a least upper bound. –  May 03 '14 at 01:54
  • 1
    @Hurkyl I was trying to put this in words, but I agree with you - the cardinality argument breaks down not only because of Andre's point, but also because without infinity you might even have $\Bbb R$ countable. I'm interested in both sides of this question - if it's true, I get a proof that the real numbers imply infinity, and if it's false, I get a construction of the real numbers that doesn't need infinity. – Mario Carneiro May 03 '14 at 01:59
  • It might also be relevant that the theory of real closed fields is o-minimal. Given this, it is not clear to me how one would use the ordered field structure to construct a set which the model thinks is countable. – Miha Habič May 03 '14 at 02:04
  • @Hurkyl Why does $e=\sum_{n=0}^\infty\frac1{n!}$ fail? – Mario Carneiro May 03 '14 at 02:17
  • @Miha Here is a construction of $\Bbb N$ as a class: from transfinite recursion (which does not need infinity for its proof), we can construct the class function $f(\emptyset)=1$, $f(\operatorname{suc}n)=f(n)+1$; then the range of $f\upharpoonright\omega$ is $\Bbb N$. Thus this theory is not o-minimal. – Mario Carneiro May 03 '14 at 02:30
  • I wasn't claiming that the whole theory (together with the set-theoretic part) was o-minimal. I was speculating that, since the ordered field structure doesn't seem to give you sets of appropriate size by itself, I don't see an obvious way to get them at all. – Miha Habič May 03 '14 at 02:33
  • @Mario: Hrm. I think you've convinced me that we can do some basic calculus in your setting that we can't do in the theory of real ordered fields. –  May 03 '14 at 02:49
  • @Hurkyl I just showed how $\Bbb N$ is a definable class above. Using a similar method, you can construct all sorts of countable sequences as definable classes. In this case $g(\emptyset)=1$, $h(\emptyset)=0$, $g(\operatorname{suc}n)=g(n)f(n)$, $h(\operatorname{suc}n)=h(n)+1/g(n)$, then $\sup(\operatorname{ran}h)=e$. – Mario Carneiro May 03 '14 at 02:50
  • @Sanath: How do you show that Zorn's lemma is equivalent to the axiom of choice? Or is the axiom of choice different from the rest of the axioms? – Asaf Karagila May 03 '14 at 05:44

1 Answers1

5

The question is a bit tricky to formalize. If we work in $\mathsf{ZF}-\text{Infinity} + \neg \text{Infinity}$ then any ordered field is necessarily a proper class, so the least upper bound property is really an axiom schema and not a single axiom. However, I think that in any reasonable formulation the answer to the question is "yes".

Work in $\mathsf{ZF}-\text{Infinity}$. If $\omega$ is a set then we're done, so assume that $\omega$ is a proper class (in which case it is the class of all ordinals.) Then there is a definable surjection $\omega \to V$.

Assume that $\mathcal{R} = (R,+^\mathcal{R},\times^\mathcal{R},<^\mathcal{R})$ is an ordered field. We can either formalize what we are proving as a theorem schema with one theorem for every possible quadruple of formulas defining an ordered field, or we can formalize it as a theorem in the language of set theory expanded by predicate symbols $R$, $+$, $\times$, and $<$. In any case, we will show that $\mathcal{R}$ is not complete.

Recall that $V$ is countable, so in particular $R$ is countable. Let $f : \omega \to R$ be a surjection. We may then use Cantor's proof of the uncountability of the reals to define a $<^\mathcal{R}$-bounded subclass of $R$ with no least upper bound (if $\mathcal{R}$ were complete, we would get an element of $R$ not in the range of $f$, but every element of $R$ is in the range of $f$, so instead the argument tells us that $\mathcal{R}$ is not complete.)

More details: we recursively define a strictly $<^\mathcal{R}$-increasing sequence $(a_n : n<\omega)$ and a strictly $<^\mathcal{R}$-decreasing sequence $(b_n : n<\omega)$ such that for every $n < \omega$ we have $a_n <^\mathcal{R} b_n$ and either $f(n) <^\mathcal{R} a_n$ or $b_n <^\mathcal{R} f(n)$. (We don't need the Axiom of Choice to choose $a_n$ and $b_n$ because the universe is definably well-ordered in order type $\omega$ via $f$.) Then the set $\{x \in R : \exists n \in \omega\,(x <^\mathcal{R} a_n)\}$ is a bounded subset of $\mathcal{R}$ with no least upper bound.

EDIT: In summary, your intuition is essentially correct. However, we need more than the fact that "most" models (e.g. the intended model $V_\omega$) of $\mathsf{ZF} - \text{Infinity} + \neg\text{Infinity}$ are seen to be countable from the outside. We need to use the fact that the theory $\mathsf{ZF} - \text{Infinity} + \neg\text{Infinity}$ proves "$V$ is countable," which allows us, working in this theory, to use Cantor's argument to rule out the existence of a complete ordered field of the same size as $V$.

Trevor Wilson
  • 16,989