Relations and Functions — Formula Sheet

A × B = {(a, b): a ∈ A and b ∈ B}

n(A × B) = pq

Number of relations from A to B = 2^(pq)

Number of relations on A = 2^(p^2)

Relation from A to B: R ⊆ A × B

R^-1 = {(b, a): (a, b) ∈ R}

Domain of R = set of all first components

Empty relation = φ

Universal relation = A × A

Identity relation I_A = {(a, a): a ∈ A}

Reflexive: (a, a) ∈ R for every a ∈ A

Symmetric: (a, b) ∈ R ⇒ (b, a) ∈ R

Theorem 1.1: R is symmetric iff R = R^-1

Transitive: (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ R

Number of reflexive relations on A = 2^(p^2-p)

If n(A) = p, then the number of relations on A is 2^(p^2).