Artificial Intelligence & Data Science is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Relations and their properties

Relations between sets: definitions (reflexive, symmetric, antisymmetric, transitive, equivalence, partial order), representation, basic theorems, closures, composition and inverse, with worked examples and exam guidance.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Relations model connections between data items: graphs, database foreign-key links, state transitions in automata, and ordering or grouping (sorting, type hierarchies). Engineers use relation properties to design correct algorithms (e.g. checking equivalence classes, partial orders for scheduling, or ensuring no cycles in dependency graphs).

Key ideas

Start from first principles.

  • Ordered pair: the ordered pair (a, b) is the basic object where order matters: (a, b) = (c, d) iff a = c and b = d.
  • Cartesian product: for sets A and B, the Cartesian product A × B = {(a, b) | a ∈ A and b ∈ B}.
  • Relation: a relation R from A to B is any subset R ⊆ A × B. If A = B we say R is a relation on A.
  • Domain and range: for R ⊆ A × B,
    • domain(R) = {a ∈ A | ∃b ∈ B: (a, b) ∈ R},
    • range(R) = {b ∈ B | ∃a ∈ A: (a, b) ∈ R}.

Properties of relations (for a relation R on a set A):

  • Reflexive: R is reflexive iff ∀a ∈ A: (a, a) ∈ R. (Every element relates to itself.)
  • Irreflexive (or anti-reflexive): R is irreflexive iff ∀a ∈ A: (a, a) ∉ R.
  • Symmetric: R is symmetric iff ∀a, b ∈ A: if (a, b) ∈ R then (b, a) ∈ R.
  • Antisymmetric: R is antisymmetric iff ∀a, b ∈ A: [(a, b) ∈ R and (b, a) ∈ R] ⇒ a = b.
  • Asymmetric: R is asymmetric iff ∀a, b ∈ A: if (a, b) ∈ R then (b, a) ∉ R. Equivalently: R is asymmetric if and only if it is irreflexive and antisymmetric.
  • Transitive: R is transitive iff ∀a, b, c ∈ A: [(a, b) ∈ R and (b, c) ∈ R] ⇒ (a, c) ∈ R.

Common composite notions:

  • Equivalence relation: R is an equivalence relation iff R is reflexive, symmetric and transitive. Then R partitions A into equivalence classes: for a ∈ A, [a] = {x ∈ A | (a, x) ∈ R}. The equivalence classes are nonempty, pairwise disjoint, and their union is A.
    • Theorem (partition correspondence): Every equivalence relation on A induces a partition of A into equivalence classes; conversely, every partition of A defines an equivalence relation: x ~ y iff x and y are in the same block.
    • Proof sketch commonly required: show if [a] ∩ [b] ≠ ∅ then [a] = [b]; use symmetry and transitivity to move between representatives.
  • Partial order (poset): R is a partial order on A if R is reflexive, antisymmetric and transitive. The pair (A, R) is a partially ordered set or poset. If every pair of elements is comparable (for all a, b ∈ A either (a, b) ∈ R or (b, a) ∈ R) then R is a total order (linear order).
  • Comparability: two elements a, b are comparable if (a, b) ∈ R or (b, a) ∈ R.
  • Strict (irreflexive) order: a relation ≺ on A is a strict partial order if it is irreflexive and transitive; from a non-strict partial order ≤ one defines a ≺ b iff a ≤ b and a ≠ b, and conversely a ≤ b iff (a ≺ b) or (a = b). A strict total order additionally has totality: for all distinct a, b, either a ≺ b or b ≺ a.

Hasse diagrams (what to draw): for a finite poset (A, ≤):

  • Draw one labelled dot for each element of A.
  • Place elements at different vertical levels so that if a < b then the dot for b is placed higher than the dot for a.
  • Draw a line (covering edge) between a and b only when b covers a (i.e., a < b and there is no c with a < c < b). Do not draw edges implied by transitivity. Arrowheads are unnecessary: vertical position shows direction (lower to higher).

Operations and closures:

  • Inverse relation: R^{-1} = {(b, a) | (a, b) ∈ R}.
  • Composition (convention used here): if R ⊆ A × B and S ⊆ B × C then S ∘ R ⊆ A × C is defined by S ∘ R = {(a, c) | ∃b ∈ B: (a, b) ∈ R and (b, c) ∈ S}.
  • Reflexive closure of R on A: R ∪ Δ_A where Δ_A = {(a, a) | a ∈ A}.
  • Symmetric closure of R: R ∪ R^{-1} (the smallest symmetric relation containing R).
  • Transitive closure R^+: the smallest transitive relation containing R. The reflexive-transitive closure R^* = R^+ ∪ Δ_A. (Universities often ask for a proof that R^* is the intersection of all reflexive-transitive relations containing R.)

Short proofs often required in exams:

  • Show asymmetric ⇒ irreflexive and antisymmetric. Step: if (a, a) ∈ R then by asymmetry (a, a) ∉ R, contradiction, so irreflexive; if (a, b) ∈ R and (b, a) ∈ R, this cannot occur by asymmetry, so the implication [(a,b) ∈ R and (b,a) ∈ R] ⇒ a = b holds vacuously — hence antisymmetric. Conversely, if R is irreflexive and antisymmetric, then for any (a,b) ∈ R we cannot have (b,a) ∈ R (otherwise antisymmetry forces a = b, contradicting irreflexivity), so R is asymmetric.
  • Show equivalence classes partition A: prove nonempty, union covers A, and two classes either equal or disjoint. Typical exam answer: take x ∈ [a] ∩ [b], then a ~ x and b ~ x ⇒ by symmetry x ~ b and by transitivity a ~ b; then any y ∈ [a] satisfies a ~ y so b ~ y ⇒ y ∈ [b], so [a] ⊆ [b]; symmetric argument gives equality.

Representations: a relation on a finite set can be shown by a Boolean matrix M where M[i,j] = 1 iff (i, j) ∈ R; or by a digraph drawing nodes for elements and directed edges for ordered pairs.

Formulas

R ⊆ A × B — R is a relation from A to B. Symbols: R (relation), A,B (sets). Units: unitless. Applies always when defining a relation. domain(R) = {a ∈ A | ∃b ∈ B: (a,b) ∈ R} — domain of R. Symbols: domain, A,B. Units: unitless. range(R) = {b ∈ B | ∃a ∈ A: (a,b) ∈ R} — range of R. Units: unitless. R^{-1} = {(b,a) | (a,b) ∈ R} — inverse relation. Units: unitless. Applies for any relation. S ∘ R = {(a,c) | ∃b: (a,b) ∈ R and (b,c) ∈ S} — composition (convention: R then S). Symbols: R ⊆ A×B, S ⊆ B×C. Units: unitless. Δ_A = {(a,a) | a ∈ A} — diagonal (identity) on A. Units: unitless. R^{+} = ⋃_{n=1}^{∞} R^{n} and R^{*} = ⋃_{n=0}^{∞} R^{n} with R^{0} = Δ_A and R^{n+1} = R^{n} ∘ R — transitive and reflexive-transitive closures. Symbols: R^{n} = n-fold composition. Units: unitless. M_R[i,j] = 1 ⇔ (i,j) ∈ R, else 0 — adjacency matrix for finite relation. Symbols: M_R, indices i,j. Units: unitless.

Worked examples

  1. Determine properties. Let A={1,2,3} and R={(1,1),(2,2),(3,3),(1,2),(2,1)}. Steps:

    • Reflexive? Check if (1,1),(2,2),(3,3) all present: yes → reflexive.
    • Symmetric? For each (a,b) check (b,a): (1,2) present and (2,1) present; all diagonal pairs symmetric; so yes → symmetric.
    • Antisymmetric? Antisymmetry requires (a,b) and (b,a) ⇒ a=b. Here (1,2) and (2,1) with 1≠2 exist, so not antisymmetric.
    • Transitive? Check: (1,2) and (2,1) ⇒ (1,1) must be in R (it is). (2,1) and (1,2) ⇒ (2,2) (it is). No other nontrivial chains; so transitive holds. Conclusion: R is an equivalence relation (reflexive, symmetric, transitive) and partitions A into classes: [1]={1,2}, [2]={1,2}, [3]={3}. Final answer: R is an equivalence relation; equivalence classes {1,2} and {3}.
  2. Equivalence modulo 4 on integers (standard model answer): Define a ~ b iff 4 | (a − b). Verify reflexive: 4 | 0 so a ~ a. Symmetric: if 4 | (a − b) then 4 | (b − a). Transitive: if 4 | (a − b) and 4 | (b − c) then 4 | (a − c). Equivalence classes: representatives 0,1,2,3 give classes [0]={…,−8,−4,0,4,8,…} etc. Diagram: draw 4 labelled boxes for classes; show they partition Z.

  3. Partial order and Hasse diagram: Let A={1,2,3,6} with divisibility relation |. Pairs: 1 divides all, 2 divides 6, 3 divides 6, others as per divisibility. Check reflexive: yes. Antisymmetric: if a|b and b|a then a=b. Transitive: yes. Hasse diagram (draw as instructed):

    • Draw node 1 lowest, nodes 2 and 3 on next level (left and right), node 6 at top.
    • Draw edge 1–2, 1–3, 2–6, 3–6. Do not draw 1–6 (transitive). Label nodes with numbers. This is a poset; 2 and 3 are incomparable.

Common mistakes

  • When proving partitions from equivalence, assuming nonempty intersection implies equality without using symmetry+transitivity steps.
  • Drawing Hasse diagrams and forgetting to remove transitive edges (students often draw all edges and call it a Hasse diagram).
  • Using composition order inconsistently; state the convention before working examples.
  • For matrix representation, indexing mismatch: specify row = domain element, column = range element.

For your exam

Typical question types:

  • Definitions and examples: give definitions (reflexive, symmetric, antisymmetric, transitive) and provide counterexample for a false implication.
  • Short proofs: prove statements like "equivalence classes form a partition" or "asymmetric ⇒ antisymmetric and irreflexive." Full-marks answers must state assumptions, proceed with clear universal quantifier reasoning (∀, ∃), and conclude explicitly.
  • Derivations: show how to compute transitive closure or reflexive closure; show relationship between R, R^{-1}, R^{*}.
  • Numericals/diagrams: given a finite relation, check properties; draw digraph and Hasse diagram (label nodes; omit transitive edges in Hasse diagram); give adjacency matrix.
  • Algorithms: describe or trace Warshall's algorithm for transitive closure (topic later in course list). A full answer states initial matrix and each iteration clearly.

What to include for full marks: clear definitions with set quantifiers, explicit checks for each property, correct conventions for composition and orderings, and neatly labelled diagrams with explanation.

Quick check

  1. Give the definition of antisymmetric relation in symbolic form.
  2. If R is an equivalence relation on A and a ∈ A, what is the equivalence class [a]? Give one key property of equivalence classes.
  3. For the set {1,2,3} with relation R={(1,2),(2,3)}, is R transitive? Explain briefly.

Answers: 1) ∀a,b ∈ A: [(a,b) ∈ R and (b,a) ∈ R] ⇒ a=b. 2) [a]={x ∈ A | (a,x) ∈ R}; classes are either disjoint or equal and their union is A. 3) No: because (1,2) and (2,3) ∈ R but (1,3) ∉ R, so not transitive.

Notes for the reviewer: I wrote standard conventions but explicitly stated the composition convention used. I was careful about matrix/digraph indexing and Hasse diagram rules. Where I am unsure I have listed checks below.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?