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.

It's clear to me what the interpretation is when we have something like:

$$\exists x (\forall y \Phi(x, y))$$

or even how to interpret the formula when x or y are not variables in the expression $\Phi$, but when these are used in a seemingly contradictory fashion, what is the meaning of these expressions:

$$\exists x (\forall x \Phi (x))$$ $$\forall x (\exists x \Phi (x))$$

Are these even wffs?

share|improve this question
1  
These expressions don't look well-formed to me. Have you run across them somewhere? –  Grumpy Parsnip Apr 2 at 20:04
    
If one is able to conclude $\exists x\Phi(x)$ from earlier inference for some formula $\Phi$, then by Generalization, you should be able to derive the second formula. However, it looks rather odd to me, and I have not seen its usage in any texts. –  Bill Province Apr 2 at 20:19
    
@Grumpy In Metamath, this type of expression is quite well-defined, although people tend not to use it because it gives them a headache to think about. The interpretation is that since you can change bound variables on the inner quantifier, $\forall x\,\Phi(x)\leftrightarrow\forall y\,\Phi(y)$ implies $\exists x\forall x\,\Phi(x)\leftrightarrow\exists x\forall y\,\Phi(y)$. –  Mario Carneiro Apr 2 at 20:26
    
@MarioCarneiro: thanks for the clarification. –  Grumpy Parsnip Apr 2 at 20:59

2 Answers 2

up vote 7 down vote accepted

One usually takes these to be well-formed formulas.

Let us take, for example, $\exists x\forall x \Phi(x)$. When we interpret this sentence, we examine $\forall x \Phi(x)$ for all free occurrences of $x$ in $\forall x\Phi(x)$. There are no such free occurrences, so $\exists x\forall x\Phi(x)$ is true in a structure $M$ precisely if $\forall x\Phi(x)$ is true in $M$.

More informally, the $\exists x$ in front has no effect. For that reason, one would never (except for the purposes of this question!) actually use the sentence $\exists x\forall x\Phi(x)$.

share|improve this answer
    
Thanks, Andre. Does the same reasoning also apply to the second formula? Would we conclude that the two formulas assert different things? –  Bill Province Apr 2 at 20:22
    
The argument for the second formula is the same. In $\forall x\exists x\Phi(x)$, the universal quantifier has no effect. The first sentence is logically equivalent to $\forall x\Phi(x)$, and the second is logically equivalent to $\exists x\Phi(x)$. Please note that in each case it is the front quantifier that makes no difference. –  André Nicolas Apr 2 at 20:29
    
Is this interpretation consistent with the one I just posted as a comment (rename bound variables with preference to inner bindings until you have something sensible)? –  Mario Carneiro Apr 2 at 20:30
    
@AndréNicolas If the domain of discourse is empty, then $\exists x\forall x\,x=x$ is false, but $\forall x\,x=x$ is true. –  Mario Carneiro Apr 2 at 20:33
    
@MarioCarneiro: In traditional Model Theory, the underlying set $|M|$ of an $L$-structure $M$ is non-empty. –  André Nicolas Apr 2 at 20:36

The "reason way" is (so to say) a "formal" one.

See Stephen Cole Kleene, Mathematical Logic (1967), page 127 : if $x$ is not free in $A$, then

$\vdash \forall x A \equiv A$ and $\vdash \exists x A \equiv A$.

We will prove the first one :

$\forall x A \vdash A$ --- by $\forall$-elim

$\vdash \forall x A \rightarrow A$ --- by $\rightarrow$-intro --- (A)

$A \vdash A$

$A \vdash \forall x A$ --- by $\forall$-intro, $x$ not free in $A$

$\vdash A \rightarrow \forall x A$ --- by $\rightarrow$-intro --- (B)

$\vdash \forall x A \equiv A$ --- from (A) and (B) by $\equiv$-intro.

The same for $\vdash \exists x A \equiv A$.

Thus, if we apply them to $A := \forall x B$, because $x$ is not free in $A$, we have that :

$\exists x \forall x B \equiv \forall x B$.

Now, forgetting the "uselessness" of it, its "interpretation" is exactly the same as that of $\forall x B$.

share|improve this answer

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.