# Prove the following statement: If $E$ is an empty set and $A \subseteq E$, then $A$ is an empty set.

If $E$ is an empty set and $A \subseteq E$, then $A$ is an empty set.

Edit: Thanks for the \emptyset Latex command.

Given:

P: $E$ is an empty set and $A \subseteq E$

Q: $A$ is an empty set.

We have a $P \rightarrow Q$ statement.

Definition 3.1.5 states that a set with no elements is an empty set.

Since $E$ is an empty set,

$(\forall x)[x \in E \rightarrow \emptyset ]$

Definition 3.1.2 states that we let A and B be sets. Then A is a subset of B, written $A \subseteq B$, when the statement $(\forall x)[x \in A \rightarrow \in B ]$ is true.

For, $A \subseteq E$, we get $(\forall x)[x \in A \rightarrow \in E ]$

Since $E$ is an empty subset without elements, $A$ would be an empty subset.

$(\forall x)[x \in A \rightarrow \emptyset]$

I think I fumbled towards the end. I couldn't think of the right words to say.

• Latex for the empty set $\emptyset$ is \emptyset. – Robert Israel Jan 31 '14 at 4:51
• ...and if you think that one is too skinny there is also \varnothing $\varnothing$. For an easy way to look up LaTeX symbols, check out Detexify – David Jan 31 '14 at 4:53
• Apply the definition ... $A \subseteq \emptyset$ is $\forall x (x \in A \rightarrow x \in \emptyset)$; but for $x \in A \rightarrow x \in \emptyset$ being true, due to the fact that $x \in \emptyset$ is false (truth-table for $\rightarrow$, case : $False \rightarrow False$ is $True$), because there are no elements in $\emptyset$, you must have also that $x \in A$ is false, and this for all $x$. So, we have concluded that $\forall x (x \notin A)$ that means exactly : $A = \emptyset$. – Mauro ALLEGRANZA Jan 31 '14 at 9:42
• I did write that A is indeed an empty subset . – usukidoll Jan 31 '14 at 9:46

Definition: $A \subseteq B$ iff $\forall a \in A, a \in B$.

If $A \subseteq \emptyset$, then $\forall a\in A, a\in \emptyset$. But the empty set has no elements, so $A$ must have no elements. Then $A$ is the empty set by definition.

Or you could do it by contradiction: Suppose $A$ is not the empty set. Then if $A \subseteq \emptyset$, there must exist $x \in A$, s.t. $x \in \emptyset$. But then $\emptyset$ is not the empty set. This is a contradiction. So our proposition that $A$ is not the empty set must be false. So $A$ is the empty set.

• Also, hello again. – Newb Jan 31 '14 at 5:13
• hi again ^^ I wasn't doing the proof using contradiction.. I was going forward and I got that A is an empty set as well. – usukidoll Jan 31 '14 at 5:16
• @Newb - the formal translation of the definition of "subset" must be improved a little bit. It must be : $A \subseteq B$ iff $\forall a (a \in A \rightarrow a \in B)$. – Mauro ALLEGRANZA Jan 31 '14 at 7:52
• @MauroALLEGRANZA Formally, those statements mean the same thing. You're using more formal notation than I am. I don't think there is an important difference (I actually think mine is clearer, but this may be a subjective difference). – Newb Jan 31 '14 at 7:55

$\newcommand{isemptyset}[1]{#1\text{ is an empty set}}$Formally, let's use the following definition:$$\isemptyset{V} \;\equiv\; \langle \forall x :: x \not\in V \rangle$$

Then we can just calculate \begin{align} & A \subseteq E \\ = & \qquad \text{"definition of $\;\subseteq\;$"} \\ & \langle \forall x :: x \in A \;\rightarrow\; x \in E \rangle \\ = & \qquad \text{"using the assumption $\;\isemptyset E\;$ and the above definition"} \\ & \langle \forall x :: x \in A \;\rightarrow\; \text{false} \rangle \\ = & \qquad \text{"logic: simplify"} \\ & \langle \forall x :: x \not\in A \rangle \\ = & \qquad \text{"the above definition"} \\ & \isemptyset A \\ \end{align}

Hint: if $x \in A$ and $A \subseteq E$, then $x \in E$.

• True, but we are dealing with an empty subset.. E is an empty subset, so it doesn't have any elements. – usukidoll Jan 31 '14 at 4:55
• @usukidoll: Exactly! So the assumption that $A$ has any elements at all leads to a contradiction. So what can you say about $A$? – Clive Newstead Jan 31 '14 at 5:18

Maybe try a different contrapositive.

$A \subseteq E$ means $(\forall x)[x \in A \rightarrow x\in E ]$. It would be easier to use $(\forall x)[x \not\in E \rightarrow x \not\in A ]$.

Let's try again from the beginning.

Let $E$ be an empty set and $A \subseteq E$. Since $E$ is empty, we have that $\forall x$ in the universe, $x \not\in E$. Since $A \subseteq E$, we know that $x \not\in E \rightarrow x \not\in A$. Since $\forall x$ we have $x \not\in E$, we have that $\forall x, x\not\in A$. Thus $A$ is empty.

• hmm.. x doesn't belong to e and it doesn't belong to A. So that's a negation. x.x – usukidoll Jan 31 '14 at 5:13
• YES! It is ! A is empty...umm what definition did you use though? Was it 3.1.2? – usukidoll Jan 31 '14 at 5:41

If something is so obvious that you can see it is true at face value, then there is no virtue in proving it other than to exercise your skill with logic calculus, so the question has no answer without being more specific about what logic you using. Here is one possibility, there are others:

Sets: $$(\not \exists x) x \in E \land A \subseteq E \rightarrow (\not \exists y) y \in A$$

Boolean algebra:

$$(\not \exists x)\, e(x) \land (\forall z) a(z) \rightarrow e(z) \rightarrow (\not \exists y) a(y)$$

Convert to universal quantification:

$$(\forall x)\, \lnot e(x) \land (\forall z) a(z) \rightarrow e(z) \rightarrow (\forall y) \lnot a(y)$$

Contrapositive:

$$(\forall x)\, \lnot e(x) \land (\forall z) \lnot e(z) \rightarrow \lnot a(z) \rightarrow (\forall y) \lnot a(y)$$

Which is modus ponens.

Probably a good case for using the contrapositive: let $A\subseteq E$ and prove that if $A\ne\varnothing$ then $E\ne\varnothing$.

• That would mean that there isn't an empty set in A and E So the converse statement would be that If $A$ is an empty set, then $E$ is an empty set and $A \subseteq E$ Contrapositive: If $A$ is NOT AN empty set, then $E$ is NOT an empty set and $A \subseteq E$ – usukidoll Jan 31 '14 at 5:00
• Alright, so for the contrapositive A and E don't have empty sets which means that there are elements inside A and E. Therefore, by Definition 3.1.2, $(\forall x)[x \in A \rightarrow \in E ]$ – usukidoll Jan 31 '14 at 5:02
• If it's assumed that $A\ne\varnothing$ then what can you say about $A$? And then since $A\subseteq E$, what can you say about $E$? – David Jan 31 '14 at 5:04
• A has elements so it's not an empty set. $A\subseteq E$ means that A is a subset of E. Assuming that E does have elements, then it's not an empty set. But let's say that E is an empty subset... there's no elements and since $A\subseteq E$...A won't have elements. – usukidoll Jan 31 '14 at 5:06
• Your first two sentences are fine. But then you don't have to assume $E$ has elements, because... Can you see it? – David Jan 31 '14 at 5:08