Symmetric relation

A symmetric relation is a type of binary relation. Formally, a binary relation R over a set X is symmetric if:^[1]

\forall a,b\in X(aRb\Leftrightarrow bRa),

where the notation aRb means that (a, b) ∈ R.

An example is the relation "is equal to", because if a = b is true then b = a is also true. If R^T represents the converse of 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]

Examples

In mathematics

"is equal to" (equality) (whereas "is less than" is not symmetric)
"is comparable to", for elements of a partially ordered set
"... and ... are odd":

Outside mathematics

"is married to" (in most legal systems)
"is a fully biological sibling of"
"is a homophone of"
"is a co-worker of"
"is a teammate of"

Relationship to asymmetric and antisymmetric relations

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 "is less than or equal to" and "preys on").

Symmetric and antisymmetric (where the only way a can be related to b and b be related to a is if a = b) are actually independent of each other, as these examples show.

Properties

A symmetric and transitive relation is always quasireflexive.^[a]
One way to count the symmetric relations on n elements, that in their binary matrix representation the upper right triangle determines the relation fully, and it can be arbitrary given, thus there are as many symmetric relations as n × n binary upper triangle matrices, 2^n(n+1)/2.^[3]

Note that S(n, k) refers to Stirling numbers of the second kind.

Notes

^ If xRy, the yRx by symmetry, hence xRx by transitivity. The proof of xRy ⇒ yRy is similar.

References

^ a b Biggs, Norman L. (2002). Discrete Mathematics. Oxford University Press. p. 57. ISBN 978-0-19-871369-2.
^ "MAD3105 1.2". Florida State University Department of Mathematics. Florida State University. Retrieved 30 March 2024.
^ Sloane, N. J. A. (ed.). "Sequence A006125". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.