10 - Proofs in set theory

Proving Set Membership

How to prove $x$ is in some set $A$ .

If the set is described using set builder notation, we have to prove a number meets all the conditions to be in the set.
For example:
$Screen Shot 2023-09-26 at 10.58.34 AM.png$

It should be within the stated domain (for example, $x \in N$ ).

Proving Inclusion of Sets

$Screen Shot 2023-09-26 at 11.13.32 AM.png$

Proving Equality

$\forall x, x \in A \Leftrightarrow x \in B .$
$Screen Shot 2023-09-26 at 11.20.52 AM.png$

Laws of sets

$Screen Shot 2023-09-26 at 11.21.26 AM.png$

In class practice

We work directly. Let $A = {x \in Z : 4 | x}$ and $B = {x \in Z : 2 | x}$ . It holds that $A \subseteq B$ . Assume $x \in A$ . Thus $x = 4 k$ for some $k \in Z$ . Hence $x = 2 (2 k)$ . Thus $2 ∣ x$ . Thus $x \in B$ . $◻$

HW 10

Ben Finch

E 10.1
a) Yes, 3 is one of the elements listed in the set.
b) No $π$ is not one of the elements listed in the set.
c) Yes, $π$ is a real number.
d) Yes, $\frac{2}{3}$ is a real number and $\frac{2}{3} < 1$ .
e) No, $\frac{2}{3} \notin Z$ .

E 10.2
Proof: Assume $(x, y) \in A$ . Thus $(x, y) \in Z$ x $Z$ and $4 ∣ x - y$ . Hence $x - y$ = $4 n$ for some $n \in Z$ . There are two cases:

Case 1. Suppose $x$ is even. Thus $x = 2 m$ for some $m \in Z$ . We find

\begin{aligned} y & = x - 4 n \\ = 2 m - 4 n \\ = 2 (m - 2 n) \end{aligned}

Hence, $y$ is also an even integer.

Case 2. Suppose $x$ is odd. Thus $x = 2 k + 1$ for some $k \in Z$ . We find

\begin{aligned} y & = x - 4 n \\ = 2 k + 1 - 4 n \\ = 2 (k - 2 n) + 1 \end{aligned}

Hence, $y$ is also an odd integer.

In all cases $x$ and $y$ share the same parity. Thus $(x, y)$ satisfy all conditions to be part of set $B$ . Hence, $A \subseteq B$ . $◻$

E 10.3
Proposition:
Let X be the set of integers which are congruent to −1 modulo 6 and let Y be the set of integers which are congruent to 2 modulo 3. Prove X ⊆ Y.

Proof:
We work directly. Assume $a \in X$ . Thus $6 | (a - (- 1))$ and $a + 1 = 6 k$ for some $k \in Z$ . Now consider some $b \in Y$ . Thus $3 ∣ (b - 2)$ and $b = 3 m + 2$ for some $m \in Z$ . We find

\begin{aligned} a & = 6 k - 1 \\ = 3 (2 k) - 1 \\ = 3 (2 k) - 3 + 2 \\ = 3 (2 k - 1) + 2 \end{aligned}

The above expression confirms that $a$ can be written in the form $3 m + 2$ where $m \in Z$ , which is the definition of the set $Y$ . Therefore, $a \in Y$ . Thus, we can conclude that for all $a \in X$ , $a \in Y$ , and therefore $X \subseteq Y$ . $◻$

E 10.4
(a) Let $x \in \overset{―}{A \cap B}$ . This means that $x \notin A \cap B$ . Hence, $x \notin A$ and $x \notin B$ , which is equivalent to $x \in \overset{―}{A}$ or $x \in \overset{―}{B}$ . So, $x \in \overset{―}{A} \cup \overset{―}{B}$ .

Therefore, $\overset{―}{A \cap B} \subseteq \overset{―}{A} \cup \overset{―}{B}$ . $◻$

(b) Proof that $\overset{―}{A} \cup \overset{―}{B} \subseteq \overset{―}{A \cap B}$ :

Let $x \in \overset{―}{A} \cup \overset{―}{B}$ . This means that $x \in \overset{―}{A}$ or $x \in \overset{―}{B}$ , which is equivalent to $x \notin A$ or $x \notin B$ . Hence, $x \notin A \cap B$ and therefore, $x \in \overset{―}{A \cap B}$ .

Therefore, $\overset{―}{A} \cup \overset{―}{B} \subseteq \overset{―}{A \cap B}$ . $◻$

(c) We have proved that $\overset{―}{A \cap B} = \overset{―}{A} \cup \overset{―}{B}$ since they are subsets of each other.

E 10.5

Let $n \in X - (X - Y)$ . We want to prove that $n \in X \cap Y$ .

We have: $n \in X - (X - Y)$ , which means that $n \in X$ and $n \notin (X - Y)$ . Thus $n \notin X$ or $n \in Y$ . Since we've already established that $n \in X$ , the latter must be true: $x \in Y$ .

Therefore, since $x \in X$ and $x \in Y$ , we have $x \in X \cap Y$ . $◻$

E 10.6

Assume $a \in X \cup \emptyset$ .

This means that $a \in X$ or $a \in \emptyset$ . However, the latter is not possible since the empty set $\emptyset$ has no elements.

Therefore, $a \in X$ must be true. Hence, this implies that $X \cup \emptyset = X$ . $◻$

E 10.7
Let $n \in Z$ .

Let $x \in {x \in Z : n | x}$ . This implies $n | x$ . By definition, there exists an integer $k$ such that $x = n k$ . This is equivalent to $x \equiv 0 (\mod n)$ . Thus ${x \in Z : n | x} \subseteq {x \in Z : x \equiv 0 (\mod n)}$ .

Let $x \in {x \in Z : x \equiv 0 (\mod n)}$ . This implies $x \equiv 0 (\mod n)$ . By definition, $x = n k$ for some integer $k$ , which means $n | x$ . Thus ${x \in Z : x \equiv 0 (\mod n)} \subseteq {x \in Z : n | x}$ .

Therefore, ${x \in Z : n | x} = {x \in Z : x \equiv 0 (\mod n)}$ .

E 10.8
Prove that $A - (B \cap C) \leq (A - B) \cup (A - C)$
Proof: Let $A, B, C$ be sets.

Let $x \in A - (B \cap C)$ . Thus $x \in A$ and $x \notin B \cap C$ . Hence $x \notin B$ and $x \notin C$ . There are two cases:

Case 1: $x \in B$ . Then $x \notin C$ . Then $x \in (A - C)$ , so $x \in (A - B) \cup (A - C)$

Case 2: $x \notin B$ Then $x \in A - B$ , so $x \in (A - B) \cup (A - C)$ . $◻$

E 10.9

Proof:

(1) $⋃_{n \in N} S_{n} \subseteq Z$

By definition of the sets $S_{n}$ , every element in each set $S_{n}$ is an integer. Hence, every element in the union of all $S_{n}$ is also an integer, proving that $⋃_{n \in N} S_{n} \subseteq Z$ .

(2) $Z \subseteq ⋃_{n \in N} S_{n}$

We have two cases:

If $x$ is non-negative, then $x \in S_{x}$ since $x \leq x$ . Therefore, $x$ belongs to $⋃_{n \in N} S_{n}$ .
If $x$ is negative, then $x \in S_{n}$ for any $n \in N$ since $n \geq - x$ . Therefore, $x$ belongs to $⋃_{n \in N} S_{n}$ .

Therefore, we have shown that $Z \subseteq ⋃_{n \in N} S_{n}$ .

Thus we have $⋃_{n \in N} S_{n} = Z$ . $◻$