Cardinality

Cardinality refers to how many elements are in a set.

\[ \left|\{1, 2, 3\}\right| = 3\\ \left|\{1, 2, 3, 4, 5, 6\}\right| = 6\\ \left|\{0, 5\}\right| = 2\\ \left|\emptyset\right| = 0\\ \left|\{\{1, 2, 3\}, 5, 6\}\right| = 3\\ \left|\mathbb{N}\right| = \infty \]

Power Sets

A power set is the set containing all subsets of a given set

\[ A = \{0, 1\}\\ \\ P(A) = \{S|S \subseteq A \}\\ \\ \begin{aligned} P(A) = \{&\\ &\emptyset,\\ &\{0\},\\ &\{1\},\\ &\{0, 1\},\\ \} \end{aligned} \]

Note that the power set can also be written as $2^A$ instead of $P(A)$ - Note the relation between the cardinality of the power set and powers of two.

For every set $A$

\[ \emptyset \in P(A)\\ A \in P(A)\\ \left|P(A)\right| = 2^\left|A\right| \]

Membership

Membership refers to whether or not an object belongs to a set/is a member of a set.

\[ A = \{ 1, 2, 3 \}\\ 1 \in A\\ 2 \in A\\ 3 \in A\\ 3 \textrm{ is an element of } A\\ \\ 4 \notin A\\ 4 \textrm{ is not an element of } A\\ \\ \\ \{ x, y \} \in \{b, \{x, y\}, z, 13\}\\ x \notin \{b, \{x, y\}, z, 13\}\\ \\ \\ \emptyset \in \{\emptyset, 1, 2, 3\}\\ \emptyset \notin \{1, 2, 3\}\\ \]

Subsets

A set is a subset of another if all of its elements are in that set.

\[ A = \{ 1, 2, 3 \}\\ B = \{ 1, 2, 3, 4, 5 \}\\ \\ A \subseteq B\\ \textrm{if } x \in A \textrm{, then } x \in B \textrm{ for any object } x \]
The empty set ($\emptyset$) is a subset of any set

Supersets

Supersets are the opposite of subsets

\[ A = \{ 1, 2, 3 \}\\ B = \{ 1, 2, 3, 4, 5 \}\\ \\ B \supseteq A\\ \textrm{if } x \in A \textrm{, then } x \in B \textrm{ for any object } x \]

Subset/Superset Maths

Example

\[ A = \{ 1, 5, 7 \}\\ B = \{ y|y = 2n - 1 \textrm{ for some } n \in \mathbb{Z} \}\\ \\ 1 = 2(1) - 1\\\therefore 1 \in B\\\\ 5 = 2(3) - 1\\\therefore 5 \in B\\\\ 7 = 2(4) - 1\\\therefore 7 \in B \]

All elements of $A$ are in $B$, $A \subseteq B$

Example

\[ A = \{ 4, 7, 12, 16 \}\\ B = \{ y|y = 3n + 1 \textrm{ for some } n \in \mathbb{Z} \}\\ \\ 12 = 3n + 1\\ 12 - 1 = 3n\\ 11 = 3n\\\\ \frac{11}{3} = n\\ n \notin \mathbb{Z}\\ \therefore 12 \notin B \]

Not all elements of $A$ are in $B$, $A \nsubseteq B$

Equality

How can we check that two sets contain the same elements?

  • Check that $A \subseteq B$
  • Check that $B \subseteq A$
  • If they are both subsets of each other then they must be equal
  • (Because every element of $A$ must then be in $B$ and vice-versa…)

Example

\[ A = \{x|x=2n+1 \textrm{ for some } n \in \mathbb{Z}\}\\ B = \{y|y=2m-3 \textrm{ for some } m \in \mathbb{Z}\}\\ \\ A \subseteq B\\ \textrm{If } x \in A \textrm{ then } x = 2n+1 \textrm{ for some } n \in \mathbb{Z}\\ \\ x = 2n+1\\ x = 2n+4-4+1\\ x = (2n+4) + (-4+1)\\ x = (2n+4) + -3\\ x = 2(n+2) -3\\ x = 2m - 3 \textrm{ where } m=n+2 \textrm{ for some } n \in \mathbb{Z}\\ \textrm{so } m \in \mathbb{Z} \textrm{ and hence, } x \in B \\ B \subseteq A\\ \textrm{If } y \in B \textrm{ then } y = 2m-3 \textrm{ for some } m \in \mathbb{Z}\\ \\ y = 2m-3\\ y = 2m+(-4+4)-3\\ y = (2m-4)+(4-3)\\ y = 2(m-2)+1\\ y = 2n+1 \textrm{ where } n=m-2 \textrm{ for some } m \in \mathbb{Z}\\ \textrm{so } n \in \mathbb{Z} \textrm{ and hence, } y \in A \]