Second-order logic

The second -order predicate logic is a branch of mathematical logic. It extends the first-order predicate logic to the possibility of quantifying over all relations. The second- order predicate logic is therefore really more expressive than the first stage, however, has to mourn the loss of important records, such as the compactness of the set.

  • 2.1 structures and interpretations
  • 2.2 models
  • 5.1 Finite quantities
  • 5.2 Countable quantities
  • 6.1 invalidity of the compactness theorem
  • 6.2 invalidity of the set of Löwenheim - Skolem
  • 6.3 incompleteness of second -order logic

The language of the second -order predicate logic

This article uses the imported article first order predicate logic terms and descriptions.

Symbols

The symbols of the second -order predicate logic in addition to those of the first stage

  • Logical symbols
  • Variable symbols,
  • A (possibly empty ) set of constant symbols,
  • A (possibly empty ) set of function symbols,
  • A (possibly empty ) set of relation symbols

Additionally

  • Relations variable symbols,

Whose arity is necessary if listed as a superscript. They occur in addition to the variable symbols. Even if the intended application, namely the quantification over all relations, already is in the name, we want to refrain at this point as in the first order predicate logic and first see the purely syntactic symbols and the subsequent formation laws. The constant, function and relation symbols, and compiled into an amount that one calls the signature of the language. Note that the relation symbols are part of the signature, the relation variable symbols are not.

Terms and expressions

Terms, more terms are as explained in the first-order logic by the specified therein education laws. Thus, by means of further education legislation expressions were defined. We complement this by two additional rules:

  • Is an n- ary relation symbol and variables are terms, then an expression.
  • If an expression and a relation variable symbol, and are also expressions.

2nd stage

All expressions, which can be created according to the rules given above form, with the designated language, the Roman stands for the second stage. This is expressed, that one can quantify over all variables not only, but according to the second law of formation given above also all relation variables. This allows us to more expressions than in the first order predicate logic form, while for example the Peano axioms are not formulated in the first order predicate logic, we shall see below, that the second stage has a sufficient expressiveness.

Metalinguistic expressions

In the following we will use metalinguistic expressions for formulas, ie we will use in our formulas spellings that are not covered by above mentioned rules. Instead of we use small letters instead of capital letters and as such, making sure that no conflicts arise with the elements of the signature. Furthermore, we allow ourselves suggestive abbreviations such as for. The only reason for this is the improved readability of the formulas occurring; it is clear in each case which syntactically correct expression is meant by such a formula.

Semantics

Structures and interpretations

We start from a language and are now assign a meaning to the symbols introduced above. We proceed as in the first-order logic and define as there structures over the signature in order to assign our symbols therein constants, functions, relations can. An interpretation is a pair of a relation of the same arity maps consisting of a structure over a set and a so-called allocation function of each variable an element and each relation variables. If such an assignment, a variable, and so is again that of occupancy, with the exception of at all points with matches and only at the point has the potentially different value. Is analogous to a relational variable and a ratio, so that assignment is that, only at the position having the potentially different value than at all points coincides with. One writes and

Models

We say that an interpretation is a model for a term, and write for it, if this arises due to the following rules, where the rule -like structure of the language is used:

Thus, the symbols assigned to a substantive meaning. Is a set of expressions of the considered language and for all, we write for short again. Is a set of sentences, that is, containing no free variables, so we can also say that a model is because the model relationship does not depend in this case on the specific assignment from.

Peano axioms

As is known, let the Peano axioms can not be formulated in the first order predicate logic, since the induction axiom makes a statement about all subsets of the considered basic set, but can not be quantified over all subsets. However, since subsets are nothing more than single-digit ratios, you can take the signature, where 0 is a constant symbol, called a zero element, and a single-digit function symbol, called successor function, make the following expressions:

Consider interpretations, ie structures in which the symbol is 0 then element of a set and a defined on this function, so the first expression says that 0 is not a successor, because 0 is different from all the images. The second line expresses the injectivity of the successor function. The third line finally states that every unary relation ( ie subset of the considered basic range) that applies to 0 and with each, to which it applies, also applies to the successor, applies to all variables, thus the induction axiom is formulated. Thus the second -order predicate logic is really more expressive than that of first order.

Finally, one can show that the two structures, the models are above expressions are isomorphic. In QL, the second stage so there is no non-standard models of natural numbers.

Real Numbers

The theory of the parent body, which can be formulated with the signature in the language does not allow a clear identification of the real numbers up to isomorphism, because the completeness axiom, according to which each non-empty, bounded above set has a supremum, can be divided into not formulate. This lack of expressiveness of first-order predicate logic leads to non-standard analysis. In the treated here predicate logic second stage following symbolization of completeness succeed:

To explain this formula, note that the digit ratio is back for subsets of the population of an interpretation. For all subsets so it should apply: If it is not empty, and if it is bounded above, then there is one, so that this upper bound on the amount, and each small element no longer upper bound is. Thus, the completeness axiom is formulated in.

Widths

The second -order predicate logic provides opportunities over widths of sets of talking that go far beyond the first order predicate logic. In the following we use the abbreviation

What appears in every interpretation means that there is exactly one with.

Finite quantities

As is known, can not be expressed in first-order logic that a set is finite. One can only means of sets of the type

Say that a lot ( ie, the base region of an interpretation ) has at least elements. then only applies to quantities with exact elements. The finite amount would then be an infinite disjunction

Which can be formed neither in the first nor in the second stage. In QL, the second stage one has but

Each model of this sentence means that the binary relation is a function of the base region in itself, says that this is injective, and that it is surjective. The above formula indicates, therefore, that any injective function of the base region is automatically surjective in itself, a statement that is known to be exactly true for finite sets. Therefore, the formula actually means that all of them fulfilling models are finite. This again shows that the second -order predicate logic is really more expressive than the first stage.

Countable sets

One can in QL second stage even express that a set is countable, because a lot is at most countable if and only if there is a linear order relation on her, in the beginning of each section is finite. The fact that a linear order is, apparently is

Described, because this formula from left to right so that the binary relation is irreflexive, transitive and linear. A unary relation which is a subset of the base region is, if and only finite if every injective function of this subset in itself is already surjective, which can be symbolized in analogy to the above as follows:

The following formula symbolized then, that there is a linear order on a set, in which each initial section is finite, and that is equivalent to the fact that the amount is at most countable:

Defects of the second -order predicate logic

As the following comments show, the greater expressive power of second order logic leads to many important sets of first-order predicate logic no longer apply.

Invalidity of the compactness theorem

With the introduced above formulas and can be easily shown that for the second-order logic predicate no compactness theorem may apply. Clearly, every finite subset of the set of formulas

Satisfiable, that is, they have a model for a finite subset of this set of formulas is suitable for in

Included, so any finite set with at least elements is a model. In contrast, there is no model for the entire set of formulas, because a model of must be a finite set and therefore can not all meet.

However, since the compactness theorem holds for the first order predicate logic, this argument shows once again that in the first-order logic can not be formulated.

Invalidity of the set of Löwenheim - Skolem

In the section thickness we had created a formula whose models are exactly the maximum countable sets. Would the Löwenheim - Skolem also apply to the predicate second-order logic, it would have to give a countable set of formulas model, but this can not be, because every model of is necessarily uncountable.

Incompleteness of the second -order predicate logic

In the first-order logic one can set up a sequent calculus and proof of this is that it is sufficient for all derivations in a language of first-order predicate logic, which is the so-called Gödel's completeness theorem. One might try to extend such sequent calculus for elements that define the handling of relations variable symbols in order for the predicate calculus second stage, all derivations to run in such a calculus in a purely syntactic way. One such attempt is bound to fail, because with a complete sequent calculus for predicate logic second stage could transmit the evidence that it closes in the first order predicate logic to the compactness theorem to the predicate second-order logic, but we already know that the compactness theorem here does not apply.

If we denote the closure in such a sequent calculus with, it means that the term can by applications of the rules of the sequent calculus derived from the formula amount. The notation as above mean that every model that satisfies, must also meet. The currently executing consideration shows that if there is no sequent calculus, such that for all sets of formulas and expressions the equivalence

Applies. This does not exclude that there might be a sequent calculus that satisfies this equivalence for, then you would get at least a sequent calculus for general statements, but even that is not the case, as Kurt Gödel showed. This statement is called the incompleteness of second -order predicate logic. It should be noted that this is not the Gödel's incompleteness theorem.

659177
de