# 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”.