Axioms

Foundational Axioms

In mathematics, a set is a collection of objects. Those objects might be dogs, people, trees, numbers, values, variables, or more abstractly, propositions. For example, the set of all coins includes nickels, sterling, and yen. The set of all countries includes Japan, Palau, and Uruguay. The set of all integers includes 1 and -117. We can visualize a set as:

Sets can be finite (there are only so many countries), or infinite (there are infinitely many of numbers). Each object in a set is called a member of that set.

Set Notation

To help make our future discussions more efficient, let's agree on some basic notation and terminology. First, the notion of logical identity.

Sets can be expressed in a variety of ways:

• "The set of all integers whose square is between, and includes, one and nine."
• ${A = \{ x \in \mathbb{Z} : x^2 \leq 9 \}}$
• ${B = \{ x \in \mathbb{Z} : \lvert x \rvert \leq 3 \}}$
• ${C = \{ -3, -2, -1, 0, 1, 2, 3 \}}$

Let's go over these approaches. We denote the notion of set membership with the symbol ${\in.}$ This is a variant of the lowercase epsilon (${\epsilon}$), which is the first letter of the Greek word ${ἐστί,}$ meaning "is."

A set may be made more explicit through set roster notation. For instance, $\{ 0, 1, 2 \}$ is a set containing the elements 0, 1, and 2. If the set has too many elements to list, ellipses may be used. For example, the set of all integers from 0 to 100 may be written as: $\{ 0, 1, 2, \ldots , 100 \}$. Likewise, the set of all positive integers may be written as $\{ 1, 2, 3, \ldots \}$.

We can also specify sets in set builder notation. Suppose that $S$ is a set, and $P(x)$ is a property that elements of $S$ may or may not satisfy. We can define a new set that contains all the elements of $S$ such that $P(x)$ is true:

The pipe character, |, is shorthand for "such that." Thus, above notation refers to all the elements of ${S}$ with the property $P(x)$. Note that in some mathematical contexts, the phrase "such that" is often abbreviated "s.t." or $\ni$. Thus, the above set may appear in some texts as:

Subsets

Some sets are themselves elements of another set. These sets are called subsets.² For example, the set of all Herefords is a subset of the set of all cows, and the set of all bonobos is a subset of the set of all great apes. More formally:

If ${A \subseteq B}$ is true, then we can infer: For every element ${x,}$ if ${x \in A,}$ then ${x \in B.}$ We describe ${A}$ and ${B's}$ relationship with statements such as "${A}$ is contained in $B$" and "${B}$ contains ${A.}$"

If $A \nsubseteq B$ is true, then we can infer: There is at least one element $x$ such that $x \in A$ and $x \notin B$. In other words, if $A$ is not a subset of $B$, then there is at least one element in $A$ that is not an element of ${B.}$

From the definition above, if we are asked to prove that ${A}$ is a subset of ${B,}$ we must show that if ${x}$ belongs to ${A,}$ then ${x}$ also belongs to ${B.}$ If we are asked to prove that ${A}$ is not a subset of ${B,}$ we must find a single ${x}$ that belongs to ${A}$ but does not belong to ${B.}$

The definition above implies that the empty set is a subset of all sets, and a given set is a subset of itself. In other words, for the set ${A,}$ the sets ${\varnothing}$ and ${A}$ are subsets of ${A.}$ We say that ${A}$ and ${\varnothing}$ are trivial subsets of ${A.}$

This follows directly from the definition. The proposition ${\varnothing \subseteq A}$ if, for all ${x \in \varnothing,}$ ${x \in A.}$ Because the sufficient condition, ${x \in \varnothing}$ is false, it follows that ${x \in A}$ is true. This is an example of a vacuous proof.

The case of ${A \subseteq A}$ straightforward. Given that ${A}$ and ${A}$ are the same sets, every ${x \in A}$ implies that ${x \in A.}$ Because the sufficient condition is true and the necessary condition is true, it follows that ${A \subseteq A}$ by definition.

The Empty Set

Some sets have no members. For example, the set of all positive integers greater than their squares is the empty set. If there is even a single element in the set, then the set is not the empty set. Such a set (a set with a single member) is called a singleton.

Importantly, we shouldn't confuse the lack of an element with the lack of a subset. The empty set does have a subset—the empty set. But the fact that it has a subset does not imply that it has an element. We will see why this is the case shortly.

The empty set is both an interesting and useful concept to have. Proferred by George Boole, the empty set embodies the concept of nothingness. Nothingness is a difficult concept to think about, but as with many things in mathematics, the idea is encapsulated—abstracted away—into a single symbol: ${\varnothing.}$ The abstraction allows us to reason about nothingness differently. Usually, when we think of filling an empty pint with beer, we tend to think that we are somehow negating the glass's emptiness; sort of "removing" the nothingness inside the pint. ${\varnothing,}$ however, is a member of every set except itself. We cannot remove nothingness from the set of all natural numbers—it's always there.

The empty set is a very useful notion, but it can also be a footgun if we don't use it carefully. To prevent fiascos, we will always denote the empty set with the null symbol: ${\varnothing.}$ At no point do we ever write:

This is equivalent to a spelling mistake in mathematics. Second, the set containing an empty set is not the same as the empty set:

Once more, these are two very different things. One is an actual object (${\varnothing}$), the other is a box containing a single object (${\{ \varnothing \}}$). The empty set can be thought of as representing an empty folder. If we place an empty folder ${A}$ inside an empty folder ${B,}$ then the folder ${A}$ is no longer empty: It contains a folder. The distinction between elements and subsets is a critical distinction.

Set Identity

Consider the following sets:

By the axiom of extension, ${A,}$ ${B,}$ and ${C}$ all have the same elements. Observing this, we have the following definition:

From the definition above, given to sets ${A}$ and ${B,}$ to prove that ${A}$ is equal to ${B,}$ we prove that ${A \subseteq B}$ and ${B \subseteq A.}$

Cardinality

Suppose we have the following set, called ${A:}$

How many elements are in this set? There are 4. The number of elements in a set is called the set's cardinality. The term cardinality is derived from the term cardinal number (a number used for counting, rather than ordering). Cardinality plays a special role in both mathematics and programming. For example, in computer science, an uncountable function is a function where no computer program can be written to find all its values. In other words, there are some functions that we, as programmers, cannot write simply because the cardinality of the function's set of outputs is either too large to count or cannot be counted at all.

The notation ${n(A)}$ is not the only one way to denote cardinality. Some texts denote cardinality with ${\lvert A \rvert }$ and ${\text{card}(A) .}$ We use ${n(A),}$ but will switch notations as necessary for clarity. Note that when analyzing cardinality, the axiom of extension applies. The set ${A = \{ 1, 1, 2 \}}$ and ${B = \{ 1, 2 \}}$ are the same sets. Thus, both ${A}$ and ${B}$ have a cardinality of 2 (i.e., ${n(A) = n(B) = 2.}$)

Another useful fact when handling cardinality: The empty set is the only set with a cardinality of 0:

Further note that because sets denote the number of elements in a set, for our purposes, we follow the axiom that cardinality can never be negative.⁴ Because we're discussing set algebra, we are careful to state this axiom explicitly:

Set Union

Suppose there are two sets, $A$ and $B$. The union of $A$ and $B$, denoted ${A \cup B,}$ is the set of all elements of both $A$ and $B$. Visually:

Venn diagrams are named after the English mathematician John Venn, who introduced their usage in 1881. More formally:

Set Intersection

In the Venn diagram below, the grey region is called the set intersection.

Here is the definition of intersection:

This is a deceptively simple definition. For example, ${\set{1,2,3} \cap \set{2,3,4}}$ very clearly yields the intersection ${\{ 2, 3 \}.}$ But here's a slighly more devilish one:

It's very tempting to say the intersection here is 3. The correct answer, however, is

The slip is forgetting the fact that the intersection operation always returns a set. As an aside, because of how long the word "intersection" is, the symbol ${\cap}$ is often read "cap" (again from its corresponding LaTeX command, \cap). For example, the expression

is often read "${A}$ cap ${B.}$"

Cardinalities of Intersections and Unions

Suppose we had the following sets ${A}$ and ${B:}$

$$\begin{aligned} A &= \{ 2, 4, 5, 6, 10, 11, 14, 22 \} \\ B &= \{ 1, 2, 3, 5, 7, 8, 11, 12, 13 \} \end{aligned}$$

As a Venn diagram, sets ${A}$ and ${B}$ are visualized as such:

We see that the union of ${A}$ and ${B}$ is:

$$A \cup B = \{ 5, 2, 11 \}$$

The cardinalities of the sets and the union:

$$\begin{aligned} n(A) &= 8 \\ n(B) &= 9 \\ n(A \cup B) &= 14 \\ n(A \cap B) &= 3 \end{aligned}$$

Notice that the cardinality of the union is not simply ${n(A) + n(B).}$ This is because simply adding ${n(A)}$ and ${n(B)}$ results in counting the elements in the intersection twice. Accordingly, to compute the cardinality of ${A \cup B,}$ we must subtract ${A \cap B.}$ This yields the following formula:

lemma. Let ${A}$ and ${B}$ be non-empty, finite sets. The cardinality of ${A \cup B}$ is given by the formula:

$$n(A \cup B) = n(A) + n(B) - n(A \cap B)$$

From the above formula, we can derive a second formula for the cardinality of the intersection:

lemma. Let ${A}$ and ${B}$ be non-empty, finite sets. The cardinality of ${A \cap B}$ is given by the formula:

$$n(A \cap B) = n(A) + n(B) - n(A \cup B)$$

Disjoint Sets

Some sets have no elements in common, and we call them disjoint. For example, the two sets below are disjoint:

Here's an explicit definition:

Set Difference

Let $A$ and $B$ both be sets. The difference of $A$ and $B$, denoted ${A \setminus B}$ (read "$A$ set minus $B$) is the set of all elements in $A$ and not in $B.$ In other words, ${A \setminus B = \{ x : (x \in A) \land (x \notin B) \}.}$

More formally:

We say that ${A \setminus B}$ is the complement of ${B}$ with respect to ${A.}$

Complements

The complement of a set ${S}$ more generally refers to the set of all elements not contained in ${S.}$ If we have a defined universal set ${U}$ and ${A \subset U,}$ then the complement of ${A}$ is the set of all elements in ${U}$ that are not inside ${A.}$

Set Identities

Knowing the set operations, it's often helpful to know several set identities by heart to quickly perform deductions. These identities are presented below:

Symmetric Difference

The symmetric difference between two sets ${A}$ and ${B}$ is defined as:

That is to say, the symmetric difference of sets ${A}$ and ${B}$ is the set made up of all the elements which are in ${A}$ or ${B}$ but not both. We can think of this as akin to the "exclusive or."

The symmetric difference has the following properties:

Power Sets

A mathematician requested a VISA to enter the United States with his family (him, his wife, and his son). The embassy replied, "Please submit passport photos of your family." Unsure whether multiple persons were supposed to be in each photo, the mathematician took one for every combination. Each on their own, him and his wife, him and his son, his wife and his son, etc. Photos taken, the mathematician returned to the embassy.

The clerk was dumbfounded. After several minutes she said, "There's no one in this photo."

"Yes. That is a photo of the empty set."

This amusing exchange illustrates the notion of a power set. Consider the set ${B = \{ 0, 1 \},}$ the set of binary digits. Using our definition of subsets, what are all the different possible subsets of ${B?}$ We can lay them out:

There are four different possible subsets. Suppose we place all these possible subsets in an entirely new set:

We call the set above the power set of ${B,}$ and denote as:

The symbol ${\mathcal{P}}$ is used in these notes, but other symbols are used throughout mathematics: ${\mathscr{P}, \mathbb{P}, \wp,}$ and a few others. Defining the power set more formally:

One peculiar application of the definition above is with the empty set. What is the size of the power set of ${\mathcal{P}(\varnothing)?}$ It is 1, since the only subset of ${\varnothing}$ is ${\{\varnothing\}.}$ Next, what is the size of the power set of ${ \{ \varnothing \}?}$ It is 2, since ${\mathcal{P}(\{ \varnothing \}) = \{ \varnothing, \{ \varnothing \} \}.}$ If we continue this pattern:

The pattern above yields to a direct corollary (as well as several other ideas we will explore in the sections on number theory):

The proof of this corollary: Let ${A}$ be a set. For every subset of ${A,}$ there are two possibilities for each element ${x \in A:}$ Either (1) ${x}$ is in the subset, or ${x}$ is not in the subset. Therefore, it follows that for ${n}$ elements, there are ${2^n}$ possibilities in making a subset of ${A.}$ From the definition of the powerset, it follows that the number of subsets of ${A}$ is ${2^n.}$

Big Unions & Intersections

At this point, we have a much better understanding of basic set theory. We can now introduce the generalized forms of unions and intersections. Because sets comply with the laws of associativity, the sets ${A \cup B \cup C}$ and ${A \cap B \cap C}$ are unambiguous. In other words, we don't need parentheses to communicate what we mean. ${A \cup B \cup C}$ is the same set as ${(A \cup B) \cup C}$ which is the same set as ${A \cup (B \cup C).}$ The same goes for ${A \cap B \cap C.}$

For example, suppose ${A = \{ 1, 2 \},}$ ${B = \{ 1, 4 \},}$ and ${C = \{ 1, 7 \}.}$ Then ${A \cup B \cup C = \{ 1, 2, 4, 7 \},}$ and ${A \cap B \cap C = \{ 1 \}.}$ The set ${A \cup B \cup C}$ is the set containing all the elements that occur in at least one of ${A,}$ ${B,}$ and ${C.}$ The set ${A \cap B \cap C}$ contains all the elements in all three of ${A,}$ ${B,}$ and ${C.}$ We can extend this idea to any ${n}$ number of sets:

From the definition above, it follows that the notation ${\bigcup\limits_{i = 1}^{n} A_i}$ represents a set. Accordingly, when we write ${x \in \bigcup\limits_{i = 1}^{n} A_i,}$ we imply that ${x}$ is a member of at least one of ${A_1, A_2, \ldots, A_n.}$ This idea also applies to intersections:

Special Number Sets

Certain number sets are used so frequently in mathematics that we denote them with symbols.