Section 2.1 – Sets¶
definition: A set is a collection of objects. The objects are called elements or members.
- If $x$ is and element of set $S$ then we write $x \in S$.
Explicit Listing Notation¶
Listing all the elements in a set.
Examples
Implicit Listing Notation¶
List enough elements to make the pattern obvious.
Examples
It's debated whether or not the natural numbers contain $0$.
Set Builder Notation¶
Describe the elements by providing some characteristic of them.
Example
Suppose we want the prime numbers,
Translates to "All values of $x$ such that $x$ is prime".
Examples
Set Properties¶
definition: Sets $A$ and $B$ are equal ($A = B$) if they have the same elements. That is,
Note:¶
- Sets are unordered,
- Unless specified repeated elements are ignored,
Empty Set¶
definition: The empty set is the set with no elements written, $\emptyset$ or ${}$.
Example
The years that Vancouver has won the Stanley Cup $= \emptyset$.
Example
Example
Does $\emptyset = { \emptyset }$?
Solution
No. The second set has one element, the first set has no elements.
Example
How many elements does,
have?
Solution
Three,
- $\emptyset$
- ${ \emptyset, { { \emptyset } } }$
- ${ \emptyset }$
Subsets¶
definition: Let $A$ and $B$ be sets. $A$ is a subset of $B$ ($A \subseteq B$) if every element in $A$ is also in $B$ (but not necessarily the reverse). That is $x \in A \Rightarrow x \in B$.
- If $A$ is not a subset of $B$ we write $A \not\subseteq B$
Example
Let $A = { 1 ,2 , \emptyset }$ and $B = { 1,3,A }$. Which of the following are true?
- $\emptyset \in A$
- ${ 1 } \in A$
- $2 \in B$
- $A \in B$
- ${A} \in B$
- $A \subseteq B$
Solution
Only 1 and 4 are true. 2, 3, 5 and 6 are false.
Proper Subsets¶
definition: $A$ is a proper subset of $B$ if $A \subseteq B$ and $A \neq B$. It is written $A \subset B$.
Properties of Sets¶
- Any set $S$ has $S \subseteq S$.
- Any set $S$ has $\emptyset \subseteq S$.
- An $n$ element set has $2^n$ subsets.
Example
How many subsets does ${ a,b }$ have?
Solution
Four,
- ${ a }$
- ${ b }$
- ${ a, b }$
- $\emptyset$
The Transitive Property of Subsets¶
If $A$, $B$ and $C$ are sets such that,
then,
Proof¶
(RTP: Must show every element in $A$ is also in $C$)
Suppose that $A \subseteq B$ and $B \subseteq C$. Let $x \in A$. So then since $A \subseteq B$, $x \in B$. And so, since $B \subseteq C$, $x \in C$.
Proposition¶
Let $A$ and $B$ be sets. $A = B$ if and only if $A \subseteq B$ and $B \subseteq A$.
Must show:
- $A = B \Rightarrow A \subseteq B \text{ and } B \subseteq A$
- $A \subseteq B \text{ and } B \subseteq A \Rightarrow A = B$
($\Rightarrow$) Suppose $A = B$. Let $x \in A$, and so $x \in B$ since $A = B$.
Let $y \in B$, and so $y \in A$, since $A = B$
($\Leftarrow$) Suppose $A \subseteq B$ and $B \subseteq A$. Suppose then to the contrary $A \neq B$.
WLOG, $\exists x \in A \text{ such that } x \not\in B$.
Which is a contradiction since $A \subseteq B$.
Power Sets¶
defnition: The power set of a set $A$ (denoted $\mathcal{P}(A)$) is the set whose elements are the subsets of $A$.
Example
Let $A = { a, b, }$. What is the power set of $A$?
Subsets of $A$ are:
- ${ a }$
- ${ b }$
- ${ a, b }$
- $\emptyset$
Solution
Properties of Power Sets¶
Let $\mathcal{P}(A)$ be a power set of $A$.
- Every element of $\mathcal{P}(A)$ is a set.
- If $A$ has $n$ elements, $\mathcal{P}(A)$ has $2^n$ elements.
- $\emptyset \in \mathcal{P}(A)$
- $A \in \mathcal{P}(A)$
- $X \in \mathcal{P}(A) \iff X \subseteq A$
Proposition¶
Let $A$ and $B$ be sets.
($\Rightarrow$) Suppose $A \subseteq B$. Let $X \in \mathcal{P}(A)$. Then $X \subseteq A \subseteq B$.
($\Leftarrow$) Suppose $\mathcal{P}(A) \subseteq \mathcal{P}(B)$. Recall $A \subseteq \mathcal{P}(A) \subseteq \mathcal{P}(B)$.