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

Compliments Proof 2

Let A \subset S and B \subset S . Prove that A \subset C(B) if and only if B \subset C(A) .

Let’s begin by letting A \subset C(B) and assume that B \not\subset C(A) . From this assumption it follows that \exists_{x \in B} : x \notin C(A) \Rightarrow \exists_{x \notin C(A)} : x \in B . This means that \exists_{x \in A} : x \notin C(B) \Rightarrow A \not\subset C(B) . This creates a contradiction with the above statement and therefore B \subset C(A) . This proves the second half of the statement, and now we must prove the first half of the statement.

We will now let B \subset C(A) and assume that A \not\subset C(B) . From this assumption it follows that \exists_{x \in A} : x \notin C(B) \Rightarrow \exists_{x \notin C(B)} : x \in A . This means that \exists_{x \in B} : x \notin C(A) \Rightarrow B \not\subset C(A) creating a contradiction with the above statement and therefore A \subset C(B) .

Compliments Proof

Let A \subset S , B \subset S . Prove that A \subset B if and only if C(B) \subset C(A)

Let C(B) \subset C(A) and assume that A \not\subset B . From this assumption it follows that \exists_{x\in A} : x\notin B , which means that \exists_{x\notin B} : x\in A , which can also be stated as \exists_{x\in C(B)} : x \notin C(A) \therefore C(B) \not\subset C(A) which contradicts with the above assumption and therefore A \subset B . Now if we let A \subset B and assume that C(A) \not\subset C(B) than it follows that \exists_{x\in C(A)} : x \notin C(B) \Rightarrow \exists _{x\in A} : x \notin B . This means that A \notin B which contradicts the above statement and therefore C(A) \subset C(B) . This came from  http://ashleymills.com/.