OL { list-style-type: decimal } OL OL { list-style-type:lower-alpha } .model { font-family: cursive } </STYLE> &html.header; <H1/&title;/ <OL><LI> Suppose the predicate R defines a finite subset of ω. Say ~R = {a_1_, …, a_n_}~. Let ~ψ_0_ = ∀y(x<y ∨ x=y)~. ψ_0_ asserts that ~x = 0~. For ~i > 0~ let ~ψ_i_ = ∀a{ψ_(i-1)_(x/a) → [a<x ∧ ∀y¬(a<y ∧ y<x)]}~. ψ_i_ asserts that ~x = i~ by claiming it is the successor of i-1. Let ~σ(i) = ∀x(ψ_a<SUB/1/_ → x=i) ∨ … ∨ ∀x(ψ_a<SUB/n/_ → x=i)~ σ(i) explicitly defines R. Since &sigma asserts that i is one of a_1_ through a_n_. Cofinite sets are done in a similar manner, except that ~σ(i) = ¬[∀x(ψ_a<SUB/1/_ → x=i) ∨ … ∨ ∀x(ψ_a<SUB/n/_ → x=i)]~. Suppose that R defines a subset of ω that is neither finite nor cofinite. Assume that σ explicitly defines R. Therefore ~(ω, <) &models ∀x∃y(x<y &rarr (σ(x) ↔ ¬σ(y))~. Let &germB; be the discrete ordering with a subset isomorphic to &omega, and the remaining set isomorphic to one copy of the integers. Clearly ~(ω, <) ≺ &germB;~. So ~&germB &models ∀x∃y(x<y ∧ (σ(x) ↔ ¬σ(y))~ Let a∈B but a∉ω. There is a b∈B &st; ~a < b~ and ~&germB ⊧ σ[a]~ ⇔ ~&germB ¬models; σ[b]~, Clearly b∉ω Let ~c = b-a~. There is an automorphism of &germB; that maps each x∉ω to x-c. In particular b is mapped to b-c=a. Therefore ~&germB ⊧ σ[a]~ ⇔ ~&germB ⊧ σ[b]~, which is a contradiction. So R cannot be explicitly definable. <LI><OL><LI> Let ~σ_1_ = ∀x(∀y(x<y ∨ x=y) → Rx)~ Let ~σ_2_ = ∀x_1_∀x_2_{[x_1_<x_2_ &and ∀z ¬(x_1_<z ∧ z<x_2_)] → (Rx_1_ ↔ ¬Rx_2_)}~ Suppose ~(ω, <, R) ⊧ σ_1_ &and σ_2_~ ~∀y∈ω(0<y ∨ 0=y)~, so by σ_1_, ~(ω, <, R) ⊧ R0~. Suppose ~(ω, <, R) ⊧ Rk~ ⇔ k is even. Noting that ~∀z∈ω ¬(k<z ∧ z<(k+1))~, so by σ_2_, ~(ω, <, R) &models Rk~ ⇔ ~(ω, <, R) ⊧ ¬R(k+1)~. So ~(ω, <, R) &models R(k+1)~ ⇔ ~(ω, <, R) ¬models Rk~ ⇔ k is odd ⇔ k+1 is even. So by induction ~∀n∈ω (ω, <, R) ⊧ Rn~ ⇔ n is even. Now suppose Q is a predicate such that Qn ⇔ n is even. The only n in &omega &st; ~∀y(n<y &or n=y)~ is 0. So ~(ω, <, Q) ⊧ σ_1_~. Suppose n and m are such that ~[n<m ∧ ∀z ¬(n<z ∧ z<m)]~. Clearly ~m = n+1~. Since ~(ω, <, Q) &models Qn~ ⇔ ~(ω, <, Q) &models ¬Q(n+1)~, then ~(ω, <, Q) &models σ_2_~. So ~(ω, <, Q) &models σ_1_ ∧ σ_2_~. So finally we conclude ~(ω, <, R) &models σ_1_ ∧ σ_2_~ ⇔ R=Q. So even numbers are implicitly definable. The set of even numbers is neither finite nor cofinite. So by Question 1, even numbers are not explicitly definable. <LI> Let ~φ_1_ = ∀a(a+z=a)~ Let ~φ_2_ = ∀a∀z((φ_1_ ∧ ¬z=a) → [¬z=e ∧ ∃y(y+e)=a])~ Let ~σ_1_ = ∀z∀y(φ_1_ → R(z,y,z))~ Let ~σ_2_ = ∀e∀a∀b((φ_2_ &and a+e=b) → ∀w∀x∀y[R(b,w,x) ↔ (R(a,w,y) ∧ y+w=x)])~ Claim: ~(ω, +, R) ⊧ σ_1_ ∧ σ_2_~ ⇔ R is the ⋅ relation. (ie, R(m,n,k) ⇔ m⋅n=k). Proof: φ_1_ asserts that z is 0 by saying a is the additive identity. φ_2_ asserts that e is 1 by saying that e is not 0 and for all non-zero numbers a there is a y such that y+e=z. σ_1_ asserts that for all y, R(0,y,0). This is clearly true of the ⋅ relation. σ_2_ asserts that for all a, w and x, R(c+1,w,x) ⇔ R(c,y,x-y). This is true of the ⋅ relation. Furthermore σ_1_ and σ_2_ are exactly the relations that define multiplication, therefore multiplication is implicitly definable. </OL> <LI> Let ~X ⊆ A~ and have cardinality ~< κ~, and Σ a complete 1-type for Th &germA;_X_. So there is a &germB; modeling ~Th &germA;_X_~ and b∈B &st; ~Σ = {φ | φ is 1-ary and &germB; ⊧ φ[b]}~. Let ~X_1_ = {x∈X | x <^&germB;^ b}~, and ~X_2_ = {x∈X | b <^&germB;^ x}~. Since X_1_ and X_2_ both have cardinality ~< κ~, then by the properties that &germA; are given in the question, there is an a∈A such that X<a<Y (or X_1_<a if X_2_ is empty, or a<X_2_ if X_1_ is empty). Let φ∈Σ ~&germB; ⊧ φ[b]~. Since the theory of dense linear orderings admits elimination of quantifiers, there is some quantifier free formula ψ &st; ~T ⊧ φ ↔ ψi~ ~&germB; &models ψ[b]~ For any constant &underlineC;, we have ~b < &underlineC;~ ⇔ ~a < &underlineC;~, and ~&underlineC; < b~ ⇔ ~&underlineC; < a~. Since ψ is a boolean combination of these relations, then ~&germA;_X_ &models ψ[a]~ So, ~&germA;_X_ &models φ[a]~, since &germA; is also models T. So, Σ is realized in &germA;_X_, and we conclude that Σ is κ-saturated. <LI> Let T_1_ or T_2_ have no infinite models. &Wlog; assume that T_1_ has no infinite model. Let &germA;_1_ and &germA;_2_ be models of T_1_ and T_2_ respectively. A_1_ is finite. Let &germC;_1_ and &germC;_2_ be ρ reducts of &germA;_1_ and &germA;_2_. Let σ be a ρ sentence. ~&germC;_1_ ⊧ σ~ ⇔ ~T_1_ ⊧ σ~ ⇔ ~T_2_ ⊧ σ~ ⇔ ~&germC;_2_ ⊧ σ~. So &germC;_1_ and &germC;_2_ are elementarily equivalent, and by result c) given in the question, &germC;_1_ and &germC;_2_ are isomorphic. Suppose both T_1_ and T_2_ have infinite models. By result b) there exist &germA;_1_ and &germA;_2_ which are ℵ_1_-saturated models of T_1_ and T_2_, having cardinality ℵ_1_. Let &germC;_1_ and &germC;_2_ be ρ reducts as before. Using the same argument as before &germC;_1_ and &germC;_2_ are elementarily equivalent. By result a) we conclude that &germC;_1_ and &germC;_2_ are isomorphic. In either case, &germC;_1_ and &germC;_2_ are isomorphic. Let f be an isomorphism between &germC;_1_ and &germC;_2_. Let &germA; be a ρ_1_∪ρ_2_ structure extending &germA;_1_ such that for all ρ_2_ relations R, ~R^&germA;^(a_1_, …, a_n_) = f^-1^(R^&germA;_2_^(f(a_1_), …, f(a_n_)))~. Define ρ_2_ operators in a similar way. Clearly ~&germA; models T_1_~ since it extends &germA;_1_. Let ~T_2_ ⊧ σ~ If σ is atomic, then by the definition of &germA;, &germA; ⊧ σ If ~σ = ψ_1_ C ψ_2_~ for some boolean connective C, and assuming ~&germA; ⊧ ψ_1_~ and ~&germA; ⊧ ψ_2_~, then it must be the case that ~&germA; ⊧ σ~. A similar argument holds for the ¬ connective. If ~σ = ∀xψ~ and ~&germA; ⊧ ψ~, then since the universe for &germA;_1_ are &germA;_2_ are isomorphic under f, then ~&germA; ⊧ σ~. Therefore, ~&germA; ⊧ T_2_~, so ~&germA; ⊧ T_1_∪T_2_~. <LI> Let ρ_1_ be the non-logical symbols in θ_1_, and ρ_2_ be the non-logical symbols in θ_2_. Suppose there is no φ in ρ_1_∩ρ_2_ &st; ~⊧ θ_1_ → φ~ and ~⊧ φ → θ_2_~. Therefore this is no φ &st; ~θ_1_ → φ~ and ~¬θ_2_ → ¬φ~ are logically valid. Claim: both θ_1_ and ¬θ_2_ have models. Proof: Suppose θ_1_ had no model. Let ~φ = ¬∀x(x=x)~ Then is is clear that ~⊧ θ_1_ → φ~ It is also clear that ~⊧ φ → θ_2_~ But this contradicts the assumption that there is no interpolant. Therefore θ_1_ has a model, and by a similar argument ¬θ_2_ also as a model. Claim: ~{θ_1_, ¬θ_2_}~ has a model. Proof: Let ~Δ_1,0_ = {θ_1_}~ and ~Δ_2,0_ = {¬θ_2_}~ Let {ψ_i_}_i∈ω_ be an enumeration of all ρ_1_∩ρ_2_ sentences; Let ~Δ_1,i+1_ = Δ_1,i_∪{ψ_i_}~ and ~Δ_2,i+1_ = Δ_2,i_∪{ψ_i_}~ if φ_i_ is consistent with both Δ_1,i_ and Δ_2,i_. Otherwise, let ~Δ_1,i+1_ = Δ_1,i_~ and ~Δ_2,i+1_ = Δ_2,i_~. Let ~Δ_k_ = ⋃{Δ_k,i_}~ Each finite subset of Δ_1_∩Δ_2_ is consistent, so Δ_1_∩Δ_2_ is consistent. Claim: Δ_1_∩Δ_2_ is complete. Proof: Let φ_i_ be a ρ_1_∩ρ_2_ sentence that is not in Δ_1_∩Δ_2_ Case 1: Both ~{θ_1_, φ_i_}~ and ~{¬θ_2_, φ_i_}~ are inconsistent. Then ~⊧ θ_1_ → ¬φ_i_~ and ~⊧ ¬θ_2_ → ¬φ_i_~ Let ~φ_j_ = ¬φ_i_i~ ~Δ_1,j_ ⊧ θ_1_~ and ~Δ_2,j_ ⊧ ¬θ_2_~. Therefore φ_j_ is consistent with both Δ_1,j_ and Δ_2,j_ So, ~φ_j_ = ¬φ_i_~ is in Δ_1_∩Δ_2_. Case 2: ~{θ_1_, φ_i_}~ is consistant and ~{¬θ_2_, φ_i_}~ is inconsistent. ~⊧ ¬θ_2_ → ¬φ_i_~ ~¬models; θ_1_ → φ_i_~ So there is some model of θ_1_ &germA; &st; ~&germA; ⊧ ¬φ_i_~ So ~{θ_1_, ¬φ_i_}~ and ~{θ_2_, ¬φ_i_}~ are consistent, and by Case 4, φ_i_ or ¬φ_i_ is in Δ_1_∩Δ_2_. Case 3: ~{θ_1_, φ_i_}~ is inconsistant and ~{¬θ_2_, φ_i_}~ is consistent. This is similar to case 2. Case 4: ~{θ_1_, φ_i_}~ is consistant and ~{¬θ_2_, φ_i_}~ is consistent. If Δ_1,i_∩Δ_2,i_ and φ_i_ are consistent, then φ_i_ is in Δ_1,i_∩Δ_2,i_. If Δ_1,i_∩Δ_2,i_ and φ_i_ are inconsistent, then ~Δ_1,i_∩Δ_2,i_. ⊧ ¬φ_i_~, so ¬φ_i_ is in Δ_1_∩Δ_2_. Therefore Δ_1_∩Δ_2_ is complete. Extend Δ_1_ to Σ_1_, a complete consistent set of ρ_1_ sentences. Extend Δ_2_ to Σ_2_, a complete consistent set of ρ_2_ sentences. So by Question 4, Σ_1_∪Σ_2_ has a model &germA;. So ~&germA; ⊧ θ_1_~, and ~&germB; ⊧ ¬θ_2_~. So ~θ_1_ → θ_2_~ is not logically valid. <LI> Assume there is no disjunction of the form φ(t_0_^1^,t_1_^1^)∨…∨φ(t_0_^m^,t_1_^m^) that is logically valid. Let ~ρ′ = ρ + c~ Let ~Γ = {¬φ(t_0_,t_1_) | t_0_, and t_1_ are closed ρ′ terms}~ Let F be a finite subset of Γ Let ~σ = ⋀F~ Suppose F had no model. Then ¬σ would be logically valid. But ¬σ is logically equivalent to ~σ&prime = φ(t_0_^1^,t_1_^1^)∨…∨φ(t_0_^m^,t_1_^m^)~, for some set of closed terms. Let &germA; be any ρ structure. Extend it to &germA;′ a &rho′ structure by mapping c an arbitrary element a. ~&germA;′ ⊧ σ′~, so ~&germA;&prime ⊧ σ′(c/x)[a]~. But a and &germA; were arbitrary, so σ′(c/x) is a logical validity. This contradicts our assumption. So F has a model. Since every finite subset of Γ has a model, then Γ has a model &germA; consisting of closed terms of ρ′ By the definition of Γ, for all a and b in A, ~&germA; ⊧ ¬φ[a,b]~ So ~&germA; ⊧ ∀x_0_∀x_1_¬φ~ So ~&germA; ⊧ ¬∃x_0_∃x_1_φ~ So ¬∃x_0_∃x_1_φ is not logically valid. </OL> &html.footer;

]]> A'> B'> C'> D'> %common; %HtmlDtd; ]> &html.head; OL { list-style-type: decimal } OL OL { list-style-type:lower-alpha } .model { font-family: cursive } </STYLE> &html.header; <H1/&title;/ <OL><LI> Suppose the predicate R defines a finite subset of ω. Say ~R = {a_1_, …, a_n_}~. Let ~ψ_0_ = ∀y(x<y ∨ x=y)~. ψ_0_ asserts that ~x = 0~. For ~i > 0~ let ~ψ_i_ = ∀a{ψ_(i-1)_(x/a) → [a<x ∧ ∀y¬(a<y ∧ y<x)]}~. ψ_i_ asserts that ~x = i~ by claiming it is the successor of i-1. Let ~σ(i) = ∀x(ψ_a<SUB/1/_ → x=i) ∨ … ∨ ∀x(ψ_a<SUB/n/_ → x=i)~ σ(i) explicitly defines R. Since &sigma asserts that i is one of a_1_ through a_n_. Cofinite sets are done in a similar manner, except that ~σ(i) = ¬[∀x(ψ_a<SUB/1/_ → x=i) ∨ … ∨ ∀x(ψ_a<SUB/n/_ → x=i)]~. Suppose that R defines a subset of ω that is neither finite nor cofinite. Assume that σ explicitly defines R. Therefore ~(ω, <) &models ∀x∃y(x<y &rarr (σ(x) ↔ ¬σ(y))~. Let &germB; be the discrete ordering with a subset isomorphic to &omega, and the remaining set isomorphic to one copy of the integers. Clearly ~(ω, <) ≺ &germB;~. So ~&germB &models ∀x∃y(x<y ∧ (σ(x) ↔ ¬σ(y))~ Let a∈B but a∉ω. There is a b∈B &st; ~a < b~ and ~&germB ⊧ σ[a]~ ⇔ ~&germB ¬models; σ[b]~, Clearly b∉ω Let ~c = b-a~. There is an automorphism of &germB; that maps each x∉ω to x-c. In particular b is mapped to b-c=a. Therefore ~&germB ⊧ σ[a]~ ⇔ ~&germB ⊧ σ[b]~, which is a contradiction. So R cannot be explicitly definable. <LI><OL><LI> Let ~σ_1_ = ∀x(∀y(x<y ∨ x=y) → Rx)~ Let ~σ_2_ = ∀x_1_∀x_2_{[x_1_<x_2_ &and ∀z ¬(x_1_<z ∧ z<x_2_)] → (Rx_1_ ↔ ¬Rx_2_)}~ Suppose ~(ω, <, R) ⊧ σ_1_ &and σ_2_~ ~∀y∈ω(0<y ∨ 0=y)~, so by σ_1_, ~(ω, <, R) ⊧ R0~. Suppose ~(ω, <, R) ⊧ Rk~ ⇔ k is even. Noting that ~∀z∈ω ¬(k<z ∧ z<(k+1))~, so by σ_2_, ~(ω, <, R) &models Rk~ ⇔ ~(ω, <, R) ⊧ ¬R(k+1)~. So ~(ω, <, R) &models R(k+1)~ ⇔ ~(ω, <, R) ¬models Rk~ ⇔ k is odd ⇔ k+1 is even. So by induction ~∀n∈ω (ω, <, R) ⊧ Rn~ ⇔ n is even. Now suppose Q is a predicate such that Qn ⇔ n is even. The only n in &omega &st; ~∀y(n<y &or n=y)~ is 0. So ~(ω, <, Q) ⊧ σ_1_~. Suppose n and m are such that ~[n<m ∧ ∀z ¬(n<z ∧ z<m)]~. Clearly ~m = n+1~. Since ~(ω, <, Q) &models Qn~ ⇔ ~(ω, <, Q) &models ¬Q(n+1)~, then ~(ω, <, Q) &models σ_2_~. So ~(ω, <, Q) &models σ_1_ ∧ σ_2_~. So finally we conclude ~(ω, <, R) &models σ_1_ ∧ σ_2_~ ⇔ R=Q. So even numbers are implicitly definable. The set of even numbers is neither finite nor cofinite. So by Question 1, even numbers are not explicitly definable. <LI> Let ~φ_1_ = ∀a(a+z=a)~ Let ~φ_2_ = ∀a∀z((φ_1_ ∧ ¬z=a) → [¬z=e ∧ ∃y(y+e)=a])~ Let ~σ_1_ = ∀z∀y(φ_1_ → R(z,y,z))~ Let ~σ_2_ = ∀e∀a∀b((φ_2_ &and a+e=b) → ∀w∀x∀y[R(b,w,x) ↔ (R(a,w,y) ∧ y+w=x)])~ Claim: ~(ω, +, R) ⊧ σ_1_ ∧ σ_2_~ ⇔ R is the ⋅ relation. (ie, R(m,n,k) ⇔ m⋅n=k). Proof: φ_1_ asserts that z is 0 by saying a is the additive identity. φ_2_ asserts that e is 1 by saying that e is not 0 and for all non-zero numbers a there is a y such that y+e=z. σ_1_ asserts that for all y, R(0,y,0). This is clearly true of the ⋅ relation. σ_2_ asserts that for all a, w and x, R(c+1,w,x) ⇔ R(c,y,x-y). This is true of the ⋅ relation. Furthermore σ_1_ and σ_2_ are exactly the relations that define multiplication, therefore multiplication is implicitly definable. </OL> <LI> Let ~X ⊆ A~ and have cardinality ~< κ~, and Σ a complete 1-type for Th &germA;_X_. So there is a &germB; modeling ~Th &germA;_X_~ and b∈B &st; ~Σ = {φ | φ is 1-ary and &germB; ⊧ φ[b]}~. Let ~X_1_ = {x∈X | x <^&germB;^ b}~, and ~X_2_ = {x∈X | b <^&germB;^ x}~. Since X_1_ and X_2_ both have cardinality ~< κ~, then by the properties that &germA; are given in the question, there is an a∈A such that X<a<Y (or X_1_<a if X_2_ is empty, or a<X_2_ if X_1_ is empty). Let φ∈Σ ~&germB; ⊧ φ[b]~. Since the theory of dense linear orderings admits elimination of quantifiers, there is some quantifier free formula ψ &st; ~T ⊧ φ ↔ ψi~ ~&germB; &models ψ[b]~ For any constant &underlineC;, we have ~b < &underlineC;~ ⇔ ~a < &underlineC;~, and ~&underlineC; < b~ ⇔ ~&underlineC; < a~. Since ψ is a boolean combination of these relations, then ~&germA;_X_ &models ψ[a]~ So, ~&germA;_X_ &models φ[a]~, since &germA; is also models T. So, Σ is realized in &germA;_X_, and we conclude that Σ is κ-saturated. <LI> Let T_1_ or T_2_ have no infinite models. &Wlog; assume that T_1_ has no infinite model. Let &germA;_1_ and &germA;_2_ be models of T_1_ and T_2_ respectively. A_1_ is finite. Let &germC;_1_ and &germC;_2_ be ρ reducts of &germA;_1_ and &germA;_2_. Let σ be a ρ sentence. ~&germC;_1_ ⊧ σ~ ⇔ ~T_1_ ⊧ σ~ ⇔ ~T_2_ ⊧ σ~ ⇔ ~&germC;_2_ ⊧ σ~. So &germC;_1_ and &germC;_2_ are elementarily equivalent, and by result c) given in the question, &germC;_1_ and &germC;_2_ are isomorphic. Suppose both T_1_ and T_2_ have infinite models. By result b) there exist &germA;_1_ and &germA;_2_ which are ℵ_1_-saturated models of T_1_ and T_2_, having cardinality ℵ_1_. Let &germC;_1_ and &germC;_2_ be ρ reducts as before. Using the same argument as before &germC;_1_ and &germC;_2_ are elementarily equivalent. By result a) we conclude that &germC;_1_ and &germC;_2_ are isomorphic. In either case, &germC;_1_ and &germC;_2_ are isomorphic. Let f be an isomorphism between &germC;_1_ and &germC;_2_. Let &germA; be a ρ_1_∪ρ_2_ structure extending &germA;_1_ such that for all ρ_2_ relations R, ~R^&germA;^(a_1_, …, a_n_) = f^-1^(R^&germA;_2_^(f(a_1_), …, f(a_n_)))~. Define ρ_2_ operators in a similar way. Clearly ~&germA; models T_1_~ since it extends &germA;_1_. Let ~T_2_ ⊧ σ~ If σ is atomic, then by the definition of &germA;, &germA; ⊧ σ If ~σ = ψ_1_ C ψ_2_~ for some boolean connective C, and assuming ~&germA; ⊧ ψ_1_~ and ~&germA; ⊧ ψ_2_~, then it must be the case that ~&germA; ⊧ σ~. A similar argument holds for the ¬ connective. If ~σ = ∀xψ~ and ~&germA; ⊧ ψ~, then since the universe for &germA;_1_ are &germA;_2_ are isomorphic under f, then ~&germA; ⊧ σ~. Therefore, ~&germA; ⊧ T_2_~, so ~&germA; ⊧ T_1_∪T_2_~. <LI> Let ρ_1_ be the non-logical symbols in θ_1_, and ρ_2_ be the non-logical symbols in θ_2_. Suppose there is no φ in ρ_1_∩ρ_2_ &st; ~⊧ θ_1_ → φ~ and ~⊧ φ → θ_2_~. Therefore this is no φ &st; ~θ_1_ → φ~ and ~¬θ_2_ → ¬φ~ are logically valid. Claim: both θ_1_ and ¬θ_2_ have models. Proof: Suppose θ_1_ had no model. Let ~φ = ¬∀x(x=x)~ Then is is clear that ~⊧ θ_1_ → φ~ It is also clear that ~⊧ φ → θ_2_~ But this contradicts the assumption that there is no interpolant. Therefore θ_1_ has a model, and by a similar argument ¬θ_2_ also as a model. Claim: ~{θ_1_, ¬θ_2_}~ has a model. Proof: Let ~Δ_1,0_ = {θ_1_}~ and ~Δ_2,0_ = {¬θ_2_}~ Let {ψ_i_}_i∈ω_ be an enumeration of all ρ_1_∩ρ_2_ sentences; Let ~Δ_1,i+1_ = Δ_1,i_∪{ψ_i_}~ and ~Δ_2,i+1_ = Δ_2,i_∪{ψ_i_}~ if φ_i_ is consistent with both Δ_1,i_ and Δ_2,i_. Otherwise, let ~Δ_1,i+1_ = Δ_1,i_~ and ~Δ_2,i+1_ = Δ_2,i_~. Let ~Δ_k_ = ⋃{Δ_k,i_}~ Each finite subset of Δ_1_∩Δ_2_ is consistent, so Δ_1_∩Δ_2_ is consistent. Claim: Δ_1_∩Δ_2_ is complete. Proof: Let φ_i_ be a ρ_1_∩ρ_2_ sentence that is not in Δ_1_∩Δ_2_ Case 1: Both ~{θ_1_, φ_i_}~ and ~{¬θ_2_, φ_i_}~ are inconsistent. Then ~⊧ θ_1_ → ¬φ_i_~ and ~⊧ ¬θ_2_ → ¬φ_i_~ Let ~φ_j_ = ¬φ_i_i~ ~Δ_1,j_ ⊧ θ_1_~ and ~Δ_2,j_ ⊧ ¬θ_2_~. Therefore φ_j_ is consistent with both Δ_1,j_ and Δ_2,j_ So, ~φ_j_ = ¬φ_i_~ is in Δ_1_∩Δ_2_. Case 2: ~{θ_1_, φ_i_}~ is consistant and ~{¬θ_2_, φ_i_}~ is inconsistent. ~⊧ ¬θ_2_ → ¬φ_i_~ ~¬models; θ_1_ → φ_i_~ So there is some model of θ_1_ &germA; &st; ~&germA; ⊧ ¬φ_i_~ So ~{θ_1_, ¬φ_i_}~ and ~{θ_2_, ¬φ_i_}~ are consistent, and by Case 4, φ_i_ or ¬φ_i_ is in Δ_1_∩Δ_2_. Case 3: ~{θ_1_, φ_i_}~ is inconsistant and ~{¬θ_2_, φ_i_}~ is consistent. This is similar to case 2. Case 4: ~{θ_1_, φ_i_}~ is consistant and ~{¬θ_2_, φ_i_}~ is consistent. If Δ_1,i_∩Δ_2,i_ and φ_i_ are consistent, then φ_i_ is in Δ_1,i_∩Δ_2,i_. If Δ_1,i_∩Δ_2,i_ and φ_i_ are inconsistent, then ~Δ_1,i_∩Δ_2,i_. ⊧ ¬φ_i_~, so ¬φ_i_ is in Δ_1_∩Δ_2_. Therefore Δ_1_∩Δ_2_ is complete. Extend Δ_1_ to Σ_1_, a complete consistent set of ρ_1_ sentences. Extend Δ_2_ to Σ_2_, a complete consistent set of ρ_2_ sentences. So by Question 4, Σ_1_∪Σ_2_ has a model &germA;. So ~&germA; ⊧ θ_1_~, and ~&germB; ⊧ ¬θ_2_~. So ~θ_1_ → θ_2_~ is not logically valid. <LI> Assume there is no disjunction of the form φ(t_0_^1^,t_1_^1^)∨…∨φ(t_0_^m^,t_1_^m^) that is logically valid. Let ~ρ′ = ρ + c~ Let ~Γ = {¬φ(t_0_,t_1_) | t_0_, and t_1_ are closed ρ′ terms}~ Let F be a finite subset of Γ Let ~σ = ⋀F~ Suppose F had no model. Then ¬σ would be logically valid. But ¬σ is logically equivalent to ~σ&prime = φ(t_0_^1^,t_1_^1^)∨…∨φ(t_0_^m^,t_1_^m^)~, for some set of closed terms. Let &germA; be any ρ structure. Extend it to &germA;′ a &rho′ structure by mapping c an arbitrary element a. ~&germA;′ ⊧ σ′~, so ~&germA;&prime ⊧ σ′(c/x)[a]~. But a and &germA; were arbitrary, so σ′(c/x) is a logical validity. This contradicts our assumption. So F has a model. Since every finite subset of Γ has a model, then Γ has a model &germA; consisting of closed terms of ρ′ By the definition of Γ, for all a and b in A, ~&germA; ⊧ ¬φ[a,b]~ So ~&germA; ⊧ ∀x_0_∀x_1_¬φ~ So ~&germA; ⊧ ¬∃x_0_∃x_1_φ~ So ¬∃x_0_∃x_1_φ is not logically valid. </OL> &html.footer;