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 $xSy$ 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}$ * $\mathbb{N}$ by $(a,b)T(c,d)$ if and only if $a≤c$ and $b≤d$.

For each relation state whether the relation is reflexive, symmetric, anti-symmetric and explain why so?

Also 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.

This was the question that was given for my exams. I would attempt it myself but really don't know how to do so. Can anybody please tell me how to attempt it.


Honestly, I think that the best way to approach this as a beginning math student is just to try to parse through a few examples. If you find a counterexample, you're done, otherwise, after a few tries, see if you can see why it would be true. Try it out with $R$:

Reflexivity: $\forall X\in P(\mathbb{N}), R(X,X)$. Note that $A\cup A=A$, so $R(A,A)$ iff $|A|\geq 2$. Does every subset of $\mathbb{N}$ have cardinality greater than 2?

Symmetry: $\forall X,Y\in P(\mathbb{N}),R(X,Y)\to R(Y,X)$. If $|X\cup Y|\geq 2$, what can you conclude about $|Y\cup X|$?

Antisymmetry: $\forall X,Y \in P({\mathbb{N}}), (R(X,Y)\land R(Y,X)) \to X=Y$. If you can show that $R$ is symmetric, you only need to find a pair of different sets whose union has cardinality greater than $2$.

Transitivity: $\forall X,Y,Z\in P({\mathbb{N}}), (R(X,Y)\land R(Y,Z))\to R(X,Z)$. Try an examples for $X$ and $Z$ such that $X$ does not relate to $Z$. See if you can then find a $Y$ such that $R(X,Y)$ and $R(Y,Z)$.

  • $\begingroup$ N could contain 0 or 1. Does that mean it would not be reflexive? I am not sure what you mean by the other cases. $\endgroup$ – SAR Apr 27 '16 at 16:31
  • $\begingroup$ Maybe I'm confused, but I assume you mean $\mathbb{N}$, i.e. the natural numbers? Depending on convention, $0$ may or may not be a natural number, but I don't see how that's relevant to reflexivity. My point was just trying out examples with $R$: you should be able to find some set of natural numbers $A$ such that $|A\cup A|=|A|<2$ (in fact, you can find infinitely many, but that's beside the point). $\endgroup$ – Kevin Long Apr 27 '16 at 16:39
  • $\begingroup$ Not to mention $|\emptyset \cup \emptyset| = |\emptyset| = 0$. Or consider A = {5}. |A U A| = |{5} U {5}| = |{5}| = 1. $\endgroup$ – fleablood Apr 27 '16 at 16:59

Work it out by the definitions.

Reflexivity: means x R x for all x.

So: $ARB \iff |A\cup B| \ge 2$. Does $|A \cup A| \ge 2$ for all subsets of the natural numbers? Well... $|A \cup A| = |A|$. Do all subsets have cardinality $\ge 2$? Obviously not as, say {0} or {1} or {k} have cardinality of 1 (not to mention $|\emptyset| = 0$).

So R is not reflexive because $\{k\}\not R\{k\}$ because $|\{k\}\cup\{k\}| \not \ge 2$.

If $x S z \iff \lfloor x \rfloor = \lfloor z \rfloor$. Is it reflexive? That means does $\lfloor x \rfloor = \lfloor x \rfloor$ for all rational x? Well, yes. Can't put it any simpler than that.

Is T reflexive? The means is $a \le a$ and $b \le b$ for all $(a,b)$? Well, ... yes.

Symmetry: means $x R y \iff y R x$

If $A R B$ does it follow $B R A$? Well, if $|A \cup B| \ge 2$ does it follow that $|B \cup A| \ge 2$? Since $A \cup B = B \cup A$ it must. So R is symmetric.

Is S symmetric. Does it follow that if $\lfloor x \rfloor = \lfloor z \rfloor$ then $\lfloor z \rfloor = \lfloor x \rfloor$. Well, yes... equality is equality. So S is symmetric.

Is T symmetric. For $(a,b)$ and $(r,s)$, if $a \le b$ and $r \le s$, does it also follow tht $b \le a$ and $s \le r$? Well... no.

Transitive: If $s R t$ and $t R v$ then $s R v$.

R: if $|A \cup B| \ge 2$ and $|B \cup C| \ge 2$ does it follow that $|A \cup C| \ge 2$? Hint: what if $A = C$ and $|A| = 1$?

S: if $\lfloor x \rfloor = \lfloor z \rfloor$ and $\lfloor z \rfloor = \lfloor w \rfloor$ Does it follow that $\lfloor x \rfloor = \lfloor w \rfloor$? Hint: if $a = b$ and $b = c$, does $a = c$. Again, equality is equality.

T: If ($a \le b$ and $r \le s$) and ($b \le c$ and $s \le t$) does it follow that ($a \le c$ and $r \le t$)?

  • $\begingroup$ Oh, I didn't do anti-symmetry. $\endgroup$ – fleablood Apr 27 '16 at 17:00
  • $\begingroup$ Thanks. All this is confusing and my lecture slides does a really poor job of explaining stuff. $\endgroup$ – SAR Apr 27 '16 at 17:27

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.