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.

Is $\vDash \exists x ( Q x \to \forall x Qx)$ a valid sentence?

$Q$ is a unitary relation.

I suppose that $\vDash Q x \to \forall x Qx$ , which is equivalent to $\vDash Q x \to \forall y Qy$ is invalid, since there is a structure $\mathfrak{A}$ with the universe $|\mathfrak{A}|=\{a,b\}$ plus one relation $Q = \{a\}$ and a function $s$ which sends the variable $x$ to $a$. But I got confused henceforth this point.

I'm inclined to reason that, since $x$ is bounded, the part $\forall x$ is redundant, the sentence should be valid.

share|improve this question

2 Answers 2

up vote 6 down vote accepted

Whether it's even well-formed depends on the low-level details of how you define syntax.

But even if it is well-formed in the syntax you use, using a variable $x$ as a dummy variable in a context where $x$ already has meaning is usually a bad idea.

That said, typically in syntax that allows such a thing, a variable acquires the innermost meaning. Therefore

$$\exists x ( Q x \to \forall x Qx)$$

is the same expression as

$$\exists x ( Q x \to \forall y Qy)$$

and is a different expression than

$$\exists x ( Q x \to \forall y Qx)$$

share|improve this answer
2  
Well, you surely can't say the first is the same expression as the second. They are equivalent expressions. –  Peter Smith Jan 9 '13 at 22:45
    
+1; exactly what I was coming in here to say - canonically, I would consider this to not be a WFF by most rules. –  Steven Stadnicki Jan 9 '13 at 22:49
2  
@Peter: Again that depends on how you define syntax. Is the choice of glyph part of the identity of the expression, or are the glyphs just used to indicate repeated appearances of the same variable, or some other similar sort of thing? If the glyph is part of the identity of an expression, then indeed they would not be identical expressions. I was trying to avoid the word "equivalent" to avoid confusion with $\leftrightarrow$. –  Hurkyl Jan 9 '13 at 22:49

Yes, it is.

The "flaw" in your purported counterexample to the validity of:

(A) --- $∃x(Qx \rightarrow ∀xQx)$

is that you are "reading" it as : $∃xQx \rightarrow ∀xQx$, which is not [this is implied by the structure $\mathcal A$ with universe $|\mathcal A| = \{ a,b \}$ such that $Q^{\mathcal A} = \{ a \}$].


We prove the vaildity of (A) in two ways.

Formal proof

We have that :

$\vdash (∀xβ \rightarrow α) \leftrightarrow ∃x(β \rightarrow α)$, if $x$ does not occur free in α [see this post for the proof].

If we apply it to (A), we get :

(B) ---$∀xQx \rightarrow ∀xQx$

which is clearly valid.


Semantic proof

Consider an interpretation $\mathcal A$ whatever and consider the conditional : $Qx \rightarrow ∀xQx$ : if $Qx$ holds for all $x$, then the conditional is true; thus, also $∃x(Qx \rightarrow ∀xQx)$ is.

If there is an object $a \in |\mathcal A|$ such that $a \notin Q^{\mathcal A}$ , then $\forall xQx$ is false.

Now, what is the condition for $\mathcal A \vDash \exists x \varphi[s]$ , i.e. such that $\mathcal A$ satisfy $\varphi$ with the assignment $s : Var \mapsto |\mathcal A|$ ?

It is :

for some $a \in |\mathcal A|$, we have $\mathcal A \vDash \varphi[s(x|a)]$.

Thus, if we consider an assignment $s$, we have that $\mathcal A \vDash (Qx \rightarrow ∀xQx)[s(x|a)]$ [because $\forall xQx$ is false precisely because $Q$ does not hold for $a$, and so we have : $False \rightarrow False$, which is $True$ ].

But, having shown that :

for some $a \in |\mathcal A|$, we have $\mathcal A \vDash (Qx \rightarrow ∀xQx)[s(x|a)]$

we may conclude with :

$\mathcal A \vDash \exists x (Qx \rightarrow ∀xQx)[s]$.

But this holds for $s$ and $\mathcal A$ whatever; thus :

$\vDash \exists x (Qx \rightarrow ∀xQx)$.


Comment

A further "informal" argument is the following.

By tautological equivalence, we may rewrite : $\exists x (Qx \rightarrow ∀xQx)$ as :

$\exists x (\lnot Qx \lor ∀xQx)$.

$\exists$ "works" as a "generalized" disjunction; thus, we can "distribute" it over $\lor$, obtaining the equivalent formula :

$\exists x \lnot Qx \lor ∀xQx$,

due to the fact that $\exists x \forall xQx$ has the same meaning of $\forall xQx$, $x$ being already bound.

But $\exists x \lnot Qx \lor ∀xQx$ is clearly valid; it means that either all objects are $Q$ or there is some object which is not, and this must hold in all universes.

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.