Concept
What do reflexivity, symmetry, and antisymmetry mean for endorelations?
Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk / Chapter 1
"Lots of the relations we care about are endorelations, or relations between a set and itself. Throughout this section, assume that R is the relation in question, and that it is defined from set A to set A. A relation R is reflexive if xRx for every x ∈ A. Other ordered pairs can also be in the relation, of course, but if we say it is reflexive, we are guaranteeing that every element is related to itself. “hasSeen” is almost certainly a reflexive relation, presuming that mirrors are relatively widespread in the world. “thinksIsBeautiful” is not reflexive, however: some people think themselves beautiful, and others do not. A relation is symmetric if xRy whenever yRx and vice versa. This does not mean that (x, y) is in the relation for every x and y—only that if (x, y) is in the relation, then (y, x) is guaranteed to also be in the relation. An example would be “hasShakenHandsWith.” If I have shaken hands with you, then you have shaken hands with me, period. A relation is antisymmetric if xRy whenever yRx and vice versa, unless x and y are the same. Put another way, if (x, y) is in the relation, then (y, x) cannot be, except when the two elements are the same. An example would be “isTallerThan.” If I am taller than you, then you cannot be taller than me. We could in fact be the same height, in which case neither pair would be in the relation, but in any event the two cannot coexist."
Related Ideas
- What are the reflexive, symmetric, antisymmetric, and transitive properties of the endorelation T?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What is transitivity, and how can it be tested in an explicit relation?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- Is H reflexive?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- Is H symmetric?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- Is H antisymmetric?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What properties does the outranks relation have?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What properties does the sameShirtColor relation have?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What are partial orders and partially ordered sets?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1