Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | |||
sav08:notes_on_congruences [2009/05/06 11:56] vkuncak |
sav08:notes_on_congruences [2015/04/21 17:30] (current) |
||
---|---|---|---|
Line 26: | 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 52: | 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$. | ||