Ein Direkter Beweis für die Allgemein‐Rekursive Unlösbarkeit des Entscheidungsproblems des Prädikatenkalküls der Ersten Stufe mit Identität (Q3240233)

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 3124821
Language Label Description Also known as
default for all languages
No label defined
    English
    Ein Direkter Beweis für die Allgemein‐Rekursive Unlösbarkeit des Entscheidungsproblems des Prädikatenkalküls der Ersten Stufe mit Identität
    scientific article; zbMATH DE number 3124821

      Statements

      Ein Direkter Beweis für die Allgemein‐Rekursive Unlösbarkeit des Entscheidungsproblems des Prädikatenkalküls der Ersten Stufe mit Identität (English)
      0 references
      0 references
      1956
      0 references
      Mathematical logic and foundations
      0 references
      By a direct proof of the recursive unsolvability of the decision problem for first-order logic the author in effect means a proof which does not depend on results in recursive function theory. Such a proof is obtained by reconstructing a rudimentary ``theory'' of recursive functions within first-order logic itself. Given a system \(E\) of equations which define a recursive funetion \(f\), we may think of the different terms which can be constructed out of materials present in \(E\) as individuals and of the structure \(S\) which is imposed on them by the formation rules and by \(E\) as determined by suitable first-order expressions. The author shows that one can construct a formula \(B_{E,f}\) which ``says'' that \(f\) is defined by \(E\), i.e. which is satisfied by \(S\) and which is such that every structure satisfying it has a substructure isomorphic wich \(S\). Moreover, given an arbitrary function \(f\) and a number \(n\), the author shows how to construct a formula \(C_{f,n}\) which ``says'' that \(f(n)\neq 0\). This formula depends on \(n\) recursively, but it is independent of \(E\). The conjunction \(B_{E,f}\& C_{f, n}\) will then be satisfiable if and only if \(f(n) = O\) does not follow from the defining equations \(E\) of \(f\). If the decision problem for first-order logic were solvable, there would be a recursive function \(\varphi\) such that \(\varphi(t) = O\) whenever \(A_t\) (i.e. the formula no. \(t\) in some fixed enumeration of all the well-formed first-order formulae) is satisfiable. Then the function \(\psi(t) = \varphi(\zeta(t))\) is also recursive where \(C(t)\) is the number of the formula \(B_{E,f}\& C_{f,t}\). The function \(\psi\) is therefore definable by some system of equations, say \(E\). Now let \(q\) be the number of the formula \(B_{E,f}\). Then the formula \(B_{E,f}\& C_{f, n} =A_{\zeta, q}\) is one hand satisfiable if and only if \(\psi(q) = \varphi(\zeta(q))\neq 0\), for \(\psi\) was assumed to be defined by \(E\). On the other hand, \(\varphi\) was assumed to be such that \(\varphi(\zeta(q))=0\) if and only if \(A_{\zeta(q)}\) is satisfiable. This contradiction shows that there cannot be any function \(\varphi\) of this kind, i.e. that the decision problem for first-order logic is unsolvable.
      0 references

      Identifiers