Explanation for this Limitation of 1-Order Logic Concerning Supremum

83 Views Asked by At

In some book I found the statement that it is not possible in the predicate calsulus to express the sentence, that every bounded nonempty subset of an ordered field has a supremum. I thought that could be expressed as follows, for a subset $X \subset K$ of some ordered field $K$

\begin{align} \left[ X\subset K \land X \neq \emptyset \land \forall x\in X\ \exists a\in K(x<a) \right] \to \exists s\in K\ \forall y\in K\left(( \forall x\in X\ x<y)\to s<y \right) \end{align} What is wrong about that ?

1

There are 1 best solutions below

3
On BEST ANSWER

In first-order logic (as opposed to higher-order logics) we can only quantify over individual objects in the domain in question, rather than e.g. subsets of the domain or functions on the domain. So if we're working in the context of ordered fields, the sentence you've written is not first order.


Although not directly related to your question, it's worth saying a bit more about the consequences of this limitation on quantification - which turn out to be extremely significant! The two most important are the compactness and Löwenheim-Skolem (especially downward Löwenheim-Skolem, the upward part being a corollary of compactness) theorems:

  • Compactness: if $\Gamma$ is any first-order theory and every finite subset of $\Gamma$ is satisfiable, then $\Gamma$ is satisfiable.

  • Löwenheim-Skolem: if $\Gamma$ is any first-order theory in a language of size $\kappa$, and $\Gamma$ has at least one infinite model, then $\Gamma$ has at least one infinite model of every infinite cardinality $\ge\kappa$. In particular, if $\Gamma$ is countable then $\Gamma$ has models of every infinite cardinality.

It turns out that in a precise sense we can't strengthen first-order logic at all without losing at least one of these properties. In particular, second-order logic fails both properties. (The proof of this is a bit lengthy, especially in the case of Löwenheim-Skolem if you're not already familiar with some set theory; however, I can add them if you're interested.)