Sets, Functions, Relations and Equivalence Classes

If X and Y are (not necessarily distinct) sets, then their cartesian product X × Y is the set of all ordered pairs (x, y), where x ∈X and y ∈Y. The plane is R × R. Observe that if X and Y are finite sets, say, |X| = m and |Y| = n (we denote the number of elements in a finite set X by |X|), then |X × Y| = mn. Some Set Theory

A function f : X →Y is a surjection (or is onto) if im f = Y. Thus, f is surjective if, for each y ∈Y, there is some x ∈X (probably depending on y) with y = f (x). The following definition gives another important property a function may have.

A function f : X →Y is an injection (or is one-to-one) if, whenever a and a′ are distinct elements of X, then f (a) ̸= f (a′). Equivalently (the contrapositive states that) f is injective if, for every pair a, a′ ∈X, we have f (a) = f (a′) implies a = a′. The reader should note that being injective is the converse of being well-defined: f is well-defined if a = a′ implies f (a) = f (a′); f is injective if f (a) = f (a′) implies a = a′. There are other names for these functions. Surjections are often called epimorphisms and injections are often called monomorphisms. The notation A ↠B is used to denote a surjection, and the notations A }→B or A ↣B are used to denote injections.

A function f : X →Y is a bijection (or a one-to-one correspondence) if it is both an injection and a surjection. Some Set Theory

A function f : X →Y has an inverse if there is a function g : Y →X with both composites g ◦f and f ◦g being identity functions.

If X and Y are sets, then a relation from X to Y is a subset R ⊆X × Y. We usually write x R y to denote (x, y) ∈R. If X = Y, then we say that R is a relation on X. Let us give a concrete illustration to convince the reader that this definition is reasonable. Let R = {(x, y) ∈R × R : (x, y) lies on or above the line y = x}. The reader should recognize that x R y holds if and only if, in the usual sense, x ≤y.

A relation x ≡y on a set X is reflexive: if x ≡x for all x ∈X; symmetric: if x ≡y implies y ≡x for all x, y ∈X; transitive: if x ≡y and y ≡z imply x ≡z for all x, y, z ∈X. A relation that has all three properties—reflexivity, symmetry, and transitivity—is called an equivalence relation.

A family of subsets Ai of a set X is called pairwise disjoint if Ai ∩A j = ∅ for all i ̸= j. A partition of a set X is a family of pairwise disjoint nonempty subsets, called blocks, whose union is all of X.

Let f : X →Y and g : X →Y be functions. Then f = g if and only if f (a) = g(a) for every a ∈X. Remark. This proposition resolves the problem raised by the ambiguous term rule. If f , g : R →R are given by f (x) = (x + 1)2 and g(x) = x2 + 2x + 1, then f = g because f (a) = g(a) for every number a. ◀

(i) Composition is associative: If f : X →Y, g : Y →Z, and h : Z →W are functions, then h ◦(g ◦f ) = (h ◦g) ◦f. (ii) If f : X →Y, then 1Y ◦f = f = f ◦1X.

(i) If f : X →Y and g : Y →X are functions such that g ◦f = 1X, then f is injective and g is surjective. (ii) A function f : X →Y has an inverse g: Y →X if and only if f is a bijection.

If the set of all the bijections from a set X to itself is denoted by SX, then composition of functions satisfies the following properties: (i) if f , g ∈SX, then f ◦g ∈SX; (ii) h ◦(g ◦f ) = (h ◦g) ◦f for all f, g, h ∈SX; (iii) the identity 1X lies in SX, and 1X ◦f = f = f ◦1X for every f ∈SX; (iv) for every f ∈SX, there is g ∈SX with g ◦f = 1X = f ◦g.

Let X and Y be sets, and let f : X →Y be a surjection. (i) If T ⊆S are subsets of X, then f (T ) ⊆f (S), and if U ⊆V are subsets of Y, then f −1(U) ⊆f −1(V ). (ii) If U ⊆Y, then f f −1(U) = U. (iii) The composite f∗f ∗: P(Y) →P(Y) = 1P(Y), and so f ∗: W ↦f −1(W) is an injection. (iv) If S ⊆X, then S ⊆f −1 f (S), but strict inclusion is possible. Remark. If f is not a surjection, then W ↦f −1(W) need not be an injection: There is some y ∈Y with y /∈f (X), and f −1({y}) = ∅= f −1(∅). ◀

If ≡is an equivalence relation on a set X, then the equivalence classes form a partition of X. Conversely, given a partition {Ai : i ∈I} of X, there is an equivalence relation on X whose equivalence classes are the blocks Ai.

Our definitions allow us to treat a degenerate case. If X is a set, what are the functions X →∅? Note first that an element of X × ∅is an ordered pair (x, y) with x ∈X and y ∈∅; since there is no y ∈∅, there are no such ordered pairs, and so X × ∅= ∅. Now Some Set Theory a function X →∅is a subset of X × ∅of a certain type; but X × ∅= ∅, so there is only one subset, namely ∅, and hence at most one function, namely, f = ∅. The definition of function X →∅says that, for each x ∈X, there exists a unique y ∈∅with (x, y) ∈f . If X ̸= ∅, then there exists x ∈X for which no such y exists (there are no elements y at all in ∅), and so f is not a function. Thus, if X ̸= ∅, there are no functions from X to ∅. On the other hand, if X = ∅, then f = ∅is a function. Otherwise, the negation of the statement “ f is a function” begins “there exists x ∈∅, etc.” We need not go on; since ∅has no elements in it, there is no way to complete the sentence so that it is a true statement. We conclude that f = ∅is a function ∅→∅, and we declare it to be the identity function 1∅. ◀ The special case when the image of a function is the whole target has a name.

(i) We have just seen that an equivalence relation can be defined on a set from a partition. Let I = [0, 1] be the closed unit interval, and define a partition of I whose blocks are the 2point set {0, 1} and all the 1-point sets {a}, where 0 < a < 1. The family of all the blocks, that is, of all the equivalence classes, can be viewed as a circle, for we have identified the two endpoints of the interval. Here is another construction of the circle, now from R instead of from I. Define a relation on R by a ≡b if a −b ∈Z. The family of all blocks is again the circle (we have identified the endpoints of any interval of length 1). (ii) Define an equivalence relation on the square I×I in which the blocks are {(a, 0), (a, 1)}, one for each a ∈I, {(0, b), (1, b)}, one for each b ∈I, as well as all the singleton sets {(a, b)} in the interior of the square. The family of all equivalence classes can be viewed as a torus (the surface of a doughnut): Identifying the left and right sides of the square gives a cylinder, and further identifying the top and bottom ends of the cylinder gives a torus. ◀