[Math] Is first-order logic more expressive than propositional logic with infinite statements

first-order-logiclogicpropositional-calculus

I read that the difference between propositional logic and first-order logic is that in the latter, we can quantify over individual objects. However, if infinitely long statements are allowed, it appears to me that statements in first-order logic can be turned into statements in propositional logic by the following process:

  1. Turn existential quantifiers into universal quantifiers: $\exists x .\varphi \left( x\right) \longrightarrow \neg \forall x .\neg \varphi \left( x\right)$
  2. Expand universal quantifiers into (possibly infinite) conjunctions (if the quantifiers are nested, do this repeatedly from the outermost one): $\forall x\in \left\{ a, b,\ldots \right\} .\varphi \left( x\right) \longrightarrow \varphi \left( a\right) \wedge \varphi \left( b\right) \wedge \ldots $
  3. Substitute predicates for their definitions, with the parameters instead of free variables: when $\varphi \left( x\right) : x = 10$, $\varphi \left( a\right) \longrightarrow a = 10$

Is this correct, and is propositional logic with infinite statements as expressive as first-order logic, or are there statements that can't be converted this way?

Best Answer

The answer to your question is a qualified no. Part of the reason is that we can't assume that every object in our model is named by an individual constant. So for instance, it could be that our model satisfies the sentence $\bigwedge_{i \in I} \neg P(c_i)$, where "$\bigwedge_{i \in I}$" indicates (possibly infinite) conjunction over index set $I$, and $c_i$ are all constants of the language, and yet this same model also satisfies the sentence $\exists x P(x)$. It's just that the object in our model which satisfies $P(x)$ is unnamed.

Of course, you're right that there is a strong analogy between quantifiers and infinite conjunctions/disjunctions in the following sense: if we require that every object in our domain is named by a constant, and if we allow for arbitrary conjuncts/disjuncts, then we can translate the quantified sentences into quantifier-free sentences using (possibly infinite) conjunctions/disjunctions. Logicians sometimes define substitutional quantifiers for this purpose: for instance, letting $\Sigma$ be a new substitutional quantifier, $\Sigma x \varphi(x)$ is true in a model just in case for some constant $c$, $\varphi(c)$ is true in that model, i.e. just in case $\bigvee_{i \in I} \varphi(c_i)$ is true in that model, where $I$ indexes the constants of $L$.

With that said, an infinitary propositional logic without quantifiers is not the same as a first-order logic with quantifiers. For one thing, in a propositional logic, you can only say $p$ is true or false. Your models aren't collections of objects with structure, but rather are simply truth value assignments for the proposition letters. So it's hard to say in what sense, if any, an infinitary propositional logic is the same as first-order logic without infinitary conjunctions/disjunctions. Their models don't even look alike.

Furthermore, even an infinitary predicate logic without quantifiers fails to be equivalent to first-order logic with quantifiers (but only finite conjunctions/disjunctions). The reason is simple: in first-order logic, there is no sentence which is true exactly when the domain is infinite. However, if the language you invoke has (at least) countably many constants $c_i$, then the sentence $\bigwedge_{\substack{i,j \in \omega \\ i \neq j}} c_i \neq c_j$ can only be true in infinite models. Hence, infinitary predicate logic without quantifiers is not compact, and so can't be equivalent to first-order logic.

Related Question