Appendix: Brief Introduction to Sets

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

\[ A = \{0,1,2 \}. \]

Order does not matter in sets, so it is equally valid to write the same set as

\[ A = \{ 2, 0, 1\}. \]

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:

\[ B = \{ 3, \mbox{blue}, \mbox{dog}, \{4,6\} \}. \]

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:

\[\begin{align*} 0 & \in A \\ 2 & \in A \\ 2 & \notin B \\ 3 & \notin A \\ 3 & \in B \\ \{4,6\} &\notin A\\ \{4,6\} &\in B \\ 4 & \notin B \end{align*}\]

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\):

\[\begin{align*} 3 &\longleftrightarrow &1\\ \mbox{blue } &\longleftrightarrow &2\\ \mbox{dog } &\longleftrightarrow &3\\ \{4,6 \} &\longleftrightarrow &4 \end{align*}\]

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

\[ A \cup C = \{0,1,2,4,6 \}. \]

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,

\[ A \cap C = \{ 0, 2 \}. \]

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

\[ \overline{C} = \{ 1,3,5 \}. \]

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: