• English only

# Differences

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

 sav08:notes_on_congruences [2009/05/06 10:04]vkuncak sav08:notes_on_congruences [2015/04/21 17:30] (current) Both sides previous revision Previous revision 2009/05/06 11:56 vkuncak 2009/05/06 10:04 vkuncak 2009/05/06 10:00 vkuncak 2009/05/05 23:36 vkuncak 2008/04/26 16:51 damien 2008/04/26 16:14 damien 2008/04/23 10:17 vkuncak 2008/04/23 10:16 vkuncak 2008/04/23 00:11 vkuncak 2008/04/23 00:06 vkuncak 2008/04/22 23:57 vkuncak 2008/04/22 23:49 vkuncak 2008/04/22 23:45 vkuncak 2008/04/22 23:35 vkuncak 2008/04/22 23:29 vkuncak 2008/04/22 22:46 vkuncak 2008/04/22 22:44 vkuncak 2008/04/22 22:35 vkuncak created Next revision Previous revision 2009/05/06 11:56 vkuncak 2009/05/06 10:04 vkuncak 2009/05/06 10:00 vkuncak 2009/05/05 23:36 vkuncak 2008/04/26 16:51 damien 2008/04/26 16:14 damien 2008/04/23 10:17 vkuncak 2008/04/23 10:16 vkuncak 2008/04/23 00:11 vkuncak 2008/04/23 00:06 vkuncak 2008/04/22 23:57 vkuncak 2008/04/22 23:49 vkuncak 2008/04/22 23:45 vkuncak 2008/04/22 23:35 vkuncak 2008/04/22 23:29 vkuncak 2008/04/22 22:46 vkuncak 2008/04/22 22:44 vkuncak 2008/04/22 22:35 vkuncak created Line 6: Line 6: We assume no relation symbols other than congruence itself. ​ (We represent a predicate $p(x_1,​\ldots,​x_n)$ as $f_p(x_1,​\ldots,​x_n)=true$.) We assume no relation symbols other than congruence itself. ​ (We represent a predicate $p(x_1,​\ldots,​x_n)$ as $f_p(x_1,​\ldots,​x_n)=true$.) + ===== Intersection of Congruences ===== ===== Intersection of Congruences ===== Line 25: Line 26: Transitive: Transitive: - $\begin{array}{rcl} + \begin{equation*}\begin{array}{rcl} (x,y) \in \bigcap S \wedge (y,z) \in \bigcap S &​\rightarrow&​ (x,y) \in r_1,r_2 \wedge (y,z) \in r_1,r_2 \\ (x,y) \in \bigcap S \wedge (y,z) \in \bigcap S &​\rightarrow&​ (x,y) \in r_1,r_2 \wedge (y,z) \in r_1,r_2 \\ r_1,r_2 ~~ \text{transitive} & \rightarrow & (x,z) \in r_1,r_2 \\ r_1,r_2 ~~ \text{transitive} & \rightarrow & (x,z) \in r_1,r_2 \\ & \rightarrow & (x,z)\in \bigcap S & \rightarrow & (x,z)\in \bigcap S - \end{array}$ + \end{array} \end{equation*} Congruence conditions: Congruence conditions: $\forall x_1,​\ldots,​x_n,​y_1,​\ldots,​y_n.$ $\forall x_1,​\ldots,​x_n,​y_1,​\ldots,​y_n.$ - $\begin{array}{rcl} + \begin{equation*}\begin{array}{rcl} ​\bigwedge_{i=0}^n (x_i,y_1) \in \bigcap S & \rightarrow & \bigwedge_{i=0}^n (x_i,y_1) \in r_1,r_2 \\ ​\bigwedge_{i=0}^n (x_i,y_1) \in \bigcap S & \rightarrow & \bigwedge_{i=0}^n (x_i,y_1) \in r_1,r_2 \\ - ​r_1,​r_2 ~~ \text{congruence relations} & \rightarrow & f(x_1,​\ldots,​ x_n) = f(y_1,​\ldots,​ y_n) \in r_1,r_2 \\ + ​r_1,​r_2 ~~ \text{congruence relations} & \rightarrow & (f(x_1,​\ldots,​ x_n), f(y_1,​\ldots,​ y_n)) \in r_1,r_2 \\ & \rightarrow & f(x_1,​\ldots,​ x_n) = f(y_1,​\ldots,​ y_n) \in \bigcap S & \rightarrow & f(x_1,​\ldots,​ x_n) = f(y_1,​\ldots,​ y_n) \in \bigcap S - \end{array}$ + \end{array} \end{equation*} **End of Proof.** **End of Proof.** Line 51: Line 52: Define ​ Define ​ - $\begin{array}{rcl} + \begin{equation*}\begin{array}{rcl} C(r) &=& r \cup \Delta_D \cup r^{-1} \cup r \circ r\ \cup \\ C(r) &=& r \cup \Delta_D \cup r^{-1} \cup r \circ r\ \cup \\ & & \{ ((f(x_1,​\ldots,​x_n),​f(y_1,​\ldots,​y_n)) \mid \bigwedge_{i=1}^n (x_i,y_i) \in r \} & & \{ ((f(x_1,​\ldots,​x_n),​f(y_1,​\ldots,​y_n)) \mid \bigwedge_{i=1}^n (x_i,y_i) \in r \} \end{array} \end{array} -$ + \end{equation*} Let $r_{n+1} = C(r_n)$ for $n \ge 0$. Let $r_{n+1} = C(r_n)$ for $n \ge 0$.