Tarski-Vaught Test
In particular: throughout.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links.
To discuss this in more detail, feel free to use the talk page.
Once you have done so, you can remove this instance of {{MissingLinks}} from the code.
Merge the various sections and appropriately modularise the various logical steps so as to reduce the repetition as far as possible.
Until this has been finished, please leave {{refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.
Theorem
Let $\mathcal M, \mathcal N$ be $\mathcal L$-structures such that $\mathcal M$ is a substructure of $\mathcal N$.
 |
Work In Progress: The page Definition:Structure is a disambiguation page, in which the form in which it is used here may not be included. The level of clarity in this page generally needs improving. Hence the invocation of the Disambiguate template. (discuss) You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by completing it. When this has been done, the template should be removed from the code. |
If you are familiar with this area of mathematics, you may be able to help improve $\mathsf{Pr} \infty \mathsf{fWiki}$ by determining the precise term which is to be used.
To discuss it in more detail, feel free to use the talk page.
When this has been done, {{Disambiguate}} should be removed from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
Then $\mathcal M$ is an elementary substructure of $\mathcal N$ if and only if:
- for every $\mathcal L$-formula $\phi \left({x, \bar v}\right)$ and for every $\bar a$ in $\mathcal M$:
- if there exists an $n$ in $\mathcal N$ such that $\mathcal N \models \phi \left({n, \bar a}\right)$
- then there exists an $m$ in $\mathcal M$ such that $\mathcal N \models \phi \left({m, \bar a}\right)$.
|
Work In Progress: Before sense can be made of this page, Definition:Substructure and Definition:Elementary Substructure need to be written. (discuss) You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by completing it. When this has been done, the template should be removed from the code. |
If you are familiar with this area of mathematics, you may be able to help improve $\mathsf{Pr} \infty \mathsf{fWiki}$ by determining the precise term which is to be used.
To discuss it in more detail, feel free to use the talk page.
When this has been done, {{Disambiguate}} should be removed from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
The condition on the right side of the if and only if statement above can be rephrased as:
- Every existential statement with parameters from $\mathcal M$ which is satisfied in $\mathcal N$ can be witnessed by an element from the substructure $\mathcal M$.
Generalization
Let $\mathcal N$ be an $\mathcal L$-structure, and $\mathcal M \subseteq \mathcal N$.
Then $\mathcal M$ is the universe of an elementary substructure of $\mathcal N$ if and only if:
- for every $\mathcal L$-formula $\phi \left({x, \bar v}\right)$ and for every $\bar a$ in $\mathcal M$
- if there exists an $n$ in $\mathcal N$ such that $\mathcal N \models \phi \left({n, \bar a}\right)$
- then there exists an $m$ in $\mathcal M$ such that $\mathcal N \models \phi \left({m, \bar a}\right)$.
The condition on the right side of the if and only if statement above can be rephrased as::
- Every existential statement with parameters from $\mathcal M$ which is satisfied in $\mathcal N$ can be witnessed by an element from the subset $\mathcal M$.
Proof
Sufficient Condition
Let $\mathcal M$ be an elementary substructure of $\mathcal N$.
Then $\mathcal N \models \exists x \phi \left({x, \bar a}\right)$ implies that $\mathcal M \models \exists x \phi \left({x, \bar a}\right)$.
Hence there exists some $m$ in $\mathcal M$ such that:
- $\mathcal M \models\phi \left({m, \bar a}\right)$.
Passing back up to $\mathcal N$ yields the result.
Worth making it explicit exactly what that result is, so as to clarify what is being sought here.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this point in more detail, feel free to use the talk page.
If you are able to explain it, then when you have done so you can remove this instance of {{Explain}} from the code.
$\Box$
Necessary Condition
Let $\mathcal M$ be such that:
- For every $\mathcal L$-formula $\phi \left({x, \bar v}\right)$ and for every $\bar a$ in $\mathcal M$:
- if there exists an $n$ in $\mathcal N$ such that $\mathcal N \models \phi \left({n, \bar a}\right)$
- then there exists an $m$ in $\mathcal M$ such that $\mathcal N \models \phi \left({m, \bar a}\right)$.
It is to be shown that $\mathcal M$ is an elementary substructure of $\mathcal N$.
That is:
- for every $\mathcal L$-formula $\psi \left({\bar v}\right)$
and:
- for every $\bar a$ in $\mathcal M$:
- $\left({\mathcal M \models \phi \left({\bar a}\right)}\right) \iff \left({\mathcal N \models\phi \left({\bar a}\right)}\right)$
The proof proceeds by induction on complexity of formulas.
Let $\psi$ be quantifier free.
From Quantifier Free Formula is Preserved by Superstructure, quantifier free formulas with parameters from $\mathcal M$ are preserved when passing to and from superstructures.
Hence the result holds.
Let the result holds for $\psi$.
Consider $\neg \psi$:
We have that:
- $\left({\mathcal M \models \neg \psi \left({\bar a}\right)}\right) \iff \left({\mathcal M \not \models \psi \left({\bar a}\right)}\right)$
By the inductive hypothesis:
- $\left({\mathcal M \not\models\psi \left({\bar a}\right)}\right) \iff \left({\mathcal N \not\models\psi \left({\bar a}\right)}\right)$
Thus the result follows for $\neg \psi$.
Let the result hold for $\psi_0$ and $\psi_1$.
Consider $\psi_0 \wedge \psi_1$:
We have:
- $\mathcal M \models \psi_0 \left({\bar a}\right) \wedge \psi_1 \left({\bar a}\right)$
- $\mathcal M \models\psi_0 \left({\bar a}\right)$
and:
- $\mathcal M \models \psi_1 \left({\bar a}\right)$
By the inductive hypothesis:
- $\mathcal M \models\psi_0 \left({\bar a}\right)$ and $\mathcal M \models \psi_1 \left({\bar a}\right)$
- $\mathcal N \models\psi_0 \left({\bar a}\right)$ and $\mathcal N \models \psi_1 \left({\bar a}\right)$
Thus the result follows for $\psi_0 \wedge \psi_1$.
Let the result holds for $\psi$.
Consider:
- $\exists x: \psi \left({x}\right)$
We prove the two directions of this case separately.
First let:
- $\mathcal M \models \exists x: \psi \left({x, \bar a}\right)$
Then there exists $m \in \mathcal M$ such that:
- $\mathcal M \models \psi \left({m, \bar a}\right)$
By the inductive hypothesis:
- $\mathcal N \models \psi \left({m, \bar a}\right)$
and so:
- $\mathcal N \models \exists x: \psi \left({x, \bar a}\right)$
Conversely, let:
- $\mathcal N \models \exists x: \psi \left({x, \bar a}\right)$
By assumption, there exists $m \in \mathcal M$ such that:
- $\mathcal N \models \psi \left({m, \bar a}\right)$
By the inductive hypothesis:
- $\mathcal M \models \psi \left({m, \bar a}\right)$
and hence:
- $\mathcal M \models \exists x: \psi \left({x, \bar a}\right)$
completing the proof.
$\blacksquare$
Proof of Generalization
Sufficient Condition
Let $\mathcal M$ be an elementary substructure of $\mathcal N$.
Then:
- $\left({\mathcal N \models \exists x: \phi \left({x, \bar a}\right)}\right) \implies \left({\mathcal M \models \exists x \phi \left({x, \bar a}\right)}\right)$
Hence there exists $m \in \mathcal M$ such that:
- $\mathcal M \models \phi \left({m, \bar a}\right)$
Passing back up to $\mathcal N$ yields the result.
$\Box$
Necessary Condition
Let $\mathcal M$ be such that:
- for every $\mathcal L$-formula $\phi \left({x, \bar v}\right)$ and for every $\bar a$ in $\mathcal M$:
- if there exists an $n$ in $\mathcal N$ such that $\mathcal N \models \phi \left({n, \bar a}\right)$
- then there exists an $m$ in $\mathcal M$ such that $\mathcal N \models \phi \left({m, \bar a}\right)$.
It is easily shown, using formulae of the form $\phi \left({x, \bar v}\right) = f \left({\bar v}\right) = x$, that $\mathcal M$ is closed under functions, and hence the universe of a substructure.
This article contains statements that are justified by handwavery, in particular:
"It is easily shown" is not used on this site.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding precise reasons why such statements hold.
If you are able to do this, then when you have done so you can remove this instance of {{Handwaving}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
To discuss this in more detail, feel free to use the talk page.
It remains to be shown that $\mathcal M$ is an elementary substructure of $\mathcal N$.
That is:
- for every $\mathcal L$-formula $\psi \left({\bar v}\right)$ and for every $\bar a$ in $\mathcal M$:
- $\left({\mathcal M \models \phi \left({\bar a}\right)}\right) \iff \left({\mathcal N \models \phi \left({\bar a}\right)}\right)$
The proof proceeds by induction on complexity of formulas.
Let $\psi$ is quantifier free.
From Quantifier Free Formula is Preserved by Superstructure, quantifier free formulas with parameters from $\mathcal M$ are preserved when passing to and from superstructures.
Hence the result holds.
Let the result hold for $\psi$.
Consider $\neg \psi$:
We have:
- $\left({\mathcal M \models \neg \psi \left({\bar a}\right)}\right) \iff \left({\mathcal M \not \models \psi \left({\bar a}\right)}\right)$
By the inductive hypothesis:
- $\left({\mathcal M \not \models \psi \left({\bar a}\right)}\right) \iff \left({\mathcal N \not \models \psi \left({\bar a}\right)}\right)$
Hence the result follows for $\neg \psi$.
Suppose the result holds for $\psi_0$ and $\psi_1$.
Consider $\psi_0 \wedge \psi_1$:
We have that:
- $\mathcal M \models \psi_0 \left({\bar a}\right) \wedge \psi_1 \left({\bar a}\right)$
- $\mathcal M \models \psi_0 \left({\bar a}\right)$ and $\mathcal M \models \psi_1 \left({\bar a}\right)$
By the inductive hypothesis:
- $\mathcal M \models \psi_0 \left({\bar a}\right)$ and $\mathcal M \models \psi_1 \left({\bar a}\right)$
- $\mathcal N \models \psi_0 \left({\bar a}\right)$ and $\mathcal N \models \psi_1 \left({\bar a}\right)$
The result then follows for $\psi_0 \wedge \psi_1$.
Let the result hold for $\psi$.
Consider $\exists x: \psi \left({x}\right)$:
We prove the two directions of this case separately.
First let:
- $\mathcal M \models\exists x \psi \left({x, \bar a}\right)$
Then there exists $m \in \mathcal M$ such that:
- $\mathcal M \models \psi \left({m, \bar a}\right)$
By the inductive hypothesis:
- $\mathcal N \models \psi \left({m, \bar a}\right)$
and so:
- $\mathcal N \models\exists x \psi \left({x, \bar a}\right)$
Conversely, let:
- $\mathcal N \models \exists x: \psi \left({x, \bar a}\right)$
Then by assumption, there exists $m \in \mathcal M$ such that:
- $\mathcal N \models \psi \left({m, \bar a}\right)$
By the inductive hypothesis:
- $\mathcal M \models \psi \left({m, \bar a}\right)$
and hence:
- $\mathcal M \models \exists x: \psi \left({x, \bar a}\right)$
completing the proof.
$\blacksquare$
These two proofs need to be merged and rationalised.
Until this has been finished, please leave {{refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.
Generalization
Merge this in with the above. No attempt at tidying has been made on the below, except to correct spelloes and bring $\LaTeX$ style up to house style.
Until this has been finished, please leave {{refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.
Another common statement of the theorem does not require $\mathcal M$ to be a substructure of $\mathcal N$, it is enough for it to be a subset of $\mathcal N$.
The ($\implies$) is shown just the same as above, while the other direction easily follows, since $\mathcal M$ satisfying the condition that for every $\mathcal L$-formula $\phi \left({x, \bar v}\right)$ and for every $\bar a$ in $\mathcal M$, if there is an $n$ in $\mathcal N$ such that $\mathcal N \models \phi \left({n, \bar a}\right)$, then there is an $m$ in $\mathcal M$ such that $\mathcal N \models \phi \left({m, \bar a}\right)$, is closed under functions (by directly applying the condition to formulae of the form $\phi \left({x, \bar y}\right) = \left({x = f \left({\bar y}\right)}\right)$), and hence the universe of a substructure, which reduces it to the statement above.
$\blacksquare$
Source of Name
This entry was named for Alfred Tarski and Robert Lawson Vaught.