Empty set and universal instantiation

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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