Movatterモバイル変換

[0]ホーム

Jump to content

Symmetric relation

Edit links

From Wikipedia, the free encyclopedia

Type of binary relation

Transitive binary relations

	Symmetric	Antisymmetric	Connected	Well-founded	Has joins	Has meets	Reflexive	Irreflexive	Asymmetric
			Total, Semiconnex					Anti- reflexive
Equivalence relation	Y	✗	✗	✗	✗	✗	Y	✗	✗
Preorder(Quasiorder)	✗	✗	✗	✗	✗	✗	Y	✗	✗
Partial order	✗	Y	✗	✗	✗	✗	Y	✗	✗
Total preorder	✗	✗	Y	✗	✗	✗	Y	✗	✗
Total order	✗	Y	Y	✗	✗	✗	Y	✗	✗
Prewellordering	✗	✗	Y	Y	✗	✗	Y	✗	✗
Well-quasi-ordering	✗	✗	✗	Y	✗	✗	Y	✗	✗
Well-ordering	✗	Y	Y	Y	✗	✗	Y	✗	✗
Lattice	✗	Y	✗	✗	Y	Y	Y	✗	✗
Join-semilattice	✗	Y	✗	✗	Y	✗	Y	✗	✗
Meet-semilattice	✗	Y	✗	✗	✗	Y	Y	✗	✗
Strict partial order	✗	Y	✗	✗	✗	✗	✗	Y	Y
Strict weak order	✗	Y	✗	✗	✗	✗	✗	Y	Y
Strict total order	✗	Y	Y	✗	✗	✗	✗	Y	Y
	Symmetric	Antisymmetric	Connected	Well-founded	Has joins	Has meets	Reflexive	Irreflexive	Asymmetric
Definitions, for all $a, b {\displaystyle a,b}$ and $S\neq \varnothing :$	${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$	${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$	${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$	${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$	${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$	${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$	$a R a {\displaystyle aRa}$	${\text{not }}aRa$	${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$

Y indicates that the column's property is always true for the row's term (at the very left), while✗ indicates that the property is not guaranteed
in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric,
is indicated by Green tick

Y in the "Symmetric" column and✗ in the "Antisymmetric" column, respectively.

All definitions tacitly require thehomogeneous relation $R {\displaystyle R}$ betransitive: for all $a, b, c, {\displaystyle a,b,c,}$ if $a R b {\displaystyle aRb}$ and $b R c {\displaystyle bRc}$ then $a R c . {\displaystyle aRc.}$
A term's definition may require additional properties that are not listed in this table.

Asymmetric relation is a type ofbinary relation. Formally, a binary relationR over asetX is symmetric if:^[1]

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

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

An example is the relation "is equal to", because ifa =b is true thenb =a is also true. IfR^T represents theconverse ofR, thenR is symmetric if and only ifR =R^T.^[2]

Symmetry, along withreflexivity andtransitivity, are the three defining properties of anequivalence relation.^[1]

Examples

[edit]

In mathematics

[edit]

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

Outside mathematics

[edit]

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

Relationship to asymmetric and antisymmetric relations

[edit]

By definition, a nonempty relation cannot be both symmetric andasymmetric (where ifa is related tob, thenb cannot be related toa (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 andantisymmetric (where the only waya can be related tob andb be related toa is ifa =b) are actually independent of each other, as these examples show.

Mathematical examples
	Symmetric	Not symmetric
Antisymmetric	equality	divides, less than or equal to
Not antisymmetric	congruence inmodular arithmetic	// (integer division), most nontrivialpermutations

Non-mathematical examples
	Symmetric	Not symmetric
Antisymmetric	is the same person as, and is married	is the plural of
Not antisymmetric	is a full biological sibling of	preys on

Properties

[edit]

A symmetric andtransitive relation is alwaysquasireflexive.^[a]
One way to count the symmetric relations onn 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 asn ×n binary upper triangle matrices, 2^n(n+1)/2.^[3]

Number ofn-element binary relations of different types
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	4,096	1,024	355	219	75	24	15
n	2^n²		2ⁿ⁽ⁿ⁻¹⁾	2^n(n+1)/2			∑ⁿ _k=0k!S(n,k)	n!	∑ⁿ _k=0S(n,k)
OEIS	A002416	A006905	A053763	A006125	A000798	A001035	A000670	A000142	A000110

Note thatS(n,k) refers toStirling numbers of the second kind.

Notes

[edit]

^IfxRy, theyRx by symmetry, hencexRx by transitivity. The proof ofxRy ⇒yRy is similar.

References

[edit]

^^a ^bBiggs, 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. Retrieved30 March 2024.
^Sloane, N. J. A. (ed.)."Sequence A006125".TheOn-Line Encyclopedia of Integer Sequences. OEIS Foundation.

Movatterモバイル変換

Examples

In mathematics

Outside mathematics

Relationship to asymmetric and antisymmetric relations

Properties

Notes

References

See also