4

What is the difference between first-order languages (where the universal and existential quantifiers are defined as infinite disjunctions and conjunctions, respectively) and languages with infinitely long expressions (which allow infinite disjunctions and conjunctions)?

0
1

There are a few differences:

  • Infinitary predicate logic is not compact. FOL is. See a proof on this excellent answer.
  • Their models are different. Practically, predicate logic doesn't even have a model, as its valuation (or interpretation) function v*(...) is always equivalent to its truth-value function v(...). This is not the case with FOL.
  • Since we can have unnamed objects in FOL (that is, objects that do not map to constants), we can arguably be more expressive. Keeping that in mind, ∀xP(x) can capture more "things" than P(A) ∧ P(B) ∧ P(C) ∧ ....
0

As a start, consider taking an infinite disjunction that happens to be true and adding another term at the end, that happens to be false. In evaluation, would you ever get to that last term? Obviously it makes the whole thing false, but you have an infinite task to exhaust before even considering it.

We want finite proofs. So should we consider this provably false or throw it into some ambiguous category? What if we somehow imagine replacing each term of our infinite sequence with another infinite sequence? Things get weird.

Infinitary languages, and transfinite sequences in general, create a lot of such silly problems. So in logic, outside of the theory of orderings itself, we generally prefer transfinite sets but only arbitrarily long sequences. The fact that quantifiers are over sets and not sequences lets us have that.

If you want to model quantifiers as infinite statements, they are sequential. So you are pulled down a certain rabbit hole into transfinite induction and the vagaries of ordinal representations.

0

In formal languages quantifiers are not defined, they are basic symbols manipulated according to axiomatized rules. When language is interpreted then quantifiers are interpreted as infinite conjunctions or disjunctions, but interpretations are external to the language itself, and it does not always behave as "expected". For example, Gödel showed that there are predicates P in Peano arithmetic such that P(n) is provable for n=1,2,..., but ∀xP(x) is unprovable, so the quantifier does not reduce to "infinite conjunction". Peano arithmetic is ω-incomplete. There are even consistent extensions of it that prove every P(n) together with ¬∀xP(x), they are ω-inconsistent.

Languages that allow infinite expressions are called infinitary languages and can themselves be of first or higher order, depending on what one can quantify over. Even first order infinitary languages are much more expressive than their finitary counterparts, for example they can specify the standard model of arithmetic, which finitary Peano arithmetic can not, it allows non-standard models with "infinite numbers". However, infinitary languages usually lack nice structural properties, which makes them intractable. For example, any finitary language is compact, if a conclusion is derivable from a set of premises it is already derivable from a finite subset of it. But this is obviously false even in first order infinitary languages, an infinite conjuction is not derivable from any finite subset of its terms.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy