LARA

Differences

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

Link to this comparison view

sav08:notes_on_congruences [2009/05/06 10:04]
vkuncak
sav08:notes_on_congruences [2015/04/21 17:30]
Line 1: Line 1:
-====== Notes on Congruences ====== 
  
-We say that a relation $r \subseteq D \times D$ is a //​congruence//​ with respect to a set of functions and relations iff, when we consider a first-order language containing symbols for these functions and relations and interpret '​eq'​ as $r$, the [[Axioms for Equality]] hold in the resulting structure $I$. 
- 
-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 represent a predicate $p(x_1,​\ldots,​x_n)$ as $f_p(x_1,​\ldots,​x_n)=true$.) 
- 
-===== Intersection of Congruences ===== 
- 
-**Theorem:​** Let $S$ be a set of congruences. ​ Then $\bigcap S$ is also a congruence. ​ Note: we define $\bigcap S = \{ x \mid \forall r \in S. x \in r \}$. 
- 
-**Proof:** 
- 
-We will consider the case of $S = \{ r_1, r_2\}$. 
-It case be generalized to arbitrary number of relation, because $\cap$ is associative. 
- 
-Reflexive: 
-$\forall x. (x,x) \in r_1 \wedge (x,x) \in r_2$ because $r_1,r_2$ are congruence. ​ 
-It implies that $(x,x) \in \bigcap S$. 
- 
-Symmetric: 
-$\forall x,y. ((x,y) \in r_1 \rightarrow (y,x) \in r_1) \wedge ((x,y) \in r_2 \rightarrow (y,x) \in r_2)$ because $r_1,r_2$ are congruence. ​ 
-It implies that $(x,y) \in \bigcap S \rightarrow (y,x) \in \bigcap S$. 
- 
-Transitive: 
-\[\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 \\ 
-r_1,r_2 ~~ \text{transitive} & \rightarrow & (x,z) \in r_1,r_2 \\ 
- & \rightarrow & (x,z)\in \bigcap S 
-\end{array} \] 
- 
-Congruence conditions: 
-$\forall x_1,​\ldots,​x_n,​y_1,​\ldots,​y_n.$ 
-\[\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 \\ 
- ​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 
-\end{array} \] 
- 
-**End of Proof.** 
- 
-===== Existence of the Least Congruence Containing Given Relation ===== 
- 
-**Theorem:​** Let $r_0$ be a relation. ​ Let $S$ be the set of all congruences $r$ such that $r_0 \subseteq r$ and let $r_* = \bigcap S$.  Then $r_*$ is the least congruence containing $r_0$, that is 
-  * $r_*$ is a congruence 
-  * $r_0 \subseteq r_*$ 
-  * if $r'$ is a congruence such that $r_0 \subseteq r'$, then $r_* \subseteq r'$ 
- 
-===== Construction of the Least Congruence Containing Given Relation ===== 
- 
-Define ​ 
-\[\begin{array}{rcl} 
-   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 \}  
-\end{array} 
-\] 
-Let $r_{n+1} = C(r_n)$ for $n \ge 0$.  
- 
-**Theorem:​** $\bigcup_{n \ge 0} r_n$ is the least congruence containing $r_0$. 
- 
-**Proof (sketch):** 
- 
-  * $r_* \subseteq \bigcup_{n \ge 0} r_n $: $\bigcup_{n \ge 0} r_n$ is a congruence that contains $r_0$, thus $r_* \subseteq \bigcup_{n \ge 0} r_n$. 
-  * $\bigcup_{n \ge 0} r_n \subseteq r_* $: by induction on $n$. 
-    * $n=0$: $r_0 \subseteq r_*$ by definition of $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.**