LARA

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision 		Previous revision
sav08:sets_and_relations [2009/03/10 14:02]
vkuncak 		sav08:sets_and_relations [2010/02/26 22:03]
vkuncak
Line 167: Line 167:
 When $S \subseteq A$ and $r \subseteq A \times A$ we define **image** of a set $S$ under relation $A$ as When $S \subseteq A$ and $r \subseteq A \times A$ we define **image** of a set $S$ under relation $A$ as
 \[ \[
-   S.r = \{ y.\ \exists x. x \in S \land (x,y) \in r \}+   S\bullet ​r = \{ y.\ \exists x. x \in S \land (x,y) \in r \}
 \] \]
 +
  
 ==== Transitive Closure ==== ==== Transitive Closure ====
Line 196: Line 197:
 or, equivalently,​ the least relation $s$ (with respect to $\subseteq$) that satisfies or, equivalently,​ the least relation $s$ (with respect to $\subseteq$) that satisfies
 \[ \[
-    \Delta_A\ \cup\ (s \circ s)\ \subseteq\ s+    \Delta_A\ \cup\ r \cup (s \circ s)\ \subseteq\ s
 \] \]
  
Line 294: Line 295:
  
  
-==== More Properties ==== 
  
 +
 +
 +==== Range, Image, and Composition ====
 +
 +The following properties follow from the definitions:​
 \[ \[
-   S.r = ran(\Delta_S ​\circ r)+   (S \bullet r_1) \bullet r_2 = S \bullet (r_1 \circ r_2)
 \] \]
 \[ \[
-   S.r_1.r_2 ​= S . (r_1 \circ r_2)+   ​S ​\bullet r = ran(\Delta_S ​\circ r)
 \] \]
  
 ===== Further references ===== ===== Further references =====
  
 +  * [[sav08:​discrete_mathematics_by_rosen|Discrete Mathematics by Rosen]]
   * [[:Gallier Logic Book]], Chapter 2   * [[:Gallier Logic Book]], Chapter 2