2

The below picture is a problem involving relations from a review set. I have only seen problems with relations involving matrices and solving for the properties of reflexive, symmetric, and transitive.

So determining if a relation is anti-symmetric and quite simply approaching parts B and C where you're given the relation not already in a matrix is problematic.

Is there a way to transform the given relation in B and C to a matrix? And how, from a matrix, can we determine if the relation is anti-symmetric?

Here is the review problem

Here is the matrix setup for B.

\begin{bmatrix}X&1&2&3&4&5&6\\1&?&?&?&?&?&?\\2&?&?&?&?&?&?\\3&?&?&?&?&?&?\\4&?&?&?&?&?&?\\5&?&?&?&?&?&?\\6&?&?&?&?&?&?\end{bmatrix}

Mr.Mips
  • 173
  • 1
    An example of a symmetric relation: $aRb$ iff $\gcd(a,b)=1$; here, for example, $2R3$ implies $3R2$, so both hold, yet $2\neq 3$, so $R$ is not antisymmetric. – Shaun Dec 09 '18 at 03:44
  • 1
    An example of an antisymmetric relation: $aRb$ iff $a\le b$; here, if $x\le y$ and $y\le x$, then $x=y$, yet $1\le 2$ does not imply $2\le 1$, so $R$ is not symmetric. – Shaun Dec 09 '18 at 03:48
  • @Shaun Hmm, I think I see. So can we say unless there exists (a,b) ∈ R and (b,a) ∈ R, and a ≠ b, the relation is anti-symmetric? – Mr.Mips Dec 09 '18 at 03:55
  • 1
    NB: For my first example, I assumed that $R$ is a relation on the natural numbers; for the second, $R$ is a relation on the real numbers. Stating what a relation is on is important (and I forgot to include the information due to it being late here at the time of writing). – Shaun Dec 09 '18 at 03:56
  • Precisely, since the negation of a statement of the form $(A\land B)\to C$ is of the form $(A\land B)\land\lnot C$. – Shaun Dec 09 '18 at 03:58
  • 1
    @Shaun Great. I won't bother you anymore since it's late for you. Thank you for the clarification – Mr.Mips Dec 09 '18 at 03:59
  • 1
    You're welcome :) – Shaun Dec 09 '18 at 04:00
  • After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark $\checkmark$ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?, What should I do if someone answers my question?. – Shaun Dec 09 '18 at 04:21
  • 1
    I have recently posted an answer here. Just draw the matrix and check for every relation, you will get it. – tarit goswami Dec 09 '18 at 06:17

1 Answers1

1

See my comments on the question for examples demonstrating the difference between symmetric and antisymmetric relations.

Given a relation $R$ on a set $X$ with $|X|=n<\infty$, say, then $R$ is equivalent to an $n\times n$ matrix $\mathcal{R}$ with entries in $\{0, 1\}$ (or $\{\text{false, true}\}$ if you prefer), where, if one labels the rows & columns according to the elements of $X$, the entry

$$\mathcal{R}_{ij}:=\begin{cases} 0\,\text{(false)} & \text{if not } \quad iRj, \\ 1\,\text{(true)} & \text{if }\quad iRj. \end{cases}$$

As far as I am aware, there is no easy way to see if $R$ is (anti)symmetric on $X$, given only $\mathcal{R}$, but I could be wrong.

Shaun
  • 44,997