What is the formulation of the Least Upper Bound propierty in First Order Logic?

Question

I've been readining about the completeness Godel's theorems. Accordingly, the axioms of $R$ in first order logic make up one of these sets that is complete and consistent. But I've always seen the axiom of the least upper bound formulated in second order logic. What is the equivalent formulation in first order logic?

Answer 1

There is no properly equivalent formulation in first-order logic to the completeness property of $(\Bbb R,\leq)$.

One reason is that the second-order axiom allows us to quantify over all the subsets of $\Bbb R$, and there are $2^{2^{\aleph_0}}$ of those.

We can write a schema which says that every definable subset - with parameters - if it has an upper bound, then it has a least upper bound. If we don't allow parameters then there are only $\aleph_0$ subsets that we can define, and that is far from being enough; and if we do allow parameters then we can at most define $2^{\aleph_0}$ subsets, which is still far from enough to cover all the subsets.

There is, however, a small trick that we can use: We define a new language which contains another predicate $S$ and another binary symbol relation $\in$. We add the axioms which say that if $x\in y$ then $S(y)$ and $\lnot S(x)$; and that the axioms of $\leq$ are only applicable to the elements for which $\lnot S$ holds.

In short, we allow two sort of objects in our universe, sets and real numbers and we want to make sure that the things that were true in $(\Bbb R,\leq)$ are true for the things which are not sets.

Now we can write the following statements:

$$\varphi(A,x)=S(A)\land\forall y(y\in A\rightarrow y\leq x)$$ This is a formula stating that $x$ is an upper bound of the set $A$. And finally we can write:

$$\forall A(S(A)\land\exists y(\varphi(A,y)\rightarrow\exists y(\varphi(A,y)\land\forall z(\varphi(A,z)\rightarrow y\leq z))$$

We still have to slightly modify our model, now its universe is $\Bbb R\cup\cal P(\Bbb R)$ and the relations are $\leq$ and $\in$ as we normally think of them. It is not hard to verify that indeed the above statement is true.