I am having a hard time understanding some things dealing with these relations. The five relations we are dealing with are reflexive, symmetric, transitive, irreflexive, and antisymmetric.

$R$ is reflexive is $xRx$ for all $x \in A$.

$R$ is symmetric if $xRy$ implies $yRx$ for all $x, y \in A$.

$R$ is transitive if $xRy$ and $yRz$ implies $xRz$ for all $x, y, z \in A$.

$R$ is irreflexive if $(x, x) \notin R$ for all $x \in A$.

$R$ is antisymmetric is $xRy$ and $yRx$ implies $x = y$ for all $x, y \in A$.

All of them make sense to me besides the last one.

The example in the book says to list all the properties that apply for the given relation: The "has a common national language with" relation on countries.

I am having trouble deciding which ones it has.

To me it makes sense that a country has a common national language with itself, so I think it's reflexive? Also, let's say you have two countries like the USA and England, it makes sense to me that it is symmetric since USA has a common national language with England and, vice verse, England has a common national language with the USA, but for some of the other examples I think it is symmetric when it is not so I am not certain here.

Transitive makes sense so that if country A has a common national language with country B, and country B has a common national language with country C, that country A has a common national language with country C.

Reflexive makes sense up above, but here is where I get confused since it makes sense for it to be irreflexive as well.

How can it not be antisymmetric as well? From my definitions above, aren't they the same thing?

  • $\begingroup$ The "has a common national language with" is not transitive. Suppose A has just English, B has English and Spanish, and C has just Spanish. A and C have no common national language. $\endgroup$ – TravisJ Apr 21 '15 at 0:35
  • $\begingroup$ A good example of irreflexive is the $\geq$ relation on real numbers. If $x\leq y$ and $y\leq x$ then $x=y$. Or, set containment $\subseteq$, if $A\subseteq B$ and $B\subseteq A$ then $A=B$. $\endgroup$ – TravisJ Apr 21 '15 at 0:35
  • $\begingroup$ I noticed I had an error. It should have read, "...England shares a common language with the USA." Fixed now. $\endgroup$ – generic user007 Apr 21 '15 at 0:37
  • $\begingroup$ @TravisJ I did not think of that. Thank you. I presumed there could only be one national language. $\endgroup$ – generic user007 Apr 21 '15 at 0:38
  • $\begingroup$ @DietDrPepsi, actually a lot of countries have multiple national languages... especially countries that were colonized by the British or French (a lot of Africa for example), and several European countries (Switzerland comes to mind, French, German, Italian--I think). $\endgroup$ – TravisJ Apr 21 '15 at 0:40

An example of an antisymmetric relation would be ordering on numbers. $x \le y$ and $y \le x$ imply $x=y$, for any $x$ and $y$.

$\le$ is also reflexive ($x\le x$ for all $x$) and transitive (if $x\le y$ and $y \le z$, then $x \le z$).
A relation which has these three properties (reflexive, transitive, antisymmetric) is called a partial order. (If for every $x, y \in A$ either $x\le y$ or $y \le x$, then we have a total order).

The strict order $\lt$ differs from $\le$ by being irreflexive (it is never the case that $x \lt x$) and asymmetric (not to be confused with antisymmetric; you cannot have both $x\lt y$ and $y \lt x$ at the same time, unlike $\le$.)

Equality is a symmetric relation: $y=x$ implies $x=y$. An equivalencce relation is one which, like $=$, is reflexive, transitive, and symmetric.

Regarding your example, the "common language" relation on countries is

  • reflexive (all countries share a common language with themselves);
  • not transitive, as illustrated by TravisJ's comment;
  • not antisymmetric. A counterexample would be the US and the UK. Both share a common language (English), but they are obviously not the same country.
  • In fact, the relation is actually symmetric, since if A shares a language with B, then B also shares a language with A.

On numbers define $xRy$ to mean any number dividing $x$ also divides $y$. Now what is the consequence when $aRb$ and $bRa$ are both true?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.