Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Are the following two assertions always true, always false or meaningless?

$\exists i \in \emptyset$

$\forall i \in \emptyset$

Because it seems that one encounters expressions of this kind fairly similar in mathematics, especially if we are dealing with degenerate cases of definitions. Let me give an example (in graph theory) of such a case. There, one can formalize the idea the two vertices are connected in the following way: Let $G=(V,E)$ be a graph and let $v,w\in V $. We define $v$ and $w$ to be "connected" if: $\exists n \in \mathbb{N}, \ \exists \alpha: \left\{ 1,\ldots,n \right\} \rightarrow V, \ \alpha_0=v \ \& \ \alpha_n=w \ \ \forall i\in \mathbb{N}, 0\leqslant i \ \& \ i<n:\ \left\{ \alpha_i, \alpha_{i+1} \right\} \in E$

Now, if we would ask, if every node is connected to itself (a fact which intuitively we would want to be true), we would have to exhibit an $n$ and a sequence $\alpha$, such that [bla bla...]. The obvious choice for $n$ is 0. But for this choice of $n$, no mattter which sequence $\alpha$ we would consider, the set of the $i$'s would be empty, because the set of the $i$'s is actually $\left\{ i\in \mathbb{N} | 0\leqslant j \ \& \ j<n \right\}$. But for $n=0$ this set is the empty set. Thus, because we quantify $\forall i \in \left\{ i\in \mathbb{N} | 0\leqslant j \ \& \ j<0 \right\}=\emptyset$, should the statement be true/false by definition?

EDIT: Sorry, for my unclear formulation and to everybody who on my fault interpreted it wrongly. The way Carl Mummert or Listing interpreted it, was what I meant.

share|improve this question
7  
In my opinion, in the present form of the question - with $\exists i\in I$ and $\forall i\in I$ - they are not even propositions, so nothing can be said about the truth values. If you would be asking about $(\exists i\in I)i=i$ and $(\forall i\in I)i=i$, then the first one is false and the second one is true. (You can replace $i=i$ by any proposition $P(i)$.) –  Martin Sleziak Jul 9 '11 at 11:19
    
But maybe I have misunderstood you and you're asking about $(\exists i)i\in\emptyset$ and $(\forall i)i\in\emptyset$. They are both false. But I don't think this is what you had in mind. –  Martin Sleziak Jul 9 '11 at 11:22

2 Answers 2

up vote 16 down vote accepted

When we translate mathematical statements into formal logic, the "bounded quantifiers" $(\exists x \in I) P(x)$ and $(\forall x \in I) P(x)$ are usually viewed as abbreviations, as follows:

  • $(\exists x \in I) P(x)$ is an abbreviation of $(\exists x)(x \in I \land P(x))$.

  • $(\forall x \in I) P(x)$ is an abbreviation of $(\forall x)(x \in I \to P(x))$.

With these conventions, the bounded quantifiers continue to make sense even when $I$ is empty. In that case, $(\exists x \in \emptyset) P(x)$ will always be false, and $(\forall x \in \emptyset) P(x)$ will always be true, regardless of the formula $P(x)$. So, for example, $(\exists x \in \emptyset)(i = i)$ is false and $(\forall x \in \emptyset)(i \not = i)$ is true.

A nice property of this definition of the bounded quantifiers is that it makes them dual in the sense that for any set $I$ (possibly empty) and any formula $P(x)$, we have

  • $(\exists x \in I) P(x) $ if and only if $\lnot (\forall x \in I)\lnot P(x)$
  • $(\forall x \in I)P(x) $ if and only if $ \lnot (\exists x \in I)\lnot P(x)$

These can be verified by direct calculation: $$ \begin{split} (\exists x \in I) P(x) & \Leftrightarrow (\exists x) (x \in I \land P(x)) \\ & \Leftrightarrow \lnot (\forall x) \lnot (x \in I \land P(x)) \\ & \Leftrightarrow \lnot (\forall x)(x \not \in I \lor \lnot P(x)) \\ & \Leftrightarrow \lnot (\forall x)(x \in I \to \lnot P(x))\\ & \Leftrightarrow \lnot (\forall x \in I)\lnot P(x) \end{split} $$ and $$ \begin{split} (\forall x \in I) P(x) & \Leftrightarrow (\forall x) (x \in I \to P(x)) \\ & \Leftrightarrow \lnot (\exists x) \lnot (x \not \in I \lor P(x))\\ & \Leftrightarrow \lnot (\exists x) (x \in I \land \lnot P(x))\\ & \Leftrightarrow \lnot (\exists x \in I) \lnot P(x) \end{split} $$

share|improve this answer
    
So my graph theory example is true, because of all set sets over which I quantified, one is the empty set and thus the assertion is true ? (Side question: I seem to have difficulties translating mathematical statements into formal logic and then drawing the right conclusions about them using just the rules of formal logic. Could you maybe recommend a book the explains/trains this ?) –  temo Jul 9 '11 at 13:15
    
I think there is some typo in your formula regarding whether the indexes start at 0 or 1. But once that is fixed the formula will indeed be true when there is just one node. Re formal logic, using just those rules is very time-consuming, so even in logic we don't typically write proofs just from the rules. But knowing what the rules are does help illustrate how to do some reasoning. One book I like is A mathematical introduction to logic by Enderton. –  Carl Mummert Jul 9 '11 at 13:27

In this form, these are just beginnings of propositions. But you may have meant: $$ \exists i: i\in \{\} $$ $$ \forall i: i\in \{\} $$ The second one says that every $i$ is an element of the empty set. This proposition is false. It's enough to find one counterexample. Barack Obama is not an element of the empty set. So it's false because the condition ($i$ is an element of the empty set) doesn't hold for every $i$.

The first one is weaker but it is still false. To prove that it is true, we would have to find an element $i$ that is an element of the empty set. But because the empty set has no elements, you can't find any. :-) The situation when the condition (in this case, $i$ is an element of the empty set) has exactly zero solutions is the way - and the only way - how the existential quantifier may fail.

Your comments about the graphs are far more complicated than the two simple propositions above but it is true that one must safely understand the logic of the two propositions above to be sure that he can evaluate more complex existential and universal propositions about the graphs (and everything else in maths), too.

share|improve this answer
    
This is not what he wants. I think he asks for the degenerate case where an expression has the form: $\forall i \in \emptyset: T(i)$ where $T$ is a logical operator that depends on $i$. –  Listing Jul 9 '11 at 12:13
2  
I see, so $\forall i\in \{\}: T(i)$ holds for any $T(i)$ because there is no counterexample in an empty set for which $T(i)$ would fail - it holds for everyone (all zero of them). On the other hand, $\exists i\in\{\}: T(i)$ is always untrue because there doesn't exist any $i$ in an empty set that has a property - whatever property - because there's nothing in an empty set even without adjectives. –  Luboš Motl Jul 9 '11 at 14:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.