1.1 (Mauldin) Is there a S11 set X universal for S11 sets which are not Borel? Suppose B Î S11 and for every Borel A, A £ W B. Does this imply that for every S11 A, A £ W B. (This refers to Wadge reducible.)
The first question was answered by Hjorth [75] who showed that it is independent.
1.2 A subset A Ì ww is compactly-G iff for every compact K Ì ww we have that AÇK is in G. Is it consistent relative to ZFC that compactly-S11 implies S11? (see Miller-Kunen [99], Becker [9])
1.3 (Miller [99]) Does D11 = compactly-D11 imply S11 = compactly-S11?
1.4 (Prikry see [55]) Can LÇww be a nontrivial S11 set? Can there be a nontrivial perfect set of constructible reals?
No, for first question Velickovic-Woodin [167]. No, for second question Groszek-Slaman [62]. See also Gitik [59]
1.5* (A.Ostaszewski, email 9-92) Consider Telgarsky's game G(T) where T Í 2w. Player I plays a countable cover of T Player II chooses one- say Xn.
Player I wins iff Ç{cl(Xn):n Î w} Í T.
It is known that
(a) Player I has winning strategy iff T is analytic.
(b) If there exists A an analytic subset of cl(T) not Borel separated from T, then Player II has a winning strategy.
Is the converse of (b) true?
1.6* Does there exists an analytic set which is not Borel modulo Ramsey null? Same question for the ideal generated by closed measure zero sets. For measure see Grzegorek and Ryll-Nardzewski [63].
Yes for second question, Mauldin [114].
1.7* (Sierpinski [151]) Does there exists a set of reals E such that every (uncountable) analytic set of reals is the one-to-one continuous image of E?
Yes, Slaman [155]. Earlier version of this problem had a misprint in it due to my faulty French.
1.8* (Jockusch conversation 10-95) Let for A Í w let D(A) = {a-b:a,b Î A}. Is the set {D(A): A Í w} Borel?
No, Schmerl [141].
1.9* Suppose I is a s-ideal generated by its P02 members. Then is it true that for any analytic set A either A Î I or A contains a P03 set not in I? This is suggested by a theorem of Solecki [156] that says that for any s-ideal I generated its closed members and analytic set A, either A Î I or A contains a Gd set not in I.
2.1 Does AD imply that 2w1 is the w1 union of meager sets?
Yes, Becker [12].
2.2 Does AD imply that there does not exist w2 distinct S21 sets?
Yes, Hjorth [70]
2.3 Is there a hierarchy of D12 sets?
2.4 Does AD imply every set is Ramsey?
Yes, if also assume V = L[\mathbb R] for references see Kanamori [88] page 382. Yes for ADR, see Prikry [136]
2.5 (V. Delfino [23]) (Conjecture) If f:2w®2w is Turing invariant (x º T y® f(x) º T f(y)) then there exists z such that either for every x ³ T z f(x) ³ T x or there exist c such that for every x ³ T z f(x) º T c.
2.6* (the last Victoria Delfino problem [34] or see Hauser [68]) Does ZFC + projective uniformization + every projective set has the Baire property and is Lebesgue measurable prove projective determinacy?
Woodin has shown that ZFC + projective uniformization + every projective set has the Baire property and is Lebesgue measurable implies that xf exists for every real x.
Steel [158] has shown that the answer is no.
3.1 (van Douwen [40]) If every w2 descending sequence in P(w)/finite has something beneath it is it true that every family of w2 sets with the IFIP has something beneath it? (does \mathfrak t = \mathfrak p).
3.2 (Hechler [69]) Let M be a countable transitive model of ZFC. Does there exists a generic extension M[fn : n Î w] with fn Î ww such that fn eventually dominates every element of M[fm : m > n]Çww.
For something similar with Sacks forcing see Groszek [61] and Kanovei [89].
No, Hjorth [76]
3.3 (Dow) Does the following imply \mathfrak p ³ k: "X,Y Ì [w]w,|X|,|Y| < k and "A Î X,B Î Y AÇB finite, there exists U Ì w such that for all V Î (XÈY)
No, Dow [41]. See also, Brendle [17].
3.4 Can the least k such that Indep(k) fails have cofinality w? Indep(k) means that every family B of k infinite subsets of w there exists an infinite subset Z of w such that for every A Î B, |ZÇA| = |Z\A| = w. (see Miller [120])
3.5 (Kunen [102]) Let \mathfrak m be the smallest cardinal for which MA\mathfrak m fails. Can we have w2 = cof(\mathfrak m) < \mathfrak m?
3.6* (Scheepers 7-91, Dordal [38]) Is it consistent that Àw embeds into (ww, £ *) but not Àw+1?
Yes, Farah [48], also Cummings, Scheepers, and Shelah [32]
3.7* (Vojtas [169] see Vaughan [166]) Does \mathfrak rs = \mathfrak r? This stands for reaping number.
|
|
4.1 (Roitman) Is it consistent that every maximal almost disjoint family in [w]w has cardinality greater than w1, but there exists a dominating family F in ww of cardinality w1? For a related result see Shelah [143] and also Brendle [18].
4.2 (van Douwen) CH implies there exist F Í ww which is maximal with respect to eventually different functions which is also maximal with respect to infinite partial functions also. Is there always such a one? What is the cardinality of the smallest?
This problem is discussed in Zhang [170].
4.3 (Cook, Watson) Consider paths in w×w. CH implies there is a MAD family of paths. Is there always one?
No, Steprans [159], still open for dimensions ³ 3
4.4 (Milliken, ?Hechler) A maximal almost disjoint family X is a separating family iff for all Q Î [w]w
|
4.5 (Erdös, Hechler [45]) Does MA plus the continuum is larger than Àw+2 imply that there is no mad family on Àw of size Àw+1?
4.6 (Kunen) Call I Í [w]w an independent splitting family if I is independent ( every finite boolean combination of elements of I is infinite) and splitting ( for every f:I® 2 there does not exist an infinite X such that for every A Î I, X Ì * Af(A), where A0 = A and A1 = w\A.) If CH or MA then there does exists an independent splitting family. In ZFC is there one?
Yes, P.Simon [153] (Bell pointed this out), also solved by Shelah and Brendle each independently.
4.7 (Fleissner) If there is a Luzin set, then is there a MAD family of size w1?
4.8* (Erdos-Shelah [44]) Does there always exist a completely separable mad family? A mad family M is completely separable iff for every A Í w if there are infinitely many M Î M which meet A in an infinite set, then there exists M Î M with M Í A. I don't know what the relationship of this question is to 4.4. See P.Simon [154] also.
5.1 (S. Friedman, R. David) Let Pn = 2 < wn. Does forcing with Pn Î wPn add a Cohen subset of ww+1?
Yes, Shelah [147]
5.2 (Kunen) Force with perfect P Ì 2w such that for every I Î [w]w pI:P® 2I does not have a countable range. Is w1 collapsed?
5.3 (van Douwen, Fleissner) Is it consistent with not CH that for P a c.c.c partial order of size continuum there exists a sequence Ga for a < w1 of P-filters such that for every dense set D Í P all but countably many of the Ga meet D.
No, Todorcevic [162]
5.4 Is there a Truss-like characterization of eventually different reals? How about infinitely equal reals? (Truss [164] proved that if f dominates wwÇM and g Î ww is Cohen over M[f], then f+g is Hechler generic over M.)
5.5 (Kunen [100]) Does there exists an w1 saturated s-ideal in the Borel subset of 2w which is invariant under homeomorphisms induced by permutations of w and different from the meager ideal, measure zero ideal, and the intersection ideal?
Partial Kechris-Solecki [92]. Yes, Roslanowski-Shelah [137].
5.6 (van Mill) Is it consistent that every c.c.c. boolean algebra which can be embedded into P(w)/finite is s-centered?
No, M.Bell [13], Shelah [149] gives a Borel example
5.7* Suppose M Í M[f] are models of ZFC and for every g Î wwÇM there exists infinitely many n Î w such that g(n) = f(n). Must there exists a real x Î M[f] which is Cohen over M? (If there are two such infinitely equal reals (iteratively), then there must be a Cohen real, see [120] and [4].)
5.8* (S.Watson, conversation with A.Dow Feb 1995) Can a poset change its cofinality in a generic extension but no cardinal changes its cofinality?
6.1 (Mauldin, Grzegorek) Is it consistent that the continuum is RVM and all sets of reals of cardinality w2 have zero measure?
No, apparently from the Gitik-Shelah Theorem (see Fremlin [54] 6F) it was deduced by Prikry and Solovay that if k is real-valued measurable, then there are Sierpinski sets of all cardinalities less than k.
6.2 (Fremlin) Can the cardinality of the least cover of the real line by measure zero sets have countable cofinality?
Yes, Shelah [146]
6.3 (Erdös) For every sequence converging to zero does there exist a set of positive measure which does not contain a similar sequence? Falconer [47] has shown that if the sequence converges slowly enough there does exist such a set of positive measure. H.I. Miller [128] has shown the analogous statement for Baire category to be false. I showed that for every sequence there exist a partition of the reals into two sets neither of which contains a sequence similar to the given one.
6.4 (Erdös) Suppose for every n Î w the set AÇ[n,¥) has positive measure. Must A contain arbitrarily long arithmetic progressions?
Several mathematicians have pointed out this is trivial. Probably I misquoted Erdös. I scribbled it down after one of his talks when the universe was younger. To quote Just [84]: ``The answer to 6.4 seems to be trivially `yes', unless you want the differences to be integers; then the answer seems to be trivially `no', unless you want the measure to be positive in EVERY interval, in which case the answer may not be so trivial. So, what should the problem really look like?''
6.5 Is it possible to have a Loeb-Sierpinski set of cardinality greater than w1? See Leth-Keisler-Kunen Miller [107] and Miller [125].
6.6* (Louveau) If a subset A of the plane has positive measure and contains the diagonal, then does there exist a set B in the line of positive outer measure such than B2 is a subset of A?
According to Burke [22], Fremlin and Shelah proved this fails in the Cohen real model.
7.1 Is it consistent that for every countable ordinal a there exists a P11 set of Baire order a? See Miller [117].
7.2 Is it consistent that for every uncountable separable metric space X there exists a X-projective set not Borel in X? See Miller [119],[124].
7.3 Is it consistent that the set of all Baire orders is the same as the set of even ordinals £ w1? See Miller [127].
7.4 Is it true that if X is a Qa-set and Y is a Qb-set and 2 £ a < b then |X| < |Y|? [117]
7.5 Does Rw2w1 = P(w2×w2) and 2w = w2 imply that 2w1 = w2? ( Rw2 is the family of abstract rectangles in w2×w2 and the lower subscript is the level of the Borel hierarchy.)
7.6 Does Rw2w = P(w2×w2) imply that for some n < w Rw2n = P(w2×w2)?
7.7 Does |X| = w1 imply that X is not a Qw-set?
7.8 (Mauldin) Is it consistent that there exists a separable metric space X of Baire order less than w1 (i.e. for some a < w1 every Borel subset of X is S0a in X) but not every relatively analytic set is relatively Borel?
7.9 Can the Borel hierarchy on cubes in R3 behave differently than the Borel hierarchy on rectangles in R2?
7.10 (Ulam [165]) Is there a separable metric space of each projective class order? (S12-forcing?) See Miller [119],[124].
7.11 In the Cohen real model is there an uncountable separable metric space of Baire order 2? In the random real model are there any separable metric spaces of Baire order between 2 and w1?
Answered in Miller [127].
7.12 What can we say about hierarchy orders involving difference hierarchies or even abstract w-boolean operations?
7.13 (Stone) Is it consistent to have a Borel map f:X® Y where X and Y are metric spaces and f has the property that there is no bound less than w1 on the Borel complexity of f-1(U) for U Í Y open? Fleissner [49] shows that it is consistent there is no such f using a supercompact.
7.14 (Ciesielski-Galvin [27]) Let P2(k) be the family of all cylinder sets in k3 (where cylinder means A×B where A Í k and B Í k2 or anything that could be obtained like this by permuting the three coordinates.) Is it consistent that the s-algebra generated by P2(\mathfrak c++) is equal to all subsets of (\mathfrak c++)3?
7.15 (Ciesielski) Suppose every subset of w2×w2 is in the s-algebra generated by the abstract rectangles. Does this continue to hold after adding w1-Cohen reals?
7.16* (Fleissner [50]) If X is a Q-set of size w1, then is X2 a Q-set? (Not necessarily true for X of cardinality w2.)
7.17* (Z.Balogh, conversation March 1996) Is it possible to have H Í P(\mathbb R) such that the Baire order of H is w1 and the s-algebra generated by H is P(\mathbb R)?
8.1 (Jech-Prikry [79]) Is it consistent that there exists a family F Ì ww1 of cardinality less than 2w1, such that for every g Î ww1 there exist f Î F such that for every a < w1, g(a) < f(a).
8.2 (Frankiewicz [52]) Is it consistent that bw\w is homeomorphic to bw1\w1?
8.3 Is it consistent to have CH, 2w1 > w2, and there exists F Ì [w1]w1 of cardinality w2 such that for every A Ì w1 there exists B Î F such that B Í A or BÇA = Æ?
8.4 (Kunen) Is it consistent to have 2w1 > w2 and there exists F Ì [w1]w1 of cardinality w2 such that for every uncountable A Ì w1 there exists B Î F such that B Í A?
8.5 (Kunen) Is it consistent to have a uniform ultrafilter on w1 which is generated by fewer than 2w1 sets?
8.6 (Prikry [135]) Is it consistent there exists an w1 generated ideal J such that P(w1) = P(w)/J?
8.7 (Comer) If C and D are homeomorphic to 2w1 then is CÈD? (Say if both are subsets of 2w1.)
No, Bell [15]
8.8 (Nyikos) If C×D is homeomorphic to 2w1 then must either C or D be homeomorphic to 2w1?
Yes, Bell [15] see also Bell [14], Schepin [138]
8.9 (CH) Let n(X) be the cardinality of the smallest family of meager sets which cover X. Can the cof(n((2w1)d)) (Gd-topology) be w or w1?
8.10 (Velickovic) Is it consistent that every Aronszajn line L contains a Countryman type?
8.11 Does PFA imply that any two Aronszajn types contain uncountable isomorphic subtypes?
8.12* What is the exact consistency strength of PFA? Schimmerling [139] showed that PFA implies the consistency of ZFC+$ a Woodin cardinal. Shelah building on work of Baumgartner (see [142]) showed that PFA is consistent assuming the consistency of a supercompact cardinal.
8.13* If the nonstationary ideal on w1 is w2-saturated, then must CH fail? Woodin has recently shown that the answer is yes if we also assume there is a measurable cardinal.
9.1 Is it consistent to have no P-points or Q-points? A P-point is an ultrafilter U on w with the property that every function f:w®w is either constant or finite-to-one on an element of U. A Q-point is an ultrafilter U on w with the property that every finite-to-one function f:w®w is one-to-one on an element of U. Shelah [142] showed it is consistent there are no P-points and Miller [118] showed that it is consistent there are no Q-points. Roitman and Taylor showed that if the continuum is £ w2, then there must be a P-point or a Q-point.
9.2 (M.E. Rudin) Is there always a small Dowker space?
Yes?, Balogh [3], Kojman-Shelah [97]
9.3 (Charlie Mills) In infinite dimensional Hilbert space is a sphere coverable by fewer than continuum other spheres?
9.4 Is it consistent that ww1 is pseudonormal? (Pseudonormal means disjoint closed sets can be separated if at least one is countable.)
9.5 (van Douwen) Is it consistent to have c(U(w1)) < d(U(w1)? (c is cellularity, d is density and U is uniform ultrafilters.)
9.6 Is the box product of countably many copies of the unit interval coverable by countably many zero dimensional sets?
9.7 (Hansell) Is there a non-zero-dimensional Q-space? Can there be a nonzero dimensional metric space in which every subset is Gd?
9.8 (Bing) Suppose Dn a subset of the plane is homeomorphic to a disk and for every n Î w Dn+1 Í Dn, then does Çn Î wDn have the fixed point property? (I heard about this problem from a lecture by Bing, however the problem dates from the 1920's and was discussed by Kuratowski, Mazurkiewicz, and Knaster, see Mauldin [115] problem 107.)
9.9 (Sikorski see [103](1950)) Does there exist two compact 0-dimensional nonhomeomorphic subsets of the plane such that each is homeomorphic to an open subset of the other?
Yes, Kinoshita [96] (1953) see also Halmos [64] section 29. (Thanks to R.Dougherty for reference, also 9.10.)
9.10* (Ancel 11-93) Is there a separable Hausdorff space in which every basis has cardinality 22\mathfrak c?
Yes, already known, see Juhasz-Kunen [83].
9.11* (Gulko 1995) Is there a model of ZFC in which there is a maximal almost family M on w such that for any point x Î bw\w there exists a countable subfamily of M such that x is in its closure.
0.1 (Vaught) Does every countable first order theory have countably many or continuum many countable models up to isomorphism? How about for universal theories of a partial order? For recent background see Becker [11], Becker and Kechris [10], and Kechris [93]. Vaught's conjecture is the statement that for any first order theory T in a countable language has either countable many or continuum many non-isomorphic countable models. The first major result on this is due to Morley [131] who showed that any such theory has either £ w1 or continuum many countable models up to isomorphism. His proof used a combination of model theory and descriptive set theory. It works just as well for sentences of Lw1,w in place of first order theories. On the model theoretic front, Steel [157] proved Vaught's conjecture for Lw1,w theories of trees (partial orders whose initial segments are linearly ordered) which includes the special cases of linear orders and theories of one unary operation. Also, Shelah [65] proved Vaught's conjecture for w-stable first order theories. The topological Vaught's conjecture is the following: Let G be a Polish group acting on a Borel space B. Then the equivalence relation induced by G has either countably many classes or there is a perfect set of pairwise inequivalent classes. (see [10] for some equivalent versions.)
10.2 (Martin) Show that if T is a countable first order theory with fewer than continuum many countable models up to isomorphism, then every countable model of T has an isomorphism class which is at most S0w+w+1.
10.3 (Caicedo [24]) Does every theory in Lw1,w have an independent axiomatization?
10.4 Does V=L imply there exists a complete theory T such that
|
Yes, Hjorth [71].
10.5 (Miller [121]) Are there any properly S0l+1 isomorphism classes for l a countable limit ordinal?
Yes, Hjorth [72]
10.6 Is there a theory with exactly w1 rigid countable models up to isomorphism? (same for minimal models)
Yes, for minimal models, Hjorth [73]. Yes, for rigid models, Hjorth [74]
10.7 (Baldwin) Are there continuum many complete w-stable w-categorical theories in a finite language?
Only countably many, Hrushovski [77]. Problem was mistated in earlier versions. (Thanks to J.Baldwin for reference and correction.)
10.8 (Miller-Manevitz [112]) Is it consistent that there exists a model of ZFC, M, such the unit interval of M is Lindelof and wM is w1-like?
Yes, Keisler and Schmerl [95] (it also contains many open problems)
10.9 (Miller [121]) Does there exists a pseudo-elementary class in the language of one unary operation with exactly w1 nonisomorphic countable models? (There is pseudo Lw1,w class.)
10.10 (Mati Rubin) Does there exists an embedding of the rationals into themselves such that no between function is elementarily extendable?
10.11 Duplicate of 10.6
10.12* (suggested by Fuhrken [56] [43]) Can we have a model with exactly one undefinable Lw1,w element?
10.13* Can we have a complete first order theory T with models of size À2n for n < w (but not of size À2n+1) and Àw < \mathfrak c?
10.14* (A.Enayat, letter July 1998.) Does there exist a complete theory T extending ZF which has exactly two transitive models of a given ordinal height a? The height of a model M is the least ordinal not in M.
1.1 (Mauldin, Grzegorek) Is it consistent that every universally measurable set has the Baire property? See Corazza [29].
11.2 (Mauldin) Are there always > \mathfrak c many universally measurable sets? (same question for restricted Baire property). There is a model in which there are only continuum many universal measure zero sets (see Miller [122]).
11.3 (Galvin) Does every Sierpinski set have strong first category?
Bartoszynski-Judah [5] showed that it is consistently yes. Yes, Pawlikowski [133].
11.4 (Galvin, Carlson) Is the union of two strong first category sets a set of strong first category?
Not necessarily, Bartoszynski-Shelah [6]
11.5 Does there exists a perfectly meager X Í \mathbb Rn which is not zero-dimensional? Szpilrajn(Marczewski) proved that there is such a set assuming CH, see Brown and Cox [20]. However is it consistent that there is none?
yes. Reclaw pointed out to me that: A metric space of size less than continuum has to be zero dimensional and it is consistent that all perfectly meager sets are of size less than continuum, see Miller [122].
11.6 (Kunen) Is it consistent that for every uncountable X Í \mathbb R there exists a measure zero set M such that X+M has positive outer measure? See Erdos-Kunen-Mauldin [46].
Yes, Carlson, this is true in the model for the dual Borel conjecture [26], (this was pointed out to me by Brendle and Reclaw.)
11.7 (Sierpi\'nski [152]) A set of reals X is a J-set iff for uncountable Y Í X there exist a perfect P Í X such that PÇY is uncountable. If we assume CH, then a set is a J-set iff it is s-compact. Is it consistent with not CH that J-set = s-compact?
11.8 (Fremlin-Miller [53]) Is there always an uncountable subset of the reals which is hereditary with respect to property M?
Yes, see [85]
11.9 Consider the three non c.c.c ideals: (s)0-sets, Ramsey null sets, and s-compact sets. What can one say about the properties of add, cov, non, and cof? ( add = additivity of ideal, cov = smallest cardinality of a cover of reals by subset of ideal, non = smallest cardinality of a set of reals not in ideal, cof = cofinality = smallest cardinality of a family of sets in ideal which has the property that every set in ideal is covered by some element of the family.)
11.10 Consider the notion of Laver null sets. This is defined analogously to Ramsey null sets, but use Laver forcing instead of Mathias forcing. The analogue of Galvin-Prikry Theorem is true here. What other results also go thru? What ideals arise from other notions of forcing? What about Silver forcing? What notions of forcing arise from infinite combinatorial theorems? (For example, Carlson's infinite version of the Hales-Jewett theorem [25].)
For some work in this direction, see Löwe [111] and Brendle and Löwe [19].
11.11 (Judah-Shelah [82]) Is the Borel conjecture plus the existence of a Q-set consistent?
11.12 (Daniel, Gruenhage). Given a set of reals X and ordinal a let Ga(X) be the game of length a played by two players: point picker and open. At each play of the game point picker picks a real and open responds with an open set including the real. Point picker wins a run of the game if at the end the open sets chosen cover X. The order of X is the least ordinal for which point picker has a winning strategy. What orders are possible? Daniel and Gruenhage have examples of order wn assuming CH.
all countable limit ordinals are possible, Baldwin [2]
11.13* (Komjath, see Steprans [160],[161]) Suppose every set of reals of size w1 has measure zero. Then does every w1 union of lines have planar measure zero? (Dually) Suppose the real line is union of w1 measure zero sets. Then does there exists w1 measure zero subsets of the plane such that every line is contained in one of them?
The answer is known if line is changed to graph of continuous function, see Bartoszynski, Roslanowski, Shelah [7]. There is also the analagous question for category.
11.14* (Zhou email 3-93) Does every set of size w1 is a Q-set imply that \mathfrak p > w1. For g-sets it is true.
No, Brendle points out this follows from results in Dow [41]. We don't know if ``every set of size w1 is a Q-set'' implies ``the real line cannot be covered by w1 meager sets''. It is consistent to have a Q-set plus ``the real line cannot be covered by w1 meager sets'', see Judah-Shelah [82].
11.15* (M.Laczkovich, email April 1996) Assuming CH, there is a nonmeasurable subset of the reals that differs from each of its translates in a set of measure zero (Sierpinski). Can such a set can be given in ZFC?
No, see Laczkovich, [104]
11.16* (A.Marcone, email May 1997) Is it consistent that every l-set (space) is a Q-set (space)?
2.1 Is there a Borel version of Fraisse's conjecture? Are the Borel linear orderings well-quasiordered under embedding?
Yes, Louveau and St-Raymond [109] assuming large parts of AD. See also Louveau [110]
12.2 (Laver) Is it consistent that the set of Aronszajn trees is well-quasi-ordered under embeddability? See Laver [106] and Corominas [30].
No, Todorcevic [163].
12.3 (Kunen) Is the set of all better-quasi-ordered binary relations on w a proper P12 set?
Yes, Marcone [113]
12.4 Suppose (Q, £ ) is a recursive quasi-order. Is it true that Q is BQO iff Q < w1ck is WQO?
12.5 (Kunen) Suppose (Q, £ ) is a recursive well quasi-order. Does Qw/ º have a recursive presentation? (It is countable, see Laver [105] Theorem 4.11 for wqo.)
12.6 Suppose every set is Ramsey and f:[w]w®ORD. Then does there exist X Î [w]w such that the image of [X]w under f is countable? See Louveau-Simpson [108] and Aniszcyk-Frankiewicz-Plewik [1].
12.7 Is finite graphs under homeomorphic embedding WQO?
12.8 Is the witness lemma true for LIN(Q) or TREE(Q)?
12.9 Is there an w1-descending sequence of countable posets (under embedding) each of which is the union of two chains? (Kunen, Miller: There is an w1-descending sequence of countable posets. Kunen: There is an infinite antichain of finite posets each of which is the union of two chains. The first result appears in the second edition of Fraïssé's book [51].)
12.10 Is there a parameterized version of Carlson's theorem? See Carlson [25] and Pawlikowski [132].
3.1 (Bell) Let C stand for:
(C) For every family of nonempty sets there exists a function assigning to each set in the family a compact Hausdorff topology.
Is (C) equivalent to AC? If not, what principles of choice is (C) equivalent to?
Motivation: PIT (Prime Ideal Theorem) is equivalent to every Tychonov product of compact Hausdorff spaces is compact. Hence AC is equivalent to C+PIT.
In an earlier version of these problems I had mistakenly written ``Does ZF prove C?''. However, it is known that PIT does not imply AC (see Jech [78]), hence C fails in any model of ZF + PIT + notCH.
13.2 (Dow 88) Does Stone's theorem on metric spaces (every metric space is paracompact) require AC? It is known that ZF implies that w1 with the order topology is not metrizable.
Yes, Watson see [60].
13.3* (Morillon [130]) (In ZF) does every compact Hausdorff space which is countable have an isolated point?
13.4* (M.Bell, email April 96) Is it consistent to have the prime ideal theorem plus there does not exist an w1 descending sequence of distinct sets mod finite, i.e., áAa Î [w]w: a < w1ñ with Aa Í *Ab for b < a? Bell notes that in such a model of set theory, we would have that bw\w would exist in all its glory, but hardly anything of the standard stuff about it could be proved.
4.1 Does there exist a non-trivial automorphism of the Turing degrees? (Re degrees?)
Yes for both? announced by Cooper [28]
14.2 (Jockusch) Does there exists a DNR of minimal Turing degree? (DNR means diagonally non recursive: f Î ww and for all e Î w, f(e) ¹ {e}(e).)
5.1 (Sierpi\'nski) Is there a Borel subset of the plane which meets every line in exactly two points? (Mauldin) Must such a set be zero dimensional?
Davies has shown such a set cannot be S02 and Mauldin has shown such a set must be disconnected. Miller [123] showed that if V=L then there does exist a P11 subset of the plane which meets every line in exactly two points. Kulesza [98] showed that any two point set must be zero dimensional. Mauldin [116], Dijkstra, Kunen, van Mill, [35] [36] [37], have some recent work.
15.2 (Cichon) Is it consistent to have that the real line is the disjoint union of w2 meager sets such that every meager set is contained in a countable union of them?
No, Brendle [16]
15.3 (Juhasz) Does club imply there exist a Souslin line?
No, Dzamonja-Shelah [42]. However, Juhasz tells me (4-2000) that there may be a mistake in their proof. I do not know the current status of this problem.
15.4 (Ulam [165]) Does there exist a set D dense in the plane such that the distance between any two points of D is rational?
15.5 (Miller [122]) Suppose the continuum is greater than w2, then does there exists a set of reals of cardinality the continuum which cannot be mapped continuously onto the unit interval?
15.6 Is it consistent that there exists x Î 2w such that V = L[x] ¹ L and a continuous onto function f:LÇ2w® VÇ2w?
15.7 (Price [134]) Is it consistent there is no Cech function?
15.8 (Kunen) Does the consistency of an elementary embedding of M into V imply the consistency of a measurable cardinal?
No, Vickers and Welch [168] show a Ramsey is enough.
15.9 (Erdös) Without CH can you partition the plane into countably many pieces so that no piece contains an isoceles triangle? See Kunen [101].
Yes, Schmerl [140].
15.10 Is there a Borel version of Hall's marriage theorem? As for example, the Borel-Dilworth Theorem [66].
15.11 (Davies [33]) Assuming CH for every f:\mathbb R2® \mathbb R there exists gn,hn:\mathbb R® \mathbb R such that
|
No and its also consistently false Shelah [150].
15.12 (Mauldin) CH implies that for every n ³ 3 there exists a 1-1 onto function f:\mathbb Rn® \mathbb Rn which maps each circle onto a curve which is the union of countably many line segments. Is CH necessary?
15.13 (Kunen) Can there be a Souslin tree T Í 2k such that for all a < k the Ta contains all except at most one of the a branches thru T < a. Here k is the first Mahlo or weakly Mahlo.
Yes, Shelah [148]
15.14 (Baumgartner [8]) Is it consistent that any two w2 dense sets of reals are order isomorphic?
15.15 (S. Kalikow [86]) For any set X define for x,y Î Xw, x = *y iff for all but finitely many n Î w, x(n) = y(n). X has the discrete topology and Xw the product topology. Is it consistent that there exists a map f:w2w® 2w which is continuous and for every x,y Î w2w, x = *y iff f(x) = *f(y). (Kalikow: yes for w1 in place of w2.)
Yes, Shelah [145].
15.16* (unknown 1-92) According to Erdos, Sylvestor proved that given finitely many points F in the plane not all collinear, there exists a line L which meets F in exactly two points. F = \mathbb Z×\mathbb Z is an obvious infinite counterexample. Does there exists a counterexample which is a convergent sequence? countable compact set?
15.17* Given that 2Àn = Àn+1 for each n < w what can we say about 2Àw?
Shelah has shown that if Àw is a strong limit cardinal, then 2Àw < À(2À0)+ and 2Àw < ÀÀ4. See Shelah [144] or Jech [80] or Burke-Magidor [21]. On the other hand Gitik-Magidor [58] have shown that is consistent relative to the existence of strong cardinals that 2Àw = Àw+z+1 for any z < w1. What about the gap? See Jech-Shelah [81]. Also, many variations on this questions can be given. For example, Shelah has shown that relative to a supercompact it is consistent that for the least uncountable k with Àk = k that the GCH holds up to k but 2k can be arbitrarily large. What about singular cardinals in between? What are the exact consistency strengths of these statements? Magidor-Gitik [58] have gotten Shelah's result from a weaker assumption. Gitik [57] building on work of Mitchell [129] has shown for example that the existence of a measurable k with o(k) = k++ is equiconsistent with the failure of the singular cardinal hypothesis. For more on this see Cummings [31].
15.18* (Dougherty-Kechris [39]) Is Turing equivalence is universal for countable Borel equivalence relations, i.e., for every countable Borel equivalence relation (X,E) does there exists a 1-1 Borel map f:X® 2w such that for all u,v Î X
|
15.19* (Kechris, Solecki, and Todorcevic) Is it possible to have a Borel graph with coloring number 2 but Borel coloring number 4. They have examples for n and n+1.
Yes, Laczkovich, see the appendix of [94].
15.20* (M.Bell, letter to M.E.Rudin, April 1996) Can there exist a cardinal k > \mathfrak c for which there exists k+ subsets of k each of cardinality k and with pairwise intersection finite?
S.M. Ulam, Problems in Modern Mathematics, John Wiley and Sons, 1959.
The Scottish Book, mathematics from the Scottish Cafe, ed by R.D. Mauldin, Birkhaüser, 1981.
Open Problems in Topology, ed by J. van Mill, G.M. Reed, North-Holland, 1990.
D.H. Fremlin, Problems to add to the gaiety of nations, fremdh@essex.ac.uk
M. Scheepers, The Boise problem book, marion@cantor.idbsu.edu
Victoria Delfino Problems, Cabal Seminar, Lecture notes in mathematics, 689, 839, 1019, 1333, Springer-Verlag.
Analytic Sets, ed by C.A.Roger, J.E.Jaynes, Academic Press, 1980.
B.Velickovic, Some problems in set theory, Jan 1995, boban@logique.jussieu.fr
H.Friedman, 102 problems in logic, Journal of Symbolic Logic, 40(1975), 113-129.
Arnold W. Miller
University of Wisconsin
Department of Mathematics, Van Vleck Hall
480 Lincoln Drive
Madison, WI 53706
miller@math.wisc.edu
http://www.math.wisc.edu/~miller