3
$\begingroup$

I am having trouble understanding when is a set not being an empty set an important criterion. I was working on the following:

Suppose $R$ is a relation on $A$. Let $B=\{ X\in P(A)\mid X \neq \emptyset \} $, and define a relation $S$ on $B$ as follows:

$S=\{ (X,Y)\in B\times B\mid \forall x\in X, \forall y\in Y: (x,y)\in R \} $

Prove that if $R$ is transitive, then so is $S$. Why did the empty set have to be excluded from the set $B$ to make this proof work?

The solution states that $\emptyset$ needed to be excluded since the proof proceeds by assuming $y\in Y$, from the fact that $Y\in B$ and $Y\neq \emptyset$.

My interpretation is that this is an instance of universal instantiation, which I understand. What I don't understand is that this doesn't seem to apply to all universal instantiation. For example:

Suppose $R$ is a relation on a set $A$. Prove that $R$ is symmetric iff $R=R^{-1}$.

Solution: For the right-to-left direction of the iff, suppose $R=R^{-1}$, and let $x$ and $y$ be arbitrary elements of $A$...

Here $A$ is not guaranteed not to be the $\emptyset$, so why did the restriction apply to the first case but not the latter?

Could anyone please help?

$\endgroup$
1
$\begingroup$

Consider the case :

Suppose $R$ is a relation on a set $A$ and prove that $R$ is symmetric iff $R=R^{−1}$.

What happens if $A = \emptyset$ ?

Well, we have only one relation $R$ on it, the empty relation : $\emptyset$ which is "vacuously" reflexive, symmetric and transitive.

In this case the proof "works", because e.g. $\forall x \in \emptyset \ xRx$ [i.e. $\forall x \ (x \in \emptyset \to xRx)$] holds.


Note

How we "formally" prove it ?

1) $\forall x \ \lnot (x \in \emptyset)$ --- is an axiom of set theory

2) $\lnot (x \in \emptyset)$ --- from 1) by universal instantiation

3) $\lnot P \to (P \to Q)$ --- tautology

4) $\lnot (x \in \emptyset) \to (x \in \emptyset \to xRx)$ --- from 3) by subst

5) $(x \in \emptyset \to xRx)$ --- from 2) and 4) by modus ponens

6) $\forall x \ (x \in \emptyset \to xRx)$ --- from 5) by generalization.

$\endgroup$
  • $\begingroup$ Thank you! But I actually wanted to get back to your deleted content (which is very helpful!); you mentioned that we cannot instantiate $y\in \emptyset$, which I understand. But for the symmetry example, the $\emptyset$ is vacuously symmetric since the antecedent of $\forall x\forall y ((x,y)\in \emptyset \to (y,x)\in \emptyset$) is false. But presumably we also needed to assume $(x,y)\in \emptyset$ as arbitrary (to begin the proof) before we can say that this antecedent is false! So how come $y\in \emptyset$ is ok but $(x,y)\in \emptyset$ isn't? $\endgroup$ – Daniel Mak Oct 8 '16 at 15:27
  • $\begingroup$ Terribly sorry but I still don't quite get it...Say we want to prove $\forall x(x\in \emptyset\to xRx)$. We do a universal proof and assume $x\in \emptyset$ to get $xRx$. The antecedent, $x\in \emptyset$, is false so this conditional is vacuously true (and so is the whole universal quantified statement). But this assumption, $x\in \emptyset$, seems no different from the one you described above (with regards to the transitivity proof not being able to proceed with detachment)...? $\endgroup$ – Daniel Mak Oct 10 '16 at 9:33
  • 1
    $\begingroup$ Revised : In the other case we have e.g. $∀x∀y (x∈X∧y∈∅→xRy)$ and $∀y∀z (y∈∅∧z∈Z→yRz)$ and we instantiate them to : $x∈X∧y∈∅→xRy$ and $y∈∅∧z∈Z→yRz$. In order to "run" the proof we have to assume : $x∈X∧z∈Z$ and we want to conclude with $xRz$, to "generalize" it into $XSZ$. But from $x∈X∧z∈Z$ we get $x∈X$ and $z∈Z$ (by $∨$-elimination) but we cannot "add" $y∈∅$ to get the desired $x∈X∧y∈∅$ and $y∈∅∧z∈Z$ needed for detachment. $\endgroup$ – Mauro ALLEGRANZA Oct 10 '16 at 9:44
  • $\begingroup$ My mistake, sorry... The issue is : it is not a problem related to "instantiation". $\endgroup$ – Mauro ALLEGRANZA Oct 10 '16 at 9:46
  • $\begingroup$ I think I got it now, thank you so much for your help and patience! $\endgroup$ – Daniel Mak Oct 14 '16 at 17:11
4
$\begingroup$

It is by definition of the empty set, that every statement that begins with $$ \forall x\in\emptyset,\ \cdots $$ is automatically true.

Therefore, if the empty set had not been excluded from the definition of $B$, then, for every $X \subseteq A$ we would have had: $(X, \emptyset) \in S$ as well as $(\emptyset, X) \in S$.

But then if $S$ were transitive, it would mean that for every $X, Y \subseteq A$ we would have $(X,Y)$, because $(X,\emptyset), (\emptyset, Y) \in S$. In particular, $(A, A) \in S$, i.e. $R$ is the trivial relation where $x R y$ for every $x,y \in A$.

But we were not given that $R$ is the trivial relation, so we may not make this assumption.

$\endgroup$
  • 1
    $\begingroup$ It seems to me that a better example would be : assume that $R$ is trans but not symm. Then we have $(X,\emptyset) \in S$ and $(\emptyset,X) \in S$ (as you say) but we cannot conclude with $(X,X)$ because not $xRx$, and thus the presence of $\emptyset$ does not allow to conclude with transitivity of $S$. $\endgroup$ – Mauro ALLEGRANZA Oct 8 '16 at 15:08
  • $\begingroup$ @MauroALLEGRANZA: Thanks for your comments. I've revised my answer to make the logic more explicit. $\endgroup$ – Evan Aad Oct 8 '16 at 15:34
  • $\begingroup$ @IlmariKaronen: Totally right! Corrected. Thanks! $\endgroup$ – Evan Aad Oct 8 '16 at 17:27
1
$\begingroup$

You seem to be confusing the following two sentences that may appear in a proof:

  • "If $y\in \varnothing$, then ..."
  • "Let $y \in \varnothing$."

The first is vacuously true and the second is impossible because there is no such $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.