How to determine whether a proposition is molecular or atomic?

Question

Background (subquestion): I am learning about the quantifiers $\forall$ and $\exists$. My book says that the proposition $$\forall x{\in} D\: P(x)$$ can be vacuously true, because it can be turned into the form $A\to B.$ For example, $$\forall x\,\big(3 { <} x {< }2\to x{>}0\big)$$ is a vacuous truth.

Then I naturally wonder whether $$\exists x{\in} D\:P(x)$$ can also become $A\to B.$ I believe that it's impossible, because the proposition seems to be molecular. (Being molecular means that it can't consist of smaller propositions, unlike, e.g., $E=P\to Q,$ which consists of propositions $P$ and $Q.$) But I don't know how to prove it.

Answer 1

You typically can't remove quantifiers and still have a proposition.

For example, take $\forall x \ P(x)$. If you take away the quantifier, you are left with $P(x)$. But $P(x)$ is not a proposition. With an unquantified ('free') variable like that, we can't assign a truth-value. Ogf course, if you sound it out, it looks to be a proposition ("$x$ has property P" certainly sounds like a statement), but since we don;t know what this $x$ refers to, it is in fact not a claim. Indeed, since it is a variable, we can put either a universal or an existential in front of it, and clearly $\forall x \ P(x)$ and $\exists x \ P(x)$ mean different things.

So, a claim like $\forall x \ P(x)$ is molecular.

I should mention one small caveat: If you have a quantifier in front of something that does not contain the variable that is quantified by that quantifier (e.g. $\forall x \exists y P(y)$), then we are dealing with what is called a null quantifier, and as it turns out you can simply remove null quantifiers without changing the meaning of the statement. That is, $\forall x \exists y P(y)$ is equivalent to $\exists y P(y)$. And since the latter is a proposition, one could argue that $\forall x \exists y P(y)$ is not molecular .... though I think that even in that case some would disagree and say that anytime you have a quantifier, it is molecular.

Answer 2

1. The formula $$\forall x{\in} D\:\:P(x)$$ is logically equivalent to $$\forall x\,\big(x{\in} D\to P(x)\big).$$ These formulae are vacuously true when $∀x\;x\notin D,$ since a vacuously true sentence is a conditional whose antecedent is false.

   Your example statement is vacuously true because $∀x\:\:x\notin\emptyset=\{x\mid3<x<2\}.$

2. On the other hand, the formula $$\exists x{\in} D\:\:P(x)$$ is logically equivalent to $$\exists x\,\big(x{\in} D\:\land\:P(x)\big),$$ which can't be converted to a conditional statement, so can't have an antecedent to speak of as being false. So, it is never vacuously true.

3. An atomic formula is one that cannot be broken down into smaller ones; in contrast, a molecular formula does contain quantifier(s) and/or logical operator(s).

4. $ E=P\to Q\;$ is not a well-formed formula; perhaps you mean $\;(E\leftrightarrow P)\to Q.$

Answer 3

Regarding your claim:

My book says that the proposition "∀x∈D,P(x)" can be vacuously true, because it can be turned into the form "P→Q"

You seem to conflate the truth value of the material conditional P→Q with quantified formula ∀xP(x) where x ranges over D. P→Q may be an unquantified material conditional which may be vacuously true if the antecedent P is false. Or ∀x(P(x)→Q(x)) may be the quantified version what your teacher talked about. It has nothing to do with the truth value of the formula ∀xP(x) where x ranges over D.

As for the definition of atomic well formed formula, see reference here:

Next, each formula is assigned a truth value. The inductive definition used to make this assignment is called the T-schema.

Atomic formulas (1). A formula P(t1,... ,tn)...

Atomic formulas (2). A formula t1=t2 is assigned true if t1 and t2 evaluate to the same object of the domain of discourse (see the section on equality below).

So there're two types of atomic formula (wff) in the first order logic with equality.