Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
sav08:isomorphism_of_interpretations [2008/03/19 17:14] vkuncak |
sav08:isomorphism_of_interpretations [2008/03/19 17:23] vkuncak |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== Isomorphism of First-Order Logic Interpretations ====== | ====== Isomorphism of First-Order Logic Interpretations ====== | ||
+ | |||
+ | (Building on [[First-Order Logic Semantics]].) | ||
**Example:** How many models does this formula have? | **Example:** How many models does this formula have? | ||
Line 55: | Line 57: | ||
and for every first-order logic formula $F$ we have $e_F(I_1)(F)=e_F(I_2)(F)$. | and for every first-order logic formula $F$ we have $e_F(I_1)(F)=e_F(I_2)(F)$. | ||
- | **Proof:**++|Induction on the structure of terms.++ | + | **Proof:** |
+ | ++++|Induction on the structure of terms and formulas. | ||
+ | |||
+ | |||
+ | |||
+ | ++++ | ||
**Lemma:** If $(D_1,\alpha_1)$ is an interpretation for language ${\cal L}$, if $D_2$ is a set and $s : D_1 \to D_2$ a bijective function, then there exists a mapping $\alpha_2$ of symbols in ${\cal L}$ such that $(D_2,\alpha_2)$ is an interpretation for ${\cal L}$ and $(D_2,\alpha_2)$ is isomorphic to $(D_1,I_1)$. | **Lemma:** If $(D_1,\alpha_1)$ is an interpretation for language ${\cal L}$, if $D_2$ is a set and $s : D_1 \to D_2$ a bijective function, then there exists a mapping $\alpha_2$ of symbols in ${\cal L}$ such that $(D_2,\alpha_2)$ is an interpretation for ${\cal L}$ and $(D_2,\alpha_2)$ is isomorphic to $(D_1,I_1)$. | ||
Line 64: | Line 71: | ||
$\alpha_2(f)(e_1,\ldots,e_n) = $++|$s(\alpha_1(f)(s^{-1}(e_1),\ldots,s^{-1}(e_n))$ ++ | $\alpha_2(f)(e_1,\ldots,e_n) = $++|$s(\alpha_1(f)(s^{-1}(e_1),\ldots,s^{-1}(e_n))$ ++ | ||
+ | |||
+ | $((e_1,\ldots,e_n) \in \alpha_2(R)) = $++|$((s^{-1}(e_1),\ldots,s^{-1}(e_n)) \in \alpha_1(R))$ ++ | ||
**End of proof.** | **End of proof.** |