STEP-BY-STEP LESSON · §8.1
Relations on Sets
Represent a relation as a set of ordered pairs and read its diagram.
Before you begin
The Language of Relations and Functions
A relation from A to B is a set of selected pairs in A×B. An object may relate to several objects or none.
R⊆A×B
Every x in A must have exactly one associated y in B. Different inputs may share an output.
f(x)=y
Set Theory: Definitions and the Element Method of Proof
The statement x∈A concerns one object. A⊆B says that every element of A belongs to B.
A⊆B ⇔ ∀x(x∈A ⇒ x∈B)
X=Y means X⊆Y and Y⊆X. One inclusion still allows extra elements in the second set.
X=Y ⇔ (X⊆Y ∧ Y⊆X)
Symbols
- aRb
- a is related to b by R
- A×B
- Cartesian product of ordered pairs
- M[a,b]
- matrix entry in row a and column b
Definitions and notation for this topic
Relation
R ⊆ A×B
A set of ordered pairs describing which objects are related.
A function is a special kind of relation.
The notation aRb means (a,b)∈R. A relation on A has R⊆A×A; reflexivity, symmetry and transitivity below concern that setting.
Separate glossary example
On ℤ, define aRb to mean a≤b.
Matrix of a finite relation
M[a,b]
For R⊆A×B on finite ordered sets, M[a,b]=1 if (a,b)∈R and 0 otherwise. State the row order A and column order B.
An entry represents a particular ordered pair. A multigraph adjacency matrix may count parallel edges and therefore have entries greater than 1; that is a different convention.
Separate glossary example
For A=(1,2), B=(u,v), R={(1,v),(2,u)}, the matrix is [[0,1],[1,0]].
Step by step
Step 1 / 6
Specify the two positions
A relation from A to B selects pairs (a,b) from A×B. Order matters: the first coordinate comes from A and the second from B.
R⊆A×B
A relation may select no pairs or all pairs.
Worked example
On A={1,2,3}, define R by a<b and list its pairs.
- For a=1, b=2 and b=3 work: (1,2),(1,3).
- For a=2 only b=3 works: add (2,3). For a=3 no b works.
- Thus R={(1,2),(1,3),(2,3)}. Pair (2,1) is absent because 2<1 is false.
Optional self-check
If R={(a,b)}, must (b,a) also be in R when a≠b?
Show answer
No. The reverse pair must be specified or follow from the relation’s definition.