2

The question: Let $L=${S}, S is a two-place relation. I need to show that there exists a theory - $T$, in the vocabulary L such that for each structure $M$ to interpret $L$:

$M\models T \leftrightarrow S^M$ is a partial order on the world and on the world there exist infinite maximum elements in a relation to $S^M$.

I have tried using the compatible theorem but without any success, and now I'm stuck.

rain11
  • 29

2 Answers2

2

First we can knock out the axioms that $S$ is a partial order, which are standard:

  • $\psi_1\equiv\forall v(v S v)$                                                       (reflexivity)
  • $\psi_2\equiv\forall v,w([vSw\wedge wSv]\rightarrow v=w)$        (anti-symmetry)
  • $\psi_3\equiv\forall u,v,w([uSv\wedge vSw]\rightarrow uSw)$        (transitivity)

Now, to express that there are infinitely many maximal elements with respect to $S$, we can use a common trick. Recall that a theory $T$ can have infinitely many axioms. In particular, if we want to express "there are infinitely many elements satisfying property $P$", we can add infinitely many axioms to $T$, one for each $n\in\mathbb{N}$, each expressing "there are greater than $n$ elements satisfying property $P$", and this will suffice. So, consider the following $L$-sentence:

  • $\phi_n\equiv\exists v_1,\dots,v_n\big[\left(\bigwedge_{i<j}v_i\neq v_j\right)\wedge\left(\bigwedge_{i=1}^n \forall w[ v_i S w\rightarrow v_i=w]\right)\big]$

$\phi_n$ states precisely that there are $n$ distinct elements, each maximal with respect to $S$. So, if $T$ contains all $\phi_n$ for every $n\in\mathbb{N}$, then any model of $T$ must have infinitely many maximal elements with respect to $S$. In particular, letting $T=\{\psi_1,\psi_2,\psi_3\}\cup\{\phi_n\}_{n\in\mathbb{N}}$ gives the desired theory.

Atticus Stonestrom
  • 11,426
2

You can start with the usual axioms for a partial order, and for each $n\in\Bbb N$ add the following formula: $$\exists x_1,\dots,x_n: \bigwedge_{i< j}\lnot (x_i=x_j)\,\land\,\bigwedge_i\psi(x_i)$$ where $\psi(x)$ is a formula stating that $x$ is a maximal element.

Berci
  • 90,745