Subsets
Subset
A set is a subset of a set if every element of $B$ is also an element of $A$. Notation is $\boxed{B \subseteq A}$.
Link to original
Venn diagram of
For example:
We always have, for every set : and
Proper subset
is a proper subset of , , if $B$ is a subset of $A$ and there is some element in $A$ that is not in $B$. Essentially, $B \subset A$ if $B \subseteq A$ but $B \neq A$.
Link to original
title: Example 1
Let $A = \{ x | x \text{ is a prime number and } 42 \leq x \leq 51 \}$.
Let $B = \{ x | x = 4k + 3 \text{ and } k \in \mathbb N \}$.
**Show that $A \subseteq B$.**
We need to show that every element in $A$ is also in $B$.
Prove that $\forall x(x \in A \rightarrow x \in B)$
Take an **arbitrary** $x \in A$, then $x$ is a prime number and $42 \leq x \leq 51$,
so we either have $x = 43$ or $x = 47$.
- We can have $43 = 4 \times 10 + 3$, so $k = 10$ shows that $43 \in B$.
- We can have $47 = 4 \times 11 + 3$, so $k = 11$ shows that $47 \in B$.
$\therefore A \subseteq B$title: Example 2
Using $A$ and $B$ from above.
**Show that $A \subset B$.**
We know that $A \subseteq B$, so we just need to find an element $x \in B$ that $x \notin A$.
For example, $x = 3$:
- As $0 \in \mathbb N$ and $3 = 4 \times 0 + 3$, we have $3 \in B$.
- Although $42 \nleq 3$, so we have $3 \notin A$.
$\therefore A \subset B$title: Example 3
Let $A = \{ 3k + 1 | k \in \mathbb N \}$.
Let $B = \{ 4k + 1 | k \in \mathbb N \}$.
**Show that $A \nsubseteq B$.** ($A$ is not a subset of $B$)
Prove that $\neg \forall x (x \in A \rightarrow x \in B)$
We need to find a counterxample: an element $x \in A$ such that $x \notin B$.
For example, $x = 4$:
- $4 = 3 \times 1 + 1$ so $k = 1$ shows $4 \in A$.
- We need to show that $4 \notin B$, that is, there is no $k \in \mathbb N$ such that $4 = 4k + 1$.
If $k = 0$, then $4k + 1 = 4 \times 0 + 1 = 1 \neq 4$.
If $k \geq 1$, then $4k + 1 \geq 4 \times 1 + 1 = 5 \ge 4$.
So it is not possible to fina a $k \in \mathbb N$ such that $4 = 4k + 1$, and so $4 \notin B$.
$\therefore A \nsubseteq B$