0

Just wondering if these formulae are valid in classical logic:

  1. $\forall x \exists x (Px) \leftrightarrow \exists x (Px)$
  2. $\exists x \forall x (Px) \leftrightarrow \forall x (Px)$
  3. $\forall x (Py) \leftrightarrow Py$
  4. $\exists x (Py) \leftrightarrow Py$

I 'm a beginner (using Suppes'Introduction to Logic). Couldn't find any sources on this. Thanks!

Stranger
  • 299

1 Answers1

3

See in Patrick Suppes, Introduction to Logic (1957 - Dover reprint), the recursive definition of formulas [page 52] :

(a) Every atomic formula is a formula.

[...]

(d) If $R$ is a formula and $v$ is a variable then $(v)R$ and $(\exists v)R$ are formulas.

Thus, according to the syntax, $Px$ is an atomic formula; so $(∃x)Px$ is a formula, and also $(x)(∃x)Px$ [i.e. $∀x∃x(Px)$] is a formula.

Now for the "meaning": of course quantifying a variable which is not present in a formula does nothing.

In formula $∃x(Px)$ there are no a free variable $x$; thus the "meaning" of $∀x∃x(Px)$ is exactly $∃x(Px)$.

How to prove it ? See BASIC RULES OF INFERENCE, page 99.

(a) Start with $∀x∃x(Px)$ and apply US :

from $∀xS$, derive $S(t)$, provided that no free occurrence of $x$ within scope of quantifier using variable of $t$ [i.e. we have to avoid that the term $t$, if containing a variable $y$, will be "captured" by a quantifier $\forall y$ or $\exists y$ already present into $S$].

In our case, $∃x(Px)$ has no free occurrences of $x$; thus, applying US we simply obtain $∃x(Px)$.

Thus, by Rule C.P [page 29] we may conclude with :

$∀x∃x(Px) \rightarrow ∃x(Px)$.

(b) Now consider $∃x(Px)$ and apply UG :

from $S$ derive $∀xS$, provided that $x$ is not flagged.

In our case, $∃x(Px)$ has no free occurrences of $x$; thus, $x$ is not flagged and we may apply UG to obtain $∀x∃x(Px)$.

Again by Rule C.P :

$∃x(Px) \rightarrow ∀x∃x(Px)$.

Finally, apply the definition of $\leftrightarrow$ to conclude with :

$∀x∃x(Px) \leftrightarrow ∃x(Px)$.

Note

The same approach, using the "existential" rules, applies to : $∃x∀x(Px)↔∀x(Px)$.

Community
  • 1
Mauro ALLEGRANZA
  • 94,169
  • Thank you for the very useful answer. Additionally, I was under the impression that $P(y)$ means that $y$ is the only free variable used in $P$. I guess it can have other free variables too? Suppes doesn't seem to talk about this (at least not yet, and I'm at pg 93). If there are other free variables in $P$ (say $x$ and $z$), why only point out $y$? Why not all free variables in $P$ i.e. write $P(x,y,z)$ instead of $P(y)$? – Stranger Sep 30 '14 at 11:09
  • @VijayKonnur - we need a distiction: if $P$ is a predicate letter, it has its own arity, i.e.the number of argument-places. In this case we have always to indicate them; thus, for binary (arity=2)predicate $P$ we have to write the (atomic) formulae $P(x,y)$ or $P(t_1,t_2)$. For formulae, using meta-variables, like $\varphi$ (it is not part of the formal language, bur part of the math-english used to speak of the formal languag and stands for a "generic" formula) the convention is that writing $\varphi(x_1,\ldots,x_n)$ we mean that free variables of $\varphi$ are among $x_1,\ldots,x_n$. – Mauro ALLEGRANZA Sep 30 '14 at 11:27
  • Ok makes sense. We're not talking about a any particular predicate P but a generic formula of the meta language. It would have been more appropriate to use phi etc. I guess. Thanks a lot! – Stranger Sep 30 '14 at 13:53
  • @VijayKonnur - You are right ... but you must take into account that Suppes' book is quite hold, prior to LaTex and word-processors ... Thus, there is a typographical distinction between predicate letters, like $R$ (see page 45) and meta-variables for fomulae, like (bold) R (see page 52); the problem is that the difference is not so apparent like changing font (latin vs greek). – Mauro ALLEGRANZA Sep 30 '14 at 14:00