Sets

Sets are one of the most fundamental structures in mathematics.
Set: an unordered collection of objects (with no duplicates allowed).
- Compare arrays you use in programming: they (1) have an order and (2) allow duplicates (you can put 17 into the same array several times).
The things in a set are called its elements or members.
- … and a set contains its elements.
We will write sets with curly braces. The set containing the first four natural numbers is: \[\{0,1,2,3\}\,.\]
- The symbol \(\in\) is “is an element of”.
- For example, we can write: \[2\in\{1,2,3\}\,,\\ 4\notin\{1,2,3\}\,,\\ \mbox{The set of one digit integers is }\{0,1,2,\ldots,9\}\,.\]
- And we can name sets just like any other value in mathematics: Let \(S\) be the set of students in this class and \(b\) be Barack Obama. Then \(S\) has about 55 elements, but \(b\notin S\).
Two sets are equal if the contain the same elements.
- More precisely, sets \(A\) and \(B\) are equal if and only if \(\forall x(x\in A \leftrightarrow x\in B)\).
- If that condition is true, we can write \(A=B\).
Remember that order doesn't matter and duplicates don't count.
- These sets are all equal: \[\begin{align*} \{7,8,9\} &= \{9,8,7\}\\ &= \{7,7,8,8,9,9\}\\ &= \{7,9,8,7,7,8\}\,.\end{align*} \]
- We only care about one thing: is a value it in the set or not?
- Maybe saying “no duplicates allowed” before was wrong. Maybe should have been “duplicates are allowed, but they don't count.”
Each set has a certain number of (distinct) elements.
- That is its cardinality.
- e.g. the set \(\{7,8,9\}\) has cardinality 3.
- Cardinality is written with vertical bars around the set like this: \[|\{7,8,9\}|=3\,,\\|S|\approx 55\,.\]
- We have to be a little careful: \[ |\{7,7,8,8,9,9\}| = 3\,\\ |\{\{1,2,3\}, \{4,5,6\}\}| = 2\,. \]
Sets can have an infinite number of elements.
- e.g. the set of integers, the set of real numbers.
Sets can contain others sets, or any other object we can define.
- Set of all sets of truth values: \(\{\{\},\{\mathrm{T}\},\{\mathrm{F}\},\{\mathrm{T},\mathrm{F}\}\}\).
- Set of things I feel like putting in this example: \(\{\{-1,1\}, \text{数学}, \pi, \text{the ace of spades}\}\).

Set Builder Notation

If sets are very simple, we can define them by just listing elements (maybe with a “…”).
- Set of positive integers less than 100: \(\{1,2,3,\ldots,99\}\).
- Set of positive integers: \(\{1,2,3,\ldots\}\).
- Set of powers of two: \(\{1,2,4,8,16,\ldots\}\)
For more complicated sets, that isn't going to work. e.g. set of rational numbers, set of primes, set of students in lecture today.
- There's not any (obvious) way to write those with the “…”.
Set builder notation is a way to describe the elements of a set with enough precision and flexibility to be useful.
- The set of positive integers less than 100: \(\{n\mid n\in\mathbf{Z}\text{ and }0<n<100\}\).
- Read that literally as “the set of all \(n\) for \(n\) an integer and \(0<n<100\).”
- The thing before the vertical bar: the values that go in the set.
- After the bar: where those values come from and conditions.
More examples:
- The set of prime numbers: \(\{n\mid n\in\mathbf{Z}, n>1, \text{the only divisors of }n\text{ are 1 and }n\}\).
- The set of rational numbers: \(\mathbf{Q} = \{m/n \mid m,n\in\mathbf{Z}\text{ and }n\ne 0\}\).
Compare list comprehensions in Haskell, Python, etc.

More Set Basics

Important sets:
- When the set of real numbers, rationals, integers, or natural numbers are typeset it's usually in bold: \(\mathbf{R}, \mathbf{Q}, \mathbf{Z}, \mathbf{N}\).
- It's hard to hand-write bold, so people write something more like \(\mathbb{R}, \mathbb{Q}, \mathbb{Z}, \mathbb{N}\).
- They mean the same thing either way: \[ \mathbf{R} = \text{the set of real numbers}\,,\\ \mathbf{Z} = \text{the integers} = \{\ldots,-2,-1,0,1,2,\ldots\}\,,\\ \mathbf{Q} = \text{the rational numbers} = \{m/n \mid m,n\in\mathbf{Z}\text{ and }n\ne 0\}\,,\\ \overline{\mathbf{Q}} = \text{the irrational numbers} = \{x \mid x\in\mathbf{R} \wedge x\notin\mathbf{Q}\}\,,\\ \mathbf{N} = \text{the natural numbers} = \{n\mid n\in\mathbf{Z}\text{ and }n\ge 0\}\,. \]
- Some also use \(\mathbf{Z^{+}}\), \(\mathbf{Q^{+}}\) etc. for the sets of integers/rationals greater than zero.
- The empty set is used often enough that it gets special notation, a slashed zero: \(\emptyset=\{\}\). \[ |\emptyset| = 0\,,\\ |\{\emptyset\}| = 1\,,\\ |\{\emptyset, \{\}\}| = 1\,,\\ |\{\emptyset, \{\emptyset\}\}| = 2\,. \]
We already have the “element of” symbol: \(5\in\mathbf{Z}\) and \(\sqrt{2}\notin\mathbf{Q}\).
When writing quantifiers, we can use sets to give the domain very easily.
- For example, \[ \forall x{\in}\mathbf{Z^{+}}(x+1\gt 0)\,,\\ \neg\forall x{\in}\mathbf{Z}(x+1\gt 0)\,,\\ \exists x{\in}\mathbf{R}(x^2 = 2)\,,\\ \neg\exists x{\in}\mathbf{Q}(x^2 = 2)\,. \]

Subsets

A subset of a set is a set that is entirely contained in another.
- We will write \(A\subseteq B\) for “\(A\) is a subset of \(B\)”.
- And formally define it as, \[A\subseteq B \equiv \forall x(x\in A \rightarrow x\in B)\,.\]
- In other words, every member of \(A\) is also in \(B\).
Theorem: For every set \(S\), we have \(\emptyset\subseteq S\).
Proof: We need to show that for any element \(x\) if \(x\in \emptyset\) then \(x\in S\).

Since the empty set has no elements, the premise of that implication is always false. We know that \(\mathrm{F}\rightarrow p\) is always true, so the theorem is valid.∎
Theorem: For every set \(S\), we have \(S\subseteq S\).
Proof: We need to show that for any element \(x\) if \(x\in S\) then \(x\in S\). By definition, if we pick an element of \(S\) (for the premise), then it is in \(S\) (for the conclusion).∎
[Aside: The book calls those a “vacuous proofs”. They're actually hard to write because there's so little to say.]
Theorem: A subset of any set has cardinality less than or equal to the set: if \(A\subseteq B\), then \(|A|\le|B|\).
Proof: [Vacuous proofs are boring, so I won't do another.]
Note: The symbol “\(\subseteq\)” looks a little like \(\le\), which makes sense: it is the set version since a set is a subset of itself, just like a number is less-than-or-equal-to itself.
A proper subset is a subset that is not identical. That is, \[\begin{align*} A\subset B &\equiv A\subseteq B \wedge A\ne B \\ &\equiv \forall x(x\in A \rightarrow x\in B) \wedge \exists x(x\notin A \wedge x\in B)\,. \end{align*}\]
- i.e. there is at least one element in \(B\) missing from \(A\).
- So, \(\subset\) and \(\lt\) are similar in the same way as \(\subseteq\) and \(\le\).
Of course, (non-empty) sets have other subsets besides \(\emptyset\) and themselves.
- e.g. For the set \(S=\{a,b,c\}\), \[ \emptyset\subseteq S\,,\\ \{a\}\subseteq S\,,\\ \{a,b\}\subseteq S\,,\\ S\subseteq S\,. \]
- … and a bunch of others.

Power Sets

It makes good sense to ask what are all of the subsets of a set? How many of them are there?
The power set of a set is the set of all if its subsets.
- Written \(P(S)\) (or in other books, sometimes \(\mathcal P(S)\) or \(\mathscr{P}(S)\)).
- A real definition: \[P(S) = \{A \mid A\subseteq S\}\,.\]
- For example, with \(S=\{a,b,c\}\), \[P(S) = \left\{\emptyset, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\right\}\,.\]
What is the cardinality of the power set?
- For a set \(S\), the power set has \(|P(S)|=2^{|S|}\) elements.
- Another notation for power set of \(S\) is \(2^S\). Then we could write \(|2^S|=2^{|S|}\), which looks either very nice or very confusing, depending on your perspective.
- [We'll stick with the \(P(S)\) notation from the text.]

Cartesian Product

Another operation that would be useful on two sets: all possible ways to take things from multiple sets.
- For example: “I have an apple, and orange, and a pear. The TA has a pencil, a pen, an eraser, and a book. You take one thing from each of us.”
- You are selecting one element from each set. What are the possible selections you can make? How many possibilities are there?
The Cartesian product of sets \(A\) and \(B\) is the set of all (ordered) pairs of values from \(A\) and \(B\).
- It is written \(A\times B\).
- Definition: \[A\times B = \{(a,b)\mid a\in A, b\in B\}\,.\]
- For example, \[\begin{align} \{a,b\}\times\{c,d,e\} &= \{(a,c), (a,d), (a,e), (b,c), (b,d), (b,e)\}\,,\\ \{10,20,30\}\times\{x,y,z\} &= \{(10,x), (10,y), (10,z),\\&\quad (20,x), (20,y), (20,z),\\&\quad (30,x), (30,y), (30,z)\}\,. \end{align}\]
- A standard deck of playing cards is basically the Cartesian product \[\{♠,♣,♥,♦\}\times\{\mathrm{A},2,3,4,5,6,7,8,9,\mathrm{J},\mathrm{Q},\mathrm{K}\}\,.\]
Theorem: For sets \(A\) and \(B\), it is not necessarily the case that \(A\times B = B\times A\). That is, \(\times\) is not commutative (in the way that \(\vee\) and \(\wedge\) were).
Proof strategy: Since we're disproving a universal statement, all we have to do is find a counterexample. This theorem does not imply that we cannot find two sets so that \(A\times B = B\times A\), just that it isn't always true.

Proof: Suppose \(A=\{a\}\) and \(B=\{b\}\). Then, \[A\times B = \{(a,b)\}\,,\\B\times A = \{(b,a)\}\,.\] Since \((a,b)\ne (b,a)\), we see that \(A\times B \ne B\times A\).∎
We can extend to the Cartesian product of more than two things in the obvious way: \[ A_1\times A_2\times\cdots\times A_n =\\ \{(a_1,a_2,\ldots,a_n) \mid a_1\in A_1, a_2\in A_2, \ldots, a_n\in A_n\}\,.\]
- For example, \[\{1,2\}\times\{a,b\}\times\{\mathrm{up}, \mathrm{down}\} = \\ \{(1,a,\mathrm{up}), (1,a,\mathrm{down}), (1,b,\mathrm{up}), (1,b,\mathrm{down}),\\ (2,a,\mathrm{up}), (2,a,\mathrm{down}), (2,b,\mathrm{up}), (2,b,\mathrm{down})\} \]
- It gets hard to actually list the elements, but we always mean the same thing: “every possible combination of things from these sets”.