PMATH 330 Assignment IX due Nov 25th This document will get longer after each lecture! Answer each problem with justification, except where indicated. That means writing actual sentences. 1. Let L = {+, 0}, where + is a binary function symbol, and 0 is a constant symbol. Let T be the theory consisting of the following formulas: x1 x2 (x1 + x2 x2 + x1 ) x1 x2 x3 ((x1 + x2 ) + x3 ) x1 + (x2 + x3 )) x1 (x1 + 0 x1 ) x1 x2 x3 (x1 + x2 x1 + x3 x2 x3 ) addition is commutative addition is associative 0 is the identity element of addition addition has a cancellation law (a) Let N be the model with domain N and the usual + and 0. Does N |= T ? (b) Show that T |= x1 x2 (x2 + x1 x1 x2 0) (c) Show T is not complete, by finding a sentence such that T 6|= and T 6|= . 2. Let T be a theory such that all models of T are isomorphic to each other. Show that T is complete. 3. Let L consist of a binary relation symbol <. Let T be the theory consisting of the following sentences: x1 (x1 < x1 ) x1 x2 x3 ((x1 < x2 x2 < x3 ) x1 < x3 ) x1 x2 (x1 < x2 x2 < x1 x1 x2 ) x1 x2 (x1 < x2 x3 ((x1 < x3 x3 < x2 ))) x1 x2 (x2 < x1 x3 ((x2 < x3 x3 < x1 ))) Informally, these axioms say that < gives a strict linear order in which for each element a, there is a greatest element less than a and a least element greater than a (this is usually called a discrete linear order). Show that there are (at least) two nonisomorphic models of T (it's probably easiest to use our idea from class of trying to add a \"new\" element to one model to get another nonisomorphic model). 4. Let L consist of a binary relation symbol E. Let T be the theory consisting of the 1 following sentences: x1 (E(x1 , x1 )) x1 (E(x1 , x2 ) E(x2 , x1 )) x1 x2 x3 x4 (x2 x3 x2 x4 x3 x4 E(x1 , x2 ) E(x1 , x3 ) E(x1 , x4 )) x1 x2 x3 x4 x5 ((E(x1 , x2 ) E(x1 , x3 ) E(x1 , x4 ) E(x1 , x5 )) x2 x3 x2 x4 x2 x5 x3 x4 x 3 x5 x4 x5 ) Informally, these axioms say that the relation E describes the edges of a graph in which each vertex has an edge to exactly three other vertices (the third sentence says there are at least three, and the fourth says that there are at most three). (a) If G is a model of T , a cycle of length n 3 in G is a set a1 , a2 , a3 , . . . , an of distinct elements in the domain of G such that for 1 i < n, (ai , ai+1 ) E G , and (an , a1 ) E G . 1 For each n 3, give a sentence n which says that a structure has no cycles of length n. (b) Let T 0 = T {n | n 3}. Informally, a model of T 0 is just a model of T in which there are no cycles of any length. Show that T is not complete, by giving a model G1 of T which is not a model of T 0 , and a model G2 of T 0 . You can just sketch the structures as graphs, rather than specifying everything formally. HINT: to build G2 , start with a single vertex, and then add vertices and edges to meet the axioms of T but avoid adding any cycles. 5. Let L be a finite language. Show that the set of all L-formulas is countable. HINT: You may assume that if A1 , A2 , A3 , is a countable family of sets, each of which is countable or finite, then their union A1 A2 A3 is also countable or finite. 2 FURTHER HINT: I gave a very rough outline of a very similar fact a month or so ago, when I said we could form a list 0 , 1 , 2 , . . . of all formulas of propositional logic (so those are countable, too). The general idea is to split the set of all formulas up into countably many sets, each of which is finite, and then apply the first hint. FINAL HINT: How many L-formulas are there which have length n and which use only the variables x1 , . . . , xn ? 1 A cycle of length 3 looks like a triangle, a cycle of length 4 looks like a square, and so on. . . The proof of this is similar to the fact that N2 is countable. First, order each of the sets as a sequence. Then arrange the sequences in columns. Then put the columns side-by-side, and you get a grid that looks like N2 , so the same diagonal-traversing trick we used in that case can be used again. There are subtleties that this sketch avoids mentioning, though: what do you do if the sets overlap, or if some are finite? 2 2 COMMENT: This also works if the language is countable, but you have to split the formulas up more aggressively. 6. Suppose L is a language containing uncountably many constant symbols. Show there are uncountably many L-formulas. HINT: if you show that there is a bijection from the set of constant symbols to some subset of the formulas, then it follows that that subset is uncountable, and therefore so is the set of all formulas so it is sufficient to show that we can get a different formula for each constant. COMMENT: In fact, if L has infinitely many symbols then the cardinality of the set of all L-formulas is actually equal to the cardinality of the language L. Combining this with the comment from the previous question, we see that if F is the set of all L-formulas, then |F| = max(|F|, |N|). This will be mentioned later, when we discuss the completeness theorem for first order logic. Probably on Monday? 3