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

→ Main article : 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

• There are also notation without brackets, such as the Polish notation ; but these are usually not that easy to read. The third definition line above is in this notation (compare: first-order predicate logic §Term ):

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

→ See also: Logical formulas ;  Term §expressions ;  First order predicate logic § Expressions .

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})}$

Propositional links

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

→ Main article : 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

See also : 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]).