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:notes_on_congruences [2008/04/26 16:51] damien |
sav08:notes_on_congruences [2009/05/06 10:04] 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 65: | Line 65: | ||
| * $\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.** | ||