Skip to main content

Section 7.1 Basics of Set Theory

Subsection 7.1.1 Set Basics

The term set was first introduced by Georg Cantor (1845-1918).

Recall the set-builder notation \(A = \set{x \in S: P(x)}\text{.}\) This means that the set \(A\) is the set of all elements \(x \in S\) such that \(P(x)\) is true. Using mathematical logic,

\begin{equation*} \brac{x \in A} \equiv \brac{x \in S \land P(x)} \end{equation*}

Using mathematical logic, the definition of set equality can be written as,

\begin{equation*} A = B \equiv \brac{x \in A \leftrightarrow x \in B} \end{equation*}

Subsection 7.1.2 Cardinality, Finite and Infinite Sets

Definition 7.1.1.

Let \(A\) be a set. The cardinality (or size or cardinal number) of a set \(A\text{,}\) denoted by \(n(A)\) or \(\abs{A}\text{,}\) is the number of elements in \(A\text{.}\)

  • The empty set has cardinality zero, \(\abs{\emptyset} = 0\text{,}\) and it is the unique set with this property.

Some sets have infinitely many elements. In roster notation, which can be indicated by an ellipsis “\(\dots\)”.

Definition 7.1.2.

Intuitively, a finite set has a finite number of elements, i.e. the number of elements in the set is a whole number. An infinite set has infinitely many elements, i.e. the number of elements in the set is not a whole number.

Subsection 7.1.3 Sets Inside Sets

A set is a collection of objects, and sets are themselves objects. Then, a set can include other sets among its elements.

Note that \(1 \in \set{1,3}\) (the object 1 is in the set containing 1 and 3), but \(\set{1} \not\in \set{1,3}\) (the set containing 1 is not an element of the set containing 1 and 3). However, \(\set{1} \in \set{\set{1},3}\) (the set containing 1 is an element of the set containing 3 and the set containing 1). In general, an object is not the same as a set containing that object.

Subsection 7.1.4 Subsets

Definition 7.1.4.

A set \(A\) is a subset of a set \(B\text{,}\) denoted by \(A \subseteq B\text{,}\) if every element of \(A\) is also an element of \(B\text{.}\)

Using mathematical logic, this can be written as a universal conditional statement,

\begin{equation*} (A \subseteq B) \equiv (\forall x \in A, x \in B) \equiv (x \in A \implies x \in B) \end{equation*}

Also, \(A\) is not a subset of \(B\text{,}\) denoted by \(A \not\subseteq B\text{,}\) if there exists some \(x \in A\) such that \(x \notin B\text{.}\)

\begin{equation*} (A \not\subseteq B) \equiv (\exists x \in A \text{ s.t. } x \notin B) \end{equation*}

The set of holidays is a (proper) subset of the set of all days in the calendar year.

Intuitively, the notation \(\subseteq\) is analogous to the less than or equal to sign \(\leq\text{.}\)

All sets are subsets of themselves. In other words, for all \(A\text{,}\) \(A \subseteq A\text{.}\) Note that a set is not a strict subset of itself.

This is because, for every element in \(A\text{,}\) that element is in \(A\text{.}\)

The important number sets have the following inclusion relationship,

\begin{equation*} \mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R} \subseteq \mathbb{C} \end{equation*}

Note that only sets can be subsets of other sets. In particular, elements are not subsets of other sets. For example, \(1 \subseteq \set{1, 2, 3}\) is false, whereas \(\set{1} \subseteq \set{1, 2, 3}\text{.}\) Instead, we have \(1 \in \set{1,2,3}\text{.}\)

Definition 7.1.8.

A set \(A\) is a proper subset of \(B\text{,}\) denoted by \(A \subset B\text{,}\) if \(A\) is a subset of \(B\) and \(A \neq B\text{.}\) In other words, \(B\) contains at least one element that is not in \(A\text{.}\) In mathematical logic,

\begin{equation*} (A \subset B) \equiv (\forall x \in A, x \in B) \land (\exists x \in B \text{ s.t. } x \notin A) \end{equation*}

Sometimes, we want to refer to a set containing another set, rather than being contained within another set.

Definition 7.1.9.

\(B\) is a superset of \(A\text{,}\) \(B \supseteq A\text{,}\) if \(A\) is a subset of \(B\text{.}\)

\(B\) is a proper superset of \(A\text{,}\) \(B \supset A\text{,}\) if \(A\) is a proper subset of \(B\text{.}\)

Intuitively, the prefix “super-” means bigger, and “sub-” means lesser, somewhat similar to \(>\) and \(\lt\) for comparing numbers.

Subsection 7.1.5 Remark on Subset Notation

Mathematicians are somewhat divided on how to write subsets and strict subsets. Here, \(A \subseteq B\) represents \(A\) being a subset of \(B\text{,}\) and \(A \subset B\) (without the horizontal line) being a strict subset of \(B\text{.}\) However, in some textbooks, \(A \subset B\) is used to mean \(A\) being any subset of \(B\text{,}\) not just strict subsets. Unfortunately, this convention contradicts the previous notation, however is it also widely used. In light of this, somtimes \(A \subsetneq B\) is used instead of \(A \subset B\) to denote a strict subset, since the latter can be used to mean a general subset.

Subsection 7.1.6 Proving One Set is a Subset of Another

To prove that \(A \subseteq B\text{,}\)

  1. Suppose that \(x\) is a particular but arbitrarily chosen element of \(A\text{.}\)

  2. Show that \(x\) is an element of \(B\text{.}\)

This is called an element argument, because it involves proving that every element in one set is also an element of another. This is a fundamental proof technique of set theory.

To prove that \(A \subseteq B\text{,}\) find a counterexample to the definition of subset, an element \(x \in A\) where \(x \notin B\text{.}\)

Subsection 7.1.7 Equality of Sets Using Subsets

Then, to prove that two sets are equal, \(A = B\text{,}\) we can prove that \(A \subseteq B\) and \(B \subseteq A\text{,}\) and prove each of these two statements using an element argument. In other words, a “set equality” proof basically consists of two subset proofs.

Subsection 7.1.8 Transitivity of Subsets

We want to show that for all \(a \in A\text{,}\) we have \(a \in C\text{.}\) Let \(a \in A\text{.}\) Since \(A \subseteq B\text{,}\) this implies that \(a \in B\text{.}\) Then, since \(B \subseteq C\text{,}\) this implies that \(a \in C\text{,}\) as desired.

Subsection 7.1.9 Number of Subsets

Consider a finite set \(A\) with \(n\) elements. How many possible subsets does \(A\) have? Consider this for \(n = 0, 1, 2, 3\) etc.

  • For \(n = 0\text{,}\) \(A = \emptyset\text{,}\) which has 1 subset, \(A\) itself.

  • For \(n = 1\text{,}\) say, \(A = \set{a}\text{,}\) there are 2 subsets, \(A\) itself and the empty set.

  • For \(n = 2\text{,}\) \(A = \set{a, b}\text{,}\) there are 4 subsets: \(\set{a, b}, \set{a}, \set{b}\text{,}\) and \(\emptyset\text{.}\)

  • For \(n = 3\text{,}\) \(A = \set{a, b, c}\text{,}\) there are 8 subsets: \(\set{a, b, c}, \set{a,b}, \set{a,c}, \set{b,c}, \set{a}, \set{b}, \set{c}\text{,}\) and \(\emptyset\text{.}\)

In summary,

\begin{equation*} \begin{array}{c|c|c|c|c} \text{Number of elements} \amp 0 \amp 1 \amp 2 \amp 3 \\ \hline \text{Number of subsets} \amp 1 \amp 2 \amp 4 \amp 8 \end{array} \end{equation*}

From these examples, we might conjecture that the number of subsets of a set with \(n\) elements is \(2^n\text{.}\)

A subset of \(A\) is a set with some selection of the elements of \(A\text{.}\) The number of possible subsets is the number of selections of the elements of \(A\text{.}\) Using the fundamental counting principle, there are two choices for each element (each element can either be in the subset or not in the subset), and there are \(n\) choices to be made (one for each element). Thus, the number of ways to make this selection, is,

\begin{equation*} \underbrace{2 \cdot 2 \cdot 2 \cdots 2}_{\text{$n$ factors of 2}} = 2^n \end{equation*}

Thus, there are \(2^n\) possible subsets.

By induction, for \(n = 0\text{,}\) \(A = \emptyset\) has \(1 = 2^0\) subsets.

Then, assume the result is true for \(n = k \in \mathbb{N}\text{,}\) that every set with \(n\) elements has \(2^n\) subsets. Then, let \(B = \set{a_1, a_2, \dots, a_n, a_{n+1}\) be a set with \(n+1\) elements, and we want to show that \(B\) has \(2^{n+1}\) subsets.

Then, let \(B = A \cup \set{a_{n+1}}\) where \(A = \set{a_1, \dots, a_n}\) has \(n\) elements. Each subset \(X\) of \(A\) corresponds to 2 subsets of \(B\text{.}\) One is simply \(X\) itself, since every subset of \(A\) is also a subset of \(B\text{.}\) The other is the set \(X \cup \set{a_{n+1}}\text{.}\) Since there are \(2^n\) subsets of \(A\) and each corresponds to 2 subsets of \(B\text{,}\) this means there are at least \(2 \cdot 2^n = 2^{n+1}\) subsets of \(B\text{.}\)

Also, any subset of \(B\) must either include \(a_{n+1}\) or not include \(a_{n+1}\text{.}\) If it includes \(a_{n+1}\text{,}\) then it must be of the form \(X \cup \set{a_{n+1}}\) for some subset \(X\) of \(A\text{.}\) If it doesn't include \(a_{n+1}\text{,}\) then it is a subset of \(A\text{.}\) In this way, we have accounted for every possible subset of \(B\text{.}\)

Subsection 7.1.10 Power Sets

Don't confuse \(P(A)\) to mean the probability of the event \(A\text{.}\) In this context, this means the power set of \(A\text{.}\)

  • \(\displaystyle P(\set{1, 2}) = \set{\emptyset, \set{1}, \set{2}, \set{1, 2}}\)

  • \(\displaystyle P(\set{1, 2, 3} = \set{\emptyset, \set{1}, \set{2}, \set{3}, \set{1, 2}, \set{1, 3}, \set{2, 3}, \set{1, 2, 3}}\)

  • \(\displaystyle P(\set{5}) = \set{\emptyset, \set{5}}\)

  • \(\displaystyle P(\emptyset) = \set{\emptyset}\)

  • \(\displaystyle P(P(\emptyset)) = P(\set{\emptyset}) = \set{\emptyset, \set{\emptyset}}\)

Recall that a set \(A\) with \(n\) elements has \(2^n\) subsets. Using power set notation,

Let \(X \in P(A) \cup P(B)\text{.}\) Then, by definition of union, \(X \in P(A)\) or \(X \in P(B)\text{.}\) By definition of a power set, \(X \subseteq A\) or \(X \subseteq B\text{.}\) Without loss of generality, let \(X \subseteq A\text{.}\) Then, let \(x \in X\text{.}\) Since \(X \subseteq A\text{,}\) \(x \in A\text{.}\) Then, since \(A \subseteq A \cup B\text{,}\) we have \(x \in A \cup B\text{.}\) Therefore, \(X \subseteq A \cup B\text{,}\) and so \(X \in P(A \cup B)\text{.}\)

Subsection 7.1.11 Well-Defined Sets

Sets must be well-defined, in that it must be clear and unambiguous which elements are in the set and which are not. In other words, given any object, it must be clear whether that object is in the set or not.

The set of all young adults is not well-defined, because it depends on the definition of “young adult”. The set of all people aged 20 or older is well-defined.

The set of the top 5 airports in the country is not well-defined, because the quality of an airport is subjective and up to interpretation.

Subsection 7.1.12 Aside on Definitions

Definitions are very important in mathematics to facilitate clear communication of ideas. However, it is an unfortunate fact that it is impossible to define every concept. Recall that a set is defined as a “collection of distinct objects”. This naturally leads to the question of how a collection is defined. After all, “set” and “collection” seem to be almost synonyms, so defining one in terms of the other seems unhelpful. Theoretically, we could define “collection”, say as an group or aggregate of things. This isn't much more helpful, since now we would have to define a group or aggregate. This could continue indefinitely, until we run out of suitable words.

In this way, a concept like a set is simply defined intuitively. For most purposes, this will be sufficient.

Subsection 7.1.13 Aside on Sets and Math Definitions

Today, most mathematical objects are “formally” defined in terms of sets. For example, functions are defined as a particular kind of set. In fact, numbers, such as natural numbers \(1, 2, \dots\text{,}\) can be defined using sets.

Subsection 7.1.14 Venn Diagrams, Euler Diagrams

Relationships between sets can be represented graphically using a Venn diagram, or a Euler diagram. First intorduced in 1881, by John Venn, British mathematician. The idea is that sets \(A\) and \(B\) are represented as regions in the plane, and elements are thought of as points in the plane.