《Three-old-pieces.pdf》由会员分享，可在线阅读，更多相关《Three-old-pieces.pdf（8页珍藏版）》请在三一文库上搜索。
1、Three old pieces Kees Doets May 31, 1999 Abstract This contribution consists of three pieces that are independent of each other. The fi rst one recalls an expedition into Swedish Lapland undertaken by Johan and myself 25 year ago and is mainly picturesque, the second one is a remark to Johans 1972 M
2、asters Thesis centering around a new equivalent of the Prime Ideal Theorem, and the fi nal one is a short proof of the Boundedness Theorem that is fundamental for the paper of Johan and Jon Barwise on pebble games. Contents 12 22 35 1 1 At the time when Johan was exactly half the age he is now, we d
3、eparted for the North in order to make an extended hike in Lapland. The undertaking must have been less agreeable to Johan for several reasons. Scientifi cally, he cannot have found much inspiration with me during the many hours that we shared company in our cramped bivouac: it was in this period th
4、at he was laying the foundations for what now is well-known as modal correspondence theory, and modal logic wasnt exactly my favorite subject.However, a far greater problem was looming over our expedition. Only one week earlier, Johan had fallen deeply and irrevocably for the charms of a girl by the
5、 name of Lida, and, instead of looking forward to romantic hours in sunny Amsterdam, he had to face sub-arctic swarms of ruthless mosquitoes. We left early august for the 3000 kms drive taking us beyond the Polar Circle. In Malm o we purchased the lightest tent possible, not withstanding the fact th
6、at it by necessity also was the smallest one. In H arn osand, Johan had to visit a dentist for the fi rst time. Far north in Vietas, we changed from car to backpack in a nasty drizzle. That night, a few hours prior to our take-off , we witnessed on tv Nixons fall from presidency. At the end of our s
7、econd days hike into vacuum lapponia, it turned out that H arn osands dentistry wasnt as unfallible as wed hoped for. We walked back to civilisation, Johan in pains all the way. This time, a Malmberget dentist took care of Johan, sending him away equipped with both a new fi lling in his tooth and a
8、do-it-yourself emergency kit in his pack. There remained suffi ciently many days for a somewhat smaller venture through the heart of Sarek, which was completed without further problems. In particular, I was thankful I never had to melt the do-it-yourself kit into Johans molar. Some late august eveni
9、ng, I delivered Johan, at the Weteringplantsoen, to the arms of Lida. 2 Exactly two years prior to the events related above, Johan fi nished a Masters Thesis Ben72 on weakenings of the Axiom of Choice, to which the following is a footnote. Call a set S a selector for a collection A of sets if every
10、intersection a S (where a A) is a singleton. The following is one of the standard applications of Compactness. On Selectors. Suppose that every fi nite subcollection of a certain collection of fi nite sets has a selector. Then the collection itself has a selector as well. This is generalized in Ben7
11、2 to the following (Johans) Proposition, in which the target-class of singleton-subsets of the previous proposition can be just any class K of subsets: 2 JP. Suppose that A is a collection of fi nite sets and K S aA(a) is such that ? for every fi nite B A there exists S S B such that a B(aS K). Then
12、 S S A exists such that a A(a S K). Johan proves JP using the Tychonov Theorem for T2-spaces and shows that it implies the Boolean Prime Ideal Theorem, settling JP as an equivalent of the latter. Looking for illustrations of the use of clauses in a text on resolution (where clauses are all-important
13、), it occurred to me that JP allows a proof that is amusing in its simplicity. Recall that a (propositional) clause is a fi nite set of literals (propositional variables and their negations) mimicking the disjunction of its elements. Thus, a clause is satisfi ed by a truth assignment if at least one
14、 of its elements takes the value true. Proof of JP. Consider the elements of S A as propositional variables. is the set of all clauses of the form (ab)b where a A, b a, and b 6 K (I use the notation b = x | x b, where x denotes the negation of a variable x). Any truth assignment : S A true,false is
15、associated with a set S= x S A | (x) = true. JP is now (almost) immediate from Clausal Compactness (a set of clauses is satisfi able whenever everyone of its fi nite subsets is) and the following Claim. satisfi es iff a A(a S K). The proof of this is straightforward but omitted, since a similar clai
16、m follows below.? Refl ecting on this proof, the following modifi cation eventually presented itself. First, note that, instead of requiring ? for arbitrary fi nite B A, it suffi ces to require this only for subcollections a A | a Y where Y S A is fi nite, since these subcollections are “dense” amon
17、g the fi nite ones: every fi nite B A is contained in the collection a A | a S B of this form. This explains the somewhat diff erent wording of the following, where collections of fi nite sets appear to have vanished. JP+. Suppose that X is a set and L is a collection of pairs (Y,S) where Y X is fi
18、nite and S Y that satisfi es if (Y,S) L and Y 0 Y , then (Y 0,S Y0) L. If for every fi nite Y X there exists S Y with (Y,S) L, then S X exists such that for every fi nite Y X, (Y,S Y ) L. This is reminiscent of the fact that a structure can be expanded into a model of a universal fi rst-order theory
19、 whenever all its fi nite substrucures can be so expanded cf. Doe71. The versatility of JP+(much greater than that of either JP or the former model-theoretic principle) is witnessed by the following examples. In 14 and 8, the objects to be constructed are plain sets; however, in 5 it is a relation a
20、nd in 6 a sequence of sets: note how this circumstance aff ects the choice of X in each case. 3 1. JP+immediately implies JP. As indicated above, put X = S A and let (Y,S) L iff a A(a Y a S K). 2. Also, the Boolean Prime Ideal Theorem is a straightforward consequence of JP+ . (X is the boolean algeb
21、ra; (Y,S) L iff S Y 0 is a prime ideal for every subalgebra Y 0 included in Y .) 3. By coincidence, JP+also easily implies another equivalent of the Boolean Prime Ideal Theorem considered by Johan: the fact that an inverse limit of a system of non-empty fi nite sets is non-empty. To see this, let A
22、be the system of non-empty fi nite sets, put X = S A, and let (Y,S) L iff S is a selector for a A | a Y that respects the morphisms of the system. 4. JP+implies K onigs Lemma, also discussed in Ben72. For, suppose given an infi nite, fi nitely-splitting tree. For an integer n, let Tn be the (fi nite
23、) set of nodes of height n, let X = S nTn be the set of nodes of the tree, and let (Y,S) L iff S is a selector of Tn| Tn Y that consists of pairwise comparable nodes. 5. JP+readily implies the Order Extension Principle: every partial ordering can be extended to a linear one.If P is the partially ord
24、ered set, let X = P2 , and let (Y,S) L iff S is a linear ordering of Dom(Y ) = x P | y(x,y) Y (y,x) Y ) that extends the given partial ordering on Dom(Y ). 6. JP+also implies another classic in this area: the fact that a graph G is k-colorable whenever everyone of its fi nite subgraphs is.This time,
25、 put X = (x,i) | x G 1 6 i 6 k; let (Y,S) L iff the k sets Ci= x G | (x,i) S (i = 1,.,k) form a coloring of the subgraph x G | i(x,i) Y . 7. The following problem comes from Mil95 (a text that introduces mathe- matical logic using the “Moore-method”, via exercises that one often wont fi nd elsewhere
26、); the reader may like to answer it using JP+: “Given a set of students and a set of classes, suppose each student wants one of a fi nite set of classes, and each class has a fi nite enrollment limit. Show that if each fi nite set of students can be accommodated, they all can be accommodated.” Proof
27、 of JP+. Again, the elements of X are taken as propositional variables. For fi nite Y X, Yis the set of all clauses (Y S) S, where S Y and (Y,S) 6 L. As above, S = x | x S, where x is the negation of the variable x; and, for a truth assignment : X true,false, Sis the associated set x X | (x) = true.
28、 Claim. |= Y iff (Y,S Y ) L. Proof. First, note that, if S Y , then: |= (Y S) S S Y 6= S. For: |= x Y S, iff x (S Y ) S; and |= x S, iff x S (SY ). 4 It follows that: |= YS Y (Y,S) 6 L |= (Y S) S S Y (Y,S) 6 L S Y 6= S SS Y = S (Y,S) L (Y,S Y ) L. Now assume the hypotheses of JP+. Let be the union o
29、f all Ywhere Y X is fi nite. By the Claim, it suffi ces to satisfy . By Clausal Compactness, it suffi ces to satisfy all fi nite subsets of . Thus, suppose that is fi nite. Let Y X be the union of the fi nitely many fi nite Y 0 X such that for some S, (Y 0 S) S . By the Claim and by hypothesis, Y is
30、 satisfi able. By , every Y0with Y 0 Y will be satisfi ed as well. A fortiori, is satisfi ed. ? Remark. Observe that the collections K of JP and L of JP+dont need to be defi nable in any way a condition that one would expect necessary for a proof using Compactness. Related to this, the sets of claus
31、es Yused in the proof are very much diff erent from those used in standard compactness arguments for the proposition on selectors and the above-mentioned examples 2, 46. E.g., in the case of 6, one would use, for every fi nite G0 G, the clauses (x,1),. ,(x,k) (x G0), (x,i),(x,j) (x G0, i 6= j), and
32、(x,i),(y,i) (for vertices x,y G0 connected by an edge). The set of these clauses is computable from G0in time quadratic in the size of G0, a fact that is essential in the complexity reduction of graph colorability to clausal satisfi ability. On the other hand, Yis exponential in the size of Y . Now
33、note that JP+has brought us almost back to our starting point Clausal Compactness. 8. To see how easily Compactness is implied, let A be a set of clauses that is fi nitely satisfi able.Note that any S S A that is consistent, that is: does not contain a pair of opposite literals, can be thought of as
34、 a truth assignment that assigns true to the variables in S and false to the variables of which the negation is in S. Obviously, a clause is satisfi ed by this truth assignment iff it is intersected by S. Thus, in order to apply JP+to the problem of satisfying A, put X = S A and defi ne, for fi nite
35、 Y X, (Y,S) L iff S is consistent and intersects every clause in A which is included in Y . In view of 18, JP+might well be considered as a purely set-theoretic form of Clausal Compactness. 3 At the time, logic was very much dominated by set theory, thanks to the inven- tion of forcing some ten year
36、s earlier. Therefore, it was remarkable that Barwise became prominent with his admissible fragments of infi nitary languages. Un- til then, infi nitary compactness hypotheses strictly belonged to the realm of 5 large cardinals, but the Barwise Compactness Theorem turned out to be an instrument of gr
37、eat versatility at a more modest level. One year after Johan and I forced our way through the Lapland wastes, Barwise published the fi nal word Bar75 on the subject.From the present perspective, BvB96 seems therefore but an afterthought: it could have been written some twenty years earlier. The pape
38、r presents a most elegant view on interpolation and preservation. One of its cornerstones is the following (BvB96 Theorem 3, p.5): Boundedness Theorem. If = ( m such that a0,.,ak1,ak Am0. By IH, Am0|= (a0,.,ak1,ak). Thus, Am0|= xk(a0,.,ak1). However, Am Am0. Hence, Am|= xk(a0,.,ak1). ? Next, let Mnc
39、onsist of all models (A,ai)i k and (B,bi)ik (A,ai)ik. Claim 1. ? is well-founded. Proof. By Lemma 3, the union of a ?-descending sequence of models is again a model of ; but in such a union there is a -descending sequence of elements, contrary to the assumption that all models of are well-founded.?
40、Thus, every model in S nMn has a ?-rank. Let (A,ai)inbe an arbitrary model of + SK such that an1 a0. Then S(A,ai)in, the submodel of (A,ai)inthat is Skolem-generated from a0,.,an1, can be assumed to be in Mn. Claim 2. The -rank of an1in (A,ai)inis bounded by the ?-rank of the model S(A,ai)in. Proof.
41、 Induction w.r.t. the ?-rank of S(A,ai)in, as in Barwises proof. Let an A be an arbitrary element such that an an1. Then S(A,ai)i6n? S(A,ai)in. Thus, the ?-rank of S(A,ai)i6nis smaller than the ?-rank of S(A,ai)in; and, by IH, the -rank of anin (A,ai)i6nis 6 the ?-rank of S(A,ai)i6n. Consequently, t
42、he -rank of anin (A,ai)i6nis the ?-rank of S(A,ai)in; and since anwas arbitrary, Claim 2 is follows.? Finally, suppose that A is any model of . By Lemma 1, we may w.l.o.g. assume that A has been expanded into a model of SK.The Boundedness Theorem now follows from the fact that the -rank of A is boun
43、ded by the ?-rank of S(A). To see this, let a be an arbitrary element of A. Then the -rank of a in A is (by Claim 2) 6 the ?-rank of S(A,a), which is (since S(A,a) ? S(A) the ?-rank of S(A).? 7 References Bar75J. Barwise: Admissible Sets and Structures. Springer, Berlin etc. 1975. Ben72J. van Benthe
44、m: Weakenings of the axiom of choice (in dutch: “Verzwakkingen van het keuze-axioma”). Masters thesis, Dept. of Mathematics, University of Amsterdam 1972. BvB96J. Barwise and J. van Benthem: Interpolation, preservation, and pebble games. Report ML-1996-12, ILLC 1996. Doe71K. Doets:A theorem on the existence of expansions, Bull. de lAc.Pol. des Sci., Vol. XIX Nr. 1 1971 pp.13. Mil95A.W. Miller: Introduction to mathematical logic. Dept. of Math., Univ. of Wisconsin 1995. 8