Reflexive, irreflexive, symmetric, asymmetric, antisymmetric, transitive, and connex relations on a set

Let $A$ be a set and let $R$ be a relation on $A$, that is $R\subseteq A\times A$ (Relation, $\mathrm{dom}R$, $\mathrm{ran}R$, $\mathrm{fld}R$, and the specialisations "relation from $A$ to $B$" and "relation on $A$", The Cartesian product $A\times B:=\{z\in \mathcal{P}(\mathcal{P}(A\cup B)):\mathrm{\exists }a\in A\mathrm{\exists }b\in Bz=(a,b)\}$). Then $R$ is:

• reflexive on $A$ when $(a,a)\in R$ for every $a\in A$;
• irreflexive when $(a,a)\mathrm{\notin }R$ for every $a\in A$;
• symmetric when $(a,b)\in R$ implies $(b,a)\in R$, for all $a,b\in A$;
• asymmetric when $(a,b)\in R$ implies $(b,a)\mathrm{\notin }R$, for all $a,b\in A$;
• antisymmetric when $(a,b)\in R$ and $(b,a)\in R$ imply $a=b$, for all $a,b\in A$;
• transitive when $(a,b)\in R$ and $(b,c)\in R$ imply $(a,c)\in R$, for all $a,b,c\in A$;
• connex on $A$ when, for all $a,b\in A$, $(a,b)\in R$ or $(b,a)\in R$.

Reflexivity and irreflexivity have short forms in terms of the identity relation ${\mathrm{\Delta }}_A$ of The identity relation ${\mathrm{\Delta }}_A=\{(a,b)\in A\times A:a=b\}$ and the membership relation ${\in }_A=\{(a,b)\in A\times A:a\in b\}$, because the elements of ${\mathrm{\Delta }}_A$ are exactly the pairs $(a,a)$ with $a\in A$: $R$ is reflexive on $A$ if and only if ${\mathrm{\Delta }}_A\subseteq R$ (Subset $x\subseteq y$, proper subset $x⊊y$, and the separation notation $\{z\in x:\phi (z)\}$), and irreflexive if and only if $R$ and ${\mathrm{\Delta }}_A$ have no common element.

• Reflexivity and connexity mention $A$; the others do not. Whether $R$ is symmetric, asymmetric, antisymmetric or transitive depends on $R$ alone, whereas "reflexive on $A$" and "connex on $A$" depend on the ambient set: the empty relation is reflexive on $\mathrm{\varnothing }$ and on no other set. The qualifier is therefore kept in the name of those two.

• "Total" is ambiguous, "connex" is not. The connex property above is also called total in much of the literature, but "total relation" is used elsewhere for the unrelated condition that every element of $A$ is related to something. Only "connex" is used here for the property defined above.

• The named combinations, and the exact agreement with Partial order and partially ordered set. That item names its structures in terms of a relation $\le$ on a set $P$, and each of its clauses is one of the properties above applied to $\le$, so the two vocabularies describe one set of conditions and not two:

  • a partial order on $P$ is a relation on $P$ satisfying its clauses (R), (A) and (T), which are reflexivity on $P$, antisymmetry and transitivity as defined above, quantified over the same set $P$;
  • the strict order $x<y:⟺x\le y$ and $x\mathrm{\ne }y$ associated there with a partial order $\le$ is the relation $\le \setminus {\mathrm{\Delta }}_P$ of the properties above, and it is irreflexive and transitive; that identification and the fact that nothing is lost in passing between the two presentations are proved in On a set $A$, $R\mapsto R\setminus {\mathrm{\Delta }}_A$ and $S\mapsto S\cup {\mathrm{\Delta }}_A$ are mutually inverse bijections between the partial orders on $A$ and the irreflexive, transitive relations on $A$; $R\setminus {\mathrm{\Delta }}_A$ is the strict order of $R$, and every irreflexive transitive relation is asymmetric, whose clause on asymmetry also reconciles the two usual definitions of a strict order;
  • two elements $x,y\in P$ are comparable there when $x\le y$ or $y\le x$, so a relation on $A$ is connex on $A$ exactly when every two elements of $A$ are comparable;
  • consequently what that item calls a total order — a partial order in which every two elements are comparable — is a relation on $P$ that is reflexive on $P$, antisymmetric, transitive and connex on $P$. "Connex" here and "total order" there are therefore the same condition read twice: connexity is the single extra clause that turns a partial order into a total one, and it is the connex reading of the word total, never the left-total one warned against above.

  Reflexive on $A$, symmetric and transitive is what Equivalence relation, equivalence class, and the quotient set $A\mathrm{/}\sim$ calls an equivalence relation.