1.2 - Set Theory Review

1.2.1

a

Theorem

$\sqrt{3}$ is irrational.

\begin{proof}
Assume for contradiction that $\sqrt{3}$ is rational, so then:

\frac{p}{q} = \sqrt{3}

for some $p, q \in Z$ where $q \neq 0$ and $p, q$ don't share any common factors. Squaring both sides gives that:

p^{2} = 3 q^{2}

so $3 | p^{2}$ , or $p^{2}$ has a factor of $3$ . Notice that because of that:

\frac{p^{2}}{3} = \frac{p}{3} \cdot p \in Z

so then since $p \in Z$ then clearly $3 | p$ so then set $p = 3 k$ for some $k \in Z$ so then:

(3 k)^{2} = 3 q^{2} \Rightarrow 9 k^{2} = q^{2} \Rightarrow q^{2} = 3 p^{2}

so then $q^{2}$ is divisible by $3$ , and by the same argument $3 | q$ which contradicts $p, q$ not sharing any factors.
\end{proof}
Note that the argument would follow similarly for $\sqrt{6}$ , except that when we breakup $p^{2} / 6$ notice that 6 isn't prime so then we'll get:

\frac{p^{2}}{6} = \frac{p}{2} \cdot \frac{p}{3}

so we show that $p$ is either divisible by 2 or by 3 and continue the argument to show that $q$ shares the same factor.

b

The proof for showing $\sqrt{4}$ would work in the same way it did for 1.2 - Set Theory Review#1.2.1#a since we'd get to:

p^{2} = 4 q^{2} = 2 (2 q^{2})

so then $p$ is even, so then $p = 2 k$ :

(2 k)^{2} = 2 (2 q^{2}) \Rightarrow 4 k^{2} = 4 q^{2} \Rightarrow k^{2} = q^{2}

but this couldn't lead to a contradiction as $k = | q |$ so then $p = 2 | q |$ so then:

\frac{p}{q} = \frac{2 | q |}{q} = \pm 2

which doesn't give a contradiction.

1.2.3

a

Postulate

If $A_{1} \supseteq \dots$ are all sets with an infinite number of elements, then $⋂_{n = 1}^{\infty} A_{n}$ is infinite as well.

This is a false statement. Consider the superset $(0, 1) \subseteq R$ , and have $A_{i}$ defined by:

A_{i} = (0, \frac{1}{2^{i}})

We can see that $A_{i + 1} = A_{i} \cap (\frac{1}{2^{i + 1}}, 1)$ so then by that definition then $A_{i + 1} \supseteq A_{i}$ as required. But all of these sets are uncountably infinite, but notice that $⋂_{n = 1}^{\infty} A_{n} = \emptyset$ . This is because if there were some $x \in ⋂_{n = 1}^{\infty} A_{n}$ then I can construct a new set $A^{'}$ where:

A^{'} = (0, \frac{x}{2})

where clearly $A^{'}$ is in our sequence of sets, but $x \notin A^{'}$ by definition. But this larger set is finite in length (length 0) which is a counter example to the postulate at hand.

b

Postulate

If $A_{1} \supseteq \dots$ are all sets with finite number of elements, then $⋂_{n = 1}^{\infty} A_{n}$ is finite as well.

This is a true statement. Namely, we know that if $A_{1} \supseteq A_{2}$ then $A_{1} \cap A_{2} = A_{1}$ which is finite, and in general then $A_{1} \supseteq \dots = A_{1}$ so then clearly $⋂_{n = 1}^{\infty} A_{n} = A_{1}$ is finite.

c

Postulate

$A \cap (B \cup C) = (A \cap B) \cup C$

This is a false statement. Let $A = {1, 2}, B = {2, 3}$ and $C = {3, 1}$ . Notice that:

A \cap (B \cup C) = {1, 2} \cap {1, 2, 3} = {1, 2}

but:

(A \cap B) \cup C = {2} \cup {3, 1} = {1, 2, 3}

and these don't equal.

d

Postulate

$A \cap (B \cap C) = (A \cap B) \cap C$

This is a true statement. For $\supseteq$ let $x \in (A \cap B) \cap C$ so then $x \in C$ and $x \in A \cap B$ so $x \in A$ and $x \in B$ . Then $x \in B \cap C$ and thus $x \in A \cap (B \cap C)$ . The other direction is proved similarly WLOG.

e

Postulate

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

This is a true statement.

$\subseteq$ . Let $x \in A \cap (B \cup C)$ . Then $x \in A$ and $x \in B \cup C$ . If $x \in B$ then $x \in A \cap B$ so then $x \in (A \cap B) \cup (A \cap C)$ . Then if $x \notin B$ then $x \in C$ by requirement so then similarly $x \in A \cap C$ and $x$ is in the RHS set. Thus we get $\subseteq$ .

$\supseteq$ . Let $x$ be in the RHS set. Suppose $x \in A \cap B$ so then $x \in A$ and $x \in B$ . Then $x \in B \cup C$ so then $x \in A \cap (B \cup C)$ . WLOG the same applies for $C$ .

1.2.5 (De Morgan's Laws)

a

Theorem

$(A \cap B)^{c} \subseteq A^{c} \cup B^{c}$

\begin{proof}
Let $x \in (A \cap B)^{c}$ . Then $x \notin A \cap B$ . For one case if $x \in A$ then we must have that $x \notin B$ so then $x \in B^{c}$ so then $x \in A^{c} \cup B^{c}$ . If instead $x \notin A$ then $x \in A^{c}$ and we get the same result.
\end{proof}

b

Theorem

$(A \cap B)^{c} \supseteq A^{c} \cup B^{c}$

\begin{proof}
Let $x \in A^{c} \cup B^{c}$ . If $x \in A^{c}$ then $x \notin A$ , so clearly $x \notin A \cap B$ . Thus, then $x \in (A \cap B)^{c}$ . WLOG, the same applies if $x \in B^{c}$ .
\end{proof}

c

Theorem

$(A \cup B)^{c} = A^{c} \cap B^{c}$

\begin{proof}
First $\subseteq$ . Let $x \in (A \cup B)^{c}$ . Then $x \notin A \cup B$ . Notice if $x \in A$ then that's a contradiction and same for $x \in B$ , so then $x \notin A$ and $x \notin B$ so then $x \in A^{c} \cap B^{c}$ .

Then $\supseteq$ . Let $x \in A^{c} \cap B^{c}$ , thus $x \in A^{c}$ and $x \in B^{c}$ . Then $x \notin A$ and $x \notin B$ . Notice by similar reasoning prior that $x \notin A \cup B$ so $x \in (A \cup B)^{c}$ .
\end{proof}

1.2.7

Given function $f$ and a subset of its domain $A$ , we denote $f (A) = {f (x) : x \in A}$ as the range of $f$ over set $A$ .

a

Given $f (x) = x^{2}$ and $A = [0, 2]$ and $B = [1, 4]$ then we know that:

f (A) = [0, 4], f (B) = [1, 16]

so then:

f (A \cap B) = f ([1, 2]) = [1, 4]

while:

f (A) \cap f (B) = [1, 4]

so in this case $f (A \cap B) = f (A) \cap f (B)$ . Similarly

f (A \cup B) = f ([0, 4]) = [0, 16]

while:

f (A) \cup f (B) = [0, 16]

so $f (A) \cup f (B) = f (A \cup B)$ in this case.

b

In general we don't have $f (A \cap B) = f (A) \cap f (B)$ . For instance, if $A = [- 1, 0]$ and $B = [0, 2]$ then:

f (A) = [0, 1], f (B) = [0, 4]

f (A \cap B) = f ([0]) = {0}

f (A) \cap f (B) = [0, 1]

here clearly $f (A \cap B) \neq f (A) \cap f (B)$ .

c

Theorem

For any $g : R \to R$ then $g (A \cap B) \subseteq g (A) \cap g (B)$ .

\begin{proof}
Let $y \in g (A \cap B)$ be arbitrary. Then there is some $x \in A \cap B$ such that $f (x) = y$ by definition. Clearly $x \in A$ and $x \in B$ . Thus, since $f (x) = y$ then $y \in f (A)$ since $x \in A$ and likewise $y \in f (B)$ . Thus, $y \in g (A) \cap g (B)$ , completing the proof.
\end{proof}

1.2.9

Given some $f : D \to R$ and a subset $B \subseteq R$ , denote $f^{- 1}$ as the preimage, namely:

f^{- 1} (B) = {x \in D : f (x) \in B}

a

Let $f (x) = x^{2}$ . If $A$ is the closed interval $[0, 4]$ and $B$ is the closed interval $[- 1, 1]$ then:

f^{- 1} (A) = [- 2, 2], f^{- 1} (B) = [- 1, 1]

Notice that:

f^{- 1} (A \cap B) = f^{- 1} ([0, 1]) = [- 1, 1]

while:

f^{- 1} (A) \cap f^{- 1} (B) = [- 1, 1]

so in this case $f^{- 1} (A \cap B) = f^{- 1} (A) \cap f^{- 1} (B)$ . Similarly:

f^{- 1} (A \cup B) = f^{- 1} ([- 1, 4]) = [- 2, 2]

while:

f^{- 1} (A) \cup f^{- 1} (B) = [- 2, 2]

so then $f^{- 1} (A \cup B) = f^{- 1} (A) \cup f^{- 1} (B)$ in this case.

b

Theorem

For any $g : R \to R$ then:

$g^{- 1} (A \cap B) = g^{- 1} (A) \cap g^{- 1} (B)$
$g^{- 1} (A \cup B) = g^{- 1} (A) \cup g^{- 1} (B)$
for all sets $A, B \subseteq R$ .

\begin{proof}
We prove the former.

$(\subseteq)$ . Let $x \in g^{- 1} (A \cap B)$ . Then there is some $f (x) \in A \cap B$ by definition. Then $f (x) \in A$ and $f (x) \in B$ separately. Thus then $x \in g^{- 1} (A)$ and similar for $B$ , so then $x \in g^{- 1} (A) \cap g^{- 1} (B)$ .

$(\supseteq)$ . Let $x \in g^{- 1} (A) \cap g^{- 1} (B)$ . Then $x \in g^{- 1} (A)$ and similar for $B$ . Then there is some $f (x) \in A$ and likewise $f (x) \in B$ . Thus $f (x) \in A \cap B$ . Thus, $x \in g^{- 1} (A \cap B)$ .

For the latter:

$(\subseteq)$ . Let $x \in g^{- 1} (A \cup B)$ . Then there's some $f (x) \in A \cup B$ . If $f (x) \in A$ then $x \in g^{- 1} (A)$ so then $x \in g^{- 1} (A) \cup g^{- 1} (B)$ . WLOG, the same can be sead if $f (x) \in B$ instead (ie: $f (x) \notin A$ ).

$(\supseteq)$ . Let $x \in g^{- 1} (A) \cup g^{- 1} (B)$ . If $x \in g^{- 1} (A)$ then $f (x) \in A$ so then $f (x) \in A \cup B$ so then $x \in g^{- 1} (A \cup B)$ . WLOG, the same works if $x \in g^{- 1} (B)$ instead.
\end{proof}

1.2.11

We'll negate certain statements into their opposites:

a

The opposite of "for all reals where $a < b$ then there is some $n \in N$ where $a + 1 / n < b$ " is:

"there are reals $a < b$ where, for any $n \in N$ , we have it that $a + 1 / n \geq b$ ".

Here the original claim is true, as we can always choose some lowest fraction that's less than some $ε > 0$ .

b

The opposite of "there is a real $x > 0$ such that $x < 1 / n$ for all $n \in N$ " is:

" for all reals $x > 0$ there is some $n \in N$ such that $x \geq 1 / n$ "

Here the negation is true for similar reasons to 1.2 - Set Theory Review#1.2.11#a.

c

The opposite of "between every two distinct real numbers is a rational number" is:

"there are two real numbers such that there exist no rational numbers between them"

I'm pretty sure that the negation is true since $Q$ is not complete.

1.2.13

We'll be allowed to use De Morgan's Laws here from 1.2 - Set Theory Review#1.2.5 (De Morgan's Laws).

a

Theorem

For any $n \in N$ :

(A_{1} \cup A_{2} \cup \dots \cup A_{n})^{C} = A_{1}^{c} \cap \dots \cap A_{n}^{c}

\begin{proof}
We prove this via induction. The base case for $A_{1}, A_{2}$ is just the simpler De Morgan's Law from 1.2 - Set Theory Review#1.2.5 (De Morgan's Laws)#c. Let $k \in N$ be arbitrary, and suppose the theorem holds for $n \leq k$ . Consider the $k + 1$ case, then:

(A_{1} \cup \dots \cup A_{k} \cup A_{k + 1})^{c} = ([A_{1} \cup \dots \cup A_{k}] \cup A_{k + 1})^{c}

Since the LHS set is composed of $n = k \leq k$ sets and the RHS set is just one set, we can use our Inductive Hypothesis:

= [A_{1} \cup \dots \cup A_{k}]^{c} \cap A_{k + 1}^{c} = A_{1}^{c} \cap \dots \cap A_{k}^{c} \cap A_{k + 1}^{c}

completing the proof by induction.
\end{proof}

b

We'll show that induction can't always be used. We'll show that $⋂_{i = 1}^{n} B_{i} \neq \emptyset$ for some $n \in N$ but $⋂_{i = 1}^{\infty} B_{i} = \emptyset$ . Let $B_{i} = (0, \frac{1}{2^{i}})$ . Here any finite intersection allows us to find some $x$ in that intersection, but intersecting all infinitely many sets, as we saw in 1.2 - Set Theory Review#1.2.3#a that we get the empty set.

c

Theorem

${(⋃_{i = 1}^{\infty} A_{i})}^{c} = ⋂_{i = 1}^{\infty} A_{i}^{C}$

\begin{proof}
We prove $(\subseteq)$ first. Let $x$ be an element of the LHS. Then $x \notin ⋃_{i = 1}^{\infty} A_{i}$ . That means that there isn't any set $A_{i}$ where $x \in A_{i}$ . Hence, for all sets $A_{i}$ then $x \notin A_{i}$ , so then $x \in A_{i}^{c}$ for all these sets. Hence, then $x \in ⋂_{i = 1}^{\infty} A_{i}^{c}$ as required.

Now for $(\supseteq)$ . Let $x$ be an element of the RHS. Then $x \in A_{i}^{c}$ for all $i$ . Hence, then $x \notin A_{i}$ for all $i$ . Then there doesn't exist any sets $A_{i}$ where $x \in A_{i}$ so then $x \notin ⋃_{i = 1}^{\infty} A_{i}$ . Hence, $x$ is in the LHS.
\end{proof}