F彐r(o(x)→v(x))→(彐ro(x)→v(x) T彐x(o(x)→v(x) F彐ro(x) T彐ro(x) F彐x(x) T彐ro(x) T o(co), new constant co T彐x(o(x)→v(x) T o(c1)v(c1), new constant c1 Fo(c1) F彐rp(x) Fw(c1) F v(c1) Figure 6: Tableau of 4.(b) 7. Given a language L, T is the theory and o is a sentence of L. T is finitely satisfiable if every finite subset of T is satisfiable. Answer the following question (a) If T is finitely satisfiable, prove that either TUo or TU no is finite satisfiable (4 marks) (b)If T is general, prove or disprove the result in(a) (2 marks Solution. (a) Suppose that TU o is not finitely satisfiable. (1 mark) Then, there is a finite A C Tsuch that A FT.(1 mark) We claim that TU o is finitely satisfiable Let∑ be a finite subset of t. Because△u∑ is satisfiable and△U∑-,∑U{o is satisfiable. (2 mark) Thus TU( o is finitely satisfiable (b)Given a general T, if T is satisfiable, then its every finite subset is also satisfiable. (1 mark)Then it also holds. (1 mark 8. In 1977 it was proved that every planar map can be colored with four colors(Of course there are only finite countries on map). If two countries are adjacent, they must be colore with two different colorsF ∃x(ϕ(x) → ψ(x)) → (∃xϕ(x) → ∃xψ(x)) T ∃x(ϕ(x) → ψ(x)) F ∃xϕ(x) → ∃xψ(x) T ∃xϕ(x) F ∃xψ(x) T ∃xϕ(x) T ϕ(c0), new constant c0 T ∃x(ϕ(x) → ψ(x)) T ϕ(c1) → ψ(c1), new constant c1 F ϕ(c1) T ψ(c1) F ∃xψ(x) F ψ(c1) ⊗ F ∃xψ(x) F ψ(c1) . . . Figure 6: Tableau of 4.(b) 7. Given a language L, T is the theory and ϕ is a sentence of L. T is finitely satisfiable if every finite subset of T is satisfiable. Answer the following question: (6 marks) (a) If T is finitely satisfiable, prove that either T ∪ {ϕ} or T ∪ {¬ϕ} is finite satisfiable. (4 marks) (b) If T is general, prove or disprove the result in (a). (2 marks) Solution. (a) Suppose that T ∪ {ϕ} is not finitely satisfiable.(1 mark) Then, there is a finite ∆ ⊂ T such that ∆ |= T. (1 mark) We claim that T ∪{¬ϕ} is finitely satisfiable. Let Σ be a finite subset of T. Because ∆ ∪ Σ is satisfiable and ∆ ∪ Σ |= ¬ϕ, Σ ∪ {ϕ} is satisfiable.(2 mark) Thus T ∪ {¬ϕ} is finitely satisfiable. (b) Given a general T, if T is satisfiable, then its every finite subset is also satisfiable.(1 mark) Then it also holds.(1 mark) 8. In 1977 it was proved that every planar map can be colored with four colors(Of course there are only finite countries on map). If two countries are adjacent, they must be colored with two different colors. 6