1.

Motivation to Relations and Formal Definition

In everyday life, we constantly talk about relationships between objects or people. For
instance:

●​ "Alex is the brother of Ben."

●​ "5 is less than 10."
●​ "New York City is in the state of New York."
●​ "Calculus I is a prerequisite for Calculus II."

Each of these phrases in bold describes a connection or relationship between two entities. In
mathematics, we need a precise, formal way to capture this idea of a connection. A relation
is the tool we use. It formally defines a relationship as a collection of ordered pairs of
elements that satisfy the specified connection. If "a is related to b," we represent this with the
ordered pair (a, b).

Example: A "Knows" Relation

Consider a group of four people: {Alice, Bob, Carol, David}. Let's define a "knows" relation
where (x, y) means "x knows y". The complete set of these connections might be:

●​ Alice knows Bob. -> (Alice, Bob)

●​ Bob knows Alice. -> (Bob, Alice)
●​ Bob knows Carol. -> (Bob, Carol)
●​ Carol knows David. -> (Carol, David)
●​ Alice knows David. -> (Alice, David)

The relation, which we can call K, is simply the set of these ordered pairs:

K = { (Alice, Bob), (Bob, Alice), (Bob, Carol), (Carol, David), (Alice, David) }.

This set precisely captures the "knows" relationship within this group.

Formal Definition

A binary relation R from a set A to a set B is a subset of the Cartesian product A x B. If (a, b)
is an element of R, we write a R b and say "a is related to b."

If A = B, the relation R is a binary relation on the set A.

2. Graphical Representation of Relations
A relation on a set A can be represented by a directed graph (or digraph).
1.​ Each element of the set A is represented by a dot, called a vertex.
2.​ If (a, b) is in the relation R, we draw a directed edge (an arrow) from vertex a to
vertex b.
3.​ If an element is related to itself, i.e., (a, a) is in R, we draw a loop at vertex a.

Example 1

Let A = {1, 2, 3, 4} and R = { (1,1), (1,2), (2,1), (2,3), (3,4), (4,1) }.

The graph would have 4 vertices (1, 2, 3, 4). The edges would be:

Example 2

Let B = {a, b, c} and S be the "is a predecessor of" relation in the alphabet.

S = { (a,b), (a,c), (b,c) }.

The graph would have 3 vertices (a, b, c). The edges would be:

3. Matrix Representation of Relations

A relation R from a set A = {a1, a2, ..., am} to a set B = {b1, b2, ..., bn} can be represented
by an m x n matrix M_R, called the relation matrix.
1.​ The rows are indexed by the elements of A and the columns by the elements of B.
2.​ The entry at row i and column j, denoted M_R[i, j], is defined as:
○​ M_R[i, j] = 1 if (ai, bj) is in R.
○​ M_R[i, j] = 0 if (ai, bj) is not in R.
Example 1

Let A = {1, 2, 3} and B = {x, y}. Let R = { (1,y), (2,x), (2,y), (3,x) }.

The matrix M_R is a 3x2 matrix.

Example 2

Let A = {1, 2, 3} and R be the "less than" relation on A, so R = { (1,2), (1,3), (2,3) }.

The matrix M_R is a 3x3 matrix.

4. Sets and Relations

The concept of a relation is fundamentally built upon the concept of a set. A relation is
nothing more than a specific kind of set: a set of ordered pairs.

Motivational Connection

Think of the set of all students in a school, S, and the set of all available courses, C. How do
we represent the relationship "is enrolled in"?

We can't just list the sets S and C. We need to explicitly link individual students to individual
courses. The most natural way to do this is to form pairs: (student, course). For example,
(John Smith, Math 101).

The entire enrollment list for the school is the set of all such pairs. This set of pairs is the "is
enrolled in" relation.
Formal Connection
1.​ To define a relation, we must first define the sets it connects. Let's have a set of
people A = {Alice, Bob} and a set of pets B = {Cat, Dog}.
2.​ To define the "universe" of all possible pairings between A and B, we form the
Cartesian Product A x B, which is {(Alice, Cat), (Alice, Dog), (Bob, Cat), (Bob,
Dog)}.
3.​ A specific relation, such as "owns", is then defined as a subset of this Cartesian
product. If Alice owns a cat and Bob owns a dog, the "owns" relation R is:​
R = { (Alice, Cat), (Bob, Dog) }.
4.​ Notice that R is a subset of A x B. This is the formal connection: A relation from A
to B is any subset of the power set of A x B.

5. Cartesian Product
Motivation

Before we can talk about a specific relationship between elements from two sets, A and B,
we first need a way to describe the set of all possible pairings of an element from A with an
element from B. This complete set of all possible ordered pairs serves as the universal set
from which any specific relation can be drawn. This universal set of pairs is called the
Cartesian Product.

Formal Definition

The Cartesian Product of two sets A and B, denoted A x B (read "A cross B"), is the set of all
possible ordered pairs (a, b) where a is an element of A and b is an element of B.

A x B = { (a, b) | a ∈ A and b ∈ B }.

The cardinality of the Cartesian product is given by |A x B| = |A| * |B|.

Example

Let A = {1, 2} (a set of numbers) and B = {a, b, c} (a set of letters).

●​ A x B = { (1,a), (1,b), (1,c), (2,a), (2,b), (2,c) }.

●​ |A| = 2, |B| = 3, so |A x B| = 2 * 3 = 6.

Note that the Cartesian product is not commutative: A x B ≠ B x A.

●​ B x A = { (a,1), (a,2), (b,1), (b,2), (c,1), (c,2) }.
6. Examples and Non-examples of Relations
A relation R on a set A must be a subset of A x A.

Let A = {1, 2, 3}. Then A x A = { (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3) }.

Examples of Relations
1.​ R1 = { (1,1), (2,2), (3,3) }. This is the "is equal to" relation on A. It is a valid relation
because every pair in R1 is also in A x A.
2.​ R2 = { (1,2), (1,3), (2,3) }. This is the "is less than" relation on A. It is a valid relation.
3.​ R3 = { (1,1), (1,2), (2,1), (2,2), (3,3) }. This is a valid relation.
4.​ R4 = ∅ (the empty set). This is a valid relation, representing a relationship that holds
for no pairs. It is a subset of A x A.

Non-examples of Relations
1.​ R5 = { (1, 4), (2, 3) }. This is not a relation on A because the pair (1, 4) is not in A x A
(since 4 is not in A).
2.​ R6 = { 1, (1,2) }. This is not a relation because 1 is not an ordered pair, so it cannot
be an element of A x A.

7. Number of Relations
Let A and B be two sets with cardinalities |A| = m and |B| = n.
1.​ The cardinality of the Cartesian product A x B is |A x B| = m * n.
2.​ A relation from A to B is defined as any subset of A x B.
3.​ The number of subsets of a set with k elements is given by 2^k (the cardinality of its
power set).
4.​ Therefore, the total number of possible relations from A to B is 2^(m*n).

If the relation is on a single set A with |A| = n, then m = n. The number of relations on A is
2^(n*n) or 2^(n^2).

Example:

How many relations are there on the set A = {a, b}?

●​ |A| = 2.
●​ The number of relations is 2^(2^2) = 2^4 = 16.
●​ A x A = {(a,a), (a,b), (b,a), (b,b)}. The 16 relations correspond to the 16 subsets of
this set, from the empty set ∅ to the full Cartesian product A x A.
8. Reflexive Relation
Definition: A relation R on a set A is reflexive if every element in A is related to itself.
●​ Formal condition: For every a ∈ A, (a, a) ∈ R.

Examples
1.​ The "is equal to" (=) relation on the set of integers is reflexive because every integer
is equal to itself (a = a).
2.​ The "less than or equal to" (<=) relation on the set of real numbers is reflexive
because a <= a is always true.
3.​ The "is a subset of" (⊆) relation on a collection of sets is reflexive because every set
is a subset of itself (A ⊆ A).
4.​ Non-example: The "is less than" (<) relation is not reflexive because a < a is never
true.

Matrix Representation

A relation R on A is reflexive if and only if all the elements on the main diagonal of its matrix
M_R are 1.

M_R[i, i] = 1 for all i.

This matrix represents a reflexive relation.

Number of Reflexive Relations

Let |A| = n. The matrix is n x n.

●​ There are n^2 total possible pairs in A x A.

●​ For a relation to be reflexive, the n pairs on the main diagonal, (a1,a1), (a2,a2), ...,
must be in the relation. There is only 1 choice for each of these (they must be
included).
●​ The remaining n^2 - n off-diagonal pairs can either be in the relation or not (2 choices
for each).
●​ The total number of reflexive relations is 1^n * 2^(n^2 - n) = 2^(n^2 - n).
9. Symmetric Relation
Definition: A relation R on a set A is symmetric if for every (a, b) ∈ R, the pair (b, a) is also
in R.
●​ Formal condition: If a R b, then b R a.

Examples
1.​ The "is equal to" (=) relation is symmetric. If a = b, then b = a.
2.​ The "is a sibling of" relation is symmetric. If Alice is a sibling of Bob, then Bob is a
sibling of Alice.
3.​ The "is on the same team as" relation is symmetric.
4.​ Non-example: The "less than or equal to" (<=) relation is not symmetric. 3 <= 5 is
true, but 5 <= 3 is false.

Matrix Representation

A relation R is symmetric if and only if its matrix M_R is symmetric, meaning the matrix is
equal to its transpose.

M_R[i, j] = M_R[j, i] for all i, j.

This matrix is symmetric. Notice the values are mirrored across the main diagonal.

Number of Symmetric Relations

Let |A| = n. The n x n matrix has n diagonal elements and n^2 - n off-diagonal elements. The
off-diagonal elements come in (n^2 - n) / 2 pairs of the form (i,j) and (j,i).

●​ For the n diagonal elements, we can either include (i,i) or not (2 choices each).
●​ For each of the (n^2 - n) / 2 pairs of off-diagonal positions, we make one choice:
either include both (i,j) and (j,i) or include neither. We cannot include one without the
other. This gives 2 choices for each pair of positions.
●​ The total number of symmetric relations is 2^n * 2^((n^2 - n)/2) = 2^(n + (n^2 - n)/2) =
2^((2n + n^2 - n)/2) = 2^((n^2 + n)/2) = 2^(n*(n+1)/2).
10. Transitive Relation
Definition: A relation R on a set A is transitive if for every (a, b) ∈ R and (b, c) ∈ R, the
pair (a, c) is also in R.
●​ Formal condition: If a R b and b R c, then a R c.

Examples
1.​ The "is equal to" (=), "less than" (<), and "less than or equal to" (<=) relations are all
transitive. If a < b and b < c, then a < c.
2.​ The "is an ancestor of" relation is transitive. If A is an ancestor of B, and B is an
ancestor of C, then A is an ancestor of C.
3.​ The "is a subset of" (⊆) relation is transitive. If A ⊆ B and B ⊆ C, then A ⊆ C.
4.​ Non-example: The "is the mother of" relation is not transitive. If Alice is the mother
of Brenda, and Brenda is the mother of Carol, Alice is the grandmother of Carol, not
the mother.

Matrix Representation

A relation R is transitive if for every pair of entries M_R[i, j] = 1 and M_R[j, k] = 1, the entry
M_R[i, k] is also 1.

This is equivalent to saying that if an entry in the matrix square M_R^2 is non-zero, the
corresponding entry in M_R must be 1. (Here, matrix multiplication uses boolean OR instead
of addition). More formally, R is transitive if and only if R^2 ⊆ R.

Number of Transitive Relations

There is no simple closed-form formula for the number of transitive relations on a set of n
elements. This is a well-known difficult counting problem in combinatorics.
11. Antisymmetric Relation
Definition: A relation R on a set A is antisymmetric if for every (a, b) ∈ R with a ≠ b, the
pair (b, a) is not in R.
●​ Formal condition: If a R b and b R a, then a = b.
●​ This means that the only way for a relation to exist in both directions is if it's a loop on
a single element.

Examples
1.​ The "less than or equal to" (<=) relation on integers is antisymmetric. If a <= b and b
<= a, it must be that a = b.
2.​ The "is a subset of" (⊆) relation is antisymmetric. If A ⊆ B and B ⊆ A, then A = B.
3.​ The "divides" relation on the set of positive integers is antisymmetric. If a divides b
and b divides a, then a = b.
4.​ Non-example: The "is a sibling of" relation is not antisymmetric, because if Alice is a
sibling of Bob, Bob is also a sibling of Alice, but Alice is not Bob.

Matrix Representation

A relation R is antisymmetric if for every i ≠ j, M_R[i, j] and M_R[j, i] are not both 1.

If M_R[i, j] = 1 and i ≠ j, then M_R[j, i] must be 0.

This matrix represents an antisymmetric relation. For any off-diagonal 1, its mirror image
across the diagonal is 0.

Number of Antisymmetric Relations

Let |A| = n.

●​ For the n diagonal elements (i,i), they can either be in the relation or not. This gives
2^n choices.
●​ For each of the (n^2 - n) / 2 pairs of off-diagonal positions (i,j) and (j,i), there are three
possibilities:
1.​ (i,j) is in the relation, (j,i) is not.
2.​ (j,i) is in the relation, (i,j) is not.
3.​ Neither is in the relation.​
(They cannot both be in the relation). This gives 3 choices for each pair of
positions.
●​ The total number of antisymmetric relations is 2^n * 3^((n^2 - n)/2).
12. More Examples of Relations
Let A = {1, 2, 3}. Let's analyze some relations on A.
1.​ R1 = { (1,1), (2,2) }
○​ Reflexive? No, because (3,3) is missing.
○​ Symmetric? Yes. There are no pairs (a,b) where a != b, so the condition "if
(a,b) in R then (b,a) in R" is vacuously true.
○​ Antisymmetric? Yes. The condition "if (a,b) in R and (b,a) in R then a=b" is
true. For (1,1), 1=1. For (2,2), 2=2.
○​ Transitive? Yes. There are no cases of (a,b) and (b,c) to check, so it's
vacuously true.
2.​ R2 = { (1,2), (2,1), (1,1) }
○​ Reflexive? No, (2,2) and (3,3) are missing.
○​ Symmetric? Yes. We have (1,2) and its reverse (2,1) is also present.
○​ Antisymmetric? No. We have (1,2) and (2,1), but 1 != 2.
○​ Transitive? Yes. (1,2) and (2,1) implies (1,1) is needed, and it is present.
(2,1) and (1,2) implies (2,2) is needed, but it is missing. Wait, let me recheck.
(2,1) in R and (1,2) in R implies (2,2) must be in R. Since (2,2) is NOT in R2,
this relation is not transitive.
3.​ R3 = { (1,2), (2,3), (1,3) } ("less than" on {1,2,3})
○​ Reflexive? No, no diagonal elements are present.
○​ Symmetric? No. (1,2) is present, but (2,1) is not.
○​ Antisymmetric? Yes. There are no pairs (a,b) and (b,a) where a != b.
○​ Transitive? Yes. (1,2) and (2,3) are present, and the required (1,3) is also
present.
4.​ R4 = { (1,1), (2,2), (3,3), (1,2) }
○​ Reflexive? Yes, all diagonal elements are present.
○​ Symmetric? No, (1,2) is present but (2,1) is not.
○​ Antisymmetric? Yes. For (1,2), its reverse (2,1) is not present.
○​ Transitive? Yes. There are no chains (a,b) and (b,c) that cause a problem.
E.g., (1,1) and (1,2) implies (1,2) is needed (it is). (1,2) and (2,2) implies (1,2)
is needed (it is).
5.​ R5 = A x A (The relation where everything is related to everything)
○​ Reflexive? Yes.
○​ Symmetric? Yes.
○​ Antisymmetric? No.
○​ Transitive? Yes.
13. Equivalence Relation
Definition

A relation R on a set A is an equivalence relation if it is Reflexive, Symmetric, and Transitive.

Equivalence relations are used to group elements that are "similar" or "equivalent" in some
way.

Examples
1.​ "has the same birthday as" on the set of all people.
○​ Reflexive: Everyone has the same birthday as themselves.
○​ Symmetric: If A has the same birthday as B, then B has the same birthday
as A.
○​ Transitive: If A has the same birthday as B, and B has the same birthday as
C, then A has the same birthday as C.​
This is an equivalence relation.
2.​ "Congruence Modulo n" on the set of integers. We say a ≡ b (mod n) if (a-b) is an
integer multiple of n. Let's test for n=3.
○​ Reflexive: a ≡ a (mod 3) because a-a = 0, which is 0*3. Yes.
○​ Symmetric: If a ≡ b (mod 3), then a-b = 3k. So b-a = -3k = 3(-k). Thus b ≡ a
(mod 3). Yes.
○​ Transitive: If a ≡ b (mod 3) and b ≡ c (mod 3), then a-b=3k and b-c=3j. Adding
these gives (a-b)+(b-c) = 3k+3j, so a-c = 3(k+j). Thus a ≡ c (mod 3). Yes.​
This is an equivalence relation.
3.​ The relation R = {(a,b) | a and b are words with the same first letter} on the set of
English words is an equivalence relation.

Matrix Representation

The matrix of an equivalence relation must be:

1.​ Reflexive: All 1s on the diagonal.

2.​ Symmetric: The matrix is symmetric about the diagonal.
3.​ Transitive: This property must also hold (checked via R^2 ⊆ R).
Number of Equivalence Relations

The number of distinct equivalence relations on a set of n elements is given by the n-th Bell
number, denoted B_n. There is no simple formula, but they can be calculated recursively.

●​ B_0 = 1
●​ B_1 = 1
●​ B_2 = 2
●​ B_3 = 5
●​ B_4 = 15

14. Partitions
Definition

A partition of a set A is a collection of non-empty subsets of A, say A1, A2, ..., Ak, such that:

1.​ Every element of A is in some subset: A1 U A2 U ... U Ak = A.

2.​ The subsets are pairwise disjoint: Ai ∩ Aj = ∅ for any i ≠ j.

Essentially, a partition chops up the set A into smaller, non-overlapping pieces that cover the
entire set.

Examples
1.​ Let A = {1, 2, 3, 4, 5, 6}.
○​ One partition is P1 = { {1,2}, {3}, {4,5,6} }.
○​ Another partition is P2 = { {1,3,5}, {2,4,6} }. (The set of odd numbers and the
set of even numbers).
2.​ Let S be the set of all students in a university. The collection of sets {Freshmen,
Sophomores, Juniors, Seniors} is a partition of S (assuming no student has multiple
classifications).

The Fundamental Theorem of Equivalence Relations

There is a perfect correspondence between equivalence relations on a set A and partitions

of the set A.

1.​ Every equivalence relation R on A induces a partition of A. The sets in the

partition are the equivalence classes. The equivalence class of an element a,
denoted [a], is the set of all elements x such that x R a.
2.​ Every partition P of A induces an equivalence relation on A. The relation R is
defined as: a R b if and only if a and b are in the same subset of the partition P.
Case Study: Congruence Modulo 3
●​ Equivalence Relation: R = { (a,b) | a ≡ b (mod 3) } on the set of integers Z.
●​ This relation induces a partition by grouping numbers with the same remainder when
divided by 3.
●​ Equivalence Classes:
○​ [0] = {..., -6, -3, 0, 3, 6, ...} (all multiples of 3)
○​ [1] = {..., -5, -2, 1, 4, 7, ...} (all numbers with a remainder of 1)
○​ [2] = {..., -4, -1, 2, 5, 8, ...} (all numbers with a remainder of 2)
●​ The Partition: The partition of Z is P = { [0], [1], [2] }. Note that every integer is in
exactly one of these sets.

15. Miscellaneous Properties of Relations

Let R and S be two relations on a set A. We can perform set operations on them.

Union and Intersection

●​ R U S = { (a,b) | (a,b) ∈ R or (a,b) ∈ S }
●​ R ∩ S = { (a,b) | (a,b) ∈ R and (a,b) ∈ S }

Preservation of Properties
1.​ Reflexive:
○​ If R and S are reflexive, then R ∩ S is reflexive. (Proof: For any a, (a,a)∈R
and (a,a)∈S, so (a,a)∈R∩S).
○​ If R and S are reflexive, then R U S is reflexive. (Proof: For any a, (a,a)∈R,
so it must be in R U S).
2.​ Symmetric:
○​ If R and S are symmetric, then R ∩ S is symmetric.
○​ If R and S are symmetric, then R U S is symmetric.
3.​ Antisymmetric:
○​ If R and S are antisymmetric, then R ∩ S is antisymmetric.
○​ R U S is not necessarily antisymmetric. (Example: Let R={(1,2)}, S={(2,1)}.
Both are antisymmetric, but R U S = {(1,2), (2,1)} is not).
4.​ Transitive:
○​ If R and S are transitive, then R ∩ S is transitive.
○​ R U S is not necessarily transitive. (Example: Let R={(1,2)}, S={(2,3)}. Both
are transitive, but R U S = {(1,2), (2,3)} is not, because it's missing (1,3)).
16. Summary and Conclusion
This chapter explored the mathematical formalization of relationships.
●​ A relation is formally a subset of a Cartesian product (A x B). A relation on a set A
is a subset of A x A.
●​ Relations can be visualized using directed graphs or represented algebraically
using 0-1 matrices.
●​ Key properties of relations on a set include:
○​ Reflexive: Every element is related to itself.
○​ Symmetric: If a R b, then b R a.
○​ Antisymmetric: If a R b and b R a, then a = b.
○​ Transitive: If a R b and b R c, then a R c.
●​ An equivalence relation is one that is reflexive, symmetric, and transitive. It serves
to group "equivalent" elements together.
●​ A partition is a way of dividing a set into non-empty, non-overlapping subsets.
●​ The Fundamental Theorem establishes a one-to-one correspondence between
equivalence relations and partitions on a set, showing they are two perspectives on
the same underlying structure. Understanding these concepts is crucial for various
fields, including database theory, computer science algorithms, and advanced
algebra.