0
$\begingroup$

Prove that the empty relation, defined on a non-empty set $A$, is asymmetric.

My work:

We need to show that if $\mathcal{R}=\varnothing$ is a relation on $A\times A$, with $A\neq\varnothing$, then for all $x,y\in A$, if $(x,y)\in\mathcal{R}$ then $(y,x)\notin\mathcal{R}$.

Proof Since $A\neq\varnothing$ let $x,y\in A$. Since $\mathcal{R}\subseteq A\times A$ then $(x,y)\in R$. By hypothesis, $(x,y)\in\varnothing$, but this is not true, because the empty relation has no element, so we have $\mathrm{F}\to\text{?}$ thus $(y,x)\notin\mathcal{R}$ (false antecedent implies that the conditional is true), hence $\mathcal{R}$ is asymmetric.

Is it correctly justified and is my reasoning consistent?

$\endgroup$
  • 1
    $\begingroup$ No, it's not true. Just because an ordered pair is in $A\times A$ it doesn't mean it's in every of subset of $A\times A$. The statement you're trying to prove is vacuously true. You can't argue the empty relation isn't asymmetric because you can't find a counter example to show that it isn't. $\endgroup$ – Ryan Greyling Aug 25 '19 at 1:01
  • 1
    $\begingroup$ Your reasoning is incorrect. $R\subseteq A\times A$ means that everything in $R$ is a pair of elements of $A$; it does not mean that every pair of elements of $A$ is in $R$. Moreover, the fact that $A$ is nonempty is really irrelevant here. $\endgroup$ – Arturo Magidin Aug 25 '19 at 1:03
  • 1
    $\begingroup$ You can just start with, "Suppose $(x,y)\in R$." This is false. $\endgroup$ – saulspatz Aug 25 '19 at 1:13
  • 1
    $\begingroup$ @manooooh: Not really. What the transitive property says is just “for all $x,y,z$, $(xMy\wedge yMz\rightarrow xMz)$”. There is no condition on where the elements are taken from; that is supposed to be “hard coded” into whatever $M$ is. So you don’t start by taking elements from some set; rather, you start by taking elements $x,y,z$ with $xMy$ and $yMz$. From this you can deduce (not assume, but deduce) that $x,y,z$ must be elements of $A$, if you need to use that. But you don’t start with that as an assumption, you derive it as a conclusion. $\endgroup$ – Arturo Magidin Aug 25 '19 at 1:36
  • 1
    $\begingroup$ @manoosch: I never mentioned any $B$, so you aren’t using my comments. You want to prove $N$ transitive, you start by picking $x,y,z$ with $xNy$ and $yNz$. The fact that $N\subseteq A^2$ allows you to conclude that $x,y,z\in A$. You don’t pick elements form some set to see if they are in $N$, you pick elements of $N$. Remember that $N$ is a set of ordered pairs, and transitivity is about what happens in $N$. So you are not understanding my commernt. $\endgroup$ – Arturo Magidin Aug 25 '19 at 17:25
2
$\begingroup$

Your proof has been pretty severely critiqued in the comments, so I'll compare it to an exemplar:

Since $A\neq\varnothing$ let $x,y\in A$. Since $\mathcal{R}\subseteq A\times A$ then $(x,y)\in R$. By hypothesis, $(x,y)\in\varnothing$, but this is not true, because the empty relation has no element, so we have $\mathrm{F}\to\text{?}$ thus $(y,x)\notin\mathcal{R}$ (false antecedent implies that the conditional is true), hence $\mathcal{R}$ is asymmetric.

Let $x,y\in A$ be given. Since $\mathcal R$ is empty, $(x,y)\in\mathcal R$ is false. Therefore, $(x,y)\in \mathcal R\to(y,x)\notin\mathcal R$ is vacuously true. Since $x$ and $y$ were arbitrary, $\mathcal R$ is asymmetric.

  • Since you are letting $x$ and $y$ be arbitrary members of $A$ instead of choosing them from $A$, you do not need to observe that $A$ is non-empty. (In fact, the empty relation over the empty set is also asymmetric.)

  • Your statement that $(x,y)\in\mathcal R$ is poorly reasoned, and vacuously false. If you meant to say that that statement is well-formed and therefore a statement whose truth we can seek establish, then it doesn't need to be said. You were supposed to show all your work in high school algebra, but not in proof-writing.

  • You demonstrate that you understand the central idea of the proof, but it's a bit messy. You'll get better at that over time.

  • I'm a believer that, like closing a set of parentheses or quotation marks, you should be clear when you are done with the scope of your universally quantified variables. The point is that this was true for all $x,y\in A$, so it's worth taking half a sentence to note that you did that any never assumed anything else about $x$ or $y$.

$\endgroup$

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.