4 Matching Annotations
1. May 2020
2. rickneff.github.io rickneff.github.io
1. R is antisymmetric iff ∀∀\forall x ∀∀\forall y [xRy ∧ yRx → x = y].

For any x and y in a set, if x is related to y and y is related to x, for it to be antisymmetric x must equal y.

Example:

We have the set [1 2 3].

For a relation to be antisymmetric, if we have (1 2) we must not have (2 1). In other words, if there is any symmetry it must be between the same elements, such as (1 1).

Additionally, if we do not have any element related to any element it is vacuously antisymmetric.

2. R is reflexive iff ∀∀\forall x [x ∈∈\in U → xRx]

For each x in the set, x must be related to x for the relation to be reflexive. In other words, each element must be related to itself.

Example:

We have the set [1 2 3].

For a relation to be reflexive, it must have (1 1), (2 2), and (3 3).

3. R is symmetric iff ∀∀\forall x ∀∀\forall y [xRy → yRx].

For any x and y in a set, if x is related to y then y must be related to x for the relation to be symmetric.

Example:

We have the set [1 2 3].

For a relation to be symmetric, if you have (1 2) you must have (2 1). Equally, (1 1) is symmetric.

4. R is transitive iff ∀∀\forall x ∀∀\forall y ∀∀\forall z [xRy ∧ yRz → xRz].

For any x, y, and z in a set, if x is related to y and y is related to z, then z must also be related to z for the relation to be transitive.

Example:

We have the set [1 2 3].

For a relation to be transitive, if we have (1 2) and (2 3), we must have (1 3). Likewise, any reflexive pair is transitive.

Additionally, if we do not have xRy and yRz (even if x, y, or z are the same element), the relation is vacuously transitive.