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:16] vkuncak |
sav08:isomorphism_of_interpretations [2008/03/19 17:34] 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 51: | Line 53: | ||
**Lemma:** If $s$ is isomorphism from $I_1$ to $I_2$, then for every first-order term $t$ we have | **Lemma:** If $s$ is isomorphism from $I_1$ to $I_2$, then for every first-order term $t$ we have | ||
\[ | \[ | ||
- | s(e_T(I_1)(t))=e_T(I_2)(t) | + | s(e_T(t)(I_1))=e_T(t)(I_2) |
\] | \] | ||
- | 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(F)(I_1)=e_F(F)(I_2)$. |
- | **Proof:**++|Induction on the structure of terms.++ | + | **Proof:** ++++|Induction on the structure of terms and formulas. |
+ | |||
+ | Case for $F_1 \land F_2$. | ||
+ | |||
+ | Case for $\exists x.F$. Induction issues. | ||
+ | |||
+ | ++++ | ||
**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 65: | Line 73: | ||
$\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)$ ++ | + | $((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.** |