# differentiate the terms deductive system, model/structure, formal system, first-order logic

I can not bring the terms deductive system, model/structure, formal system, first-order logic into order in my head ;-) It seems to me that they are not overly used in a consistent manner and sometimes even have different meanings. Maybe you can help me to sort it out in my brain ;-)

The deductive system (DS) is the syntactical manipulation mechanism, which allows formal deductions (i.e. something like Hilbert calculus). So we can decide something like $A \vdash_{DS} B$.

While a model/structure (M) gives semantic meaning to the formal language, i.e. allows for semantic truth interpretation of sentences. So we can decide something like $A \models_{M} B$.

A formal system then is the triple of a particular deductive system, a particular model and a formal language?

If talking about first-order logic we just mean the formal language together with one deductive system and a model/structure. So actually the characteristics, when talking about first-order logic is the available language, symbols, etc?

• Try asking one more clearly focused question at a time, if you want useful answers. – Peter Smith Sep 10 '13 at 10:16
• @Peter Smith: I tried and edited my post. Sorry! – logisches durcheinander Sep 10 '13 at 10:29
• logisches durcheinander: Thanks! I have tried to answer the shorter question. – Carl Mummert Sep 10 '13 at 11:54

When people say "first-order logic" they mean a logic that has a certain kind of language (built up from function symbols and relation symbols in the usual way), a certain kind of deductive system, and a certain semantics using structures. There are many variations that are all called "first-order logic", but they all behave in generally the same way.

The key aspects of first-order logic, apart from the specific kind of language, are that it has several key properties:

• Soundness: If a formula is provable, it is true in every structure (for the same language)

• Completeness: If a formula is true in every structure for its language, then the formula is provable

• Compactness: If a formula is a consequence of an infinite set $A$ of formulas, it is a consequence of some finite subset $F$ of $A$.

All the systems that people call "first order logic" will have these properties.

• Thank. Is it "for every possible structure" or "for every structure considered when talking about what is called first-order logic"? What are the certain kinds of language, deductive system and semantics -- are they defined by saying "first-order logic" or does every "first-order logic" have it's own certain language, deductive system and model? – logisches durcheinander Sep 10 '13 at 12:20
• Once a particular first-order language $L$ is fixed, there is an unambiguous definition of a "structure for the language $L$". When people say every possible structure, they always mean every possible "structure for the language $L$", where that quoted phrase has its formal definition. However, the concept of "structure for a language $L$" is sufficiently general that it covers everything we normally think about when we think about giving interpretations to the symbols of $L$ - any concrete informal interpretation can be converted to a "structure for the language $L$" in the formal sense. – Carl Mummert Sep 10 '13 at 12:24
• So actually, if I pin down a first-order language $L$ and choose which deductive system to use (e.g. natural deduction), I've settled what the "first-order logic" is I am working with and also possible structures for that language have been fixed then? So choosing a language and a particular decutive system determines the set of structures. If if additionally has the four mentioned key properties, I would call that the "first-order logic" I use? – logisches durcheinander Sep 10 '13 at 12:27
• As soon as you choose the language, the set of structures is already determined. There is a definition at en.wikipedia.org/wiki/Structure_%28mathematical_logic%29 or in any logic text. The choice of a deductive system is also determined. So really, if you know you want a first-order logic, all you have to choose is the language (also called the signature) and everything else is already defined by the general definitions for first-order logic. You can choose what kind of deductive system you want, but all the ones for first-order logic prove the same formulas ... – Carl Mummert Sep 10 '13 at 12:29
• ... namely, they prove a formula in a language $L$ if and only if that formula is true in every "structure for the language $L$". – Carl Mummert Sep 10 '13 at 12:31