Sets, Functions, and Cardinality

In order to converse mathematically about infinity, a precise common language must be established. We begin to do that, albeit somewhat informally, on this page, which will serve as a reference for future mathematical posts.

Sets

The modern study of infinity began with Georg Cantor and the birth of set theory, so we naturally start with sets. For us, sets are simply collections of objects. (As we will later see, one must be careful here to avoid paradox; ignore these subtleties for now.) Sets are represented by curly braces. So, for example, \{1,2,4\} is the set containing the numbers 1,2, and 4. We have standard notations for some common sets:

  • \mathbb{N} is the set of natural numbers (0,1,2,\ldots ).
  • \mathbb{Z} is the set of integers.
  • \mathbb{Q} is the set of rational numbers (numbers which can be expressed as ratios of integers).
  • \mathbb{R} is the set of real numbers.
  • \mathbb{C} is the set of complex numbers (numbers of the form a + bi, where a and b are real numbers and i = \sqrt{-1}).

We express the fact that an element a is a member of a set A by writing a \in A. So, for example, 2 \in \{1,2,4\}. We may express that something is not an element of a set by using \not\in. For example, 3 \not\in \{1,2,4\}.

Sets may also be presented in terms of a rule for membership. This rule is written inside the curly braces, after a vertical line (\mid), which should be read as ‘such that.’ So, for example, \{n \in \mathbb{Z} \mid n is divisible by 2\} is precisely the set of even integers. An important thing to note is that elements of sets may themselves be sets. (In fact, in modern set theory, everything is a set.) We are now ready to define the basic set-theoretic operations.

  • (Empty set) \emptyset is the set that has no elements.
  • (Union) If A and B are sets, then A \cup B = \{x \mid x \in A \mbox{ or } x \in B\}, i.e. A \cup B is the set of elements that are in either A or B (or both, of course. The word ‘or’ is not exclusive for us.)
  • (Intersection) If A and B are sets, then A \cap B = \{x \mid x \in A \mbox{ and } x \in B\}.
  • (Subset) If A and B are sets, then A \subseteq B (A is a subset of B) if every element of A is also an element of B. Note that the empty set is a subset of every set.
  • (Set difference) If A and B are sets, then A \setminus B = \{x \mid x \in A \mbox{ and } x \not\in B\}.
  • (Power set) If A is a set, then the power set of A, written \mathcal{P}(A), is the set of all subsets of A, i.e. \{B \mid B \subseteq A\}.

Let us provide an example to illustrate the notion of power set, as it is an important idea. If A = \{1,2,4\}, then \mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{4\}, \{1,2\}, \{1,4\}, \{2,4\}, \{1,2,4\}\}.

Functions

function is a relation between an input set (the domain of the function) and an output set (the codomain of the function) that assigns to each element of its domain exactly one element of its codomain. If f is a function with domain A and codomain B, we write f:A \rightarrow B and say, “f is a function from A to B.” If a \in A, then the element in B that f assigns to a is denoted by f(a).

Suppose f:A \rightarrow B.

  • f is one-to-one if f assigns distinct elements of B to distinct elements of A, i.e. whenever x and y are different elements of A, f(x) \neq f(y).
  • f is onto if every element of B is assigned to some element of A, i.e. for every element z \in B, there is x \in A such that f(x) = z.
  • f is a bijection if it is both one-to-one and onto.

Cardinality

We want to be able to compare the sizes of two sets A and B. If the sets are finite, this is easy. Just count the number of elements in A and B. The one with more elements is larger. But what if our sets are infinite? We want a natural notion of size that works for infinite sets and matches our intuition on finite sets. The notion we use is cardinality. We denote the cardinality of a set A by |A|. For now, let us not worry about what exactly a cardinality is and just talk about how to compare them, which is what we are really interested in.

What are we asserting when we say that two finite sets, A and B, are the same size? In a sense, we are saying that there is a correspondence between the elements of A and B, that we can match up each element of A with a distinct element of B in such a way that every element of B is matched with something from A. In other words, there is a bijection f:A \rightarrow B. We thus adopt this as our criterion for when arbitrary sets A and B have the same cardinality:

|A| = |B| if there is a bijection f:A \rightarrow B.

As an example, let X be the set of even natural numbers, and let f:\mathbb{N} \rightarrow X be defined by f(n) = 2n. f is a bijection, so the set of natural numbers has the same cardinality as the set of even natural numbers.

What if we want to say that a set A is smaller than a set B? To answer this, return to thinking about finite sets. Intuitively, a finite set A is smaller than or the same size as a finite set B if each element of A can be matched up with a distinct element of B (if A is smaller than B, there will be some elements of B left over). This is precisely the statement that there is a one-to-one function f:A \rightarrow B. We thus adopt this as our general definition:

|A| \leq |B| if there is a one-to-one function f:A \rightarrow B.

As an exercise, I invite you to show that, if there is a one-to-one function f:A \rightarrow B, then there is an onto function g:B \rightarrow A. Therefore, we have the following equivalent definition:

|A| \leq |B| if there is an onto function f:B \rightarrow A.

Any reasonable notion of cardinality would have the feature that, if |A| \leq |B| and |B| \leq |A|, then |A| = |B|. In our case, this amounts to the assertion that, if there are one-to-one functions f:A \rightarrow B and g:B \rightarrow A, then there is a bijection h:A \rightarrow B. Indeed, this is true, though it is surprisingly non-trivial to prove (the statement is known as the Cantor-Schroeder-Bernstein Theorem).

Finally, we define when a set A has strictly smaller cardinality than B.

|A| < |B| if |A| \leq |B| and |B| \not\leq |A|.

In other words, |A| < |B| if there is a one-to-one function f:A \rightarrow B but there is no onto function g:|A| \rightarrow |B|.

As an example, let X be a set, and consider the function f:X \rightarrow \mathcal{P}(X) defined by letting f(x) = \{x\} for every x \in X. f is one-to-one, so we have |X| \leq |\mathcal{P}(X)|. As we will show in another post, there cannot be an onto function g:X \rightarrow \mathcal{P}(X), so, in fact, |X| < |\mathcal{P}(X)|.