Let $R$, $S$ and $T$ be binary relations defined as follows

  • R is defined on $P(\mathbb{N})$ by $ARB$ if and only if $|A∩B| ≥ 2$
  • $S$ is defined on $Q$ by $x\mathbin{S}y$ if and only if $|x|=|y|$. (Note that |$q$| is defined to be the largest integer less than or equal to $q$. You can think of it is $q$ "rounded down".)
  • $T$ is defined on $\mathbb{N} \times \mathbb{N}$ by $(a,b)\mathbin{T}(c,d)$ if and only if $a≤c$ and $b≤d$.

State if any of $R,S$ and $T$ are equivalence relations or partial relations. If they are equivalence relations then describe the equivalence classes. If they are partial order relations then state whether they are total order relations or well order relation.

$R$ is reflexive, symmetric but not transitive. I am not sure if $R$ is anti-symmetric. So $R$ is neither an equivalence relation or partial order relation.

$S$ is reflexive, symmetric and transitive. I am not sure if it is anti-symmetric. If not $S$ is then an equivalence relationship. How do I define the equivalence classes?

$T$ is reflexive, anti-symmetric and transitive. So it is partial order relation of which it is well order relation I assume. I may be wrong so feel free to correct me.


1 Answer 1


The relation $R$ is not reflexive: take $A=\{1\}$; then $|A\cap A|=1<2$.

The relation $T$ is indeed a partial order, but is not a well-ordering, because, for instance, $\{(1,2),(2,1)\}$ has no minimum.

The relation $S$ is indeed an equivalence relation and it is not antisymmetric (the only equivalence relation that is also a partial ordering is the equality relation). The equivalence class of $x$ is the interval $\bigl[\lfloor x\rfloor,\lfloor x\rfloor+1\bigr)\cap\mathbb{Q}$ (where I use the more common notation $\lfloor x\rfloor$ instead of $|x|$).


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .