Appendix: Brief Introduction to Sets#
Sets are one of the simplest mathematical objects. A concise definition is:
DEFINITION
- set#
An unordered collection of unique items.
The contained items are called elements or members:
DEFINITION
- element or member (of a set)#
Any one of the unique items contained in a set.
A set is denoted using curly braces {}, with the elements listed in any order, separated by commas. I will usually use capital, non-bold letters to denote sets. Thus a simple example of a set is
Order does not matter in sets, so it is equally valid to write the same set as
There are no restrictions on what types of items can be in a set. The elements can be homeogeneous (meaning all of the same type), such as for the example set \(A\). Or the elements may be heterogeneous (of different types). For instance, the following is a valid set:
Notice that sets may even contain other sets.
Set Membership and Cardinality#
The symbol \(\in\) indicates set membership:
DEFINITION
- set membership (\(\in\))#
The symbol \(\in\) indicates set membership. Thus if \(x \in A\), then \(x\) is an element of the set \(A\).
The symbol \(\notin\) is used to indicate when an element is not a member of a set.
For our examples, the following set membership relations are true:
Note that 4 is not an element of \(B\), even though \(\{4,6\}\) is an element of \(B\). The elements of \(B\) are the specific items separated by commas and tabulated below
elements of \(B\) |
|---|
3 |
blue |
dog |
\(\{4,6 \}\) |
The number of elements in a set is called its cardinality:
DEFINITION
- cardinality (of a set)#
The number of elements in a set. For a set \(S\), the cardinality of \(S\) is denoted \(\lvert S \rvert\).
Thus, \(\lvert A \rvert = 3\) and \(\lvert B \rvert = 4\).
The cardinality of a set may be infinite. Example of sets with infinite cardinalities include:
the counting numbers \(\mathbb{N} = \{1, 2, 3, \ldots \}\)
the integers \(\mathbb{Z} = \{ \ldots, -3, -2, -1, 0, 1, 2, \ldots \}\)
the real numbers, \(\mathbb{R}\)
Two sets have the same cardinality if there is a bijection (a one-to-one and onto mapping) between members of the two sets. This means that if \(A\) and \(B\) have the same cardinality, then there is a mapping that assigns each element in \(B\) to a unique element in \(A\), and vice versa.
DEFINITION
- finite (set)#
A set \(S\) is finite if there is a mapping from the elements in \(S\) to a subset of the counting numbers \(\{1,2,\ldots,N\}\), for some \(N < \infty\).
For example, here is such a mapping for set \(B\):
Thus \(\lvert B \rvert =4\).
Finding such a mapping is equivalent to simply counting the elements in the set.
For infinite sets, finding such a bijection can be much more tricky and is beyond the scope of this book. It turns out that there are actually two different infinite cardinalities that we will consider:
DEFINITION
- countably infinite (set)#
A set \(S\) is countably infinite if there is a mapping from the elements in \(S\) to the counting numbers \(\mathbb{N}\).
The following are examples of countable sets:
the integers
the rational numbers
all even counting numbers
DEFINITION
- uncountably infinite (set)#
A set \(S\) is uncountably infinite if \(\lvert S \rvert = \infty\) and there it is not possible to create a mapping between the elements in \(S\) and the counting numbers.
Examples of uncountably infinite sets include
the real numbers, \(\mathbb{R}\)
the postive real numbers, which may be denoted \(\mathbb{R}_{>0}\)
the irrational numbers (all the real numbers except for the rational numbers)
Subsets and Intervals#
The symbol \(\subset\) is the subset relation:
DEFINITION
- subset (\(\subset\))#
A set \(A\) is a subset of a set \(B\), denoted \(A \subset B\) if \(B\) contains every element in \(A\). Mathematically, we say \(A \subset B\) if and only if \(x \in A\) implies that \(x \in B\).
Thus, every element in \(A\) is an element in \(B\), but \(B\) may also contain other elements that are not in \(A\).
If \(A \subset B\) and \(B \subset A\), then \(A=B\).
Some of the most common subsets we will use are intervals of the real line:
DEFINITION
- interval (of the real line)#
Consider a set \(I \subset \mathbb{R}\) and any \(a \in I\) and \(b \in I\), where \(b>a\). Then \(I\) is an interval if for every \(x\) satisfying \(a \le x \le b \), \(x \in I\).
Intervals can be either open, closed, or half-open:
A closed interval \([a,b]\) contains the endpoints \(a\) and \(b\).
An open interval \((a,b)\) does not contain the endpoints \(a\)~and~\(b\).
An interval can be half-open, such as \((a,b]\), which does not contain \(a\), or \([a,b)\), which does not contain \(b.\)
Intervals of the real line are uncountably infinite.
Empty Set and Power Sets#
The empty set is the set with no elements:
DEFINITION
- empty set (\(\emptyset\))#
The empty set, denoted \(\emptyset\), is the set with no elements: \(\emptyset = \{ \}\).
We sometimes have the need to find all the subsets of a set:
DEFINITION
- power set (\(2^S\))#
Given a set \(S\), the power set of \(S\), denoted \(2^S\), is the set of all subsets of \(S\). Both \(\emptyset\) and \(S\) are included in the power set.
For a finite set, the cardinality of the power set is \(\lvert 2^S \rvert = 2^{\lvert S \rvert}\).
Set Operations and Laws#
Three important operations for working with set are union, intersection, and complement:
DEFINITION
- union (\(\bigcup\))#
Given sets \(A\) and \(B\), the union of \(A\) and \(B\), denoted \(A \cup B\), is a set that contains all elements that are in either \(A\), \(B\), or both. Mathematically, we say that if \(x \in A\) or \(x \in B\), then \(x \in A \cup B\).
For example, let \(C = \{0,2,4,6\}\). Then
DEFINITION
- intersection (\(\bigcap\))#
Given sets \(A\) and \(B\), the intersection of \(A\) and \(B\), denoted \(A \cap B\), is a set that contains all elements that are in \(A\) and in \(B\). Mathematically, we say that if then \(x \in A \cap B\), then \(x \in A\) and \(x \in B\).
For example,
DEFINITION
- complement (\(\overline{A}\))#
Given some universal set \(S\) and a set \(A \subset S\), the complement of \(A\), denoted \(\overline{A}\) or \(A^c\), is the set of elements in \(S\) that are not in A. Mathematically, we can say that \(\overline{A}\) contains all \(x \in S\) such that \(x \notin A\).
Let the univeral set be \(S = \{0,1,2,3,4,6\}\). Then
We will occasionally use two laws that describe how these operations interact:
DEFINITION
- Distributive Laws#
Given sets \(A\), \(B\), \(C\), the following distributive laws hold:
\[\begin{align*} A \cap (B \cup C) &= ( A \cap B) \cup (A \cap C), \mbox{ and} \\ A \cup (B \cap C) &= ( A \cup B) \cap (A \cup C).\\ \end{align*}\]
DEFINITION
- DeMorgan’s Laws#
Given sets \(A\), \(B\), \(C\), the following hold:
\[\begin{align*} \overline{ \left( A \cup B \cup C \right) } &= \overline{A} \cap \overline{B} \cap \overline{C}, \mbox{ and}\\ \overline{ \left( A \cap B \cap C \right) } &= \overline{A} \cup \overline{B} \cup \overline{C}. \end{align*}\]
Further Review#
This was a very concise review of sets, cardinalities, and set operations. For further study, I recommend: