Relation composition

Relation composition combines two relations on a set to form a new relation on that set that consists of pairs of elements in which both elements are related to some intermediate through the original relations.

For relations \(R\) and \(S\) on a set \(A\), their composed relation \(S \circ R\), in which \(R\) is applied first, then \(S\), is defined as: $$S \circ R = \set{(a, c) : (\exists b \in A)(aRb \land bSc)}$$

If that sounded confusing, let me simplify: the new relation \(S \circ R\) is the set of all ordered pairs \((a, c)\) where a path exists from \(a\) to \(c\) via the intermediate \(b.\) This particular path connects \(a\) to \(b\) under relation \(R\), then \(b\) to \(c\) under relation \(S\), thereby linking \(a\) and \(c\) under a new composed relation.

For example, consider the two relations \(B\) "is a brother of" and \(P\) "is a parent of" on a set of people. Their composed relation \(P \circ B\) turns out to be the relation "is an uncle of." This is because an uncle is defined as the brother of a parent. Notice the order in which the relations are composed is important. An uncle is not defined as the parent of someone's brother... that's just a long-winded way of saying parent.

Logic & Proofs
Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form
Set Theory
Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof
Functions
Function • Floor function • Ceiling function • Inverse function
Algorithms
Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm
Relations
Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class
Number Theory
Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm
Induction
Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition
Combinatorics
Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle
Graph Theory
Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm
Recursion
Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort