Symmetric relation

A symmetric relation is a relation on a set that relates every pair of distinct elements either both ways or not at all. Along with reflexivity and transitivity, symmetry is one of the defining properties of an equivalence relation.

A relation \(R\) on a set \(A\) is symmetric if and only if for every distinct pair \(a, b \in A\): $$aRb \iff bRa$$

Notice that this definition is a universal statement. To prove symmetry, you must show that for every two distinct elements in a pair, they are either both related to each other, or both not related. In simple terms, you just need to show that reversing the roles of the two elements in the relation does not change whether the relation holds true or not.

Marriage is an example of a symmetric relation on a set of people. Person \(1\) being married to Person \(2\) implies that Person \(2\) is married to Person \(1\), and conversely. (Under most legal systems.)

To disprove symmetry, you only need to come up with one pair of distinct elements where order matters. More exactly, find two distinct elements \(a, b\) such that \(aRb\), but \(b \not R a.\)

Contents

Anti-symmetry

An anti-symmetric relation is a relation on a set that either goes one way or not at all.

A relation \(R\) on a set \(A\) is anti-symmetric if and only if for every distinct pair \(a, b \in A\): $$a \not R b \lor b \not R a$$
⚠ This cannot be stressed enough: anti-symmetry is not the logical opposite of symmetry! Symmetry and anti-symmetry are both sort of "extreme" properties for a relation to have. It is possible for a relation to be neither symmetric nor anti-symmetric, because some relations may go both ways, and some may not.

This is also a universal statement. To prove anti-symmetry, you must show that for every two distinct elements in a pair, the relation only goes one way, or does not exist between them at all. It would even suffice to show that two elements being related implies that they are the same element, since their distinctness is part of the definition of anti-symmetry.

Parenthood is an example of an anti-symmetric relation on a set of people. Person \(1\) being the parent of Person \(2\) implies that Person \(2\) is the child of Person \(1\), and therefore Person \(2\) cannot also be the parent of Person \(1.\)

To disprove anti-symmetry, you only need to come up with one pair of elements where order doesn't matter. More exactly, find two elements \(a, b\) such that \(aRb\) and \(bRa.\)

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