Showing content from https://en.wikipedia.org/wiki/Symmetric_relation below:
Symmetric relation - Wikipedia
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 ≠ ∅ : {\displaystyle S\neq \varnothing :} a R b ⇒ b R a {\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}} a R b and b R a ⇒ a = b {\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}} a ≠ b ⇒ a R b or b R a {\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}} min S exists {\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}} a ∨ b exists {\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}} a ∧ b exists {\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}} a R a {\displaystyle aRa} not a R a {\displaystyle {\text{not }}aRa} a R b ⇒ not b R a {\displaystyle {\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 Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively.
All definitions tacitly require the homogeneous relation R {\displaystyle R} be transitive: 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.
A symmetric relation is a type of binary relation. Formally, a binary relation R over a set X is symmetric if:[1]
-
∀ a , b ∈ X ( a R b ⇔ b R a ) , {\displaystyle \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 RT represents the converse of R, then R is symmetric if and only if R = RT.[2]
Symmetry, along with reflexivity and transitivity, are the three defining properties of an equivalence relation.[1]
-
-
-
-
-
-
Outside mathematics[edit]
- "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[edit] Symmetric 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.
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
- 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, 2n(n+1)/2.[3]
Note that S(n, k) refers to Stirling numbers of the second kind.
- ^ If xRy, the yRx by symmetry, hence xRx by transitivity. The proof of xRy ⇒ yRy is similar.
RetroSearch is an open source project built by @garambo
| Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4