Three-old-pieces.pdf
《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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Three old pieces
链接地址:https://www.31doc.com/p-3800963.html