STEP-BY-STEP LESSON · §8.2
Reflexivity, Symmetry, and Transitivity
Check reflexivity, symmetry, and transitivity separately.
Before you begin
Relations on Sets
A relation from A to B selects pairs (a,b) from A×B. Order matters: the first coordinate comes from A and the second from B.
R⊆A×B
Predicates and Quantified Statements I
P(x) is a condition whose truth depends on x. For P(x): x>2, specify allowed values first.
D={1,2,3}∀x∈D P(x) is true when the condition holds for every element of D. One violating element refutes it.
∀x∈D: x>2
∃x∈D P(x) needs at least one witness. For finite D, falsity can be established by checking every element.
∃x∈D: x>2
Symbols
- aRa
- an element is related to itself
- aRb ∧ bRc ⇒ aRc
- transitivity condition
Definitions and notation for this topic
Reflexive
∀a∈A: aRa
Every element of the underlying set is related to itself.
For every integer a, a≤a.
Separate glossary example
The relation ≤ on ℤ is reflexive.
Symmetric
∀a,b∈A: (aRb→bRa)
Whenever a is related to b, b is related to a.
Reversing the pair preserves this relationship.
Separate glossary example
The relation “has the same age as” is symmetric.
Transitive
∀a,b,c∈A: ((aRb∧bRc)→aRc)
Whenever aRb and bRc, it follows that aRc.
The requirement applies to every suitable triple of elements.
Separate glossary example
a≤b and b≤c imply a≤c.
Step by step
Step 1 / 6
Check the loops
Reflexivity requires aRa for every a∈A, including elements with no other arrows.
∀a∈A: aRa
One missing loop suffices to disprove reflexivity.
Worked example
Which of the three properties does ≤ on {1,2,3} have?
- Reflexive: 1≤1, 2≤2, 3≤3.
- Not symmetric: 1≤2 is true but 2≤1 is false. This is a specific violation.
- Transitive: if a≤b and b≤c, the order of numbers gives a≤c for any chosen a,b,c.
Optional self-check
On A={1,2}, is R={(1,2),(2,1)} transitive?
Show answer
No: 1R2 and 2R1 require 1R1, which is absent.