# Exercise on Relations

Let S and S‘ be the following subsets of the plane: $S = \{(x,y) | y = x+1, 0 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: Reflexivity$x-x \in \mathbb{Z}, \forall x \in \mathbb{R}$

Symmetry$z \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.

# Indexed Sets Excercise

Let $\{A_\alpha\}_{\alpha \in I}$, and $\{B_\alpha\}_{\alpha \in I}$ be two indexed families of subsets of a set $S$. Prove: $\cup_{\alpha \in I}(A_\alpha \cup B_\alpha)= (\cup_{\alpha \in I}A_\alpha) \cup (\cup_{\alpha \in I} B_\alpha)$

$\forall_{x \in \cup_{\alpha \in I}(A_\alpha \cup B_\alpha)}(x \in A_\alpha or x \in B_\alpha)$. This $\Rightarrow$ that $x \in \cup_{\alpha \in I}A_\alpha$ or $x \in \cup_{\alpha \in I}B_\alpha \Rightarrow x \in (\cup_{\alpha \in I}A_\alpha) \cup (\cup_{\alpha \in I}B_{\alpha}) \Rightarrow \cup_{\alpha \in I}(A_\alpha \cup B_\alpha) \subset (\cup_{\alpha \in I}A\alpha) \cup (\cup_{\alpha \in I}B_\alpha).$

$\forall_{x \in (\cup_{\alpha \in I}A_\alpha) \cup (\cup_{\alpha \in I}B_\alpha)}(x \in \cup_{\alpha \in I}A_\alpha$ or $x \in \cup_{\alpha \in I}B_\alpha) \Rightarrow x \in \cup_{\alpha \in I}(A_{\alpha} \cup B_\alpha) \Rightarrow (\cup_{\alpha \in I}A_\alpha) \cup (\cup_{\alpha \in I}B_\alpha) \subset \cup_{\alpha \in I}(A_\alpha \cup B_\alpha) \therefore (\cup_{\alpha \in I} A_\alpha) \cup (\cup_{\alpha \in I}B_\alpha) = \cup_{\alpha \in I}(A_\alpha \cup B_\alpha )$.

# Compliments Proof 4

Let $X \subset Y \subset Z$. Prove that $Z - (Y - X) = X \cup (Z - Y)$.

We will begin by letting $A = Z - (Y - X)$ and letting $B = X \cup (Z - Y)$. If $x \in A \Rightarrow x \in Z, x \notin Y - X$, so $Z - (Y - X) = Z \cap C(Y - X)$, and $Z \cap C(Y - X) = Z \cap (C(Y) \cap C(X))$ and : $Z \cap C(Y \cap C(X)) = Z \cap (C(Y) \cup X) = (Z \cap C(Y)) \cup (Z \cap X)$ since $Z \cap C(Y) = Z - Y$ and $Z \cap X = X$, it follows that $Z \cap C(Y - X) = Z \cap C(Y \cap C(X))$

This came from http://ashleymills.com/.

# Compliments Proof 3

Let $X \subset Y \subset Z$. Prove that $C_{Y}(X) \subset C_{Z}(X)$.

In order for $C_{Y}(X) \subset C_{Z}(X), \forall_{x \in C_{Y}(X)}(x \in C_{Z}(X)) \Rightarrow \exists_{x \notin X} : x \in Y \cup Z$ because $X \subset Y \subset Z$. If we assume that $\forall_{x \in X}(x \in Y \cup Z)$ then $C_{Y}(X)$ and $C_{Z}(X)$ would both be $\emptyset$ and $\emptyset \not\subset \emptyset$. $\therefore \exists_{x \notin X} : x \in Y \cup Z$. Also $\not\exists_{x \in X}: x \notin Y \cup Z$ because then $X \not\subset Y$ which creates a contradiction with the axiom above. Since $\exists_{x \in Y \cup Z}: x \notin X$, $\forall_{x \in C_{Y}(X)}(x \in C_{Z}(X)) \Rightarrow C_{Y}(X) \subset C_{Z}(X)$.

# 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/.