Sets, Relations and Functions

Sets, relations and functions are the vocabulary of data: a table is a relation, a database query is a set operation, a hash is a function. This unit defines them precisely and shows how to count and classify them.

2.1 Sets and their operations

A set is an unordered collection of distinct objects. Notation: roster {1, 2, 3}; builder \{x \mid x i s \mathrm{even} \mathrm{and} x < 10\}.

∅ is the empty set; U the universal set; |A| the cardinality; x \in A membership; A \subseteq B subset; A \subset B proper subset.

Operation	Definition
Union A \cup B	in A or B
Intersection A \cap B	in both
Difference A - B	in A but not B
Complement A'	in U but not A
Symmetric difference A \oplus B	in exactly one: (A - B) \cup (B - A)
Cartesian product A \times B	all ordered pairs (a ,\ b); |A × B| = |A| \cdot |B|
Power set P (A)	the set of all subsets; |P (A)| = 2^{|A|}

Set identities mirror logic: A \cup (B \cap C) = (A \cup B) \cap (A \cup C) ;\ (A \cup B)' = A' \cap B' (De Morgan); A \cup A' = U ;\ A \cap A' = \emptyset ;\ A - B = A \cap B'.

Prove equality by showing each side is a subset of the other, or by a membership table.

Inclusion–exclusion. |A ∪ B| = |A| + |B| − |A ∩ B|; |A ∪ B ∪ C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.

Russell, and the set of all subsets

The size of a set grows very fast when we a s k for all its subsets. A set with n elements has 2^{n} subsets, because every element is either in or out.

Bertrand Russell showed in 1901 that talking about "the set of all sets" leads to a contradiction, which is why mathematics treats sets with care.

Plate 2.1 lists the eight subsets of {a, b, c} by counting in binary and shows the doubling for larger n.

(a) Bertrand Russell (1872-1970)

(b) Subsets of {a, b, c} by binary counting

2.2 Relations

A relation R from A to B is a subset of A \times B; "a R b" means (a ,\ b) \in R. A relation on A is a subset of A \times A. A relation can be shown as a set of pairs, a matrix (1 if related), or a digraph.

Properties of a relation R on A

Property	Meaning
Reflexive	(a ,\ a) \in R for all a
Irreflexive	(a ,\ a) \notin R for all a
Symmetric	(a ,\ b) \in R \Rightarrow (b ,\ a) \in R
Antisymmetric	(a ,\ b) and (b ,\ a) \in R \Rightarrow a = b
Transitive	(a ,\ b) ,\ (b ,\ c) \in R \Rightarrow (a ,\ c) \in R

An equivalence relation is reflexive, symmetric and transitive; it partitions A into equivalence classes. A partial order is reflexive, antisymmetric and transitive; (A ,\ \leq) is a poset, drawn as a Hasse diagram (omit loops and implied edges).

Counting relations. On an n-element set there are 2^{n^{2}} relations; 2^{n^{2} - n} reflexive ones; 2^{\frac{n (n + 1)}{2}} symmetric ones. For n = 3: 512, 64 and 64.

Composition and closures. R \circ S = \{(a ,\ c) \mid \exists b : (a ,\ b) \in S ,\ (b ,\ c) \in R\} (order convention varies; here S is applied first). In matrix form it is the Boolean matrix product.

The reflexive, symmetric and transitive closures are the smallest relations containing R with that property.

Databases: a relational table is a relation; a join is a composition-like operation; a primary key makes the relation a function from key to row.

2.3 Functions

A function f: A \to B assigns each a \in A exactly one f (a) \in B. Domain A, codomain B, range = set of actual outputs.

Type	Meaning	Test
Injective (one-to-one)	f (a) = f (a') \Rightarrow a = a'	no output hit twice
Surjective (onto)	every b has some a	range = codomain
Bijective	both	invertible

Composition (g \circ f) (x) = g (f (x)); composition of bijections is a bijection; a bijection has an inverse f^{-1} with f^{-1} \circ f = id.

Special functions: floor \lfloor x \rfloor, ceiling \lceil x \rceil, mod, characteristic function of a set, recursive functions (Unit 4). Growth of functions (big-O) uses these: n \log n \ll n^{2} \ll 2^{n} \ll n !.

2.4 Cardinality and countability

Two sets have the same cardinality if a bijection exists between them.

A set is countable if it is finite or has the same size as \mathbb{N}. \mathbb{Z} is countable (list 0 ,\ 1 ,\ - 1 ,\ 2 ,\ - 2 ,\ \ldots ) ;\ \mathbb{Q} is countable; the set of all finite strings over a finite alphabet is countable (so the set of all programs is countable).

\mathbb{R} is uncountable (Cantor's diagonal argument): any list of reals in (0,1) misses the number whose nth digit differs from the nth digit of the nth number.

Consequence: there are more functions \mathbb{N} → {0,1} than programs, so some functions are not computable.

Cantor: some infinities are bigger

Georg Cantor compared infinite sets by pairing their members. The natural numbers and the even numbers can be paired one to one (n with 2 n), so they have the same size even though the evens look like half.

The real numbers cannot be listed at all: whatever list is given, change the diagonal digit of every entry and the new sequence differs from each row. Plate 2.2 pairs the numbers and runs the diagonal argument on a small list.

(a) Georg Cantor (1845-1918)

(b) A one-to-one pairing and the diagonal argument

2.5 Three kinds of function in one picture

A function assigns to every element of the domain exactly one element of the codomain. Three questions classify it (Figure 2.1). Is every codomain element hit? If yes it is surjective (onto). Does any codomain element get hit twice?

If no, it is injective (one-to-one). If both hold the function is bijective, and only a bijection has an inverse. Counting also becomes easy: between two finite sets of the same size n, there are n ! bijections.

2.6 Eight uses of sets, relations and functions

1. Databases. A table is a relation, a row is a tuple, and the join of two tables is the composition of relations. SQL's UNION, INTERSECT and EXCEPT are set operations. The structure of a school database is relational algebra at work.
2. Hashing and look-up. A hash function maps keys (names, citizenship numbers) into table slots. It is a function that is intentionally not injective, and collisions are the price. Knowing injectivity explains why collisions must be handled.
3. Data types and programming. A type is a set of values, a function signature is a domain and codomain, and a pure function maps every input to one output. Thinking in sets prevents many type bugs.
4. Equivalence and grouping. An equivalence relation partitions a set into classes. Clustering users, merging duplicate student records and congruence classes mod n use this idea.
5. Orderings and scheduling. A partial order such as "course A must come before B" is a relation. Sorting the courses so that all prerequisites come first is a topological sort. Every timetable system relies on it.
6. Encryption and codes. Encryption must be a bijection, otherwise two messages would share one ciphertext and decryption would be impossible. Checksum and error-detecting codes are functions with chosen properties.
7. Counting data. The size of the power set, 2^{n}, counts the possible subsets of n features or permissions. A system with 10 permissions has 1,024 possible permission sets.
8. Infinite data and limits of computing. Cardinality shows that there are more real numbers than programs, so some functions cannot be computed at all. This is the first step towards the theory of computation.

Formula and fact sheet

• |P (A)| = 2^{n}; |A × B| = |A| |B|; |A ∪ B| = |A| + |B| − |A ∩ B|.
• Equivalence = reflexive + symmetric + transitive (partitions); partial order = reflexive + antisymmetric + transitive.
• Relations on n-set: 2^{n^{2}}; reflexive 2^{n^{2} - n}; symmetric 2^{\frac{n (n + 1)}{2}}.
• Functions A \to B: |B|^{|A|}; injective \frac{n !}{(n - m) !}; onto by inclusion–exclusion.
• Pigeonhole: n + 1 objects in n boxes ⇒ a box with two.
• \mathbb{N} ,\ \mathbb{Z} ,\ \mathbb{Q} countable; \mathbb{R} uncountable.

Chapter summary

• Sets and bit strings: union, intersection and complement are the logical operators applied to membership.
• Relations capture structure (equivalence → partitions, order → posets); closures add forced pairs.
• Functions classified as injective, surjective, bijective; counting uses powers, falling factorials and inclusion–exclusion.
• Cardinality separates countable from uncountable infinities, with consequences for computability.

Practice

1. If A = {1, 2, 3, 4}, B = {3, 4, 5}, U = \{1 ,\ \ldots ,\ 6\}, find A \cup B ,\ A \cap B ,\ A - B ,\ B' ,\ A \oplus B ,\ |P (A)|, |A × B|.
2. Of 100 students 70 like cricket, 55 like football and 25 like neither. How many like both?
3. Prove (A \cup B)' = A' \cap B'.
4. Test the relation R on \mathbb{Z}: a R b iff a - b is even; classify and give the classes.
5. Is "divides" on positive integers an equivalence relation? A partial order?
6. Find the transitive closure of {(a, b), (b, c), (c, a)} on {a, b, c}.
7. How many reflexive and symmetric relations on a 4-element set?
8. Classify f (x) = x^{3} on \mathbb{R} \to \mathbb{R} and f (n) = n mod 5 on \mathbb{Z} \to \{0 ,\ \ldots ,\ 4\}.
9. Count the functions from a 3-set to a 5-set, and the injective ones.
10. Show that the set of positive rationals is countable (describe the listing).

Answers and worked solutions

1. A \cup B = {1,2,3,4,5}; A \cap B = {3,4}; A - B = {1,2}; B' = {1,2,6}; A \oplus B = {1,2,5}; |P (A)| = 16; |A × B| = 12.

2. Likes at least one = 100 - 25 = 75 = 70 + 55 − both ⇒ both = 50.

3. x \in (A \cup B)' \Leftrightarrow \neg (x \in A \vee x \in B) \Leftrightarrow x \notin A \wedge x \notin B \Leftrightarrow x \in A' \cap B'. ∎

4. Reflexive (0 is even), symmetric, transitive (even + even = even): an equivalence with two classes: the evens and the odds.

5. Not symmetric (2 | 4, 4 ∤ 2), so not an equivalence. It is reflexive, antisymmetric and transitive: a partial order.

6. The closure is all nine pairs of {a, b, c}²: a \to b \to c \to a lets every element reach every element, including itself.

7. Reflexive: diagonal pairs forced (4). Symmetric on the 6 off-diagonal pairs: 2^{6} = 64 relations that are both.

8. x^{3} is a bijection on \mathbb{R}. n mod 5 is onto but not injective.

9. 5^{3} = 125; injective: 5·4·3 = 60.

10. Arrange \frac{p}{q} in a grid by numerator p and denominator q; walk the diagonals p + q = 2 ,\ 3 ,\ 4 ,\ \ldots skipping fractions not in lowest terms; every positive rational appears exactly once, giving a bijection with \mathbb{N}.

Model answers: medium (5 marks) and long (10 marks) questions

Q1 (5 marks). Show that the relation "a ≡ b (mod 3)" on A = {1, 2, 3, 4, 5, 6} is an equivalence relation and list its classes.

Introduction. A relation is an equivalence relation if it is reflexive, symmetric and transitive. Here a R b means that 3 divides a - b.

Reflexive. a - a = 0 is divisible by 3, so a R a for every a.

Symmetric. If 3 divides a - b, it divides b - a = - (a - b), so a R b implies b R a.

Transitive. If 3 | (a - b) and 3 | (b - c), then 3 divides the sum (a - b) + (b - c) = a - c, so a R c.

Classes. The remainders on division by 3 give {1, 4}, {2, 5} and {3, 6}. They are disjoint and cover A, so they form a partition; the relation has 3 classes.

Conclusion R is an equivalence relation with the three classes above.

Q2 (10 marks). Define injective, surjective and bijective functions, composition and inverse, with examples; state the number of subsets of a set.

Introduction. A function f: A \to B sends each element of A to exactly one element of B. Its type is decided by how it covers B (Figure 2.1).

Types.

1. Injective. f (x) = f (y) implies x = y. Example: f (x) = 2 x on the integers; different inputs give different outputs.
2. Surjective. Every b in B equals f (a) for some a. Example: f (x) = 2 x is not surjective onto the integers, since 3 is never reached.
3. Bijective. Both. Example: g (x) = x + 3 on the integers.
4. Test for finite sets. An injective map between sets of the same finite size is automatically bijective.

Composition and inverse.

5. Composition. (g \circ f) (x) = g (f (x)). With f (x) = 2 x and g (x) = x + 3 ,\ (g \circ f) (x) = 2 x + 3, whereas (f \circ g) (x) = 2 x + 6, so composition is not commutative.
6. Inverse. Only a bijection has an inverse. For g (x) = x + 3 ,\ g^{-1} (x) = x - 3, and g^{-1} (g (x)) = x.
7. Composition of bijections is a bijection, and (g \circ f)^{-1} = f^{-1} \circ g^{-1}.

Counting.

8. Subsets. A set of n elements has 2^{n} subsets, so A = {1, 2, 3} has 8, and there are n ! bijections from A to a set of the same size (here 6).

Type	Condition	Example
Injective	no two inputs share an output	2 x on integers
Surjective	every output is reached	x^{3} on the reals
Bijective	both	x + 3
Inverse exists	iff bijective	x - 3

Conclusion. Injectivity, surjectivity and bijectivity describe how a function covers its codomain, and only bijections can be undone.