Fundamentals of Computing: Cartesian Products and Modelling Data with Sets

Lesson overview

Use Cartesian products to reason about structured data and valid combinations.

CourseFundamentals of Computing

Topic strandSet theory

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

Construct a Cartesian product from two small sets.
Explain ordered pairs as simple records.
Identify impossible or invalid pairs in a data model.

Learning outcomes

By the end of this lesson, you can construct a Cartesian product from two small sets.
By the end of this lesson, you can explain ordered pairs as simple records.
By the end of this lesson, you can identify impossible or invalid pairs in a data model.

Key vocabulary

What this lesson is about

A Cartesian product forms ordered pairs from two sets. It is the mathematical basis for many data-modelling ideas, including user-role assignments, coordinate systems, table rows and binary relations.

The key point is order. The pair (user, role) is not the same as (role, user), because each position has a different meaning in the model.

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.

Cartesian productNamed construction. The set of all ordered pairs formed from two sets. It is named after René Descartes and is written A × B.

Ordered pairPhrase. A pair where position matters. In (user, role), the first component must be a user and the second must be a role.

RelationPhrase. A selected set of ordered pairs. In a data model, it can represent permitted, observed or required pairings.

Formal notation and definitions

A \times B = {(a, b) | a \in A and b \in B}. A binary relation R from A to B is any subset R \subseteq A \times B. The order in (a, b) is part of the data.

How to read the symbols

$A\times B$ Cartesian product: all ordered pairs with first component from A and second from B.

$(a,b)$ An ordered pair. The first and second positions have different meanings.

$R\subseteq A\times B$ A relation R is a selected set of permitted or observed pairs.

Use Cartesian product notation when the position of each value matters. In data modelling, the first coordinate and second coordinate usually have different meanings.

Degree-level reasoning

At degree level, set notation is not shorthand for a diagram. It is a language for stating exactly which objects are included, excluded or related.

When proving a set identity, use element-chasing: take an arbitrary element x, show the membership condition in one set is equivalent to the membership condition in the other, then conclude equality.

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

If Users = {u1, u2} and Roles = {reader, editor}, Users x Roles lists possible user-role assignments before business rules remove invalid ones.

Objects: the Users set, the Roles set, ordered pairs (user, role), and the assigned-role relation.

Model cue: Use a table: rows are elements of A, columns are elements of B, and each cell is the ordered pair (a, b). This shows why A × B contains all possible pairings.

2. Mathematical working

Users=\{u_1,u_2\},\quad Roles=\{reader,editor\}

Users\times Roles=\{(u_1,reader),(u_1,editor),(u_2,reader),(u_2,editor)\}

AssignedRoles\subseteq Users\times Roles

Plain text version

A × B = {(a, b) | a ∈ A and b ∈ B}.
A binary relation R from A to B is any subset R ⊆ A × B.
The order in (a, b) is part of the data.

Worked use: Let Users = {u1, u2} and Roles = {reader, editor}. Users × Roles contains (u1, reader), (u1, editor), (u2, reader), and (u2, editor). A relation AssignedRoles is then a selected subset of those pairs, not necessarily every possible pair.

3. How to read the working

Read Users × Roles as every possible ordered user-role pair before any business rule is applied.
Preserve the order of each pair: (u1, editor) means user u1 has role editor, while (editor, u1) would use the fields backwards.
Read AssignedRoles ⊆ Users × Roles as a constraint: only some possible pairs are actually assigned.
Translate the subset back into data modelling language: the Cartesian product is the possible record space; the relation is the valid or observed records.

4. Computing meaning and check

The Cartesian product gives the space of possible records before constraints are applied. A relation is the selected subset that is actually permitted or observed.

Now check: Explain why (u1, editor) and (editor, u1) are different. Then state what would be wrong with treating a Cartesian product as if order did not matter.

Worked example

From scenario to formal reasoning

Scenario: If Users = {u1, u2} and Roles = {reader, editor}, Users x Roles lists possible user-role assignments before business rules remove invalid ones.

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

Reveal model answer

Let Users = {u1, u2} and Roles = {reader, editor}. Users × Roles contains (u1, reader), (u1, editor), (u2, reader), and (u2, editor). A relation AssignedRoles is then a selected subset of those pairs, not necessarily every possible pair.

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 × B = {(a, b) | a ∈ A and b ∈ B}.
Apply: Use the relevant definition from set theory; 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 treating (a, b) and (b, a) as the same. Ordered pairs preserve position because position carries meaning.

Guided practice

List Users × Roles for Users = {u1, u2} and Roles = {reader, editor}.
Circle which ordered pairs remain if only u1 can be editor and both users can be reader.
Explain why (u1, editor) is valid user-role data but (editor, u1) is a field-order error.
Write the selected assignments as a relation R ⊆ Users × Roles.

Quick checks

1. In Users × Roles, what does (u1, editor) represent?

Role editor paired with user u1 in the same order.A set containing u1 and editor with no positions.User u1 paired with role editor.

2. A relation from Users to Roles is best described as:

A single role value.A selected subset of Users × Roles.Every possible subset of Users.

Digital exam practice

Example exam task

Given Users = {u1,u2} and Roles = {reader, editor}, list Users × Roles. If both users may be readers and only u1 may be editor, write AssignedRoles and explain why reversing an ordered pair is invalid.

Notation toolkit

A\times B

Means: all ordered pairs with first component from A and second from B

How to use: Use it to define the possible record space.

(a,b)\ne(b,a)

Means: ordered pairs preserve field order

How to use: Use it when explaining why swapping fields changes the data.

R\subseteq A\times B

Means: a relation selects some valid pairs from the Cartesian product

How to use: Use it for observed or allowed assignments.

What a good answer is expected to show

A strong answer for this lesson defines the Users set, the Roles set, ordered pairs (user, role), and the assigned-role relation, applies the set theory method with visible working, and finishes by interpreting the result in the computing scenario.

How to solve it

Read Users × Roles as every possible ordered user-role pair before any business rule is applied.
Preserve the order of each pair: (u1, editor) means user u1 has role editor, while (editor, u1) would use the fields backwards.
Read AssignedRoles ⊆ Users × Roles as a constraint: only some possible pairs are actually assigned.
Translate the subset back into data modelling language: the Cartesian product is the possible record space; the relation is the valid or observed records.

Model answer

Reveal model answer

Users=\{u_1,u_2\},\quad Roles=\{reader,editor\}

Users\times Roles=\{(u_1,reader),(u_1,editor),(u_2,reader),(u_2,editor)\}

AssignedRoles\subseteq Users\times Roles,\quad (u_1,editor)\ne(editor,u_1)

Users × Roles = {(u1, reader), (u1, editor), (u2, reader), (u2, editor)}. If both users may be readers and only u1 may be editor, then AssignedRoles = {(u1, reader), (u1, editor), (u2, reader)}. The pair (editor, u1) reverses the fields, so it is not a valid element of Users × Roles.

Practise next

List Users × Roles for Users = {u1, u2} and Roles = {reader, editor}.
Circle which ordered pairs remain if only u1 can be editor and both users can be reader.

Self-marking criteria

Lists all four ordered pairs.
States AssignedRoles as a subset of Users × Roles.
Explains that pair order carries field meaning.
Identifies at least one invalid or impossible pair under the rule.
Interprets the relation as data-model evidence.

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: Number Systems: Decimal, Binary and Hexadecimal.