Wang's "Proving theorems by pattern recognition II", page 3 says:
What is the "fundamental theorem of logic"?
Asked
Active
Viewed 227 times
3
-
Completeness: (1.3.1) and (1.3.2) are one the negation of the other. Thus, (a) 1.3.1 is a theorem of predicate calculus iff (c) 1.3.2. is not satisfiable i.e. iff 1.3.1 is valid. – Mauro ALLEGRANZA Oct 11 '21 at 09:30
-
Title asks for fundamental problem, body, for fundamental theorem. Please edit for consistency, Rodrigo. – Gerry Myerson Oct 12 '21 at 12:27
-
1@GerryMyerson done – user1868607 Oct 12 '21 at 12:46
1 Answers
1
See PROCESS AND EXISTENCE IN MATHEMATICS (1961), reprinted into: Computation, Logic, Philosophy: A Collection of Essays (Kluwer, 1990), page 44:
It seems reasonable to suppose that if a theory is consistent, it must have some interpretation. [...] The fundamental theorem of logic gives a sharper answer for theories formulated as formal systems within the framework of logic, i.e., the theory of quantifiers: any such theory, if consistent, has a relatively simple model in the theory of positive integers, simple in the sense that rather low level predicates in the arithmetic hierarchy would suffice.
And see page 116 for reference to Herbrand's fundamental theorem.
Note In the book above we can find reprinted both "Proving theorems by pattern recognition I" and "Proving theorems by pattern recognition II".
Mauro ALLEGRANZA
- 94,169
-
4Self-promotion: I included a short (3 pages), purely semantical explanation of Herbrand's theorem in Section 3 of a paper "Resource Consciousness in Classical Logic" [ in "Games, Logic, and Constructive Sets" (G. Mints and R. Muskens, eds.) CSLI Lecture Notes 161 (2003) 61--74], available in pre-publication form at http://www.math.lsa.umich.edu/~ablass/llc9.pdf . – Andreas Blass Oct 12 '21 at 16:14