first order language
the set of terms of , which is built inductively from , as follows:
Any variable is a term;
Any constant symbol in is a term;
If is an -ary function symbol in , and are terms, then is a term.
the set of formulas of , which is built inductively from , as follows:
If and are terms, then is a formula;
If is an -ary relation symbol and are terms, then is a formula;
If is a formula, then so is ;
If and are formulas, then so is ;
If is a formula, and is a variable, then is a formula.
In other words, and are the smallest sets, among all sets satisfying the conditions given for terms and formulas, respectively.
Formulas in 3(a) and 3(b), which do not contain any logical connectives, are called the atomic formulas.
For example, in the first order language of partially ordered rings, expressions such as
are terms, while
are formulas, and the first two of which are atomic.
Generally, one omits parentheses in formulas, when there is no ambiguity. For example, a formula can be simply written . As such, the parentheses are also called the auxiliary symbols.
The other logical symbols are obtained in the following way :
where and are formulas. All logical symbols are used when building formulas.
In the literature, it is a common practice to write for . The first subscript means that every formula in contains a finite number of ’s (less than ), while the second subscript signifies that every formula has a finite number of ’s. In general, denotes a language built from such that, in any given formula, the number of occurrences of is less than and the number of occurrences of is less than . When the number of occurrences of (or ) in a formula is not limited, we use the symbol in place of (or ). Clearly, if and are not , we get a language that is not first-order.
First Order Languages as Formal Languages
If the signature and the set of variables are countable, then , and can be viewed as formal languages over a certain (finite) alphabet . The set should include all of the logical connectives, the equality symbol, and the parentheses, as well as the following symbols
where they are used to form words for relation, formula, and variable symbols. More precisely,
stands for the variable ,
stands for the -th relation symbol of arity , and
stands for the -th function symbol of arity ,
|Title||first order language|
|Date of creation||2013-03-22 12:42:46|
|Last modified on||2013-03-22 12:42:46|
|Last modified by||CWoo (3771)|
|Defines||first order language|