Lecture
A symmetric relation — is a type of binary relation . Formally, a binary relation R over a set X is symmetric if: [ 1 ]
where the notation aRb means that ( a , b ) ∈ R.
An example is the relation «equals», because if a = b is true, then b = a is also true. If R T represents the converse relation to R , then R is symmetric if and only if R = R T. [ 2 ]
Symmetry, along with reflexivity and transitivity , are the three defining properties of an equivalence relation . [ 1 ]
By definition, a nonempty relation cannot be both symmetric and asymmetric (where, if a is related to b , then b cannot be related to a (in the same way)). However, a relation can be neither symmetric nor asymmetric, which is the case for «less than or equal to» and «preys on»).
Symmetric and antisymmetric (where the only way to relate a to b and b to a — is if a = b ) are actually independent of each other, as these examples show.
| Symmetric | Not symmetric | |
| Antisymmetric | equality | divides , less than or equal to |
| Not antisymmetric | congruence in modular arithmetic | // (integer division), most nontrivial permutations |
| Symmetric | Not symmetric | |
| Antisymmetric | is the same person as, and is married to. | is the plural of |
| Not antisymmetric | is a full biological sibling of | preys on |
| Elements | Any | Transitive | Reflexive | Symmetric | Preorder | Partial order | Total preorder | Total order | Equivalence relation |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
| 2 | 16 | 13 | 4 | 8 | 4 | 3 | 3 | 2 | 2 |
| 3 | 512 | 171 | 64 | 64 | 29 | 19 | 13 | 6 | 5 |
| 4 | 65,536 | 3,994 | 4096 | 1024 | 355 | 219 | 75 | 24 | 15 |
| n | 2 n 2 | 2 n ( n −1) | 2 n ( n +1)/2 | ∑n k =0 k ! S ( n , k ) |
n ! | ∑n k =0 S ( n , k ) |
|||
| OEIS | A002416 | A006905 | A053763 | A006125 | A000798 | A001035 | A000670 | A000142 | A000110 |
Note that S ( n , k ) denotes the Stirling numbers of the second kind .
Comments