Differences

This shows you the differences between two versions of the page.

 sav08:isomorphism_of_interpretations [2008/03/19 17:34]vkuncak sav08:isomorphism_of_interpretations [2015/04/21 17:30] (current) Both sides previous revision Previous revision 2008/03/20 13:37 vkuncak 2008/03/19 17:34 vkuncak 2008/03/19 17:34 vkuncak 2008/03/19 17:29 vkuncak 2008/03/19 17:24 vkuncak 2008/03/19 17:23 vkuncak 2008/03/19 17:23 vkuncak 2008/03/19 17:16 vkuncak 2008/03/19 17:14 vkuncak 2008/03/19 17:12 vkuncak 2008/03/19 17:08 vkuncak 2008/03/19 17:07 vkuncak 2008/03/19 17:06 vkuncak 2008/03/19 17:06 vkuncak 2008/03/19 17:04 vkuncak 2008/03/19 17:02 vkuncak 2008/03/19 17:00 vkuncak 2008/03/19 15:31 vkuncak 2008/03/19 10:56 vkuncak 2008/03/19 08:38 vkuncak 2008/03/19 00:57 vkuncak 2008/03/19 00:52 vkuncak 2008/03/18 23:11 vkuncak 2008/03/18 23:08 vkuncak 2008/03/13 13:08 vkuncak 2008/03/13 13:05 vkuncak 2008/03/13 12:57 vkuncak Next revision Previous revision 2008/03/20 13:37 vkuncak 2008/03/19 17:34 vkuncak 2008/03/19 17:34 vkuncak 2008/03/19 17:29 vkuncak 2008/03/19 17:24 vkuncak 2008/03/19 17:23 vkuncak 2008/03/19 17:23 vkuncak 2008/03/19 17:16 vkuncak 2008/03/19 17:14 vkuncak 2008/03/19 17:12 vkuncak 2008/03/19 17:08 vkuncak 2008/03/19 17:07 vkuncak 2008/03/19 17:06 vkuncak 2008/03/19 17:06 vkuncak 2008/03/19 17:04 vkuncak 2008/03/19 17:02 vkuncak 2008/03/19 17:00 vkuncak 2008/03/19 15:31 vkuncak 2008/03/19 10:56 vkuncak 2008/03/19 08:38 vkuncak 2008/03/19 00:57 vkuncak 2008/03/19 00:52 vkuncak 2008/03/18 23:11 vkuncak 2008/03/18 23:08 vkuncak 2008/03/13 13:08 vkuncak 2008/03/13 13:05 vkuncak 2008/03/13 12:57 vkuncak 2008/03/13 12:38 vkuncak 2008/03/13 12:30 vkuncak created Line 4: Line 4: **Example:​** How many models does this formula have? **Example:​** How many models does this formula have? - $\begin{array}{l} + \begin{equation*}\begin{array}{l} (\exists x. P(x))\ \land \\ (\exists x. P(x))\ \land \\ (\exists x. \lnot P(x))\ \land \\ (\exists x. \lnot P(x))\ \land \\ Line 10: Line 10: (\forall x. \forall y. \lnot P(x) \land \lnot P(y) \rightarrow x=y) \\ (\forall x. \forall y. \lnot P(x) \land \lnot P(y) \rightarrow x=y) \\ \end{array} \end{array} -$ + \end{equation*} ++Answer:​|Infinitely many.  For example, for any integer $n$, let $I=(D,​\alpha)$ such that $D=\{n,​n+1\}$ and $\alpha(P)=\{n\}$.++ ++Answer:​|Infinitely many.  For example, for any integer $n$, let $I=(D,​\alpha)$ such that $D=\{n,​n+1\}$ and $\alpha(P)=\{n\}$.++ Line 17: Line 17: **Definition:​**:​ An isomoprhism between $(D_1,​\alpha_1)$ and $(D_2,​\alpha_2)$ is a //bijective function// $s : D_1 \to D_2$ such that **Definition:​**:​ An isomoprhism between $(D_1,​\alpha_1)$ and $(D_2,​\alpha_2)$ is a //bijective function// $s : D_1 \to D_2$ such that * for $R \in {\cal L}$, $ar(R)=n$ and all $x_1,​\ldots,​x_n \in D_1$ * for $R \in {\cal L}$, $ar(R)=n$ and all $x_1,​\ldots,​x_n \in D_1$ - $+ \begin{equation*} ​((x_1,​\ldots,​x_n) \in \alpha_1(R)) \leftrightarrow (s(x_1),​\ldots,​s(x_n)) \in \alpha_2(R)) ​((x_1,​\ldots,​x_n) \in \alpha_1(R)) \leftrightarrow (s(x_1),​\ldots,​s(x_n)) \in \alpha_2(R)) -$ + \end{equation*} * for $f \in {\cal L}$, $ar(f)=n$ and all $x_1,​\ldots,​x_n \in D_1$ * for $f \in {\cal L}$, $ar(f)=n$ and all $x_1,​\ldots,​x_n \in D_1$ - $+ \begin{equation*} s(\alpha_1(f)(x_1,​\ldots,​x_n)) = \alpha_2(f)(s(x_1),​\ldots,​s(x_n)) s(\alpha_1(f)(x_1,​\ldots,​x_n)) = \alpha_2(f)(s(x_1),​\ldots,​s(x_n)) -$ + \end{equation*} * for $x \in V$ a first-order variable, $s(\alpha_1(x)) = \alpha_2(x)$. * for $x \in V$ a first-order variable, $s(\alpha_1(x)) = \alpha_2(x)$. If $D_1=D_2$ then the isomorphism $s$ is called //​automorphism//​. If $D_1=D_2$ then the isomorphism $s$ is called //​automorphism//​. Line 39: Line 39: ++++transitive:​| if $s_1 : I_1 \to I_2$ is isomorphism and $s_2 : I_2 \to I_3$ is isomorphism,​ then we claim $s_2 \circ s_1 : I_1 \to I_3$ is isomorphism. ​ Let us prove this for the case of function symbols: ++++transitive:​| if $s_1 : I_1 \to I_2$ is isomorphism and $s_2 : I_2 \to I_3$ is isomorphism,​ then we claim $s_2 \circ s_1 : I_1 \to I_3$ is isomorphism. ​ Let us prove this for the case of function symbols: - $\begin{array}{rcl} ​ + \begin{equation*}\begin{array}{rcl} ​ (s_2 \circ s_1)(\alpha_1(f)(x_1,​\ldots,​x_n)) ​ (s_2 \circ s_1)(\alpha_1(f)(x_1,​\ldots,​x_n)) ​ &=& s_2(s_1(\alpha_1(f)(x_1,​\ldots,​x_n))) \\ &=& s_2(s_1(\alpha_1(f)(x_1,​\ldots,​x_n))) \\ Line 46: Line 46: &=& \alpha_3(f)((s_2 \circ s_1)(x_1),​\ldots,​(s_2 \circ s_1)(x_n))) ​ &=& \alpha_3(f)((s_2 \circ s_1)(x_1),​\ldots,​(s_2 \circ s_1)(x_n))) ​ \end{array} \end{array} -$ + \end{equation*} ++++ ++++ Line 52: Line 52: **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 - $+ \begin{equation*} ​s(e_T(t)(I_1))=e_T(t)(I_2) ​s(e_T(t)(I_1))=e_T(t)(I_2) -$ + \end{equation*} and for every first-order logic formula $F$ we have $e_F(F)(I_1)=e_F(F)(I_2)$. 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 and formulas. + **Proof:​** ​++++|Induction on the structure of terms and formulas. Case for $F_1 \land F_2$. Case for $F_1 \land F_2$. - Case for $\exists x.F$.  Induction issues. + Case for $\exists x.F$.  Induction issues, function update on isomorphic interpretations. - ++ + ++++ **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)$.