# Empty set and universal instantiation

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?

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.

• 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$. Oct 8, 2016 at 15:08
• @MauroALLEGRANZA: Thanks for your comments. I've revised my answer to make the logic more explicit. Oct 8, 2016 at 15:34
• @IlmariKaronen: Totally right! Corrected. Thanks! Oct 8, 2016 at 17:27

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.

• 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? Oct 8, 2016 at 15:27
• 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)...? Oct 10, 2016 at 9:33
• 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. Oct 10, 2016 at 9:44
• My mistake, sorry... The issue is : it is not a problem related to "instantiation". Oct 10, 2016 at 9:46
• I think I got it now, thank you so much for your help and patience! Oct 14, 2016 at 17:11

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