Andreas van Cranenburgh, 0440949 Basic Logic, final exam Sat Dec 12 14:15:09 CET 2009 I worked alone. Exercise 1 We have a derivation of P(s) <-> P(t) from Delta, for an arbitrary P, not occurring in Delta or in an open assumption. Since P is arbitrary, we can consider the case where the interpretation of P is the most specific and discriminating one possible: when it is only true for a single object, say the object referred to by s. In this case P(t') is equivalent to saying s=t'. With this in mind, we obtain a new derivation by replacing every occurence of P(t') by s=t', and we can proceed with the following steps: m. s=s -> s=t ^ s=t -> s=s m+1. s=s -> s=t E^m m+2. s=s I= m+3. s=t E-> m+1, m+2 Exercise 2 i) ∃y Rxy This formula determines {1, 4} because 1 and 4 are the only two assignments for x that make the formula hold in the given interpretation. ii) The set {2} cannot be determined because the relation R is completely symmetric with respect to the objects 2 and 3, so any formula that determines 2 will also determine 3, and vice versa. Theorem: a set A can be determined by a two-place predicate if A is the set of nth-arguments for which R holds, or the union or intersection of two such sets. Proof: If A is the set of first arguments for which R holds, then A contains all elements d in D such that M|= ∃y Rxy v(x/d), which is {1,4}. Likewise for second arguments for which R holds, there is the formula ∃y Ryx, which determines {2,3} . With these two as base cases, we can inductively determine some other sets: - ∃y Rxy ^ ∃y Ryx determines the intersection of {1,4} and {2,3}, which is the empty set. - ∃y Rxy v ∃y Ryx determines the union of {1,4} and {2,3}, which is the whole domain. iii) The following subsets are determined by some formula: The empty set {}: Rxx {1, 4}: ∃y Rxy {2, 3}: ∃y Ryx {1,2,3,4}: ∃y Rxy v ∃y Ryx Exercise 3 i) Suppose M is an elementary submodel of M', this means M |= φ [v] iff M' |= φ [v] for every formula φ, so also for all φ of the form P(t_1, ..., t_n) M |= P(t_1, ..., t_n) [v] <=> <[t_1]vM, ..., [t_n]vM> in I(P) M' |= P(t_1, ..., t_n) [v] <=> <[t_1]vM', ..., [t_n]vM'> in I'(P) So also: <[t_1]vM, ..., [t_n]vM> in I(P) <=> <[t_1]vM', ..., [t_n]vM'> in I'(P) Since this holds for any series of terms t_1...t_n, it holds when t_i is a free variable, which implies that it holds for any d in D, which is condition iii) of the definition of submodel. It also holds when t_i is any individual constant, so it must also be the case that I(a) = I'(a) for any individual constant a. ii) Counterexample: M' = , with the single two-place predicate R. D' = {1,2,3,4} I'(R) = { <1, 2>, <1, 3>, <4, 2>, <4, 3> } Now we construct a submodel of M': M = D = {1, 2} I(R) = {<1,2>} Condition i) is satisfied because {1,2} is a subset of {1,2,3,4}. Condition ii) is satisfied because we have no individual constants. Condition iii) is satisfied because <1,2> is in I'(R), and that is the only tuple in I(R) with only elements from D. But it is not an elementary submodel, because there is a sentence that holds for M but not for M': ∃x ∃y (Rxy ^ ~∃z (Rxz ^ y =/= z)) In M this sentence is true. When x is gets the value 1, R only holds for <1,2>. In M' it is false, because R holds for <1,2> and <1,3>. iii) => Suppose M is an elementary submodel of M', this means M |= φ [v] iff M' |= φ [v] Since this holds for all formulas φ, it also holds for formulas of the form: ∃x psi Now if M' |= ∃x psi [v], then also M |= ∃x psi [v]. By applying the semantic definiton of the existential quantifier, we know that M |= psi [v(x/d)] for some d in D. But D is a subset of D', so d is also in D'. Hence also M' |= psi [v(x/d)]. QED. <= Suppose condition b) holds: For any formula ∃x φ such that M' |= ∃x φ [v], there is some d in D such that M' |= φ [v(x/d)] If this holds, then We can prove the following by induction on the complexity of φ: Claim: for any formula φ, M |= φ [v] iff M' |= φ [v], for an arbitrary [v] Base case: Since M is a submodel of M', every atomic formula holds in M iff it holds in M', by condition a) iii) of submodels. Induction step: Induction hypothesis: chi and theta are equivalent in M and M'. - ~chi By the induction hypothesis M |= chi [v] iff M' |= chi [v] Taking the converse of this: M |/= chi [v] iff M' |/= chi [v] This is the same as the definition of negation: M |= ~chi [v] iff M' |= ~chi [v] - chi v theta By the induction hypothesis M |= chi [v] iff M' |= chi [v] and M |= theta [v] iff M' |= theta [v] Then it is easy to see that also M |= chi v theta [v] iff M' |= chi v theta [v] - ∃x chi By the induction hypothesis M |= chi [v] iff M' |= chi [v] Suppose that M |= ∃x chi [v]. Let d in D be such that M |= chi [v(x/d)]. By the induction hypothesis, M' |= chi [v(x/d)] (because v is arbitrary, and D is a subset of D' so d is in D'), and thus also M' |= ∃x chi [v]. On the other hand, suppose that M' |= ∃x chi [v]. Then by condition b) it holds that there is a d in D such that M' |= chi [v(x/d)]. By the induction hypothesis it follows that M |= chi [v(x/d)]. Then by the semantic definition it follows that M |= ∃x chi [v]. The cases of conjunction, implication and the universal quantifier are left out, because formulas containing them can be rewritten to follow these cases. iv) By adding a fourth condition to the definition of submodel: iv) for all n-ary functions f: I(f)(t_1,...,t_n) = I'(f)(t_1,...,t_n), if [t_i]vM in D for 1<=i<=n, for any v assigning the variables onto D. In words: for every function f in M' there is a function in the submodel M that is the restriction of f to the domain D. Exercise 4 i) We extend the definition of an assignment to include predicate variables: For each predicate variable in L, v assigns a finite subset of D. v(P/Q) is defined as follows: v(X/Y)(Z) = v(Z) if Z =/= X v(Y) if Z = X We retain all the first-order definitions, and add the following cases dealing with predicate variables: M |= Xt [v] iff [t]M,v is in v(X) M |= ∀X φ [v] iff for every finite subset Y of D, we have M |= φ [v(X/Y)] M |= ∃X φ [v] iff for some finite subset Y of D, we have M |= φ [v(X/Y)] ii) The following formula characterizes an infinite domain: ∀F ∃G [ ∀x (Fx -> Gx) ^ ∃x ( ~Fx ^ Gx) ] This formula can be read as: for any predicate F, there is a predicate G which is true of a superset of objects of which F is true. So for any subset described by F, there must be a larger one G. Using straightforward induction (similar to the proof that there are infinitely many natural numbers) it can be seen that the domain must contain an infinity of objects: For any finite number of objects, let F hold for that many objects. Then G must hold for a higher number. Or perhaps a more simple formula: ~∃G ∀x Gx There is no finite subset which contains all elements of the domain. iii) We can call the previous sentence φ_infinity, and construct sentences φ_n meaning there are at least n objects, in the following way: φ_2 = ∃x1 ∃x2: x1 =/= x2 φ_3 = ∃x1 ∃x2 ∃x3: x1 =/= x2 ^ x1 =/= x3 ^ x2 =/= x3 ... Now we construct an infinite set A: A = { ~φ_infinite, φ_1, φ_2, φ_3, ...} From this set we can take an arbitrary finite subset, and it will have a model. To see this observe that there will always be a highest n such that φ_n is in the subset, which allows the construction of a model with n elements. Because of this the model will not be infinite, and ~φ_infinite will be satisfied as well. If compactness would hold, the previous observation would entail that the whole set has a model. Howevere, this cannot be the case, since the set will contain a φ-sentence for every natural number, so it is infinite, which contradicts the first sentence specifying that the model is not infinite. Hence, we have a contradiction, and we must reject the assumption that compactness would hold for second-order logic.