2.2. Sets, Relations and Functions

Sets are absolutely basic entities used throughout the present-day study of mathematics. Unfortunately, however, we cannot define sets. Loosely speaking, a set is an (unordered) collection of objects. But we run into difficulty with this definition for collections that are too big. Of course, infinite sets like the set of all integers or real numbers are not too big. However, a collection of all sets is too big to be called a set. (Also see Exercise 2.6.) It is, therefore, customary to have an axiomatic definition of sets. That is to say, a collection qualifies to be a set if it satisfies certain axioms. We do not go into the details of this axiomatic definition, but tell the axioms as properties of sets. Luckily enough, we won’t have a chance in the rest of this book to deal with collections that are not sets. So the reader can, for the time being, have faith in the above (wrong) identification of a set as a collection.

An object in a set is commonly called an element of A. By the notation , we mean that a is an element of the set A. Often a set A can be represented explicitly by writing down its elements within curly brackets or braces. For example, A = {2, 3, 5, 7} denotes the set consisting of the elements 2, 3, 5, 7 which are incidentally all the (positive) prime numbers less than 10. We often use the ellipsis sign (. . .) to denote an infinite (or even a finite) set. For example, would denote the set of all (positive) prime numbers. (We prove later that is an infinite set.) Alternatively, we often describe a set by mentioning the properties of the elements of the set. For example, the set can also be described as .

Some frequently occurring sets are denoted by special symbols. We list a few of them here.

	The set of all natural numbers, that is, {1, 2, 3, . . .}
	The set of all non-negative integers, that is, {0, 1, 2, . . .}
	The set of all integers, that is, {. . . , –2, –1, 0, 1, 2, . . .}
	The set of all (positive) prime numbers, that is, {2, 3, 5, 7, . . .}
	The set of all rational numbers, that is,
	The set of all non-zero rational numbers
	The set of all real numbers
	The set of all non-zero real numbers
	The set of all complex numbers
	The set of all non-zero complex numbers
	The empty set

The cardinality of a set A is the number of elements in A. We use the symbol #A to denote the cardinality of A. If #A is finite, we call A a finite set. Otherwise A is said to be infinite. The empty set has cardinality zero.

2.2.1. Set Operations

Let A and B be two sets. We say that A is a subset of B and denote this as A ⊆ B, if all elements of A are in B. Two sets A and B are equal (that is, A = B) if and only if A ⊆ B and B ⊆ A. A is said to be a proper subset of B (denoted ), if A ⊆ B and A ≠ B (that is, B ⊈ A).

The union of A and B is the set whose elements are either in A or in B (or both). This set is denoted by A ∪ B. The intersection of A and B is the set consisting of elements that are common to A and B. The intersection of A and B is denoted by A ∩ B. If , then we say that A and B are disjoint. In that case, the union A∪B is also called a disjoint union and is referred to as by A⊎B. (For a generalization, see Exercise 2.7.) The difference of A and B, denoted A B, is the set whose elements are in A but not in B. If A is understood from the context and B ⊆ A, then we denote A B by and refer to as the complement of B (in A). The product A × B of two sets A and B is the set of all ordered pairs (a, b) where and .

The notion of union, intersection and product of sets can be readily extended to an arbitrary family of sets. Let A_i, , be a family of sets indexed by I. In this case, we denote the union and intersection of A_i, , by and respectively. The product of A_i, , is denoted by . When A_i = A for all , we denote the product also as A^I. If, in addition, I is a finite set of cardinality n, then the product A^I is also written as Aⁿ.

2.2.2. Relations

A relation ρ on a set A is a subset of A × A. For , we usually say a ρ b implying that a is related by ρ to b. Common examples are the standard relations =, ≠, ≤, <, ≥, > on (or or ).

A relation ρ on a set A is called reflexive, if a ρ a for all . For example, =, ≤ and ≥ are reflexive relations on , but the relations ≠, <, > are not.

A relation ρ on A is called symmetric, if a ρ b implies b ρ a. On the other hand, ρ is called anti-symmetric if a ρ b and b ρ a imply a = b. For example, = is symmetric and anti-symmetric, <, ≤, > and ≥ are anti-symmetric but not symmetric, ≠ is symmetric but not anti-symmetric.

A relation ρ on A is called transitive if a ρ b and b ρ c imply a ρ c, For example, =, <, ≤, >, ≥ are all transitive, but ≠ is not transitive.

An equivalence relation is one which is reflexive, symmetric and transitive. For example, = is an equivalence relation on , but neither of the other relations mentioned above (≠, <, ≥ and so on) is an equivalence relation on .

A partition of a set A is a collection of pairwise disjoint subsets A_i, , of A, such that , that is, A is the union of A_i, , and for i, , i ≠ j, . The following theorem establishes an important connection between equivalence relations and partitions.

Theorem 2.1.

The subset [a] of A defined in the proof of the above theorem is called the equivalence class of a with respect to the equivalence relation ρ.

An anti-symmetric and transitive relation is called a partial order (or simply an order). All of the relations =, ≤, <, ≥, > are partial orders on (but ≠ is not). A partial order ρ on A is called a total order or a linear order or a simple order, if for every a, , a ≠ b, either a ρ b or b ρ a. For example, if we take A = {1, 2, 3} and the relation ρ = {(1, 2), (1, 3)}, then ρ is a partial order but not a total order (because it does not specify a relation between 2 and 3). On the other hand, ρ′ = {(1, 2), (1, 3), (2, 3)} is a total order. A set with a partial (resp. total) order is often called a partially ordered (resp. totally ordered or linearly ordered or simply ordered) set.

2.2.3. Functions

Let A and B two sets (not necessarily distinct). A function or a map f from A to B, denoted f : A → B, assigns to each some element . In this case, we write b = f(a) or f maps a ↦ b and say that b is the image of a (under f). For example, if , then the assignment a ↦ a² is a function. On the other hand, the assignment (the non-negative square root) is not a function, because it is not defined for negative values of a. However, if and , then the assignment (with non-negative real and imaginary parts) is a function.

The function f : A → A assigning a ↦ a for all is called the identity map on A and is usually denoted by id_A. On the other hand, if f : A → B maps all the elements of A to a fixed element of B, then f is said to be a constant function. A function which is not constant is called a non-constant function.

A function f : A → B that maps different elements of A to different elements of B is called injective or one-one. In other words, we call f to be injective if and only if f(a) = f(a′) implies a = a′. The function given by a ↦ a² is not injective, since f(–a) = f(a) for all . On the other hand, the function given by a ↦ 2a is injective. An injective map f : A → B is sometimes denoted by the special symbol f : A ↪ B.

The image of a function f : A → B is defined to be the following subset of . It is denoted by f(A) or by Im f. The function f is said to be surjective or onto or a surjection, if Im f = B, that is, every element b of B has at least one preimage (which means f(a) = b). As an example, the function given by a ↦ a/2 (if a is even) and by a ↦ (a – 1)/2 (if a is odd) is surjective, whereas the function that maps a → |a| (the absolute value) is not surjective. A surjective map f : A → B is sometimes denoted by the special symbol f : A ↠ B.

A map f : A → B is called bijective or a bijection, if it is both injective and surjective. For example, the identity map on a set is bijective. Another example of a bijective function is that maps a to the ath prime.

Let f : A → B and g : B → C be functions. The composition of f and g is the function from A to C that takes a ↦ g(f(a)). It is denoted by g ο f, that is, (g ο f)(a) = g(f(a)). Note that in the notation g ο f one applies f first and then g. The notion of composition of functions can be extended to more than two functions. In particular, if f : A → B, g : B → C and h : C → D are functions, then (h ο g) ο f and h ο (g ο f) are the same function from A to D, so that we can unambiguously write this as h ο g ο f.

2.2.4. The Axioms of Mathematics

The study of mathematics is based on certain axioms. We state four of these axioms. It is not possible to prove the axioms independently, but it can be shown that they are equivalent in the sense that each of them can be proved, if any of the others is assumed to be true.

Let A be a partially ordered set under the relation . An element is called maximal (resp. minimal), if there is no element , b ≠ a, that satisfies (resp. ). Let B be a non-empty subset of A. Then an upper bound (resp. a lower bound) for B is an element such that (resp. ) for all . If an upper bound (resp. a lower bound) a of B is an element of B, then a is called a last element or a largest element or a maximum element (resp. a first element or a least element or a smallest element or a minimum element) of B. By antisymmetry, it follows that a first (resp. last) element of B, if existent, is unique. A chain of A is a totally ordered (under ) subset of A.

Consider the sets , and with the natural order ≤. Neither of these sets contains a maximal element. contains a minimal element 1, but and do not contain minimal elements. The subset of even natural numbers has two lower bounds, namely 1 and 2, of which 2 is the first element of .

A totally ordered set A is said to be well ordered (and the relation is called a well order), if every non-empty subset B of A contains a first element.

Axiom 2.1. Zermalo’s well-ordering principle

The set is well-ordered under the natural relation ≤. The set can be well ordered by the relation defined as . A well ordering of is not known.

Axiom 2.2. Zorn’s lemma

To illustrate Zorn’s lemma, consider any non-empty set A and define to be the set of all subsets of A. is called the power set of A and is partially ordered under containment ⊆. A chain of is a set of subsets of A such that for all i, either A_i ⊆ A_j or A_j ⊆ A_i. Clearly, the union is an upper bound of the chain. Then Zorn’s lemma guarantees that has at least one maximal element. In this case, the maximal element, namely A, is unique. If A is finite, then for the set of all proper subsets of A, a maximal element (under the partial order ⊆) exists by Zorn’s lemma, but is not unique, if #A > 1.

Axiom 2.3. Hausdorff’s maximal principle

Finally, let A be a set and , that is, is the set of all non-empty subsets of A. A choice function of A is a function such that for every we have .

Axiom 2.4. Axiom of choice

Exercise Set 2.2

2.1	Let G = (V, E) be an undirected graph. Define a relation ρ on the vertex set V of G by: u ρ v if and only if there is a path from u to v. Show that ρ is an equivalence relation on V. What are the equivalence classes for this relation? Let G = (V, E) be a directed acyclic graph. Define the relation ρ on V as in (a). Show that ρ is a partial order on V. When is ρ a total order?
2.2	Let f : A → B and g : B → A be functions. Show that if f ο g = idB, then g is injective and f is surjective. In particular, f (and also g) is bijective, if f ο g = idB and g ο f = idA. In this case, we call g to be the inverse of f and denote this as g = f–1. Show by examples that both the conditions f ο g = idB and g ο f = idA are necessary for f to be bijective.
2.3	Let f : A → B a map from a finite set A to a finite set B. Prove that #A ≤ #B, if f is injective, #A ≥ #B, if f is surjective, and #A = #B, if f is bijective.
2.4	Let A be a finite set and let f : A → A be a map. Show that the following conditions are equivalent. f is injective. f is surjective. f is bijective. Show by examples that this equivalence need not hold, if A is an infinite set.
2.5	Let A and B be two arbitrary sets, f : A → B a map, A′ ⊆ A and B′ ⊆ B. We define and . Show that: If A′ ⊆ A″ ⊆ A, then f(A′) ⊆ f(A″). If B′ ⊆ B″ ⊆ B, then f–1(B′) ⊆ f–1(B″). f–1(f(A′)) ⊇ A′. f(f–1(B′)) ⊆ B′. f(f–1(f(A′))) = f(A′). f–1(f(f–1(B′))) = f–1(B′).
2.6	Russell’s paradox A collection C is called ordinary, if C is not a member of C. A collection which is not ordinary is called extraordinary. Show that the collection of all ordinary collections is neither ordinary nor extraordinary.
2.7	Let Ai, , be a family of sets (not necessarily pairwise disjoint). For each , consider the set . Show that the family Bi, , are pairwise disjoint. The union is called the disjoint union of Ai, .