13.1: The Language of Sets and Functions (2023)

A set is an unordered collection of distinct objects, which we call its elements. \(A\) set is uniquely determined by its elements. If an object a is an element of a set \(A\), we write \(a \in A\), and say that a belongs to \(A\) or that \(A\) contains a. The negation of this statement is written as \(a \not\in A\), i.e., a is not an element of \(A.\) Note that both statements cannot be true at the same time

If \(A\) and \(B\) are sets, they are identical (this means one and the same set), which we write as \(A = B\), if they have exactly the same elements. In other words \(A = B\) if and only if forall \(a \in A\) we have \(a \in B\), and for all \(b \in B\) we have \(b \in A.\) Equivalently, \(A \neq B\) if and only if there is a difference in their elements: there exists \(a \in A\) such that \(a \not\in B\) or there exists \(b \in B\) such that \(b \not\in A.\)

Example B.1.1. We start with the simplest examples of sets.

1. The empty set (a.k.a. the null set), is what it sounds like: the set with no elements. We usually denote it by \(\emptyset\) or sometimes by \(\{~\}\). The empty set, \(\emptyset\), is uniquely determined by the property that for all \(x\) we have \(x \not\in \emptyset\). Clearly, there is exactly one empty set.
2. Next up are the singletons. A singleton is a set with exactly one element. If that element is \(x\) we often write the singleton containing \(x\) as \(\{x\}\). In spoken language, ‘the singleton \(x\)’ actually means the set \(\{x\}\) and should always be distinguished from the element \(x: x \neq \) {\(x\)}. A set can be an element of another set but no set is an element of itself (more precisely, we adopt this as an axiom). E.g., \(\{\{x\}\}\) is the singleton of which the unique element is the singleton \(\{x\}\). In particular we also have \(\{x\} \neq \{\{x\}\}.\)
3. One standard way of denoting sets is by listing its elements. E.g., the set \(\{\alpha, \beta, \gamma\}\) contains the first three lower case Greek letters. The set is completely determined by what is in the list. The order in which the elements are listed is irrelevant. So, we have \(\{\alpha, \gamma, \beta\} = \{\gamma, \beta, \alpha\} = \{\alpha, \beta, \gamma\},\) etc. Since a set cannot contain the same element twice (elements are distinct) the only reasonable meaning of something like \(\{ \alpha, \beta, \alpha, \gamma\}\) is that it is the same as \(\{\alpha, \beta, \gamma\}\). Since \(x \neq \{x\}, \{x, \{x\}\}\) is a set with two elements. Anything can be considered as an element of a set and there is not any kind of relation is required of the elements in a set. E.g., the word ‘apple’ and the element uranium and the planet Pluto can be the three elements of a set. There is no restriction on the number of different sets a given element can belong to, except for the rule that a set cannot be an element of itself.
4. The number of elements in a set may be infinite. E.g., \(\mathbb{Z}, \mathbb{R},\) and \(\mathbb{C}\), denote the sets of all integer, real, and complex numbers, respectively. It is not required that we can list all elements.

When introducing a new set (new for the purpose of the discussion at hand) it is crucial to define it unambiguously. It is not required that from a given definition of a set \(A\), it is easy to determine what the elements of \(A\) are, or even how many there are, but it should be clear that, in principle, there is unique and unambiguous answer to each question of the form “is \(x\) an element of \(A\)?”. There are several common ways to define sets. Here are a few examples.

Example B.1.2.
1. The simplest way is a generalization of the list notation to infinite lists that can be described by a pattern. E.g., the set of positive integers \(\mathbb{N} = \{1, 2, 3, \ldots \}.\) The list can be allowed to be bi-directional, as in the set of all integers \(\mathbb{Z} = \{\ldots , -2, -1, 0, 1, 2, \ldots \}.\)
Note the use of triple dots \(\ldots\) to indicate the continuation of the list.
2. The so-called set builder notation gives more options to describe the membership of a set. E.g., the set of all even integers, often denote by \(2 \mathbb{Z}\), is defined by

\[2\mathbb{Z} = \{2a ~|~ a \in \mathbb{Z}\} .\]

Instead of the vertical bar, |, a colon, :, is also commonly used. For example, the open interval of the real numbers strictly between \(0\) and \(1\) is defined by

\[(0, 1) = \{x \in \mathbb{R} : 0 < x < 1\}.\]

Definition B.2.1. Let \(A\) and \(B\) be sets. \(B\) is a subset of \(A\), denoted by \(B \subset A\), if and only if for all \(b \in B\) we have \(b \in A.\) If \(B \subset A\) and \(B \neq A,\) we say that \(B\) is a proper subset of \(A.\)

If \(B \subset A\), one also says that \(B\) is contained in \(A\), or that \(A\) contains \(B\), which is sometimes denoted by \(A \supset B.\) The relation \(\subset\) is called inclusion. If \(B\) is a proper subset of \(A\) the inclusion is said to be strict. To emphasize that an inclusion is not necessarily strict, the notation \(B \subseteq A\) can be used but note that its mathematical meaning is identical to \(B \subset A.\) Strict inclusion is sometimes denoted by \(B \subsetneq A\), but this is less common.

Example B.2.2. The following relations between sets are easy to verify:

1. We have \(\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}\), and all these inclusions are strict.
2. For any set \(A\), we have \( \emptyset \subset A\), and \(A \subset A.\)
3. \((0, 1] \subset (0, 2).\)
4. For \(0 < a \leq b, [-a, a] \subset [-b, b].\) The inclusion is strict if \(a < b.\)

In addition to constructing sets directly, sets can also be obtained from other sets by a number of standard operations. The following definition introduces the basic operations of taken the union, intersection, and difference of sets.

Definition B.2.3. Let \(A\) and \(B\) be sets. Then

1. The union of \(A\) and \(B\), denoted by \(A \cup B\), is defined by \[A \cup B = \{x ~|~ x \in A {\it{~or~}} x \in B\}.\]
2. The intersection of \(A\) and \(B\), denoted by \(A \cap B\), is defined by \[A \cap B = \{x~ |~ x \in A {\it{~and~}} x \in B\}.\]
3. The set difference of \(B\) from \(A\), denoted by \(A \setminus B\), is defined by \[A \setminus B = \{x ~|~ x \in A {\it{~and~}} x \not\in B\}.\]

Often, the context provides a ‘universe’ of all possible elements pertinent to a given discussion. Suppose, we have given such a set of ‘all’ elements and let us call it \(U\). Then, the complement of a set \(A\), denoted by \(A^c\) , is defined as \(A^c = U \setminus A.\) In the following theorem the existence of a universe \(U\) is tacitly assumed.

Theorem B.2.4. Let \(A, B,\) and \(C\) be sets. Then

1. (distributivity) \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\) and \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C).\)
2. (De Morgan’s Laws) \((A \cup B)^c = A^c \cap B^c\) and \((A \cap B)^c = A^c \cup B^c .\)
3. (relative complements) \(A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)\) and \(A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C).\)

To familiarize your self with the basic properties of sets and the basic operations if sets, it is a good exercise to write proofs for the three properties stated in the theorem.

The so-called Cartesian product of sets is a powerful and ubiquitous method to construct new sets out of old ones.

Definition B.2.5. Let \(A\) and \(B\) be sets. Then the Cartesian product of \(A\) and \(B\), denoted by \(A \times B\), is the set of all ordered pairs \((a, b),\) with \(a \in A\) and \(b \in B.\) In other words,

\[A \times B = \{(a, b) ~|~ a \in A, b \in B\} .\]

An important example of this construction is the Euclidean plane \(\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}\). It is not an accident that \(x\) and \(y\) in the pair \((x, y)\) are called the Cartesian coordinates of the point \((x, y)\) in the plane.

In this section we introduce two important types of relations: order relations and equivalence relations. A relation \(R\) between elements of a set \(A\) and elements of a set \(B\) is a subset of their Cartesian product: \(R \subset A \times B.\) When \(A = B\), we also call \(R\) simply a relation on \(A\).

Let \(A\) be a set and \(R\) a relation on \(A\). Then,

• \(R\) is called reflexive if for all \(a \in A, (a, a) \in R.\)
• \(R\) is called symmetric if for all \(a, b \in A,\) if \((a, b) \in R\) then \((b, a) \in R.\)
• \(R\) is called antisymmetric if for all \(a, b \in A\) such that \((a, b) \in R\) and \((b, a) \in R, a = b.\)
• \(R\) is called transitive if for all \(a, b, c \in A\) such \((a, b) \in R\) and \((b, c) \in R\), we have \((a, c) \in R.\)

Definition B.3.1. Let \(R\) be a relation on a set \(A\). \(R\) is an order relation if \(R\) is reflexive, antisymmetric, and transitive. \(R\) is an equivalence relation if \(R\) is reflexive, symmetric, and transitive.

The notion of subset is an example of an order relation. To see this, first define the power set of a set \(A\) as the set of all its subsets. It is often denoted by \({\cal{P}}(A).\) So, for any set \(A, {\cal{P}}(A) = \{B : B \subset A\}.\) The, the inclusion relation is defined as the relation \(R\) by setting

\[R = \{(B, C) \in {\cal{P}}(A) \times {\cal{P}}(A)~ |~ B \subset C\}\]

Important relations, such as the subset relation, are given a convenient notation of the form \(a <symbol> b\), to denote \((a, b) \in R.\) The symbol for the inclusion relation is \(\subset\).

Proposition B.3.2. Inclusion is an order relation. Explicitly,

1. (reflexive) For all \(B \in {\cal{P}}(A), B \subset B.\)
2. (antisymmetric) For all \(B, C \in {\cal{P}}(A),\) if \(B \subset C\) and \(C \subset B\), then \(B = C.\)
3. (transitive) For all \(B, C, D \in {\cal{P}}(A),\) if \(B \subset C\) and \(C \subset D,\) then \(B \subset D.\)

Write a proof of this proposition as an exercise.

For any relation \(R \subset A \times B\), the inverse relation, \(R^{-1} \subset B \times A\), is defined by

\[R^{-1} = \{(b, a) \in B \times A ~| ~(a, b) \in R\}.\]

Let \(A\) and \(B\) be sets. A function with domain \(A\) and codomain \(B\), denoted by \(f : A \rightarrow B\), is relation between the elements of \(A\) and \(B\) satisfying the properties: for all \(a \in A,\) there is a unique \(b \in B\) such that \((a, b) \in f \). The symbol used to denote a function as a relation is an arrow: \((a, b) \in f\) is written as \(a \rightarrow b\) (often also \(a \mapsto b\)). It is not necessary, and a bit cumbersome, to remind ourselves that functions are a special kind of relation and a more convenient notation is used all the time: \(f (a) = b.\) If \(f\) is a function we then have, by definition, \(f (a) = b\) and \(f (a) = c\) implies \(b = c\). In other words, for each \(a \in A\), there is exactly one \(b \in B\) such that \(f (a) = b.\) \(b\) is called the image of a under \(f\) . When \(A\) and \(B\) are sets of numbers, \(a\) is sometimes referred to as the argument of the function and \(b = f (a)\) is often referred to as the value of \(f\) in \(a\).

The requirement that there is an image \(b \in B\) for all \(a \in A\) is sometimes relaxed in the sense that the domain of the function is a, sometimes not explicitly specified, subset of \(A\). It important to remember, however, that a function is not properly defined unless we have also given its domain.

When we consider the graph of a function, we are relying on the definition of a function as a relation. The graph \(G\) of a function \(f : A \rightarrow B\) is the subset of \(A \times B\) defined by

\[G = \{(a, f (a)) ~|~ a \in A\}.\]

The range of a function \(f : A \rightarrow B\), denoted by \(range (f ),\) or also \(f (A),\) is the subset of its codomain consisting of all \(b \in B\) that are the image of some \(a \in A:\)

\[range (f ) = \{b \in B ~|~ {\rm{~there ~exists~}} a \in A {\rm{~such ~that~}} f (a) = b\}.\]

The pre-image of \(b \in B\) is the subset of all \(a \in A\) that have \(b\) as their image. This subset if often denoted by \(f^{-1} (b).\)

\[f^{-1} (b) = \{a \in A ~|~ f (a) = b\}.\]

Note that \(f^{-1} (b) = \emptyset\) if and only if \(b \in B \setminus range (f ).\)

Functions of various kinds are ubiquitous in mathematics and a large vocabulary has developed, some of which is redundant. The term map is often used as an alternative for function and when the domain and codomain coincide the term transformation is often used instead of function. There is large number of terms for functions in particular context with special properties. The three most basic properties are given in the following definition.

Definition B.4.1. Let \(f : A \rightarrow B\) be a function. Then we call \(f\)

1. injective (\(f\) is an injection) if \(f (a) = f (b)\) implies \(a = b\). In other words, no two elements of the domain have the same image. An injective function is also called one-to-one.
2. surjective (\(f\) is a surjection) if \(range (f ) = B.\) In other words, each \(b \in B\) is the image of at least one \(a \in A\). Such a function is also called onto.
3. bijective (\(f\) is a bijection) if \(f\) is both injective and surjective, i.e., one-to-one and onto. This means that f gives a one-to-one correspondence between all elements of \(A\) and all elements of \(B\).

Let \(f : A \rightarrow B\) and \(g : B \rightarrow C\) be two functions so that the codomain of \(f\) coincides with the domain of \(g\). Then, the composition ‘\(g\) after \(f\) ’, denoted by \(g \circ f\) , is the function \(g \circ f : A \rightarrow C,\) defined by \(a \mapsto g(f (a)).\)

For every set \(A\), we define the identity map, which we will denote here by \({\rm{id}}_A\) or \({\rm{id}}\) for short. \({\rm{id}}_A : A \rightarrow A\) is defined by \({\rm{id}}_A (a) = a\) for all \(a \in A\). Clearly, \({\rm{id}}_A\) is a bijection.

If \(f\) is a bijection, it is invertible, i.e., the inverse relation is also a function, denoted by \(f^{ -1} \). It is the unique bijection \(B \rightarrow A\) such that \(f^{-1} \circ f = {\rm{id}}_A\) and \(f \circ f^{-1 }= {\rm{id}}_B\) .

Proposition B.4.2. Let \(f : A \rightarrow B\) and \(g : B \rightarrow C\) be bijections. Then, their composition \(g \circ f\) is a bijection and

\[(g \circ f )^{-1} = f^{ -1} \circ g^{ -1} .\]

Prove this proposition as an exercise.