[Solved]: What is the relation between First Order Logic and First Order Theory?

Problem Detail: 

I thought that any FOT is a subset of FOL, but that does not seem to be the case, because FOL is complete (every formula is either valid or invalid), while some FOT (like linear integer arithmetic) is not complete.

So, is FOL more expressive than any of FOT? Or incomparable?

Also, the statement "there are statements that are valid in LIA but cannot be proved using axioms of LIA" is weird. How can the statement be valid if we cannot prove its validity? I always thought that if you cannot prove the validity of the statement, then you cannot claim it is valid.

Asked By : Ayrat

Answered By : Yuval Filmus

First-order logic is a mathematical subject which defines many different concepts, such as first-order formula, first-order structure, first-order theory, and many more. One of these concepts is first-order theory: it is a set of first-order formulas. Often we consider the first-order theory generated by a finite number of axioms and axiom schemes. Such a theory is closed with respect to logical derivations, and we usually only consider theories satisfying this condition.

A first-order theory is complete if for every statement $\sigma$, it contains either $\sigma$ or its negation. Not every theory is complete. Indeed, Gödel's incompleteness theorem highlights the fact that many interesting first-order theories are necessarily incomplete.

A model of a first-order theory is a valid interpretation of the theory (we leave the exact definition for textbooks). For example, the first-order theory of groups consists of all statements that follow from the group axioms. Every group is a model of the first-order theory of groups.

For every given model, very given sentence is either true or false. Gödel's completeness theorem states that if a first-order sentence is true in all models of a first-order theory, then it is provable from a finite number of sentences in the theory. For example, every first-order statement in the language of groups which holds for all groups is provable from the group axioms.

LIA is (presumably) a first-order theory which is interesting enough to be incomplete due to Gödel's incompleteness theorem. However, in the standard model – the "true" integers – every sentence is either true or false. In particular, if $\sigma$ is a statement such that neither $\sigma$ nor $\lnot \sigma$ belong to LIA, then either $\sigma$ or $\lnot \sigma$ holds for the true integers, but this fact isn't provable in LIA.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56522