0

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.

Dole
  • 2,653

1 Answers1

1

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?

Noah Schweber
  • 245,398
  • I am still having trouble grasping the basic idea of what to do. Am I supposed expand the language with infinitely many relation symbols in such way that when reduced only to the one relation symbol, the set of formulas can't be true? – Dole Mar 12 '17 at 21:56
  • @Dole You are supposed to expand the language, but not in that way. You want to add symbol(s) which describe some phenomenon you care about - in this case, an infinite descending chain. This infinite descending chain consists of a bunch of elements in relation to one another in a certain way, and you already have the relation symbol ($R$) - so what symbols do you think you should add? Think about the example in my answer - it's exactly the same idea . . . – Noah Schweber Mar 13 '17 at 01:44
  • Can you by any chance fill in the answer? In the sample answer the answer was to add infinite amount of relation symbols as $\Gamma$. I would love to see how your answer works. – Dole Mar 13 '17 at 15:24
  • @Dole No, it was to add an infinite amount of constants - "Expand the language of $T$ by infinitely many new constant symbols" . . . – Noah Schweber Mar 13 '17 at 15:27
  • I mean the sample answer we got to the problem was to have infinite relations in gamma. But I would like to see how you would prove the result by expanding the language with infinite constant symbols. – Dole Mar 13 '17 at 15:30
  • @Dole No. The answer to the sample problem did two things: (i) add infinitely many constant symbols to the language, and (ii) write infinitely many sentences describing how those constant symbols should interact. If you want to build a non-well-founded model, there's some configuration that should happen in it (what does it mean to be ill-founded?); add infinitely many constants to name the elements of such a configuration, and sentences saying that those constants behave in the right way. E.g. in the example, the configuration was "an infinite set of distinct elements." (cont'd) – Noah Schweber Mar 13 '17 at 16:21
  • We added constants to correspond to those elements, and sentences saying that the constants named distinct elements - now, do you see how to do the same thing in this case? – Noah Schweber Mar 13 '17 at 16:21
  • I mean the sample solution we got from our mathematical logic class, not the one in your answer. – Dole Mar 13 '17 at 18:25
  • @Dole Well, given that I don't have that sample solution, I can't really tell you anything about it. Maybe you can describe it to me in detail? Or, hang on - do you mean infinitely many different relation symbols (which would be weird), or one relation symbol used infinitely many times (which is really what I've been suggesting to you)? – Noah Schweber Mar 13 '17 at 18:25