3
$\begingroup$

I've had the following question in a midterm exam about first order logic, and didn't manage to solve it:

Let $\mathcal{L}$ be a language and $\mathcal{A}, \mathcal{B}$ structures over $\mathcal{L}$. We say "$\mathcal{A}$ is an elementary substructure of $\mathcal{B}$" (short $\mathcal{A}\preccurlyeq \mathcal{B}$), if $\mathcal{A}$ is a substructure of $\mathcal{B}$ and if for all formulas $\phi$ over $\mathcal{L}$ the following holds true:

$\quad \quad\quad\mathcal{A} \models \phi \Leftrightarrow \mathcal{B}\models \phi$

Now prove: Let $\mathcal{L}$ be countable. Every infinite $\mathcal{L}$ structure has a countable, elementary substructure. Note: Construct a countable Set $B_0 \subseteq B$, that for each formula $\phi(x,y)$ over $\mathcal{L}$ and for each tuple $a\in B_0$ contains a $b$ with $\mathcal{B} \models \phi(a,b)$, if such a $b$ exists.

I honestly wasn't able to solve this with the time given, and it seems to be way to long a proof for an exam. I nevertheless want to understand this, since we didn't get any solutions afterwards.

Thanks in advance!

$\endgroup$
3
$\begingroup$

(for every formula/funciton $P$, I denote $n_P$ as the number of variable it takes, and if $G$ is a function, $G[\cdot]$ is the image)

Let ${\cal A}$ be infinite model of some countable theory.

Let $B_0\subseteq A$ be countable, let $F$ be the set of function symbols, now for each $φ$ formula define $f_φ$ such that:

If $\bar x\in A^{n_φ-1}$ such that $∃y(φ(y,\bar x))$ we have $φ(f_φ(\bar x), \bar x)$, otherwise $f_φ(\bar x)$ is some arbitrary element of $A$(we need AC to prove such $f$ exists.)

Then let $B_{k+1}=B_k\cup\bigcup_\limits{f\in F}f[B_k^{n_f}]∪\bigcup_\limits{φ\text{ formula}}f_φ[B_k^{n_φ}]$ and $B=\bigcup B_k$(this is the closure of all of the function symbols and the functions we defined), because the theory is countable, and there are only countable formulas, $B$ is countable.

Now use Tarski–Vaught test to show that $B$ with the same interpretation as $\cal A$ is elementary substructure

$\endgroup$
  • $\begingroup$ Thank you so much for your answer. The only problem I have with understanding it is that we never covered the Tarski-Vaught test, so I am unsure if this is the way I was supposed to solve it in the exam. $\endgroup$ – nshct Apr 27 at 16:23
  • 1
    $\begingroup$ @nshct did you cover "canonical model of a theory"? $\endgroup$ – ℋolo Apr 27 at 16:25
  • 1
    $\begingroup$ @nshct in what method did you prove the completeness theorem? $\endgroup$ – ℋolo Apr 27 at 16:30
  • 1
    $\begingroup$ Okay, "a theory has a model iff it is not contradictory", so given a theory T with not contradictions you created a model using Henkin's functions right? If you take a look on this model, you can show that the model you get is the size of the language, if M is an infinite model of a countable theory T, create T' to be the set of all formulas true in M, add to the language countably many constant symbols, create a new theory T'' to be T'+for every 2 constant symbols a,b the axiom "a≠b", now Henkin model you create for this will be the countable model you wanted $\endgroup$ – ℋolo Apr 27 at 16:47
  • 1
    $\begingroup$ Oh I think I get it know! Thank you! $\endgroup$ – nshct Apr 27 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.