Hilbert System for Predicate Logic 1 Completeness Theorem for First Order Logic 1.1 Compactness Theorem for Propositional Logic

Content Provider	Semantic Scholar
Abstract	There are many proofs of the Completeness Theorem for First Order Logic. We follow here a version of Henkin's proof, as presented in the Handbook of Mathematical Logic. It contains a method for reducing certain problems of first-order logic back to problems about propositional logic. We give independent proof of Compactness Theorem for propositional logic. The Compactness Theorem for first-order logic and Löwenheim-Skolem Theorems and the Gödel Completeness Theorem fall out of the Henkin method. Let L = L(P, F, C) be a first order language with equality. We assume that the sets P, F, C are infinitely enumerable. We define a propositional logic within it as follows. Prime formulas We consider a subset P of the set F of all formulas of L. Intuitively these are formulas of L which are not direct propositional combination of simpler formulas, that is, atomic formulas (AF) and formulas beginning with quantifiers. Formally, we have that P = {A ∈ F : A ∈ AF or A = ∀xB, A = ∃xB f or B ∈ F}. Example 1.1 The following are primitive formulas. The following are not primitive formulas. (R(t 1 , t 2) ⇒ (c = c)), (R(t 1 , t 2) ∪ ∀x(A(x) ⇒ ¬A(x)). Given a set P of primitive formulas we define in a standard way the set P F of propositional formulas as follows.
File Format	PDF HTM / HTML
Alternate Webpage(s)	http://www3.cs.stonybrook.edu/~pfodor/courses/CSE371/ch14/chapter14.pdf
Language	English
Access Restriction	Open
Content Type	Text
Resource Type	Article