Let's suppose that we need to prove a statement of the form $\forall x(x\in A\longrightarrow\phi)$, where $\phi$ is any property (for example when we need to prove that $A\subseteq A\cup B$). Is it really necessary to consider the case when $A=\emptyset$?

I mean deductively we are only concerned when $x\in A$ is true. This means that we can directly consider the fact $x\in A$ as true and then deduce $\phi$ and we don't care about the case $A=\emptyset$ so we can forget about it. But then I'm confused here becase I've read in some books and seen some of my teachers saying something like

"if $A=\emptyset$ then the case is trivialy true because.... Let's now suppose that $\exists x\in A$, then....".

In the case of my example I would simply write something like:

Let's suppose an arbitrary $x$ such that $x\in A$. Then $x\in A \vee x \in B$. This means $x\in A\cup B$, by definition. Therefore $\forall x(x\in A\longrightarrow x\in A\cup B)$, which means $A\subseteq A\cup B$.

So, my question here is if my proof is really complete or if I'm missing the case when $A=\emptyset$.

In a more general case I can think of proving somegthing of the form $\forall x(\phi\longrightarrow \psi)$. Then I would just write as a proof by using deduction something like

"Let's suppose an arbitrary $x$ such that $\phi$ then... but this implies that... therefore $\psi$. This means $\forall x(\phi\longrightarrow \psi)$".

But here I don't know if I have to consider the case when $\phi $ is not satisfied by $x$ and mention that in the proof to be complete.

  • $\begingroup$ Technically, your thoughts are completely correct. Although $\forall\ A (\text{bla})$ seems like a typo ($\forall\ x$) $\endgroup$ – AlexR Sep 10 '13 at 19:59
  • $\begingroup$ @AlexR Thanks. Yes, sorry, that was a typo. I made the correction already. So, basically you would say that when the "trivial" case is made explicit it's just to make enphasis or something like that, but it's redundant? $\endgroup$ – Daniela Diaz Sep 10 '13 at 20:15
  • 1
    $\begingroup$ If you try to prove something for all elements in a set, yes. Usually however, the "emphasis" is needed - if you prove something for the set, such as that it is disjoint to another set and you want to have an element from the set, you'll have to exclude $A\neq\emptyset$ before you do that... $\endgroup$ – AlexR Sep 10 '13 at 20:18

If you want to prove a statement of the form $$\forall x: \quad (\Phi(x) \Rightarrow \Psi(x))$$ You can assume $x$ with $\Phi(x)$ to exist; in other words you need not require $$\{x : \Phi(x)\} \neq \emptyset$$ for the proof. (So all statements hold for the elements of the empty set ;-) )
If you want to prove $$\Psi(A)$$ for some set $A$ and want to use an element $x\in A$ for the proof, you first need to show that $$A \neq \emptyset$$ or make a branch for this as a special case.

  • 1
    $\begingroup$ $$\Psi(A) : A = \mathbb{R}$$ Showing that $A$ is open and closed doesn't suffice, because $A$ also needs to be nonempty... Sorry I can't make up a better example from scratch. $\endgroup$ – AlexR Sep 10 '13 at 20:33

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.