Orientation
Relations, Functions and Ordinals: a Working Reference
A working reference for the relational and functional apparatus the subject assumes: n-ary relations, inverses, relational product, injections and surjections, and the ordinal notation used in transfinite constructions.
Learning objectives
- Compute relational products and inverses
- Use the relational product to state congruence permutability
- Apply ordinal indexing in transfinite generation arguments
Relations
An n-ary relation on a set A is a subset of An. When n = 2 it is called a binary relation on A.
Two derived operations on binary relations are used constantly:
- Inverse. The inverse rˇ of a binary relation r on A is defined by ⟨a, b⟩ ∈ rˇ if and only if ⟨b, a⟩ ∈ r.
- Relational product. The product r ∘ s holds of ⟨a, b⟩ exactly when there is some c with ⟨a, c⟩ ∈ r and ⟨c, b⟩ ∈ s.
Congruence permutability — the condition θ ∘ φ = φ ∘ θ for all congruences — is one of the most consequential properties an algebra can have, and it is stated purely in terms of this operation. Groups and rings are congruence-permutable; lattices are not.
Functions
A function f from A to B, written f: A → B, is a subset of A × B such that each a ∈ A pairs with exactly one b ∈ B.
| Property | Condition | Notation used |
|---|---|---|
| Injective | f(a1) = f(a2) implies a1 = a2 | one-to-one |
| Surjective | for every b there is a with f(a) = b | onto |
| Bijective | both of the above | one-to-one and onto |
| Image of a set | α(A) — the direct image | α(A) |
| Preimage | α−1(A) — the inverse image | α−1(A) |
The source composes functions in the order that makes the relational product natural. When reading proofs that mix function composition with relational products, check the order rather than assuming it.
Kernels — the bridge to congruences
For f: A → B, the kernel ker(f) is the binary relation on A holding of ⟨a1, a2⟩ exactly when f(a1) = f(a2).
The kernel of any function is an equivalence relation. The central observation of the subject — and the content of the first isomorphism theorem — is that the kernel of a homomorphism is not merely an equivalence relation but a congruence, and that every congruence arises this way.
Ordinals and transfinite indexing
Ordinals appear in one recurring pattern: generating a subuniverse or a congruence by iterating a closure step until nothing new appears.
Because every basic operation takes finitely many arguments, any element produced at a stage beyond ω already had all its arguments present at some finite stage. This is exactly why Sub(A) and Con(A) are algebraic lattices, and it is the single most-used consequence of finitary arity in the whole subject.
Frequently asked questions
Why insist that operations be finitary?
Because finitary arity is what makes the generation process close at stage ω, which in turn makes Sub(A) and Con(A) algebraic lattices. Infinitary algebras exist and are studied, but they lose this property and with it much of the structure theory.
Is the relational product associative?
Yes, for binary relations on a set. It is not commutative in general — and the question of when it commutes for congruences is precisely the permutability condition that Mal'cev conditions characterise.
Source. S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, The Millennium Edition — a corrected re-typesetting of Springer-Verlag Graduate Texts in Mathematics 78 (1981). Section Preliminaries, book pages 1-4.
This page is an original exposition prepared for the KEVOS® knowledge library. It restates and reorganises mathematical results; it is not a reproduction of the source text.