Sets and relations: the building blocks of definitions in AI

Sets, subsets, operations, the Cartesian product, relations, equivalence and orders — with Venn diagrams, a relation matrix and what all of it is good for in artificial intelligence.

13 minutes Matěj Žalmánek 2026-10-15

Series AI basics Part 5 of 52

Full series syllabus 52 of 83 topics published

What you will take away

What a set, a subset and the Cartesian product are — and why the number of subsets grows exponentially.
What a relation is, what properties it has and how to draw it as a matrix and as a graph.
Why classification is a partition into equivalence classes and a model is a function — a special kind of relation.

Useful to know first: How to read mathematical notation: symbols, indices, sums and quantifiers

Sets and relations are the building blocks that almost every definition in AI is made of. A state space is a set of states, the transitions between them are relations, training data is a set of pairs, and classification splits inputs into classes. Once you understand these two concepts, you read the definitions in the following parts like ordinary text.

We covered how to write the symbols (∈, ⊆, ∪, ×) in the previous part. Here we go below the surface: what exactly they mean, what properties they have and what they are good for in artificial intelligence.

1. What a set is

Definition — set and element

A set is a basic notion that is not broken down any further (much like a point in geometry): it is a collection of mutually distinct objects, which we call its elements. For a set A and any object x we write

x ∈ A — “x is an element of A”, x ∉ A :⇔ ¬(x ∈ A) — “x is not an element of A”.

We require two things of a set:

for every object x exactly one of the statements x ∈ A, x ∉ A holds — membership is always decided unambiguously;
a set is completely determined by its elements — nothing else (order, number of repetitions) belongs to it; this is exactly what the definition of equality below says.

In plain words

A set is a bag you put things into. All we care about is what is in the bag — not the order you put things in, nor how many times. Two marbles of the same colour are one colour as far as the set is concerned.

We write a set either by listing its elements in curly braces — A = {1, 2, 3} or {↑, →, ↓, ←} — or by a property the elements satisfy: {x ∈ ℕ : x is even}. For A = {1, 2, 3} we have 2 ∈ A and 5 ∉ A. The property notation can describe infinite sets too, and in AI it is used almost always: “the set of all states from which the goal can be reached”.

Definition — equality of sets

Let A and B be sets. A and B are equal, written A = B, if and only if

∀x : (x ∈ A ⇔ x ∈ B).

So sets are the same if and only if they have exactly the same elements.

In plain words

Two bags are the same when they contain the same things. That is why {1, 2, 2} = {2, 1} = {1, 2}: neither order nor repetition matters.

Definition — cardinality and the empty set

The empty set ∅ is the set for which

∀x : x ∉ ∅,

i.e. it has no elements. By the definition of equality there is only one.

Let A be a set. A is finite if and only if A = ∅, or there exist n ∈ ℕ and mutually distinct objects a₁, …, a_n (a_i ≠ a_j for i ≠ j) such that A = {a₁, …, a_n}. The cardinality of a finite set is the number

|A| := n, |∅| := 0,

that is, the number of its elements.

In plain words

Cardinality answers the question “how much is in the bag”: |{1, 2, 3}| = 3. The empty set is an empty bag — it is still a set, there is just nothing in it.

2. Subsets and the power set

From one set we can pick smaller ones. For that we need three concepts that build on each other: the subset, the proper subset and the power set.

Definition — subset

Let A and B be sets. A is a subset of B, written A ⊆ B, if and only if

∀x : (x ∈ A ⇒ x ∈ B).

So every element of A is also an element of B. The negation is written A ⊄ B; by negating the quantifier it means ∃x : x ∈ A ∧ x ∉ B.

In plain words

A subset is a selection from the bag: you take some of the things from B and put them into a smaller bag A. You must not add anything to A that is not in B. So {1, 3} ⊆ {1, 2, 3}, but {1, 4} ⊄ {1, 2, 3}, because 4 is not in the original set. Every set is a subset of itself, and the empty set is a subset of every set.

Definition — proper subset

Let A and B be sets. A is a proper subset of B, written A ⊂ B, if and only if

A ⊆ B ∧ A ≠ B.

So there is at least one element in B that is not in A. (Some textbooks write ⊂ for an ordinary subset too; in this series ⊂ always means a proper subset.)

In plain words

A proper subset is a selection in which at least something is missing. {1, 3} ⊂ {1, 2, 3}, but {1, 2, 3} is not a proper subset of itself — you took absolutely everything.

Definition — power set

Let A be a set. The power set of A is the set

𝒫(A) := {S : S is a set ∧ S ⊆ A}.

So its elements are exactly all the subsets of A (always including ∅ and A itself).

Theorem. Let A be a finite set. Then |𝒫(A)| = 2^|A| (proof below).

In plain words

The power set is the list of all selections you can make from the bag — including the empty selection and the selection of everything. Why there are 2ⁿ of them: for each element you decide whether to put it in the selection or not. That is two options for every element, so for three elements 2 · 2 · 2 = 2³ = 8, for ten elements already 2¹⁰ = 1024 (colours as in the formula below).

For A = {a, b, c}, 𝒫(A) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} — 8 subsets in total. You will meet this exponential growth at every step in AI. A model that has to choose which of 50 features to use has 2⁵⁰ options — over a quadrillion. That is why feature selection is not done by trying every combination.

|𝒫(A)| = 2^|A|

|𝒫(A)|: the number of all subsets — how many different selections from A exist; this is what we want to count
2: for each element there are exactly two options, “in the selection” and “not in the selection” — hence the base 2
|A|: the number of elements = the number of independent decisions; independent choices multiply, and two multiplied n times is a power

The number of selections grows exponentially: every extra element doubles it.

Theorem — the number of subsets (with proof)

Theorem. Let n ∈ ℕ and A = {a₁, …, a_n}, where the elements a₁, …, a_n are mutually distinct (i.e. |A| = n). Then |𝒫(A)| = 2ⁿ. (For A = ∅ we have 𝒫(∅) = {∅} and |𝒫(∅)| = 1 = 2⁰.)

Proof. To each subset S ⊆ A we assign its characteristic vector (b₁, …, b_n) ∈ {0, 1}ⁿ, where b_i = 1 if and only if a_i ∈ S. Different subsets have different vectors and every vector belongs to some subset — the assignment is one-to-one. So there are as many subsets as there are vectors of zeros and ones of length n, and there are 2 · 2 · … · 2 = 2ⁿ of those. ∎

The proof directly gives a procedure for listing all subsets: go through the numbers 0 to 2ⁿ − 1 and read their binary representation as a characteristic vector.

def vsechny_podmnoziny(prvky):          # prvky = [a1, ..., an]
    n = len(prvky)
    for k in range(2 ** n):              # k = 0, 1, ..., 2^n − 1
        yield {prvky[i] for i in range(n)
               if (k >> i) & 1}           # i-th bit of k: is a_i in the selection?

Example — subset number 5 of {a, b, c}

5 = 1 · 2⁰ + 0 · 2¹ + 1 · 2², so the bits are (b₁, b₂, b₃) = (1, 0, 1).

Bit 1 for a and for c, bit 0 for b ⇒ the subset {a, c}.

The number 0 gives ∅, the number 7 = 111₂ gives the whole {a, b, c} — and in between there are 8 numbers altogether, so 8 subsets.

3. Set operations

Definition — union, intersection, difference, complement

Let A and B be sets. We define the sets

union A ∪ B := {x : x ∈ A ∨ x ∈ B},
intersection A ∩ B := {x : x ∈ A ∧ x ∈ B},
difference A ∖ B := {x : x ∈ A ∧ x ∉ B}.

So an element lies in A ∪ B if and only if it lies in at least one of the sets, in A ∩ B if and only if it lies in both, and in A ∖ B if and only if it lies in A but not in B. Sets with A ∩ B = ∅ are called disjoint.

Let moreover U be a set (the universal set, the “universe”) and A ⊆ U. The complement of A with respect to U is the set

A^c := U ∖ A = {x ∈ U : x ∉ A}.

Theorem (De Morgan’s laws). Let U be a set and A, B ⊆ U. Then (A ∪ B)^c = A^c ∩ B^c and (A ∩ B)^c = A^c ∪ B^c (complements with respect to U).

In plain words

Union is “either, or, or both”, intersection “both at once”, difference “this, but not that” and complement “everything else”. De Morgan’s law says that “it is not true that it is raining or snowing” is the same as “it is not raining and not snowing”.

A ∪ B — union

A ∩ B — intersection

A ∖ B — difference

A^c — complement

In AI practice, intersections come up for example when evaluating a model. If P is the set of e-mails the model flagged as spam and S the set of e-mails that really are spam (both finite and non-empty), then precision is |P ∩ S|/|P| — how many of the flagged ones really were spam — and recall is |P ∩ S|/|S| — how much of the spam the model caught.

precision = |P ∩ S|/|P| recall = |P ∩ S|/|S|

|P ∩ S|: hits — e-mails the model flagged that really are spam; in the numerator of both formulas, because both measures count only successes
|P|: everything the model flagged; we divide by it when we ask “can I trust the flag?” — false alarms increase the denominator and precision drops
|S|: all the actual spam; we divide by it when we ask “did nothing slip through?” — missed spam increases the denominator and recall drops

Same numerator, different denominator: precision measures extra mistakes, recall missed ones.

Theorem — the inclusion–exclusion principle (with proof)

Theorem. Let A and B be finite sets. Then |A ∪ B| = |A| + |B| − |A ∩ B|.

Proof. A ∪ B consists of three disjoint parts: A ∖ B, A ∩ B and B ∖ A. Moreover |A| = |A ∖ B| + |A ∩ B| and |B| = |B ∖ A| + |A ∩ B|. So the sum |A| + |B| contains all three parts, but the intersection twice; subtracting |A ∩ B| once fixes that. ∎

|A ∪ B| = |A| + |B| − |A ∩ B|

|A ∪ B|: how many elements are in at least one of the sets — this is what we want
|A|: counts everything in A, including the common part
|B|: counts everything in B — and the common part a second time
− |A ∩ B|: the correction: we counted the intersection twice, so we subtract it once, so that each element counts once

Example — precision, recall and the Jaccard index

The model flagged |P| = 50 e-mails, there are |S| = 40 actual spam e-mails, and |P ∩ S| = 36 e-mails are in both sets.

Colours as in the formulas for precision and recall:

precision = 36/50 = 0.72 — 14 flagged e-mails were false alarms,

recall = 36/40 = 0.90 — the model let 4 spam e-mails through.

By inclusion–exclusion (colours as in its formula) |P ∪ S| = 50 + 40 − 36 = 54. The ratio of the intersection to the union is the Jaccard index (in computer vision IoU, “intersection over union”, used to rate how well a detector’s bounding box fits an object): for finite sets P, S, at least one of which is non-empty,

J(P, S) := |P ∩ S|/|P ∪ S| = 36/54 = 2/3 ≈ 0.667.

4. Cartesian product and n-tuples

Definition — ordered pair and Cartesian product

Let a, b be any objects. The ordered pair (a, b) is an object with first component a and second component b such that for all objects a, b, c, d

(a, b) = (c, d) ⇔ a = c ∧ b = d.

Unlike the set {a, b} = {b, a}, order matters here. (In pure set theory the pair is introduced as (a, b) := {{a}, {a, b}} — Kuratowski’s definition, which has exactly this property.)

Let A and B be sets. The Cartesian product of A and B is the set

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

If A, B are finite, |A × B| = |A| · |B|.

In general: let n ∈ ℕ and let A₁, …, A_n be sets. An n-tuple (a₁, …, a_n) has the property (a₁, …, a_n) = (b₁, …, b_n) ⇔ ∀i ∈ {1, …, n} : a_i = b_i, and

A₁ × … × A_n := {(a₁, …, a_n) : a_i ∈ A_i for i = 1, …, n}, Aⁿ := A × … × A (n times).

In plain words

The Cartesian product is a table of all combinations. Three t-shirts and two pairs of trousers give 3 · 2 = 6 outfits. The coordinates of a point in the plane are pairs from ℝ × ℝ = ℝ².

The Cartesian product is everywhere in AI. Supervised training data is a subset of X × Y — pairs (input, correct answer). A 28 × 28 pixel photo is a point in ℝ⁷⁸⁴. And in a search problem the transition function is defined on S × A — on pairs (state, action).

Example — how many (state, action) pairs there are

A robot on a 3 × 3 grid has |S| = 9 states (cells) and |A| = 4 actions {↑, →, ↓, ←}.

|S × A| = |S| · |A| = 9 · 4 = 36.

A table that holds one number for every (state, action) pair — say, an estimate of how good that action is in that state — therefore has 36 cells. Why the counts multiply: to each of the 9 states any of the 4 actions can be added, so the pairs form 9 rows of 4.

5. Relations

Definition — relation

Let A and B be sets. A binary relation between A and B is any set R such that

R ⊆ A × B.

For a ∈ A and b ∈ B we write a R b :⇔ (a, b) ∈ R and read it “a is in relation R with b”.

A relation between A and A, i.e. R ⊆ A × A, is called a relation on the set A.

In plain words

A relation is a list of pairs that “belong together”. Who is whose parent, which city has a direct connection to which, which state leads to which. Nothing more — just a list of pairs.

A relation on a small set can be drawn in two ways. Take the relation “a divides b” (b is a multiple of a) on the set {1, …, 6}. As a matrix: there is a dot in row a and column b when a divides b. And as a directed graph: an arrow from a to b.

matrix: row a, column b

graph: arrow a → b (without loops a → a)

The relation “a divides b” on the set {1, …, 6} pairs in the relation: 14

The relation has 14 pairs. In AI you will meet both forms: the relation matrix is what the computer calculates with (a graph’s adjacency matrix, a similarity matrix), the graph is what a human draws. Transitions between states in search are a relation on the set of states, and the k-nearest-neighbours graph from label propagation is the relation “is among the nearest”.

Definition — relation matrix

Let n ∈ ℕ, let A = {a₁, …, a_n} be a set with mutually distinct elements a₁, …, a_n and R ⊆ A × A a relation on A. The matrix of the relation R (with respect to this numbering of the elements) is the table M ∈ {0, 1}^n×n with n rows and n columns and entries

M_ij := 1 if a_i R a_j, M_ij := 0 otherwise, for i, j = 1, …, n.

The number of pairs in the relation is the number of ones in the matrix: ∑_i=1ⁿ ∑_j=1ⁿ M_ij = |R|.

Theorem — how many relations there are

Theorem. Let A and B be finite sets. Then there are exactly 2^{|A| · |B|} relations between A and B.

Proof. A relation is any subset of A × B, so the number of relations is |𝒫(A × B)| = 2^{|A × B|} = 2^{|A| · |B|}. ∎

On {1, …, 6} there are 6 · 6 = 36 possible pairs and 2³⁶ = 68,719,476,736 relations. “Divides” is one of them — the one with 14 ones in its matrix.

6. Properties of relations

Definition — properties of a relation on a set

Let A be a set and R ⊆ A × A a relation on A. The relation R is

reflexive if and only if ∀a ∈ A : a R a;
symmetric if and only if ∀a, b ∈ A : (a R b ⇒ b R a);
antisymmetric if and only if ∀a, b ∈ A : ((a R b ∧ b R a) ⇒ a = b);
transitive if and only if ∀a, b, c ∈ A : ((a R b ∧ b R c) ⇒ a R c).

Antisymmetry is not the opposite of symmetry: the relation “=” is both symmetric and antisymmetric at the same time.

In plain words

Reflexive: everything is related to itself. Symmetric: it works both ways. Antisymmetric: both ways only when it is the same thing. Transitive: if there is a path from a to b and from b to c, there is also a direct one from a to c.

For relations on the set {1, …, 6} it looks like this — and the combination of properties tells you what kind of relation it is:

Relation	Reflexive	Symmetric	Antisymmetric	Transitive
`a` ≤ `b`	yes	no	yes	yes
`a` divides `b`	yes	no	yes	yes
same remainder modulo 3	yes	yes	no	yes
\|`a` − `b`\| = 1 (“neighbours”)	no	yes	no	no

Example — how a property is verified or refuted

The properties can be read directly from the relation matrix: reflexive ⇔ the diagonal is all ones (M_ii = 1), symmetric ⇔ the matrix is symmetric about the diagonal (M_ij = M_ji), antisymmetric ⇔ off the diagonal there are never ones in both places M_ij and M_ji.

To refute a property, a single counterexample is enough. “Neighbours” are not transitive: 1 R 2 (|1 − 2| = 1) and 2 R 1, but 1 R 1 does not hold (|1 − 1| = 0). Nor are they reflexive (1 R 1 does not hold) or antisymmetric (1 R 2 and 2 R 1, yet 1 ≠ 2).

To prove it, we have to go through all cases. “Divides” is transitive: if b = ka and c = lb, then c = (kl)a, so a divides c.

Definition — composition of relations and transitive closure

Let A be a set and R, Q ⊆ A × A relations on A. The composition of the relations R and Q is the relation

R ∘ Q := {(a, c) ∈ A × A : ∃b ∈ A : a R b ∧ b Q c}

— “from a you can get to c with one step of R and then one step of Q”. (Careful, the order in the notation varies in the literature; for functions g ∘ f means “f first”, here R ∘ Q means “R first”.)

The powers of a relation R are defined for k ∈ ℕ recursively by R¹ := R, R^k+1 := R^k ∘ R. The transitive closure of a relation R is the relation

R⁺ := ⋃_k=1^∞ R^k = R ∪ (R ∘ R) ∪ (R ∘ R ∘ R) ∪ …

So a R⁺ c if and only if there exist k ∈ ℕ and elements b₀, …, b_k ∈ A with b₀ = a, b_k = c and b_i−1 R b_i for i = 1, …, k — from a there is a path along the arrows of R of length at least 1 to c.

Theorem. Let R be a relation on a set A. Then R⁺ is the smallest transitive relation on A that contains R: R ⊆ R⁺, R⁺ is transitive, and for every transitive relation T on A with R ⊆ T we have R⁺ ⊆ T.

In plain words

A relation says where you can get in one step, the closure where you can get at all. In search it is the difference between “a neighbouring state” and “a reachable state”.

The closure is computed by Warshall’s algorithm: it allows each element k in turn as a stopover and adds all the shortcuts i → k → j.

def tranzitivni_uzaver(A, M):            # M[i][j] = 1 if i R j
    for k in A:                          # k may be a stopover
        for i in A:
            for j in A:
                if M[i][k] and M[k][j]:  # a path i → k → j ...
                    M[i][j] = 1          # ... gives the pair (i, j)
    return M                             # n^3 steps for n elements

For “neighbours” on {1, …, 6} the closure comes out with all 36 pairs: with steps of one, every number can reach every number, even back to itself (1 → 2 → 1). The relation “divides” is already transitive, so the closure does not change it — it stays at 14 pairs.

7. Equivalence and partition into classes

Definition — equivalence and partition

Let A be a set and R ⊆ A × A a relation on A. R is an equivalence relation if and only if it is reflexive, symmetric and transitive. If R is an equivalence and a ∈ A, the equivalence class of the element a is the set

[a] := {x ∈ A : x R a}.

Let A be a set. A partition of A is a set 𝒮 ⊆ 𝒫(A) of subsets of A (its elements are called parts or classes) that satisfies

∀S ∈ 𝒮 : S ≠ ∅ — no part is empty;
∀S, T ∈ 𝒮 : (S ≠ T ⇒ S ∩ T = ∅) — different parts are disjoint;
⋃_{S ∈ 𝒮} S = A, i.e. ∀x ∈ A ∃S ∈ 𝒮 : x ∈ S — the parts cover all of A.

So every element of A lies in exactly one part.

Theorem. Let A be a set.

If R is an equivalence on A, then the set of classes {[a] : a ∈ A} is a partition of A.
If 𝒮 is a partition of A, then the relation x ∼ y :⇔ ∃S ∈ 𝒮 : x ∈ S ∧ y ∈ S (“belongs to the same part”) is an equivalence on A and its classes are exactly the parts of 𝒮.

In plain words

An equivalence is “is the same as in some respect” — the same colour, the same remainder, the same class. Such a relation always splits the set into compartments that do not overlap and together cover everything. Every element is in exactly one compartment.

[a] = {x ∈ A : x R a}

[a]: the class of the element a — the compartment a belongs to; it can be named after any of its members
x ∈ A: candidates are taken only from the set being partitioned — the compartments divide A, nothing else
x R a: the membership condition: the compartment of a contains exactly what is “the same” as a

Theorem — classes do not overlap (with proof)

Theorem. Let A be a set, R an equivalence on A and a, b ∈ A. Then either [a] = [b], or [a] ∩ [b] = ∅. Moreover, a ∈ [a] for every a ∈ A.

Proof. Assume that [a] ∩ [b] ≠ ∅; we show [a] = [b]. Then there is z ∈ [a] ∩ [b], so z R a and z R b. By symmetry a R z, and by transitivity a R b. For every x ∈ [a] we have x R a and a R b, so x R b and x ∈ [b]; likewise the other way round. So [a] = [b]. Reflexivity moreover gives a ∈ [a] — no class is empty and every element is in some class. ∎

Example — classes of remainders modulo 3

On A = {0, …, 8}, x R a :⇔ x mod 3 = a mod 3, where x mod 3 is the remainder of the integer division of x by three.

[4] = {x ∈ {0, …, 8} : x mod 3 = 4 mod 3 = 1} = {1, 4, 7} (colours as in the formula above).

[1] = [7] = {1, 4, 7} — the same class under another name. Altogether 3 classes of 3 elements arise: {0, 3, 6}, {1, 4, 7}, {2, 5, 8}; 3 + 3 + 3 = 9 = |A|.

class [0] {0, 3, 6}

class [1] {1, 4, 7}

class [2] {2, 5, 8}

Partition of {0, …, 8} by remainder modulo 3

This is exactly what classification does: it splits the set of all possible inputs into classes — spam and not spam, dog, cat and parrot. And clustering looks for a partition of the data without anyone telling it what the classes are. The result of k-means from the part on types of learning is a partition of the points into three classes.

8. Orders

Definition — partial and total order

Let A be a set and R ⊆ A × A a relation on A. R is a partial order if and only if it is reflexive, antisymmetric and transitive. The pair (A, R) is then called a partially ordered set.

Elements a, b ∈ A are comparable if and only if a R b ∨ b R a. A partial order R is total (linear) if and only if all pairs are comparable:

∀a, b ∈ A : a R b ∨ b R a.

In plain words

An order says what comes “before” what. With numbers ordered by size you can compare anything with anything. With a partial order not always: 4 and 6 do not divide each other, so by divisibility we cannot tell which one is “smaller”.

A partial order is drawn as a Hasse diagram: smaller elements at the bottom, larger at the top and a line only between immediate neighbours — the rest follows from transitivity. Here are the divisors of 12 ordered by divisibility:

Divisors of 12 ordered by divisibility

Definition — strict order and covering

Let A be a set and ≤ a partial order on A. The strict order associated with ≤ is the relation < on A given for a, b ∈ A by

a < b :⇔ a ≤ b ∧ a ≠ b.

An element b ∈ A covers an element a ∈ A, written a ⋖ b, if and only if

a < b ∧ ¬∃c ∈ A : (a < c ∧ c < b),

i.e. a is strictly below b and no other element lies between them. The Hasse diagram of a finite partially ordered set draws a line (from bottom to top) exactly between the pairs a ⋖ b.

a ⋖ b ⇔ a < b ∧ ¬∃c ∈ A : a < c < b

a ⋖ b: “I draw a line between a and b” — what we are defining
a < b: strictly smaller: a must be below b and not the same — the loops a ≤ a always hold, so we do not draw them
¬∃c ∈ A : a < c < b: nothing in between: if there were some c there, the relation a < b would already follow by transitivity through c and the line would be superfluous

def hasseuv_diagram(A, mensi):           # mensi(a, b) means a < b
    cary = []
    for a in A:
        for b in A:
            if mensi(a, b) and not any(mensi(a, c) and mensi(c, b) for c in A):
                cary.append((a, b))      # b covers a
    return cary                          # level of an element = the longest chain below it

The diagram shows that 1 divides everything and 12 is divisible by everything — but 4 and 6, or 2 and 3, cannot be compared. Among the six divisors there are 12 strict pairs a < b, but the diagram draws only 7 of them. The remaining 5 — 1 < 4, 1 < 6, 1 < 12, 2 < 12 and 3 < 12 — can be read off along the lines, for example 1 → 2 → 4. In AI, orders show up wherever something is ranked or planned: the order of search results, priorities in the frontier of the A* algorithm, or dependencies between the steps of a plan (“first open the door, then walk through”). The graph of module prerequisites in the syllabus of this series is, incidentally, also a partial order.

9. Functions as a special kind of relation

Definition — function

Let A and B be sets. A function (mapping) from A to B, written f : A → B, is a relation f ⊆ A × B such that

∀a ∈ A ∃! b ∈ B : (a, b) ∈ f,

where ∃! is read “there exists exactly one”. So every element a ∈ A is related to exactly one element b ∈ B; it is denoted f(a). More on functions in the part Functions and mappings.

In plain words

A function is a relation that answers every question with exactly one answer. “Is a parent of” is not a function — a person can have several children. “Has mother” is a function — everyone has exactly one.

Example — few relations are functions

On A = {1, 2, 3} there are 2^{3 · 3} = 2⁹ = 512 relations. A function has to pick exactly one of the 3 images for each of the 3 elements, independently of the others: 3 · 3 · 3 = 3³ = 27 functions.

In the relation matrix this means: every row has exactly one one. The “divides” matrix is not a function — row 1 has six ones.

And so the circle closes: a model in machine learning is a function f : X → Y, that is, a special relation between inputs and outputs. Functions and their properties are the topic of the next part of the syllabus.

10. Summary

A set is a collection of elements without order and without repetition; an n-element set has 2ⁿ subsets.
Union, intersection, difference and complement are “or”, “and”, “but not” and “everything else”; a model’s precision and recall are built on intersections.
The Cartesian product makes pairs — data (input, answer) and transitions (state, action) are made of them.
A relation is a set of pairs. An equivalence partitions a set into classes (classification, clustering), an order determines what comes before what.
A function is a relation with exactly one answer — and a model is a function.

Do you see it differently? Write to support@coden-app.com.

Sets and relations: the building blocks of definitions in AI

1. What a set is

2. Subsets and the power set

3. Set operations

4. Cartesian product and n-tuples

5. Relations

6. Properties of relations

7. Equivalence and partition into classes

8. Orders

9. Functions as a special kind of relation

10. Summary

An Agent on your computer, driven from your phone