How to tell if the relations R, S and T are reflexive, symmetric, anti-symmetric or and transitive?

Question

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.

Answer 1

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)$.

Answer 2

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$)?