Ffind an ordinal type of the well-ordering

59 Views Asked by At

Let $x_n$ for $n \in N$ are variables of predicate logic. Let $F(L)$ defines set of all formulas of language $L$ and $Σ(L) = L ∪ \{(,), ¬, →, ∀\} ∪ \{x_n | n ∈ N\}$ defines corresponding alphabet. We define sequence of languages $(L_n)_{n\in N}$ without equality in the following way: $L_0 = \{P\}$ (where $P$ is unary predicate symbol) $L_{n+1} = L_n ∪ \{c_{\varphi} | \varphi \in F(L_n)\}$ for each $n \in N$ (where each $c_{\varphi}$ is a constant). Let's put $L=\cup_{n \in N}L_n$ (it probably somehow corresponds to Henkin's conservative extention) Now let's define by induction according to $n \in N$ well-orderings $\le_n$ on $\sum(L_n)^*$ in the following way:

For particular signs holds

$( \le_n ) \le_n P \le_n ¬ \le_n → \le_n ∀ \le_n x_0 \le_n x_1 \le_n x_2 \le_n . . . ;$

if $n>0$ then any of singns above is lower then arbitrary constant $c_{\varphi}$, and $c_{\varphi} \leq_{n} c_{\psi}$ iff $\varphi \leq_{n-1} \psi$. Words are being compared primarily according to length and secondarily lexicographically.

Since those orderings are pairwise compatible they define unique well-ordering $\leq = \cup_{n\in N} \leq_n$ on $Σ(L)^*$ and simultaneously on $F(L)$ subset.

I am trying to find an ordinal type of the well-ordering $\leq$ on $F(L)$. Also I am looking for an example of a well-ordering on $F(L)$ with ordinal type $\omega$.

Thanks in advance for any possible help

1

There are 1 best solutions below

1
On BEST ANSWER

There's an easy way to get an ordering of $F(L)$ with order-type $\omega$: essentially, Goedel numbers.

We'll assign positive integers to each symbol and each word, as follows:

  • A word $a_1...a_n$ is assigned the number $$Code(a_1...a_n)=\prod_{1\le i\le n} p_i^{1+code(a_i)}.$$

  • We set $code(c_\varphi)=2^{Code(\varphi)+1}$.

  • And we initialize as follows: the $i$th basic symbol (that is, from $(,),P,\neg,...$, ordered as you do) gets code $3^{i+1}$.

This isn't the most efficient numbering scheme, but it's easy to show that the map $Code$ is an injection from $F(L)$ into $\mathbb{N}$; this gives the desired ordering.


As to the ordering on $F(L)$ that you describe: it appears to be $\epsilon_0$, the limit of $\omega, \omega^\omega, \omega^{\omega^\omega}, ...$.

To see this, consider the following: we let $M_0=\mathbb{N}$ with the usual ordering, and $M_{i+1}$ be the set of words in $M_i$ ordered first by length and second lexicographically. This isn't quite your construction, but it's easier to visualize, and it's not hard to see they have the same order type.

Then by induction, $M_{i+1}$ has order type $M_i+M_i^2+M_i^3+...$, so we have

  • $M_0$ has order type $\omega$,

  • $M_1$ has order type $\omega^\omega$,

  • $M_2$ has order type $\omega^{\omega^\omega}$,

  • Etc.