Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
sav08:notes_on_congruences [2008/04/26 16:51] damien |
sav08:notes_on_congruences [2009/05/06 11:56] vkuncak |
||
|---|---|---|---|
| Line 5: | Line 5: | ||
| We next fix $D$ as well as functions and relations and consider the set of all congruences on the set $D$ with respect to these functions and relations. | We next fix $D$ as well as functions and relations and consider the set of all congruences on the set $D$ with respect to these functions and relations. | ||
| - | We assume no relation symbols other than congruence itself. We can represent predicate $p(x_1,\ldots,x_n)$ as $f_p(x_1,\ldots,x_n)=tr$ where $f_p$ is a fresh function and $tr$ is a fresh special constant (think of this constant as '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 35: | Line 36: | ||
| \[\begin{array}{rcl} | \[\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} \] | ||
| Line 65: | Line 66: | ||
| * $\bigcup_{n \ge 0} r_n \subseteq r_* $: by induction on $n$. | * $\bigcup_{n \ge 0} r_n \subseteq r_* $: by induction on $n$. | ||
| * $n=0$: $r_0 \subseteq r_*$ by definition of $r_*$ | * $n=0$: $r_0 \subseteq r_*$ by definition of $r_*$ | ||
| - | * $n \rightarrow n+1$: only elements that are **needed** to make a congruence out of $r_n$ are added to $r_{n+1}$, hence these element are also in $r_*$. | + | * $n \rightarrow n+1$: all elements introduced by $C(r_n)$ are required to be in $r_*$ by definition of congruence, so if $r_n \subseteq r_*$ then also $r_{n+1} \subseteq r_*$ |
| **End of Proof.** | **End of Proof.** | ||