# Elementary language

An elementary language (also: language of the first level with the set of symbols S) is a formal language defined within the framework of the first level predicate logic . With these languages, mathematical theories can be treated logically; so z. As the set theory etc. Experience shows even be that all mathematical statements in an appropriate first-order language formalize leave, and that all provable statements within a first-order language using the sequent calculus can be derived. ${\ displaystyle L ^ {S}}$

## The alphabet of a first level language

### definition

The alphabet of a first-level language includes the following characters:

1.  ${\ displaystyle v_ {0}, v_ {1}, v_ {2}, \ ldots}$  Symbols for variables ;
2.  ${\ displaystyle \ neg, \ wedge, \ vee, \ rightarrow, \ leftrightarrow}$  Junctions : not, and, or, if - so, exactly if;
3.  ${\ displaystyle \ forall, \ exists}$  Quantifiers : for all, there are;
4.  ${\ displaystyle \ equiv}$  Equal sign;
5.  ${\ displaystyle), (}$  technical symbols: brackets;
6.  such as
a) for each possibly empty one () amount of -ary relation symbols , all together: ;${\ displaystyle n \ geq 1}$${\ displaystyle n}$${\ displaystyle R_ {1}, R_ {2}, \ ldots}$
b) for each possibly empty one () amount of -ary function symbols , all together: ;${\ displaystyle n \ geq 1}$${\ displaystyle n}$${\ displaystyle f_ {1}, f_ {2}, \ ldots}$
c) a (possibly empty) set of symbols for constants (see note below on 0-digit functions).${\ displaystyle c_ {1}, c_ {2}, \ ldots}$

The set of characters under points 1 to 5 are the logical characters ; they are the same for all first-order languages; they are denoted by A.

The amount of characters in item 6 is called set of symbols (including signature ) ; it determines the special language of the first level. ${\ displaystyle S = \ {R_ {1}, R_ {2}, \ ldots, f_ {1}, f_ {2}, \ ldots, c_ {1}, c_ {2}, \ ldots \}}$

### Hints

• In the alphabet (mathematics) the constants from (f) (3) are not listed if the definition is otherwise identical; for this, zero-digit relations and functions are allowed in (f) (1) ( ), the latter correspond to the constants from the above definition (see also zero -digit links ).${\ displaystyle n = 0}$
• The single-digit relations define groups as they correspond to sets or general classes .

### Example: group theory

To formalize the concept of the group and the defining axioms, one proceeds as follows:

1. The variables stand for elements of the group; there is also a constant .${\ displaystyle x, y, z, \ ldots}$${\ displaystyle e}$
2. A symbol is introduced; this stands for the two-digit link between two elements.${\ displaystyle \ circ}$
3. Associative law: ${\ displaystyle \ forall x \ forall y \ forall z (x \ circ y) \ circ z \ equiv x \ circ (y \ circ z)}$
4. Neutral element: ${\ displaystyle \ forall x (x \ circ e \ equiv x)}$
5. Inverse elements: ${\ displaystyle \ forall x \ exists y (x \ circ y \ equiv e)}$

In this case there is a two-digit function symbol and a single constant . ${\ displaystyle \ circ}$${\ displaystyle e}$

### Further examples

Relation symbols Function symbols Constants Surname
${\ displaystyle \ leq}$ (binary) ${\ displaystyle +, \ cdot}$ (both two digits) 0, 1 Orderly bodies
${\ displaystyle \ circ}$ (binary) e groups
+, (both two-digit) ${\ displaystyle \ cdot}$ 0, 1 Rings
${\ displaystyle \ sim}$ (binary) Equivalence relation

## Terms

The terms of an elementary language are defined recursively . A term in elementary language is obtained by finitely many applications of the following rules ${\ displaystyle T ^ {S}}$

1. Variable symbols are terms.
2. Constant symbols are terms.
3. If there are a -digit function symbol and terms, then there is also a term.${\ displaystyle f}$${\ displaystyle n}$${\ displaystyle t_ {1}, \ ldots, t_ {n}}$${\ displaystyle f (t_ {1}, \ ldots, t_ {n})}$
Set of symbols S Example for terms from ${\ displaystyle T ^ {S}}$
${\ displaystyle (0,1, +, \ cdot, <) \}$ ${\ displaystyle 0,1,0 + 1, (0 + v_ {1}) \ cdot ((v_ {0} +1) + (v_ {2} +1)) \}$,
${\ displaystyle (0, +) \}$ ${\ displaystyle 0 + v_ {0} \}$
${\ displaystyle (1, S) \}$ ${\ displaystyle 1, S (1), S (S (1)), \ ldots}$
Remarks
o   If is an n -place function symbol and are terms, then is also a term.${\ displaystyle f}$${\ displaystyle t_ {1}, \ dotsc, t_ {n}}$${\ displaystyle ft_ {1}, \ dotsc, t_ {n}}$
• Occasionally the constants are subsumed as zero-digit functions, which is particularly evident in the bracket-free notation.

## Formulas

The formulas of language are obtained by a finite number of applications of the following rules: ${\ displaystyle L ^ {S}}$

### Atomic formulas

1. If and are terms, then is a formula.${\ displaystyle t_ {1}}$${\ displaystyle t_ {2}}$${\ displaystyle t_ {1} = t_ {2}}$
2. If there are a -digit relation symbol and terms, then is a formula.${\ displaystyle R}$${\ displaystyle n}$${\ displaystyle t_ {1}, \ ldots, t_ {n}}$${\ displaystyle R (t_ {1}, \ ldots, t_ {n})}$

1. If there is a formula, then too .${\ displaystyle \ psi}$${\ displaystyle \ neg \ psi}$
2. If and are formulas, then too ${\ displaystyle \ psi}$${\ displaystyle \ theta}$
• ${\ displaystyle \ psi \ wedge \ theta}$
• ${\ displaystyle \ psi \ vee \ theta}$
• ${\ displaystyle \ psi \ rightarrow \ theta}$
• ${\ displaystyle \ psi \ leftrightarrow \ theta}$

### Quantifiers

If is a formula and any variable symbol, then are too ${\ displaystyle \ psi}$${\ displaystyle x}$

${\ displaystyle \ exists x \ psi}$ and
${\ displaystyle \ forall x \ psi}$

Formulas.

The elementary language for the set of symbols (signature) now consists of all formulas formed according to the above rules. ${\ displaystyle L ^ {S}}$${\ displaystyle S}$

## Connection with Chomsky hierarchy

1. The rules for terms correspond to a context-free language .
2. The rules for formulas also correspond to a context-free language : Elementary languages ​​are therefore context-free languages ​​and thus a special class of formal languages .
3. The rules for evidence correspond to a context-sensitive language . A context-sensitive analysis can decide whether there is a given proof for a formula.
4. The rules for deriving a formula from a system of axioms correspond to a semi-decidable language . In general there is no algorithm for obtaining a proof that derives a formula from another set of propositions.

## swell

• HD Ebbinghaus, J. Flum, W. Thomas: Introduction to mathematical logic. BI-Wiss. Verlag, Mannheim / Leipzig / Vienna / Zurich 1992, ISBN 3-411-15603-1 .
• Hans-Peter Tuschik, Helmut Wolter: Mathematical logic - in short. Basics, model theory, decidability, set theory. BI-Wiss. Verlag, Mannheim / Leipzig / Vienna / Zurich 1994, ISBN 3-411-16731-9 .

## Individual evidence

1. Ebbinghaus u. a., Chapter VII §2: Mathematics as part of the first level.
2. Occasionally zero-digit relations are allowed, these then appear as logical constants (in principle, identifiers for true or false ).
Stefan Brass: Mathematical Logic with Database Applications . Martin Luther University Halle-Wittenberg, Institute for Computer Science, Halle 2005, p. 176 , here p. 19 ( informatik.uni-halle.de [PDF]).