6
$\begingroup$

We know that a partial order relation is a relation which is reflexive , antisymmetric and transitive. Example: (x,y) belongs to R iff x=y. For A={1,2,3}, we get R= {(1,1), (2,2), (3,3)}. Now R is reflexive, transitive and also anti-symmetric (if xRy and yRx then x=y).

So equality should be a partial order relation. Is it so? If yes, then why many authors don't mention it as an example of partial order relation. I only find <= , >= , divides, integral multiple and inclusion as an example in most of the books. I am confused.

$\endgroup$
6
  • 7
    $\begingroup$ Yes, it is. I suspect that the main reason that it’s often not explicitly mentioned as an example of a partial order is that it’s quite atypical, since in general partial orders are not symmetric. Also, it will certainly be given as an example of an equivalence relation — it is the prototypical one, after all — and some authors may fear that exhibiting it as a partial order as well will confuse many students unless the author carefully explains that it is both, which takes space that the author might prefer to spend on something else. And of course an author might want to leave it as an ... $\endgroup$ Commented Sep 25, 2013 at 6:43
  • $\begingroup$ ... exercise to prove that equality on any set is a partial order on that set. $\endgroup$ Commented Sep 25, 2013 at 6:43
  • 2
    $\begingroup$ Equality is the smallest partial order in some sense. $\endgroup$ Commented Sep 25, 2013 at 6:53
  • $\begingroup$ Thank you @brian. You cleared my doubt. $\endgroup$ Commented Sep 25, 2013 at 6:53
  • $\begingroup$ @user221458: You’re welcome. $\endgroup$ Commented Sep 25, 2013 at 6:55

1 Answer 1

1
$\begingroup$

I see I'm quite late to the party, but to cut down on the number of unanswered questions on the site, here we go!

As mentioned in the comments above, an equality relation is unique among relations in some very specific ways. I'll elucidate a few of them here.

First of all, given a set $A,$ I will denote the equality relation on $A$ by $$[=]_A:=\bigl\{\langle x,y\rangle\in A^2:x=y\bigr\},$$ or equivalently, $$[=]_A=\bigl\{\langle a,a\rangle:a\in A\bigr\}.$$


With the notation above in mind, suppose that $R$ is any relation at all, and that happens to be reflexive on some set $A.$ By definition, then, for any $a\in A,$ we have that $\langle a,a\rangle\in R.$ Since this holds for all $a\in A,$ then we have $$[=]_A\subseteq R$$ for any relation $R$ that happens to be reflexive on the set $A.$ (The converse also readily holds--if $[=]_A\subseteq R$ for some relation $R$ and some set $A,$ then $R$ is reflexive on $A$.)

Note in particular that since, equivalence relations and (nonstrict) partial orders on a set $A$ are by definition reflexive on $A,$ then any such relation contains $[=]_A$ as a subset. This property is sometimes expressed by saying that equality is the smallest reflexive relation/equivalence relation/partial order relation on a given set, as copper.hat mentioned in the comments above.


We can say even more. Suppose that $R$ is a relation with domain $A,$ and that it happens to be both symmetric and antisymmetric. Then $R$ is simply $[=]_A,$ as it turns out!

Indeed, on the one hand, suppose that $a\in A,$ so that by definition of the domain of a relation, there is some $b$ such that $\langle a,b\rangle\in R.$ Since $R$ is symmetric and $\langle a,b\rangle\in R,$ then $\langle b,a\rangle\in R.$ Since $R$ is antisymmetric, we therefore have $a=b,$ and so $\langle a,a\rangle=\langle a,b\rangle\in R.$ Thus, $[=]_A\subseteq R.$

On the other hand, take any $\langle a,b\rangle\in R,$ so that $a\in A$ by definition of the domain of a relation. Also, $\langle b,a\rangle\in R$ by symmetry, whence $a=b$ by antisymmetry, and so $\langle a,b\rangle=\langle a,a\rangle\in[=]_A.$ Thus, $R\subseteq[=]_A.$

Some immediate corollaries of this include:

  • A relation that is both symmetric and antisymmetric is necessarily an equivalence relation on its domain.
  • A relation that is both symmetric and antisymmetric is necessarily a (nonstrict) partial order relation on its domain.
  • An equality relation is the only kind of antisymmetric equivalence relation.
  • An equality relation is the only kind of symmetric partial order relation (as alluded to by Brian M. Scott in the comments above).

Other concepts that come up among partial orders are chains, branches and antichains. These concepts give us even more ways to characterize unique properties of equality relations among partial orders!

Formally, suppose $A$ is a set, $R$ a partial order on $A,$ and $S$ a subset of $A$.

  • We say that $S$ is a chain (with respect to $R$) in $A$ if for all $a,b\in S,$ we have $\langle a,b\rangle\in R$ or $\langle b,a\rangle\in R$--put another way, $R$ is a non-strict total order relation on $S.$ For short, we'll say such an $S$ is an $R$-chain in $A.$
  • We say that $S$ is a branch (with respect to $R$) in $A$ if $S$ is an $R$-chain in $A$ such that if $S'$ is any $R$-chain in $A,$ then either $S=S'$ or $S\not\subseteq S'$--put another way, $S$ is maximal (with respect to $\subseteq$) among $R$-chains in $A.$ For short, we'll say such an $S$ is an $R$-branch in $A.$
  • We say that $S$ is an antichain in $A$ with respect to $R$ if for all $a,b\in S$ with $a\neq b,$ we have $\langle a,b\rangle\notin R$ and $\langle b,a\rangle\notin R$--put another way, the elements of $S$ are pairwise incomparable with respect to $R.$ For short, we'll say such an $S$ is an $R$-antichain in $A.$

Then $[=]_A$ has some special properties with respect to these concepts, as well.

Suppose $R$ is a relation with a set $A$ as its domain and such that $A$ is also a codomain of $R,$ and further suppose that (i) every $R$-chain in $A$ is a subset of an $R$-branch of $A,$ and that (ii) for every $R$-branch $S$ in $A$ we have that $S$ has exactly one element. Equivalently, we are supposing that every $R$-chain of $A$ has cardinality either $0$ or $1.$ Then it turns out that $R$ is just $[=]_A.$ On the one hand, $[=]_A\subseteq R$ by reflexivity. To prove the other inclusion, we need only take any $\langle a,b\rangle\in R$ and show that $\langle a,b\rangle\in[=]_A.$ Indeed, we have $a\in R$ (by definition of domain), $b\in R$ (by definition of codomain), and therefore $\{a,b\}$ is an $R$-chain of $A,$ so by hypothesis must have cardinality $1$ (since it's non-empty), whence $a=b,$ and so $\langle a,b\rangle=\langle a,a\rangle\in[=]_A,$ as desired.

Upshot: $[=]_A$ is the only partial order on $A$ having no chains of cardinality greater than $1.$

Next, suppose that $R$ is a relation with a set $A$ as its domain and such that $A$ is also a codomain of $R,$ and further suppose that for every subset $S$ of $A,$ $S$ is an $R$-antichain of $A.$ Then once again, $R$ is just $[=]_A,$ with $[=]_A\subseteq R$ automatically by reflexivity. By our assumption about $A$ as the domain and as a codomain of $R,$ every element of $R$ is necessarily an element of $A\times A,$ so it remains only to exclude each element of $(A\times A)\setminus [=]_A$ from $R.$ Indeed, for any such element, say $\langle a,b\rangle,$ we have $a,b\in A$ and $a\neq b$ so since $\{a,b\}$ is an $R$-antichain in $A$ by hypothesis, then by definition of $R$-antichains in $A,$ we have $\langle a,b\rangle\notin R,$ as desired.

Upshot: $[=]_A$ is the only partial order on $A$ such that each subset of $A$ (and in particular, $A,$ itself) is an antichain in $A.$


Finally, to answer your question from the comments, let's explore what we can say about a situation in which an equality relation is a lattice order relation.

Take any set $A$ and suppose that it has the property that $A$ is a lattice under $[=]_A.$ What would that mean?

Well, by definition, it would mean that for any $a,b\in A,$ there exists a greatest lower bound $c$ of $\{a,b\}$ with respect to the partial order $[=]_A.$ That immediately makes $c$ a lower bound of $\{a,b\}$ with respect to the partial order $[=]_A,$ meaning that $\langle c,a\rangle\in[=]_A$ and $\langle c,b\rangle\in[=]_A.$ Consequently, $c=a$ and $c=b$, so $a=c$ and $c=b$ by the symmetric property of equality, so $a=b$ by the transitive property of equality. Since for all $a,b\in A$ we have that $a=b,$ that means an equality relation can only be a lattice order on a singleton or on the empty set. Indeed, even if we only require $[=]_A$ to make $A$ a join-semilattice or meet-semilattice, it still restricts $A$ to have no more than a single element.

Thus, if your definition of lattice happens to require that the underlying set have two or more elements, then the answer to whether the equality relation makes it a lattice is a firm "no." Otherwise, the answer is "it depends."

$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.