Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 38 ยท Relations and Functions

Properties of Relations

Learn the four key properties of relations: reflexive, symmetric, antisymmetric and transitive. Test them with examples, proofs and Python checkers.

A relation is just a set of pairs, but the useful ones have structure. Four properties describe most of that structure: reflexive, symmetric, antisymmetric and transitive. In the next chapter, relations with the right combination become equivalence relations (a way to say "same kind of thing") and partial orders (a way to say "comes before").

In this lesson let R be a relation on a set A, that is, R โІ A ร— A. We write a R b for (a, b) โˆˆ R.

Reflexive

R is reflexive if every element is related to itself:

Text
for all a โˆˆ A:  a R a

"Is equal to" and "is less than or equal to" are reflexive. "Is less than" is not reflexive, since 3 < 3 is false. In the matrix picture, a reflexive relation has all 1s on the main diagonal. In the arrow picture, every element has a loop.

Symmetric

R is symmetric if whenever a R b, also b R a:

Text
for all a, b โˆˆ A:  a R b  implies  b R a

"Is a sibling of" and "has the same birthday as" are symmetric. "Is less than" and "divides" are not. A symmetric relation has a matrix that is a mirror image across the main diagonal; equivalently, R = Rโปยน.

Antisymmetric

R is antisymmetric if the only way to have both a R b and b R a is when a = b:

Text
for all a, b โˆˆ A:  (a R b and b R a)  implies  a = b

"Is less than or equal to" is antisymmetric: if a โ‰ค b and b โ‰ค a then a = b. "Divides" on the positive integers is antisymmetric too. "Equal to" is both symmetric and antisymmetric.

Antisymmetric does not mean "not symmetric". Equality is both. A relation like {(1, 2), (2, 1)} is symmetric and not antisymmetric. A relation like {(1, 2)} is antisymmetric and not symmetric. The empty relation is both.

Transitive

R is transitive if a link from a to b followed by a link from b to c forces a link from a to c:

Text
for all a, b, c โˆˆ A:  (a R b and b R c)  implies  a R c

"Is less than", "is a subset of", "is an ancestor of" and "divides" are transitive. "Is a friend of" and "is perpendicular to" are not, because if a โŠฅ b and b โŠฅ c then a is parallel to c, not perpendicular. In terms of composition, R is transitive exactly when R โˆ˜ R โІ R.

Summary table for familiar relations

Relation Reflexive Symmetric Antisymmetric Transitive
= on โ„ yes yes yes yes
โ‰ค on โ„ yes no yes yes
< on โ„ no no yes yes
divides on โ„•โบ yes no yes yes
โІ on subsets yes no yes yes
"differs by exactly 1" on โ„ค no yes no no
"same remainder mod 3" on โ„ค yes yes no yes

(Check the "<" row: it is vacuously antisymmetric because a < b and b < a never both hold.)

Testing the properties by computer

On a finite set you can check each property by brute force. The checkers below are direct translations of the definitions.

Python Property checkers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Proving a property

Claim. The relation ~ on โ„ค defined by a ~ b when a โˆ’ b is divisible by 3 is reflexive, symmetric and transitive.

  • Reflexive. a โˆ’ a = 0, and 0 is divisible by 3.
  • Symmetric. If a โˆ’ b = 3k then b โˆ’ a = 3(โˆ’k), also divisible by 3.
  • Transitive. If a โˆ’ b = 3k and b โˆ’ c = 3m then a โˆ’ c = (a โˆ’ b) + (b โˆ’ c) = 3(k + m).

To disprove a property you only need one counterexample. For "differs by exactly 1" on โ„ค: 1 and 2 are related, 2 and 3 are related, but 1 and 3 are not, so it is not transitive.

Closures (a glimpse)

If a relation lacks a property, you can often add the fewest pairs possible to repair it. The transitive closure adds exactly the pairs forced by chains. For "is a parent of", the transitive closure is "is an ancestor of". The program below computes closures on small relations.

Python Repairing a relation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which relation on the integers is reflexive?

    a โ‰ค a holds for every a. The other two never relate a to itself.
  2. 2. The relation {(1, 2), (2, 1), (1, 1)} on {1, 2} is:

    It is symmetric, and (1, 2), (2, 1) show it is not antisymmetric since 1 โ‰  2.
  3. 3. Why is 'is perpendicular to' (for lines in a plane) not transitive?

    A counterexample is enough to disprove transitivity.
  4. 4. Which statement is true about '<' on the real numbers?

    a < b and b < a never hold together, so antisymmetry holds vacuously. It is transitive but not reflexive or symmetric.

Summary

  • Reflexive: a R a for all a. Symmetric: a R b โ‡’ b R a. Antisymmetric: a R b and b R a force a = b. Transitive: a R b and b R c force a R c.
  • Antisymmetric is not the opposite of symmetric.
  • Prove a property for arbitrary elements; disprove it with a single counterexample.
  • The closure of a relation adds the fewest pairs needed to gain a property.

Next: Functions