0
$\begingroup$

Just as an exercise in formula manipulation, I tried to find the simplest formula $\phi(x)$ with one free variable $x$ in the language of ZFC that defines the first transfinite ordinal $\omega$ (i.e. $\phi(x) \leftrightarrow x=\omega$). Here is my attempt (operator precedence follows the Wikipedia): $\begin{align}\phi(x):=\exists a (a \in x) \land \forall a \forall b \forall c ((a \in x \lor a = x) \to (c \in b \to (b \in a \to c \in a))) \land \\ \forall a (a \in x \to (\exists b (a \in b \land b \in x) \land (\exists b (b \in a) \to \exists b (b \in a \land \neg \exists c (b \in c \land c \in a)))))\end{align}$ It means that $x$ is non-empty ordinal (transitive set with transitive elements) that is not a successor ordinal, but each its non-empty element is a successor ordinal.

Is this formula correct? Can anybody suggest further simplification?

  • 0
    @BrianM.Scott: Yes, that is correct.2011-12-05

1 Answers 1

4

Recall that $\omega$ is an inductive set. It is the minimal inductive set.

$\begin{align*} \varphi(x):=\Bigg(\varnothing\in x&\land\forall w\Big(w\in x\rightarrow w\cup\{w\}\in x\Big)\Bigg)\\ &\land\forall y\Bigg(\bigg(\varnothing\in y\land\forall w\Big(w\in y\rightarrow w\cup\{w\}\in y\Big)\bigg)\rightarrow\forall w\Big(w\in x\rightarrow w\in y\Big)\Bigg) \end{align*}$

If you'd wish to avoid $\varnothing$ or $w\cup\{w\}$ they both can be replaced. It would make the formula considerably longer though. These two are defined as:

  1. $x = \varnothing\iff\forall y(y\in x\rightarrow y\in y)$
  2. $x=w\cup\{w\} \iff \forall z\Big((z\in w\lor z=w)\Leftrightarrow z\in x\Big)$
  • 0
    @nikov: Either you're talking about the "fully expanded" version, or your original attempt is very badly written. Mine looks a lot better, in my opinion. The differences, anyway, should not sum in more than a short amount of letters.2011-12-07