Bases for first-order theories and subtheories (Q3843604)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3176041
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Bases for first-order theories and subtheories |
scientific article; zbMATH DE number 3176041 |
Statements
Bases for first-order theories and subtheories (English)
0 references
1960
0 references
0.8961796
0 references
0.8834281
0 references
0 references
0.8800447
0 references
0.87650496
0 references
0.86857414
0 references
The basic situation considered by the author is the following: We have a theory (set of theorems) \(S\) in applied first order logic (lower predicate calculus with or without identity): we have a basis \(B\) for \(S\) (i. e. a subset of \(S\) such that \(S\) is the closure of \(B\) under deduction); and we have specified a subset \(\alpha\) of the set of all non logical symbols of \(S\). Suppose we are interested in the set \(S^{-}\) of those members of \(S\) which do not contain members of \(\alpha\), considering the symbols of \(\alpha\) as ``auxiliaries'' for the deduction of members of \(S^{-}\) from \(B\). What can we then say concerning \(S^{-}\) if we know \(B\) ? The author's first main result is to show how, in case \(B\) is finite and hence equivalent to a single prenex formula \(B_0\), we can on the basis of \(B_0\) recursively enumerate a sequence of formulas \(B_1, B_2,\ldots\) none of which contains any members of \(\alpha\) and which together constitute a basis for \(S^{-}\). All the members of this sequence \(\sigma\) are consequences of \(B_0\). An arbitrary member of \(\sigma\) is obtained, very roughly speaking, from \(B_0\) by the following operations: (i) The quantifier structure of \(B_0\) is ramified by letting parts of it to be repeated; (ii) It is converted back to the prenex form; (iii) Its matrix is transformed into propositional normal form; (iv) Those parts of the matrix are omitted which contain members of \(\alpha\) while making sure that no illicit identities can come about as a consequence. This procedure can be subjected to various further regularities; for instance, every member of \(\sigma\) can be at least as strong as its predecessors. Also, the deduction of a member \(C\) of \(S^{-}\) from \(B_0\) can be split into two parts of rather different character. First, a suitable member of \(\sigma\) is deduced from \(B_0\); then \(C\) is deduced from it. This fact, together with the regularities to which the first part of the deduction can be subjected, may be considered as bringing out the role of the ``auxiliaries''. The author considers one particularly clear cut way of generating \(\sigma\) in lower predicate calculus with identity. A theory which has a basis generable in this way he calls axiomatizable by a scheme of kind 1. This notion is seen to coincide with finite axiomatizability using additional predicate symbols. The author's results solve a part of the elimination problem for second order logic. They can be generalized into different directions. In the paper, they are first formulated for lower predicate calculus with identity. Similar results are available for a system without identity, but the formulations are usually more complicated. The proofs turn on the author's earlier papers, especially on ``Linear reasoning. A new form of the Herbrand-Gentzen theorem'' [J. Symb. Log. 22, 250--268 (1957; Zbl 0081.24402)]. The basic idea is to assume that first-order arguments are given in the form of linear proofs and then to transform them suitably by permuting applications of different rules. As a by-product of the proofs, it is seen that certain regularities can always be imposed on linear deductions as well as on the Herbrand type deductions considered by the author. A couple of corrections are made to the author's earlier papers, none of them crucial. Finally, it is proved that the two sets of (the Gödel numbers of) those pairs \(\langle B_0, \sigma\rangle\) where the associated \(S^{-}\) is, respectively, (a) finitely axiomatizable or (b) not finitely axiomatizable are not recursively enumerable. Together with the author's earlier papers, the present one throws very interesting light on a central area of mathematical logic. The wealth of detail which is needed (in spite of the author's expository skill) provokes the question whether some alternative approach might perhaps bring out the situation even more sharply.
0 references