Definition 5(size of a model). The size of a model is the cadinality of the universe A Example2.Le4=<{co,,…,cn},{P={<c0,c0>},R={<co,c0>,<c1,c1> Cn,Cn>)>. It is easy to check it is a model of a= y(R(y, y)v P(, y))A(aR(, a) Here, we give a finite model. You can also construct a infinite model Example 3. Suppose we have a language L=< (P,, f(a, yF,c, d>. Given two sentences (Va)P(c, r)and(Vr)(P(a, c), P(, d)) Remark. We know that the structure A =< M, P=<h, f(a, y)), c=0, d= 21> is a infinite model of them You can also find a finite model 4.1 Skolem-Lowenheim theorem infinite sentences. We have the following theorem Qre curious about the case that there are maybe In previous case, we have only finite sentence. We Theorem 6. If a countable set of sentences s is satisfiable, then it has a countable mod In the proof of completeness theorem, we construct the model by collecting all constants introduced by 3-style node. As any sentence a could be taken as a sequence of symbols. It is obvious that a sentence could only contributes finite possible new constants Proof. Consider the tableau proof with the root F(aM-a). The tree is not finite otherwise S is unsatisfiable. It means there is a non-contradictory path. We can construct a model along that path. There are at most countable new constants 5 Compactness theorem Theorem 7(Completeness and Soundness) 1. a is a tableau provable from S+ a is a logical consequence of s. 2. If we take a to be any contradiction such as BAnB in 1, we see that s is inconsistent if and only if s is unsatisfiable Theorem 8. Let S=a1, a2, . be a set of sentences of predicate logic. S is satisfiable if and only if every finite subset of s is satisfiableDefinition 5 (size of a model). The size of a model is the cadinality of the universe A in the structre A. Example 2. Let A =< {c0, c1, . . . , cn}, {P = {< c0, c0 >}, R = {< c0, c0 >, < c1, c1 >, . . . , < cn, cn >} >. It is easy to check it is a model of α = (∃y)(¬R(y, y) ∨ P(y, y)) ∧ (∀x)R(x, x). Here, we give a finite model. You can also construct a infinite model. Example 3. Suppose we have a language L =< {P, }, {f(x, y)}, {c, d} >. Given two sentences (∀x)P(c, x) and (∀x)(P(x, c) → P(x, d)). Remark. We know that the structure A =< N , {P =≤}, {f(x, y)}, {c = 0, d = 2} > is a infinite model of them. You can also find a finite model. 4.1 Skolem-L¨owenheim theorem In previous case, we have only finite sentence. We are curious about the case that there are maybe infinite sentences. We have the following theorem. Theorem 6. If a countable set of sentences S is satisfiable, then it has a countable model. In the proof of completeness theorem, we construct the model by collecting all constants introduced by ∃-style node. As any sentence α could be taken as a sequence of symbols. It is obvious that a sentence could only contributes finite possible new constants. Proof. Consider the tableau proof with the root F(α ∧ ¬α). The tree is not finite otherwise S is unsatisfiable. It means there is a non-contradictory path. We can construct a model along that path. There are at most countable new constants. 5 Compactness theorem Theorem 7 (Completeness and Soundness). 1. α is a tableau provable from S ⇔ α is a logical consequence of S. 2. If we take α to be any contradiction such as β ∧ ¬β in 1, we see that S is inconsistent if and only if S is unsatisfiable. Theorem 8. Let S = {α1, α2, . . .} be a set of sentences of predicate logic. S is satisfiable if and only if every finite subset of S is satisfiable. 4