0

Suppose we have a predicate symbol of one variable i.e $P(x)$, where the individial $x$ are in some fixed set $X$.

Consider the formula $$\exists yP(y)\rightarrow P(x) =: \mathcal F $$ It has one free variable, so one could say $\mathcal F = \mathcal F(x)$.

Intuitively, there should be no difference between $\exists x\mathcal F$ and $\exists z\mathcal F$, or is there? Am I allowed to write $$\exists x\mathcal F = \exists x (\exists yP(y)\rightarrow P(x))? $$ But it seems nonsensical to write $$\exists z(\exists yP(y)\rightarrow P(x))$$

Question: let $\mathcal F = \mathcal F(x)$. If one quantifies this statement, must it be quantified w.r.t to the free variable, $x$ in this case?

AlvinL
  • 8,664
  • Yes; $\exists x Fx$ and $\exists z Fz$ means the same. They both read as: "there is an $F$", that does not refer to $x$ or $z$. – Mauro ALLEGRANZA Mar 09 '18 at 10:31
  • 1
    @MauroALLEGRANZA See, you said $\exists xFx$ or $\exists zFz$. I think that answers the question. Quantifying is done w.r.t free variables and labels are changed accordingly. – AlvinL Mar 09 '18 at 10:33

1 Answers1

1

I am allowed to write : $∃x \ (∃yP(y) → P(x))$ ?

Yes.

We can "play" a little bit with equivalence to try to make sense of it.

Using the equivalence (holding in classical logic) between: $(p \to q)$ and $(\lnot p \lor q)$, we can rewrite it as follows:

$∃x \ (\lnot ∃yP(y) \lor P(x))$.

But we have that $\exists$ "distribute" over $\lor$ (the existential quantifier is a sort of infinite disjunction) to get:

$∃x \ (\lnot ∃yP(y)) \lor ∃xP(x)$.

But the leftmost existential quantifier has no effect, and thus we can remove it:

$\lnot ∃yP(y) \lor ∃xP(x)$.

The final result, which is equivalent to the original formula, is a truism but it is a valid FOL formula.

it seems nonsensical to write : $∃z(∃yP(y)→P(x))$; must it be quantified w.r.t to the free variable, $x$ in this case?

No.

We are not forced to quantify a free variable. The (usual) syntactical rules allows us to write e.g.: $∃x \ (0=1)$.

Of course, in this case the quantifier "adds" no value to the meaning: the meaning of the formula is $(0=1)$ (which is false).

Mauro ALLEGRANZA
  • 94,169