Fundamentals of Computing: Relations: Definitions, Tables, Graphs and Matrices

Lesson overview

Represent relations using several equivalent forms.

CourseFundamentals of Computing

Topic strandRelations

Assessment styleDigital exam practice

EvidenceWorked answer plus justification

Starter: make the model explicit

Before reading the worked example, write down the objects involved, the claim being made and the notation you expect to use. This prevents the common error of calculating before modelling.

Learning objectives

Define a relation on one or more sets.
Represent a relation as ordered pairs, a table, a directed graph or a matrix.
Choose the representation that best supports a question.

Learning outcomes

By the end of this lesson, you can define a relation on one or more sets.
By the end of this lesson, you can represent a relation as ordered pairs, a table, a directed graph or a matrix.
By the end of this lesson, you can choose the representation that best supports a question.

Key vocabulary

What this lesson is about

A relation describes which objects are connected to which other objects. The same relation can be written as ordered pairs, shown as a table, drawn as a graph or encoded as a matrix.

These representations support different tasks. Ordered pairs are precise, tables are systematic, graphs are visual and matrices are useful for computation.

Terms, acronyms and named methods

These are the phrases and named techniques used in this lesson. Read this section before the worked example so the notation and examples have a clear meaning.

Directed graphPhrase. A graph where edges have direction. The ordered pair (a,b) means an arrow from a to b, not necessarily from b to a.

Adjacency matrixPhrase. A matrix that records graph connections. Row i and column j record whether the i-th object is related to the j-th object.

Table representationPhrase. A systematic way to list which ordered pairs are present or absent in a relation.

Formal notation and definitions

A relation from A to B is a subset R \subseteq A \times B. A relation on A is the special case R \subseteq A \times A. aRb means (a, b) \in R. An adjacency matrix M has Mᵢⱼ = 1 when (vᵢ, vⱼ) \in R.

How to read the symbols

$R\subseteq A\times B$ A relation from A to B is a set of ordered pairs with first component in A and second component in B.

$S\subseteq A\times A$ A relation on A is the special case where both components come from A.

$aRb$ Alternative notation for saying (a,b) is in R.

$M_{ij}$ The matrix entry recording whether vertex i is related to vertex j.

Use relation notation to connect ordered pairs, graph arrows and matrix entries as the same underlying information.

Degree-level reasoning

Relations are central to databases, graphs, equivalence classes and ordering problems. The same ordered-pair definition supports several computing representations.

Property checks require quantifiers. One missing pair can disprove reflexivity, symmetry or transitivity, but proving the property needs all relevant cases.

Do not stop at a correct-looking answer. State why the method is valid, whether the result depends on a hidden assumption, and what would count as a counterexample.

Worked formal model

This section shows the model, notation, calculation and interpretation as one worked answer. The notation is part of the reasoning, not decoration.

1. Context and objects

A follows relation on users can be written as ordered pairs, displayed as a directed graph or stored as a matrix.

Objects: the source set A, target set B, ordered pairs in R ⊆ A × B, and adjacency-matrix entries when the relation is on one set.

Model cue: Use the same relation in four forms: ordered pairs, table, directed graph and adjacency matrix. The content is the same; the representation changes.

2. Mathematical working

R\subseteq Users\times Files,\quad R=\{(u_1,f_2),(u_2,f_1)\}

S\subseteq Users\times Users,\quad S=\{(u_1,u_2),(u_2,u_3)\}

M_S = \begin{bmatrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0\end{bmatrix}

Plain text version

R ⊆ Users × Files, R = {(u1,f2), (u2,f1)}
S ⊆ Users × Users, S = {(u1,u2), (u2,u3)}
Matrix for S with rows/columns u1,u2,u3:
[[0,1,0], [0,0,1], [0,0,0]]

3. How to read the working

Read R ⊆ A × B as a relation from one set to another. In an access-control example, ordered pairs can connect users to files.
Read S ⊆ A × A as a relation on one set. This special case supports directed graphs and square adjacency matrices.
Use the row and column order before reading a matrix; a 1 in row i, column j means the ordered pair (ui, uj) is present.
Translate between representations carefully: the ordered pairs, directed graph arrows and matrix entries should all describe the same relation.

4. Computing meaning and check

The relation is the underlying object; ordered pairs, arrows and matrix entries are representations of the same connections.

Now check: Create one relation from Users to Files and one relation on three users. Show the user-user relation as ordered pairs, a directed graph and a matrix.

Worked example

From scenario to formal reasoning

Scenario: A follows relation on users can be written as ordered pairs, displayed as a directed graph or stored as a matrix.

Method: Use the definitions and notation introduced above, then state what the result means in this computing scenario.

Reveal model answer

For access control, R ⊆ Users × Files can contain (u1, f2), meaning user u1 may access file f2. For users following each other, S ⊆ Users × Users is a relation on one set: (a, b) ∈ S means user a follows user b. A directed edge a → b and a matrix entry Sab = 1 express the same relation S.

Worked solution structure

How a strong answer should be written

Define: State the domain and the objects under discussion. For this lesson, begin from A relation from A to B is a subset R ⊆ A × B.
Apply: Use the relevant definition from relations; do not rely on the diagram, wording or intuition alone.
Check: Test a boundary case, counterexample candidate or representation limit.
Conclude: Write one sentence that connects the formal result back to the computing scenario.

Common misconception

A common mistake is assuming every relation behaves like a function. Relations can link one input to many outputs or none.

Guided practice

Define a relation R from Users to Files and state why this is a subset of Users × Files.
Define a relation S on Users and state why this is a subset of Users × Users.
Show a three-user follows relation as ordered pairs and as an adjacency matrix.
Explain when a relation can have one input linked to many outputs, unlike a function.

Quick checks

1. A relation from Users to Files is a subset of:

Files onlyUsers × UsersUsers × Files

2. A relation on Users is a subset of:

Users × UsersUsers ∩ UsersP(Users) only

Digital exam practice

Example exam task

Let Users = {u1,u2,u3}, Files = {f1,f2}, R = {(u1,f2),(u2,f1)} and S = {(u1,u2),(u2,u3)}. Represent R as a relation from Users to Files and S as a relation on Users, then show S as ordered pairs, directed graph language and an adjacency matrix.

Notation toolkit

R\subseteq A\times B

Means: a relation from A to B

How to use: Use it when pairs connect two different kinds of object.

S\subseteq A\times A

Means: a relation on one set

How to use: Use it for follows, links or comparisons inside one domain.

M_{ij}

Means: row i, column j of a relation matrix

How to use: Use it when reading ordered pairs from a matrix.

What a good answer is expected to show

A strong answer for this lesson defines the source set A, target set B, ordered pairs in R ⊆ A × B, and adjacency-matrix entries when the relation is on one set, applies the relations method with visible working, and finishes by interpreting the result in the computing scenario.

How to solve it

Read R ⊆ A × B as a relation from one set to another. In an access-control example, ordered pairs can connect users to files.
Read S ⊆ A × A as a relation on one set. This special case supports directed graphs and square adjacency matrices.
Use the row and column order before reading a matrix; a 1 in row i, column j means the ordered pair (ui, uj) is present.
Translate between representations carefully: the ordered pairs, directed graph arrows and matrix entries should all describe the same relation.

Model answer

Reveal model answer

R=\{(u_1,f_2),(u_2,f_1)\}\subseteq Users\times Files

S=\{(u_1,u_2),(u_2,u_3)\}\subseteq Users\times Users

M_S=\begin{bmatrix}0&1&0\\0&0&1\\0&0&0\end{bmatrix}

A relation from Users to Files can be R = {(u1, f2), (u2, f1)} ⊆ Users × Files. A relation on Users can be S = {(u1, u2), (u2, u3)} ⊆ Users × Users. With rows and columns u1, u2, u3, S has matrix [[0,1,0],[0,0,1],[0,0,0]]. Relations can link one input to several outputs, unlike functions.

Practise next

Define a relation R from Users to Files and state why this is a subset of Users × Files.
Define a relation S on Users and state why this is a subset of Users × Users.

Self-marking criteria

Uses R ⊆ A × B for a relation between two sets.
Uses S ⊆ A × A for a relation on one set.
Keeps ordered-pair direction clear.
Builds a matrix with a stated row/column order.
Explains why relations are not necessarily functions.

Extension

Change one assumption in the worked scenario and decide whether the same method still applies. If it does not, name the exact point where the reasoning breaks.

Study route

Save one clean worked answer from this lesson. Include the problem statement, notation, working, final answer and a short note explaining the computing meaning of the result.

Next lesson: Properties of Relations: Reflexive, Symmetric and Transitive.