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:sets_and_relations [2009/03/10 14:13] vkuncak |
sav08:sets_and_relations [2010/02/26 21:56] vkuncak |
||
|---|---|---|---|
| Line 169: | Line 169: | ||
| S\bullet 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 295: | Line 296: | ||
| - | ==== More Properties ==== | ||
| + | |||
| + | ==== Range, Image, and Composition ==== | ||
| + | |||
| + | The following properties follow from the definitions: | ||
| \[ | \[ | ||
| - | S \bullet r = ran(\Delta_S \circ r) | + | (S \bullet r_1) \bullet r_2 = S \bullet (r_1 \circ r_2) |
| \] | \] | ||
| \[ | \[ | ||
| - | (S \bullet r_1) \bullet r_2 = S \bullet (r_1 \circ r_2) | + | S \bullet r = ran(\Delta_S \circ r) |
| \] | \] | ||
| Line 307: | Line 311: | ||
| * [[:Gallier Logic Book]], Chapter 2 | * [[:Gallier Logic Book]], Chapter 2 | ||
| + | * [[sav08:discrete_mathematics_by_rosen|Discrete Mathematics by Rosen]] | ||