Show that $k= \{\mathfrak A|\mathfrak A\text{ is S-model and} \space R^\mathfrak{A} \space \text{is well founded}\}$ is not $\Delta$-elementary class

52 Views Asked by At

I need to show that the set:

$k= \{\mathfrak A|\mathfrak A\text{ is S-model and} \space R^\mathfrak{a} \space \text{is well founded}\}$

is not a $\Delta$-elementary class, that is:

$k \neq \{\mathfrak A|\mathfrak A\text{ is S-model and} \space \mathfrak A \models \Phi \}$

Where $\Phi$ is an arbitrary set of well formed formulas.

In S we only have the relation $R$. $R$ is a relation that takes two arguments. Well founded is defined by: $(a_{i+1}, a_i)$, won't be in R for any $i \in \mathbb N $, when $a_i \in A$ ($A$ is the universe of the model).

I start by assuming that for ever model $\mathfrak A \in k$, $\mathfrak A \models \Phi$, and then try to show that there exists $\mathfrak A \notin k$, such that $\mathfrak A \models \Phi$, but can't see how to show that.

1

There are 1 best solutions below

9
On

First of all, your definition of well-foundedness is a bit mangled: $R$ is a well-founded relation if whenever we have elements $a_1, a_2, ...,$ there is at least one $i$ such that $R(a_{i+1}, a_i)$ doesn't hold. (The way you've written it makes it sound like we can't have any $R(a_{i+1}, a_i)$ hold, that is, $R$ is the empty relation.)

Now on to the question. In general, when you want to show that a class of models isn't elementary, a good tool to use is compactness, which states that any set of sentences which is finitely satisfiable (= every finite subset has a model) is actually satisfiable. So your goal is to, for each $\Phi$, come up with a $\Gamma$ such that $\Gamma\cup\Phi$ is finitely consistent but any model of $\Gamma\cup\Phi$ can't be in $k$. This will show that $\Phi$ doesn't define $k$ (do you see why?).

Now, applying compactness here takes a trick which you've probably seen before: expanding the language. Think about how one proves that if a theory $T$ has arbitrarily large finite models, then it has infinite models:

  • Expand the language of $T$ by infinitely many new constant symbols $c_1, c_2, ...$.

  • Consider the theory $T'=T\cup\{c_i\not=c_j: i\not=j\}$, consisting of $T$ plus "the constants name distinct elements."

  • $T'$ is finitely consistent, since $T$ has arbitrarily large finite models; so $T'$ has a model $\mathcal{M}$.

  • The reduct of $\mathcal{M}$ to the language of $T$ is a model of $T$; but $\mathcal{M}$ is infinite, so its reduct is also infinite. (Do you see why each of these things is true?)

We're going to do a similar trick here: pass to a larger language, produce a model of the relevant theory, and then show that the reduct of that model to the original language is "bad." HINT: in the definition of well-foundedness, you refer to infinitely many elements $a_i$ - do you see a natural way of expanding the language that this suggests?