1
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ Try asking one more clearly focused question at a time, if you want useful answers. $\endgroup$ Commented Sep 10, 2013 at 10:16
  • $\begingroup$ @Peter Smith: I tried and edited my post. Sorry! $\endgroup$ Commented Sep 10, 2013 at 10:29
  • $\begingroup$ logisches durcheinander: Thanks! I have tried to answer the shorter question. $\endgroup$ Commented Sep 10, 2013 at 11:54

1 Answer 1

Reset to default
1
$\begingroup$

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$.

  • The Löwenheim–Skolem theorem

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

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$ Commented Sep 10, 2013 at 12:20
  • $\begingroup$ 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. $\endgroup$ Commented Sep 10, 2013 at 12:24
  • $\begingroup$ 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? $\endgroup$ Commented Sep 10, 2013 at 12:27
  • $\begingroup$ 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 ... $\endgroup$ Commented Sep 10, 2013 at 12:29
  • $\begingroup$ ... namely, they prove a formula in a language $L$ if and only if that formula is true in every "structure for the language $L$". $\endgroup$ Commented Sep 10, 2013 at 12:31

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.