Reflexive relation

A reflexive relation is a relation on a set that relates every element of that set to itself. Along with symmetry and transitivity, reflexivity is one of the defining properties of an equivalence relation.

A relation \(R\) on a set \(A\) is reflexive if and only if for every \(a \in A\): $$aRa$$

Notice that this definition is a universal statement. To prove reflexivity, you must show that every element of the set is related to itself.

Divisibility is an example of a reflexive relation on \(\mathbb Z.\) Every integer evenly divides itself.

To disprove reflexivity, you only need to come up with one element that is not related to itself.

Contents

Anti-reflexivity

An anti-reflexive relation is a relation on a set that does not relate any element of that set to itself.

A relation \(R\) on a set \(A\) is anti-reflexive if and only if for every \(a \in A\): $$a \not Ra$$
⚠ This cannot be stressed enough: anti-reflexivity is not the logical opposite of reflexivity! Reflexivity and anti-reflexivity are both sort of "extreme" properties for a relation to have. It is possible for a relation to be neither reflexive nor anti-reflexive, because some elements may be related to themselves, and some may not.

This is also a universal statement. To prove anti-reflexivity, you must show that every element of the set is not related to itself.

The relation "is greater than" \((\gt)\) on \(\mathbb Z\) is anti-reflexive because no integer can be greater than itself.

To disprove anti-reflexivity, you only need to come up with one element that is related to itself.

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