(last updated: 5:03:13 AM, October 09, 2020)
A set is a collection of objects. We normally indicate each distinct object by a symbol or string of symbols set between curly braces, e.g. \(A=\{1,2\}\) is the set contaiing the numbers one and two, or \(S=\{\text{bob, jim, jill, sue}\}\) is the set containing the for humans bob, jim, jill, and sue. Sets are unordered so that \(\{\text{bob, jim, jill, sue}\}=\{\text{jim, bob, sue, jill}\}\). Two sets are said to be equal or equivalent if they contain the same members. To denote that sue is a member of set \(A\) we say “\(\text{sue}\in S\).” We can define sets by nearly any property using notation \(\{x\mid P\}\) where \(p\) is some statement in mathematics or natural language, such as \(\{x\mid x \text{ is even}\}\).
See Section 1.1 for more thorough details.
Union
\(A\cup B=\{x\mid x\in A \text{ or } x\in B\}\)
Ex: \(A=\{1,2\},B=\{2,3,4\}\), then \(A\cup B=\{1,2,3,4\}\)
Intersection
\(A\cap B=\{x\mid x\in A \text{ and } x\in B\}\)
Ex: \(A=\{1,2\},B=\{2,3,4\}\), then \(A\cap B=\{2\}\)
Set difference
\(A-B=\{x\mid x\in A \text{ and } x\not\in B\}\)
Sometimes the set difference is denoted by \(A\setminus B\), and can be said “\(A\) without \(B\).”
Ex: \(A=\{1,2\},B=\{2,3,4\}\), then \(A- B=\{1\}\), and \(B\setminus\{3\}=\{2,4\}\).
Complement
Normally we are working within some kind of overall parent set \(U\) (for universe), e.g. the real numbers or English alphabet. The complement of set \(A\) is the set difference \(U-A\). It is everything in the universe that is not a member of \(A\). We usually denote this by \(A^c=U-A\). The set difference \(A-B=A\cap B^c\).
Ex: If our universe or parent set is \(\{1,2,3,4,5,6\}\), and \(A=\{1,2\}\), then \(A^c=\{3,4,5,6\}\).
Empty set
The empty set is denoted \(\emptyset\) and is the set with no members, \(\emptyset=\{\}\). Note that \(\emptyset\subset A\) for any set \(A\). To check this, you need to consult basic formal logic and truth tables which you encountered in Math 301.
Two sets are called disjoint if they have empty intersection \(A\cap B=\emptyset\).
Indexing sets
Note that sets can be indexed by other symbols such as \(A_1,A_2,\ldots, A_k\) and we can take any mix of unions and intersections of these. In particular, given some set \(A\) and suppose for each \(\alpha\in A\) we have a set \(B_\alpha\), then we can say we have a colleciton of sets \(\{B_\alpha\}_{\alpha\in A}\). We can define the union and intersection of all sets in this colleciton: \[\bigcup_{\alpha\in A} B_\alpha=\{x \mid \text{ $x\in B_\alpha$ is true for at least a single $\alpha\in A$}\}\] \[\bigcap_{\alpha\in A} B_\alpha=\{x \mid \text{ $x\in B_\alpha$ is true for all $\alpha\in A$}\}\]
Rules for combining sets
Associative Laws:
\((A\cup B)\cup C = A\cup (B\cup C)\)
\((A\cap B)\cap C = A\cap (B\cap C)\)
Distributive Laws:
\((A\cup B)\cap C = (A\cap C)\cup (B\cap C)\)
\((A\cap B)\cup C = (A\cup C)\cap (B\cup C)\)
DeMorgan’s Laws:
\((A\cup B)^c=A^c \cap B^c\)
\((A\cap B)^c=A^c \cup B^c\)
\[\left(\bigcup_{\alpha\in A} B_\alpha\right)^c=\bigcap_{\alpha\in A} (B_\alpha)^c\] \[\left(\bigcap_{\alpha\in A} B_\alpha\right)^c=\bigcup_{\alpha\in A} (B_\alpha)^c\]
If we have two sets \(A,B\), then we can define another set called the cartesian product and defined by \(A\times B=\{(a,b)\mid a\in A \text{ and } b\in B\}\). This is essentially just a notational convenience indicating that we are considering sets \(A\) and \(B\) simultaneously.
A set \(f\) is said to be a relation between \(A\) and \(B\) if \(f\subset A\times B\) (see Definition 1.2.1). One can also think of \(f\) as a graph. If we has axes illustrating sets \(A\) and \(B\), then each \((a,b)\) is a point on a graph.
A relation \(f\) between \(A\) and \(B\) is said to be a function from \(A\) to \(B\) if for every \(a\in A\) there is exactly one \(b\in B\) such that \((a,b)\in f\) (see Definition 1.2.3). We normally write \(f(a)=b\). \(A\) is called the domain of \(f\), and \(B\) is called the codomain of \(f\). The range of \(f\) is denoted \[f(A)=\{b\in B\mid \text{ there is some } a\in A \text{ such that } f(a)=b\}\] We denote the domain of \(f\) by \(Dom(f)\) and its range by \(Ran(f)\).
The range of \(f\) is also called the image of \(A\) under \(f\).
A function \(f: A\rightarrow B\) is called onto if \(f(A)=B\).
A function \(f: A\rightarrow B\) is called one to one if \(f(a_1)=f(a_2)\) if and only if \(a_1=a_2\).
A function \(f: A\rightarrow B\) is called a bijection if it is one to one and onto.
If function \(f\) is one to one, then we can define its inverse function \(f^{-1}\). For all \(x\in Dom(f)\) and \(y\in Ran(f)\) we have \(x\in Ran(f^{-1})\) and \(y\in Dom(f^{-1})\). In other words \(f:Dom(f)\rightarrow Ran(f)\) and \(f^{-1}:Ran(f)\rightarrow Dom(f)\).
Recall that a function is a relation, or a subset of cartesian product: \(f=\{(x,f(x)) \mid x\in Dom(f)\}\) so that its inverse function is \(f^{-1}=\{(f(x),x) \mid x\in Dom(f)\}\).
The cardinality of a set describes the size of the set, or how many members it has (see Definition 1.6.3).
Formally, for finite sets, if there exists a subset of \(\mathbb N\) \(A=\{1,2,\ldots,n\}\) such that there exists a bijection \(f:A\rightarrow B\) then we say that \(B\) has cardinality \(n\) and denote this by \(\# B=n\) or sometimes \(|B|=n\).
A set \(A\) is called countably infinite if there exists a bijection from \(\mathbb N\) to \(A\), \(f:\mathbb N\rightarrow A\).
A set \(A\) is called uncountable or uncountably infinite if it is neither finite nor countable.
A set is called at most countable if it is either finite or infinite but countable. Usually I say countable and consider finite sets to be countable in the sense that they can be counted out in a literal sense.
Ex: \(\mathbb N\) is countably infinite. Consider function \(f:\mathbb N\rightarrow\mathbb N\) given by \(f(n)=n\). This is a bijection since each natural number is unique.
If \(A\subset B\), then the cardinality of \(B\) is at least the cardinality of \(A\). This statement makes sense for finite sets. To extend it to infinite sets, we say that countable infinity is a greater cardinality than any finite cardinality, and that uncountable cardinality is greater than countable cardinality. See Theorem 1.6.6.
The set of rational numbers is countable because there exists a bijection \(f:\mathbb N\rightarrow\mathbb Q\). This means that we can list all rational numbers: \(\mathbb Q=\{q_1,q_2,q_3,\ldots\}\). It is important to realize that this listing is somewhat arbitrary and has nothing to do with the ordering of rational numbers, i.e. given \(n<m\) then we do not have that \(q_n<q_m\) in our list! If we visualize the rational numbers laid out on the number line that you are used to, then this listing necessarily “jumps around” the line and does not proceed in a single direction.
Here is such a bijective \(f\):
Consider the function \(f(1)=1\) and \[f(n+1)=\frac{1}{\lfloor f(n) \rfloor +1 -(f(n)-\lfloor f(n) \rfloor)}\] for all \(n\in\mathbb N\) where \(\lfloor x \rfloor=\)integer part of \(x\), e.g. \(\lfloor 12/5 \rfloor=2\). This function can be understood this way: \[f(n+1)=\frac{1}{(\text{integer part of $f(n)$}) +1 -(\text{fractional part of $f(n)$})}\] This function \(f\) is a bijection from \(\mathbb N\) to \(\mathbb Q^+\).
Now define \(g(n)\) by \(g(1)=0\) and \(g(2n)=f(n)\) and \(g(2n+1)=-f(n)\) for all \(n\in\mathbb N\). In this way \(g\) hits all positive rationals on the even terms and all negative rationals on the odd terms. Now \(g\) is a bijection from \(\mathbb N\) to \(\mathbb Q\). Thus \(\mathbb Q\) is countable. To actually prove this carefully would be difficult.
This shows that we can list the rational numbers like \(\mathbb Q=\{q_1,q_2,q_3,\ldots\}\).
The function \(f\) actually lists out the Stern-Brocot tree by level. The Stern-Brocot tree is a binary search tree that contains all positive rational numbers. SO we just needed to make sure we included zero and all the negative rationals, which was accomplished with the definition of \(g\) here.
First we start with the interval \((0,1)\). See Theorem 1.6.9 for Cantor’s diagonalization argument. Since \((0,1)\subset \mathbb R\) then \(\mathbb R\) is also uncountable.
Here is a bijection \(f:(0,1)\rightarrow\mathbb R\).
\[f(x)=\frac{1-2x}{x-x^2}\]
\[ \diamond \S \diamond \]