Suppose the predicate R defines a finite subset of ω. Say R = {a1, …, an}.
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(ψa1 → x=i) ∨ … ∨ ∀x(ψan → x=i)
σ(i) explicitly defines R. Since σ asserts that i is one of
a1 through an.
Cofinite sets are done in a similar manner, except that σ(i) = ¬[∀x(ψa1 → x=i) ∨ … ∨ ∀x(ψan → x=i)].
Suppose that R defines a subset of ω that is neither finite nor
cofinite. Assume that σ explicitly defines R.
Therefore (ω, <) ⊧ ∀x∃y(x<y → (σ(x) ↔ ¬σ(y)).
Let B be the discrete ordering with a subset isomorphic to ω,
and the remaining set isomorphic to one copy of the integers. Clearly
(ω, <) ≺ B.
So B ⊧ ∀x∃y(x<y ∧ (σ(x) ↔ ¬σ(y))
Let a∈B but a∉ω. There is a b∈B such that a < b and
B ⊧ σ[a] if and only if B ⊭ σ[b], Clearly
b∉ω
Let c = b-a. There is an automorphism of B that maps each
x∉ω to x-c. In particular b is mapped to b-c=a.
Therefore B ⊧ σ[a] if and only if B ⊧ σ[b],
which is a contradiction.
So R cannot be explicitly definable.
Let σ1 = ∀x(∀y(x<y ∨ x=y) → Rx)
Let σ2 = ∀x1∀x2{[x1<x2 ∧ ∀z ¬(x1<z ∧ z<x2)] → (Rx1 ↔ ¬Rx2)}
Suppose (ω, <, R) ⊧ σ1 ∧ σ2
∀y∈ω(0<y ∨ 0=y), so by σ1, (ω, <, R) ⊧ R0.
Suppose (ω, <, R) ⊧ Rk if and only if k is even.
Noting that ∀z∈ω ¬(k<z ∧ z<(k+1)), so
by σ2, (ω, <, R) ⊧ Rk if and only if (ω, <, R) ⊧ ¬R(k+1).
So (ω, <, R) ⊧ R(k+1) if and only if (ω, <, R) ⊭ Rk if and only if k is odd if and only if k+1 is even.
So by induction ∀n∈ω (ω, <, R) ⊧ Rn
if and only if n is even.
Now suppose Q is a predicate such that Qn if and only if n is even.
The only n in ω such that ∀y(n<y ∨ 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) ⊧ Qn if and only if (ω, <, Q) ⊧ ¬Q(n+1), then
(ω, <, Q) ⊧ σ2.
So (ω, <, Q) ⊧ σ1 ∧ σ2.
So finally we conclude (ω, <, R) ⊧ σ1 ∧ σ2 if and only if 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.
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 ∧ a+e=b) → ∀w∀x∀y[R(b,w,x) ↔ (R(a,w,y) ∧ y+w=x)])
Claim: (ω, +, R) ⊧ σ1 ∧ σ2 if and only if R is
the ⋅ relation. (ie, R(m,n,k) if and only if 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) if and only if
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.
Let X ⊆ A and have cardinality < κ, and Σ a
complete 1-type for
Th AX.
So there is a B modeling Th AX and b∈B
such that Σ = {φ | φ is 1-ary and B ⊧ φ[b]}.
Let X1 = {x∈X | x <B b}, and
X2 = {x∈X | b <B x}.
Since X1 and X2 both have cardinality < κ, then by the
properties that A are given in the question, there is an a∈A
such that X<a<Y (or X1<a if X2 is empty, or a<X2 if X1
is empty).
Let φ∈Σ
B ⊧ φ[b].
Since the theory of dense linear orderings admits elimination of
quantifiers, there is some quantifier free formula ψ such that T ⊧ φ ↔ ψi
B ⊧ ψ[b]
For any constant c, we have b < c if and only if a < c, and c <
b
if and only if c < a. Since ψ is a boolean combination of these relations,
then AX ⊧ ψ[a]
So, AX ⊧ φ[a], since A is also models T.
So, Σ is realized in AX, and we conclude that Σ is
κ-saturated.
Let T1 or T2 have no infinite models. Without loss of generality assume that T1 has
no infinite model.
Let A1 and A2 be models of T1 and T2 respectively.
A1 is finite.
Let C1 and C2 be ρ reducts of A1 and
A2.
Let σ be a ρ sentence.
C1 ⊧ σ if and only if T1 ⊧ σ if and only if
T2 ⊧ σ if and only if C2 ⊧ σ.
So C1 and C2 are elementarily equivalent, and by result c)
given in the question, C1 and C2 are isomorphic.
Suppose both T1 and T2 have infinite models.
By result b) there exist A1 and A2 which are
ℵ1-saturated models of T1 and T2, having cardinality
ℵ1.
Let C1 and C2 be ρ reducts as before.
Using the same argument as before C1 and C2 are
elementarily equivalent.
By result a) we conclude that C1 and C2 are isomorphic.
In either case, C1 and C2 are isomorphic.
Let f be an isomorphism between C1 and C2.
Let A be a ρ1∪ρ2 structure extending A1
such that for all ρ2 relations R,
RA(a1, …, an) = f-1(RA2(f(a1), …, f(an))).
Define ρ2 operators in a similar way.
Clearly A models T1 since it extends A1.
Let T2 ⊧ σ
If σ is atomic, then by the definition of A, A
⊧ σ
If σ = ψ1 C ψ2 for some boolean connective C, and
assuming A ⊧ ψ1 and A ⊧ ψ2, then it
must be the case that A ⊧ σ. A similar argument holds
for the ¬ connective.
If σ = ∀xψ and A ⊧ ψ, then since the universe for A1
are A2 are isomorphic under f, then A ⊧ σ.
Therefore, A ⊧ T2, so A ⊧ T1∪T2.
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 such that
⊧ θ1 → φ and ⊧ φ → θ2.
Therefore this is no φ such that θ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 = ¬φii
Δ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
⊭ θ1 → φi
So there is some model of θ1 A such that
A ⊧ ¬φ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 A.
So A ⊧ θ1, and B ⊧ ¬θ2.
So θ1 → θ2 is not logically valid.
Assume there is no disjunction of the form
φ(t01,t11)∨…∨φ(t0m,t1m) that is
logically valid.
Let ρ′ = ρ + c
Let Γ = {¬φ(t0,t1) | t0, and t1 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
σ′ = φ(t01,t11)∨…∨φ(t0m,t1m), for some set
of closed terms.
Let A be any ρ structure. Extend it to A′ a
ρ′ structure by mapping c an arbitrary element a.
A′ ⊧ σ′, so
A′ ⊧ σ′(c/x)[a].
But a and A 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 A consisting of closed terms of ρ′
By the definition of Γ, for all a and b in A,
A ⊧ ¬φ[a,b]
So A ⊧ ∀x0∀x1¬φ
So A ⊧ ¬∃x0∃x1φ
So ¬∃x0∃x1φ is not logically valid.