Exercise on Relations

Let S and S‘ be the following subsets of the plane: S = \{(x,y) | y = x+1, 0<x<2\} and S'= \{(x,y) | y-x \in \mathbb{Z} \}

a) Show that S’ is an equivalence relation on the real line and that S \subset S'.

Proof: Reflexivityx-x \in \mathbb{Z}, \forall x \in \mathbb{R}

             Symmetryz \in \mathbb{Z} \Rightarrow -z \in \mathbb{Z}

             Transitivity- If x~y, y~z then z-y=(z-x)-(x-y) and thus z-y is the difference of two integers which implies that z-y is itself an integer.

To show that S \subset S' we note that y=x+1 \Rightarrow y-x=1 which \in \mathbb{Z}

b) Show that given any collection of equivalence relations on a set A, their intersection is an equivalence relation in A.

Proof: Let \{R_\alpha\}_\alpha\in A be a nonempty class of equivalence relations and let \Omega = \cap_{\alpha \in A}R_\alpha

Reflexivity- If (x,y) \in R_\alpha, \forall_\alpha \in A then (x,y) \in \Omega \Rightarrow (y,x) \in R_\alpha, \forall_\alpha \in a \Rightarrow (y,x) \in \Omega .

Symmetry(x,x) \in R_\alpha, \forall_\alpha \in A \Rightarrow (x,x) \in \Omega .

Transitivity– If (x,y), (y,z) \in R_\alpha, \forall_\alpha \in A then (x,y), (y,z) \in \Omega \Rightarrow (x,z) \in R_\alpha, \forall_{\alpha \in A} \Rightarrow (x,z) \in \Omega \therefore the intersection is an equivalence relation on A.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s