Discrete-math 6

\begin{matrix} Denotion: (a, b) \\ (a, b) \neq (b, a) \\ (a, b) = {{a, b (elements of the pair)}, a (first item in the pair)} \\ (a, b) = (c, d) ⟺ (a = c \land b = d) \end{matrix}

\begin{matrix} A \times B = {(a, b) ∣ a \in A, b \in B} \end{matrix}

In general A \times B \neq B \times A

\begin{matrix} A = {a, b}, B = {1, 2} \\ A \times B = {(a, 1), (a, 2), (b, 1), (b, 2)} \\ B \times A = {(1, a), (1, b), (2, a), (2, b)} \end{matrix}

A \times \emptyset = \emptyset \times A = \emptyset

A \times (B \cup C) = (A \times B) \cup (A \times C)

(A \times B) \cup (C \times D) \subseteq (A \cup C) \times (B \cup D)

A \times B = B \times A ⟺ A = B

\begin{matrix} Prove or disprove: A \times (B \cup C) = (A \times B) \cup (A \times C) \\ (a, b) \in (A \times (B \cup C)) ⟺ a \in A \land (b \in B \lor b \in C) ⟺ \\ ⟺ (a \in A \land b \in B) \lor (a \in A \lor b \in C) ⟺ (a, b) \in ((A \times B) \cup (A \times C)) \\ (a, b) \in (A \times (B \cup C)) ⟺ (a, b) \in ((A \times B) \cup (A \times C)) \end{matrix}

\begin{matrix} Prove or disprove: (A \times B) \cup (C \times D) \subseteq (A \cup C) \times (B \cup D) \\ (a, b) \in ((A \times B) \cup (C \times D)) ⟺ (a \in A \land b \in B) \lor (a \in C \land b \in D) ⟺ \\ (a \in A \lor (a \in C \land b \in D)) \land (b \in B \lor (a \in C \land b \in D)) ⟺ \\ ⟺ (a \in (A \cup C) \land (a, b) \in (A \times D)) \land ((a, b) \in (C \times B) \land b \in (B \cup D)) ⟺ \\ ⟺ (a, b) \in ((A \cup C) \times (B \cup D)) \land (a, b) \in (A \times D) \land (a, b) \in (C \times B) \\ ⟹ (a, b) \in ((A \cup C) \times (B \cup D)) \\ (a, b) \in ((A \times B) \cup (C \times D)) ⟹ (a, b) \in ((A \cup C) \times (B \cup D)) ⟺ \\ ⟺ ((A \times B) \cup (C \times D)) \subseteq ((A \cup C) \times (B \cup D)) \end{matrix}

R is a relation from A to B iff R \subseteq A \times B

Empty relation R_{\emptyset} = \emptyset is also a relation, between any sets!

Relation from A to A is called "Relation on A "

\forall a \in A : (a, a) \in R

\forall a, b \in A : (a, b) \in R ⟹ (b, a) \in R

\forall a, b, c \in A : ((a, b) \in R \land (b, c) \in R) ⟹ (a, c) \in R

\begin{matrix} R = {(a, b) ∣ a, b \in Z : a \leq b} \\ Reflexive? Yes : a \leq a \\ Symmetric? No : 3 \leq 5 \land 5 ≰ 3 \\ Transitive? Yes : a \leq b \land b \leq c ⟹ a \leq c \end{matrix}

\begin{matrix} R = {(a, b) ∣ a, b \in Z : a ∣ b} \\ Reflexive? \\ 0 ∤ 0 ⟹ Not reflexive \\ Symmetric? \\ 3 ∣ 9, 9 ∤ 3 ⟹ Not symmetric \\ Transitive? \\ a ∣ b, b ∣ c ⟹ \frac{b}{a} \in Z, \frac{c}{b} \in Z \\ \frac{b}{a} \cdot \frac{c}{b} = \frac{c}{a} \in Z ⟹ a ∣ c ⟹ Transitive \end{matrix}