• 検索結果がありません。

SMALL SETS IN CONVEX GEOMETRY AND FORMAL INDEPENDENCE OVER ZFC

N/A
N/A
Protected

Academic year: 2022

シェア "SMALL SETS IN CONVEX GEOMETRY AND FORMAL INDEPENDENCE OVER ZFC"

Copied!
20
0
0

読み込み中.... (全文を見る)

全文

(1)

INDEPENDENCE OVER ZFC

MENACHEM KOJMAN Received 28 June 2004

To each closed subsetS of a finite-dimensional Euclidean space corresponds aσ-ideal of sets᏶(S) which isσ-generated overS by the convex subsets ofS. The set-theoretic properties of this ideal hold geometric information about the set. We discuss the relation ofreducibilitybetween convexity ideals and the connections between convexity ideals and other types of ideals, such as the ideals which are generated over squares of Polish space by graphs and inverses of graphs of continuous self-maps, or Ramsey ideals, which are generated over Polish spaces by the homogeneous sets with respect to some continuous pair coloring. We also attempt to present to nonspecialists the set-theoretic methods for dealing with formal independence as a means of geometric investigations.

1. Introduction

This paper has two objectives. Its first objective is to present in a unified way a connected group of set-theoretic results about convexity in Euclidean spaces [4,5,6,10,12]. These investigations concern a generalization of convexity of closed subsets of Euclidean spaces.

We call a setcountably convexif it is a countable union of convex sets anduncountably convexotherwise. Aconvex coverof a setSis a collection of convex subsets ofSwhich coversS.

It is fair to say that an uncountably convex set is “less convex” than a countably convex one. But how does one compare generalized convexity between two uncountably convex sets? For every setSRdthe collection{{x}:xS}is a convex cover ofS, so for a subset ofRdit never takes more than continuum many convex subsets to cover it. On the other hand, a closed uncountable subset ofRdis equinumerous with the continuum. So are not all uncountably convex closed subsets ofRdfor alld1 “equally nonconvex”?

Most mathematicians would probably think that the answer to this question is positive, but this is not so. For each finite dimensiond1 there exists an uncountably convex compact setSd+1Rd+1which is “strictly more convex” than every uncountably convex SRd, in the following sense:

(i) for every closed uncountably convexSRd, there is a uniform way for trans- lating convex covers ofSto convex covers ofSd+1. This makesSd+1 “at least as convex” asS,

Copyright©2005 Hindawi Publishing Corporation Abstract and Applied Analysis 2005:5 (2005) 469–488 DOI:10.1155/AAA.2005.469

(2)

(ii) there is no proof from the axioms of set theory that for some closed and un- countably convex SRd it holds thatSis at least as convex as Sd+1, because it is possible thatSd+1is a union ofstrictly fewer convex sets than the minimal number of convex subsets ofSrequired to coverSfor every closed uncountably convexSRd[6].

The second clause above brings up the second objective of this paper, which is to present the set-theoretic methodology for dealing with possible different uncountable infinities in Euclidean spaces and to demonstrate the applicability of this methodology to geometric investigations. Using the set-theoretic language of formal independence over the axioms of set theory, one can phrase and prove geometric properties of Rd which are neither expressible nor provable otherwise.

InSection 2, theconvexity idealof a closed, uncountably convex subset ofRdis defined and so is the relation ofreducibilitybetweenσ-ideals, used to compare different convexity ideals. This relation is a variant of Tukey reducibility (see [2] for a treatment of Tukey reducibility). Then the setsSdRdare constructed for alld1 and are shown to form a descending sequence in the reducibility relation.

The methodology for showing that the reducibility relations which are presented in Section 2 are not reversible is presented in Sections3 and 4is devoted to consistency results.

A particularly interesting case isd=2. The classification of generalized convexity of closed planar sets leads to some interesting connection to other ideals.Section 5describes the connection of convexity ideals in the plane tofunctions ideals, which are generated over squares of Polish spaces by graphs and inverses of graphs of continuous self-maps of the space, toRamsey ideals, and to theσ-compact idealover the Baire space.

2. Convexity ideals 2.1. Ideals and covering

Definition 2.1. (i) An ideal of sets is a nonempty collection of setsᏵwhich satisfies:

(1)A,BABᏵ, (2)ABAᏵ.

The term “ideal” will always mean “an ideal of sets.”

(ii) The domain of an idealᏵis the set domᏵ:=

Ᏽ. If domᏵ/ Ᏽ, thenᏵis a proper ideal.

(iii) If the union of every countable subfamily of an idealᏵbelongs toᏵ, thenᏵis a σ-ideal.

(iv) A subfamilyᏲᏵof an idealᏵis a covering family ofᏵif=domᏵ.

(v) IfᏲis a family of sets, then the ideal generated byᏲis

X:n

A1,. . .,An

eachAiᏲandX n i=1

Ai

. (2.1)

(vi) Theσ-ideal which isσ-generated by a familyᏲof sets is

X:

A1,A2,. . .

eachAiᏲandX i=1

Ai

. (2.2)

(3)

In what follows we will be interested in comparing the difficulty of finding covering families of one ideal to that of finding covering families of another. This will be done with the following relation of reducibility.

Definition 2.2. A reduction of an ideal᏶to an idealᏵis a function f : domᏵdom᏶ such that f1[Y]Ᏽfor allY᏶or, equivalently, such that f[X]/ ᏶for allXdomᏵ such thatX /Ᏽ. An ideal᏶is reducible to an idealᏵif there exists a reductionf of᏶to Ᏽ. WriteᏵ᏶to denote that᏶is reducible toᏵ. If bothᏵ᏶and᏶Ᏽhold, thenᏵ and᏶are equivalent.

The relationon ideals is reflexive and transitive, hence equivalence of ideals is an equivalence relation.

Claim 2.3. If f : domᏵdom᏶is a reduction of᏶toᏵ, then for every covering family Ᏻ᏶of᏶, the familyᏲ:= {f1[Y] :Y}is a covering family ofᏵ.

Proof. Since f1[Y]Ᏽfor all Y᏶, indeedᏲᏵ. To see thatᏲcovers domᏵ, let xdomᏵbe arbitrary. SinceᏳis covering, there is someY Ᏻ so that f(x)Y; so

xf1[Y].

Thus, ifᏵ᏶, then every reduction f : domᏵdom᏶gives a uniform way of trans- lating covering families ofᏵto covering families of᏶.

The simplest example ofᏵ᏶is when᏶Ᏽand dom᏶=domᏵ, that is, when᏶is a subideal of᏶with the same domain. In this case, the identity function on dom=dom᏶

is a reduction of᏶toᏵ. Things are more complicated when᏶᏶and dom᏶=domᏵ:

a reduction may or may not exist in either direction.

We will be often considering a special case of this latter situation, whenᏵis a restric- tion of᏶to a subsetAof dom᏶.

Definition 2.4. Suppose᏶is an ideal and∅ =Adom᏶. The ideal{X:XA,X}

= {XA:X}is denoted by᏶A.

Lemma2.5. Suppose thatis an ideal and that∅ =Adom᏶. Then᏶A᏶. If in additiondom᏶\Aholds, thenAholds.

Proof. To see that᏶A᏶, let f :Adom᏶be the identity map onA. For allY A, it holds thatf[Y]=Y, hence,Y /Af[Y]/ ᏶. This shows that f is a reduction of᏶to᏶A.

Assume now that dom᏶\A᏶. Let f : dom᏶A be any projection, that is, an onto function which satisfies f2=f. SupposeYdom᏶andY /᏶. It holds thatY= (YA)(Y\A) and, since (Y\A)(dom᏶\A)᏶, we have (Y\A)᏶. Therefore, sinceY /᏶, necessarily (YA)/ ᏶. But (YA) f[Y], hencef[Y]/A, sof is a

reduction of᏶Ato᏶.

Definition 2.6. A topological spaceXisPolishif it is homeomorphic to a complete metric space. A topological spaceX isperfect if it has no isolated points. For a perfect Polish spaceXletᏹ(X) denote themeager, orfirst category,σ-ideal overX, namely theσ-ideal which isσ-generated by all (closed) nowhere dense subsets ofX.

(4)

IfXis a perfect Polish space, then, sinceXhas no isolated points, each singleton{x} forxX belongs toᏹ(X), hence domᏹ(X)=X. By the previous lemma, whenever AXis a denseGδsubset of a perfect Polish spaceX, it holds thatᏹ(X) andᏹ(X)A are equivalent.

Claim 2.7. All meager ideals over all perfect Polish spaces are equivalent to each other.

Proof. SupposeX andY are perfect Polish spaces and fix countable dense setsAX andBY. SinceX andY are perfect, bothAandBare dense in themselves and thus homeomorphic to each other. Fix a homeomorphism f:AB. By Lavrentiev’s the- orem (see [9, Theorem 3.9]), there areGδ setsAX,BY so thatAA,BB and a homeomorphism f :AB(which extends f, but this is not needed here). The homeomorphism f and its inverse f1demonstrate the equivalence ofᏹ(Y)Bwith ᏹ(X)A. Sinceᏹ(X)Ais equivalent toᏹ(X) andᏹ(Y)Bis equivalent toᏹ(Y),

the equivalence ofᏹ(Y) withᏹ(X) follows.

Since up to equivalence there is just one meager ideal over a perfect Polish space, we use the symbolᏹalone to denote the meager ideal.

2.2. Convexity ideals. A subset of a real vector space is countably convex if it is a union of countably many convex sets and is uncountably convex otherwise. Letd1 be a natural number and letRd denote thed-dimensional Euclidean space with the usual Euclidean norm.

Definition 2.8. SupposeSRd. Let᏶(S) be theσ-ideal which isσ-generated overSby all convex subsets ofS. Explicitly,

X᏶(S)⇐⇒ ∃

c0,c1,. . .

eachciSis convex andX

i

ci

. (2.3)

Theσ-ideal᏶(S) is proper if and only ifSis uncountably convex. In the case thatSis closed, the closure inRd of a convex subset ofSis contained inS, and is convex. Thus, whenSis closed,᏶(S) isσ-generated by theclosedconvex subsets ofS.

Claim 2.9. Suppose SRd. Then the union of all relatively open subsets of S which belong to᏶(S) belongs to᏶(S).

Proof. LetA:=

{uS:uRdis open anduS᏶(S)}.Ais an open subset ofS. We need to show thatA᏶(S).

For everyxAthere is some open setuRd so thatxuanduS᏶(S). Since uis open and xu, there is some rational ballB, that is a ball of rational radius and rational coordinates of its center, so thatxBu, and henceBS᏶(S).

We have shown thatA=

{BS:Bis a rational ball andBS᏶(S)}. For each ra- tional ballBwhich satisfiesBS᏶(S) fix convex subsets ofS,cB0,cB1,. . ., so thatBS

icBi. Now

A= BS:Bis a rational ball andBS᏶(S)

cBi :Bis a rational ball andBS᏶(S). (2.4)

(5)

Since there are only countably many rational balls inRd, the collection {cBi :B is a rational ball andBS᏶(S)}is countable, and soAis contained in a countable union

of convex subsets ofS. ThusA᏶(S).

Definition 2.10. ForSRdletA(S) be the union of all relatively open sets in᏶(S) and let K(S) :=S\A(S).

Claim 2.11. SupposeSRd is closed and uncountably convex. ThenK(S) is nonempty and perfect.

Proof. SinceA(S)᏶(S) and ᏶(S) is proper,A(S)=ShenceK(S)= ∅. Since A(S) is open inS, K(S) is closed in S, and, since Sis closed, K(S) is closed in Rd. We argue that no pointxK(S) is isolated inK(S). Suppose to the contrary thatsK(S) and an openuxare given so thatK(S)u= {x}. Then (uS)\ {x} ⊆A(S) and hence it belongs to᏶(S). Since{x}is convex, also (uS)\ {x} ∪ {x} =uSbelongs to᏶(S).

Thus,uSA(S). But sincexS\A(S), this is a contradiction.

Definition 2.12(the convexity ideal of a closed uncountably convex set). Suppose that SRdis closed and uncountably convex. LetᏵ(S) be the ideal᏶(S)K(S)= {XK(S) : X᏶(S)}. Equivalently,Ᏽ(S) is theσ-idealσ-generated overK(S) by all intersections CK(S) of all closed and convexCSwithK(S). The idealᏵ(S) is calledthe convexity ideal of S.

Claim 2.13. For a closed uncountably convexSRd, the ideals᏶(S) andᏵ(S) are equiv- alent.

Proof. ByLemma 2.5, sinceS\K(S)=A(S)᏶(S).

Claim 2.14. SupposeSRd is closed and uncountably convex. Then for every convex CS, the intersectionCK(S) is nowhere dense inK(S).

Proof. Suppose to the contrary thatCSis convex and thatCK(S) is dense inK(S) u for some openu withuK(S)= ∅. Since the closure in Rd of Cis convex and is contained inS,K(S)u᏶(S) and henceSu᏶(S). This contradictsA(S)K(S)=

.

Corollary2.15. For a closed, uncountably convexSRd, it holds thatᏵ(S)ᏹ(K(S)) and thatdomᏵ(S)=domᏹ(K(S))=K(S). Thus,ᏹᏵ(S)for every closed, uncountably convexSRdfor alld1.

Proof. IfXSis countably convex andX

ncn, where eachcnSis convex, thenX K(S)

ncnK(S). By the previous claim,cnK(S) is nowhere dense inK(S) for each n, henceXK(S)ᏹ(K(S)). This shows theᏵ(S)ᏹ(K(S)). Also, every singleton in K(S) is a convex set, hence domᏵ(S)=K(S). ThusᏵ(S) is a subideal ofᏹ(K(S)) with

the same domain, and is reducible to it.

A covering family ofᏵ(S), for a closed and uncountably convexSRd, corresponds naturally to a covering ofSby convex subsets. The reducibilityᏹᏵ(S) which was just established shows that to cover a closed, uncountably convex set by convex subsets is at least as hard as covering a perfect Polish space by nowhere dense sets.

(6)

2.3. The structure of convexity ideals under reducibility. In this section, we will ex- amine the relation of reducibility on convexity ideals. We will construct, for eachd1, a closed and uncountably convex setSdRdwhose convexity idealᏵ(Sd) is identical with a combinatorially described idealᏵd. We will see that for every closed, uncountably convex SRd, it holds that

d+1=Sd+1

Ᏽ(S). (2.5)

We first describe the idealsᏵd combinatorially, using the standard metric on spaces of sequences, and prove thatᏵd+1dfor alld1. Then we show how to realize each ideal Ᏽdas a convexity ideal of a compact subset ofRd. The concatenation of a sequenceνto a sequenceηis denoted byηˆν.

For everyd2, letdNdenote the space of all sequences over theddistinct symbols 0, 1,. . .,d1. Let·denote the empty sequence, letx0,. . .,xn1denote a sequence of lengthn, and letxm:mNdenote an infinite sequence.

For distinct η,νdN let ∆(η,ν) :=min{n:η(n)=ν(n)} and let ρ(η,ν) :=1/2∆(η,ν) (and letρ(η,η)=0 for allη). The functionρ is a metric with whichdN is a compact metric space. There are equidistant sets of sizedindNwith respect toρbut no equidis- tant sets of sized+ 1. An open ball with centerηis the set of allνso that∆(η,ν)kfor some constantk. If a setXdNis somewhere dense indN, it must contain an equidistant subset of sized.

Definition 2.16. For everyd3, letᏵdbe theσ-ideal overdNwhich isσ-generated by all subsets which do not contain a set ofdequidistant points.

The idealᏵdis contained inᏹ(dN) for alld3 by what we observed.

We remark that it makes sense to apply the definition ofᏵd also tod=2—one gets in this case theσ-ideal of countable subsets of 2N. However, we denote theσ-ideal of countable subsets of 2NbyᏵ1and reserve the notationᏵ2for the following ideal.

Definition 2.17. LetᏵ2be theσ-ideal which isσ-generated over 2Nby all subsetsX2N which satisfy the following:∆(η,ν) is even for all distinctη,νX, or∆(η,ν) is odd for all distinctη,νinX.

The following claim follows fromTheorem 2.20andClaim 2.19below; but it also has a direct, short proof.

Claim 2.18.d+1dfor alld1.

Proof. The identity map on 2Nis a reduction ofᏵ1toᏵ2, since every countable subset of 2Nbelongs toᏵ2.

A reduction of Ᏽ2 to Ᏽ3 is achieved as follows: letg(0)= 0, 0,g(1)= 1, 0, and g(2)= 1, 1. Now define f(η)= g(η(m)) :mN, that is, the successive concatenation ofg(η(i)). Suppose that{η012}is an equidistant triple in 3Nwith∆(ηij)=mfor alli < j <3 and suppose thatηi(m)=i. Then∆(f0,f η1))=2mand∆(f1),f2))= 2m+ 1. Therefore, whenever inY2Nall∆’s are odd or all∆’s are even, f1[Y] does not contain an equidistant triple. Since f1(on sets) commutes with taking unions, for every Y2, it holds that f1[Y]3.

(7)

For the cased3, letg(i)=iifi < dand letg(d)=d1. Define f(η)= g(η(m)) : mN. Every equidistant (d+ 1)-tuple in (d+ 1)N is mapped via f to an equidistant

d-tuple. Thus, f is a reduction ofᏵdtoᏵd+1.

Claim 2.19. For every closed and uncountably convexSRd, it holds thatᏵd+1Ᏽ(S).

Proof. A uniformly continuous 1-1 functionf : (d+ 1)NK(S) is defined as follows. For everyfinitesequenceη(d+ 1)m, defineF(η)K(S) to be a closed ball of positive radius less than or equal to 1/(m+ 1) and so thatF(ηˆi)F(η) for allid. Then f(η) for an infiniteη(d+ 1)Nis defined as the unique point which satisfies{f(η)} =

mF(ηm).

LetF(·) be any ball of radius 1 inK(S).

Suppose F(η) is defined for all η(d+ 1)m and let η(d+ 1)m be given. Since conv (K(S)F(η)S, it follows, by Caratheodory’s theorem (Caratheodory’s theorem states that a point in the convex hull ofSRd belongs to the convex hull ofd+ 1 points from S), that there are y0,. . .,ydK(S)F(η) so that conv(y0,. . .,yd)S. Since S is closed, there is a sufficiently smallr >0 so that for every choice ofxiB(yi,r) forid, it holds that conv(x0,. . .,xd)S. Let f(ηˆi)=B(yi,r).

Every equidistant (d+ 1)-tuple in (d+ 1)Nis mapped via f to a (d+ 1)-tuple inK(S) whose convex hull is not contained inS. Thus,f is a reduction.

Finally, we show thatᏵdis realized as a convexity ideal inRd.

Theorem2.20. For everyd1, there exists a compact setSdRd so thatᏵ(S)=d. For d3,Sdisstar-likewith respect to a point in its interior, namely there is somex0intSdso that[x0,y]Sdfor allySd, and thereforeSdis contractible for alld3.

Proof. We start with the cased=3. Take a spherical soup bowl and place three closed spherical caps and an open pyramid on its bottom so that

(1) any point in one of the spherical caps can see any point in any other spherical cap;

(2) any choice of one point from each cap spans a triangle that meets the pyramid.

(SeeFigure 2.1.)

Repeat this construction ad infinitum inside each of the three caps. When finished, fill the bowl with soup and freeze it. The frozen soup is a compact subset ofR3which we denote byS3. Clearly,S3is star-like with respect to the center of the sphere, which belongs to the interior ofS3.

The setK(S3) consists of all points in S3which belong to infinitely many caps. The setK(S3) is thus naturally homeomorphic to 3N. WheneverX3Ndoes not contain an equidistant triple, it corresponds via the natural homeomorphism to a subset ofK(S) whose convex hull is contained inS. IfX does contain an equidistant triple, then their corresponding points inK(S) are in three caps that separated from each other simultane- ously at some stage of the construction, so their convex hull meets one of the pyramids, and is thus not contained inS3. We have shown thatᏵ(S3)=3.

A straightforward generalization of this construction gives a contractible, compact SdRdso thatᏵ(Sd)=dfor alld3.

In R2 the construction is different. Let Cdenote the standard middle-third Cantor set, namely, the set of all points in [0, 1] whose base-3 expansion omits the digit 1. Fix

(8)

Figure 2.1

a continuously differentiable function f :CRwith the following property: for allx1<

x2inC,

(1) f(x1)<(f(x2) f(x1))/(x2x1)< f(x2) if and only if the first position in whichx1andx2have different digits in their base-3 expansions is even,

(2) f(x1)>(f(x2) f(x1))/(x2x1)> f(x2) if and only if the first position in whichx1andx2have different digits in their base-3 expansions is odd.

Such a function can be defined as a uniformly continuous limit of piece-wise linear functions.

LetS2be the union of all convex hulls of triangles{(x1,f(x1)), (x2,f(x2)), (x3,f(x3))} forx1< x2< x3inCfor which either all three pairs (xi,xj) for 0< i < j <3 satisfy condi- tion (1) or all three pairs satisfy condition (2) above. Call such a trianglehomogeneous.

It is not hard to verify thatS2 is closed, and uncountably convex and thatK(S) is exactly the graph of f, and is thus naturally homeomorphic to 2N. Furthermore, the convex hull of a subset ofK(S) is contained inSif and only if all triangles from the subset are homogeneous, which means that the set itself is homogeneous. This establishes that Ᏽ(S2)=2.

Finally,Ᏽ1, the ideal of countable subsets of 2N, is the convexity ideal of the standard

Cantor set.

We point out the following.

Fact 2.21. IfSR1is closed and uncountably convex, thenᏵ1Ᏽ(S).

Thus, up to equivalence, there is exactly one convexity ideal of a closed subset ofR. The following pattern of reducibility among convexity ideals is seen now inFigure 2.2:

there is a single ideal inR1. In each dimensiond+ 1 there is single setSd+1so that all convexity ideals inRd are reducible to its convexity ideal,Ᏽd+1. All convexity ideals are reducible to the meager ideal.

3. Expanding the methodology: proofs, cardinals, models, and consistency

If one wishes to know the structure of reducibility among convexity ideals up to equiva- lence, then one must answer the following.

(9)

I1

I2

Id

Id+1

M .. .

.. .

Figure 2.2

Question 3.1. Which of the reducibility relations inFigure 2.2are reversible?

This seemingly innocent question involves formal independence over the axioms of set theory. The usual axioms of mathematics do not decide the reversibility or irreversibility of any of the reducibilities in this figure. The next section will present the relevant facts about formal independence.

Meanwhile we begin by showing that if one assumes the continuum hypothesis as an additional axiom, then all convexity ideals (and many other ideals) are equivalent to each other, and thus, with the CH, the whole figure collapses to a single point modulo equivalence. Since the CH is a consistent axiom [6], this shows the inability to prove without additional assumptions that there are two inequivalent convexity ideals.

Theorem3.2. If the continuum hypothesis holds, then every properσ-ideal on the contin- uum which isσ-generated by continuum many generators is reducible to1, the ideal of countable subsets of2N.

Proof. Assuming CH, we identify the continuum with the ordinal ω1= {α:α < ω1}. Given a properσ-ideal᏶with dom᏶=ω1 which isσ-generated byω1 generators, fix an enumerationXα:α < ω1of a set of generators ofX.

Now for eachα < ω1, let f(α) :=min(ω1\

γαXγ). Since᏶is a properσ-ideal,ω1\

γαXγis nonempty, and the definition makes sense.

Suppose thatY ᏶. Since{Xα:α < ω1}σ-generates᏶, there is a countable set{αn: nN} ⊆ω1so thatA

nXαn. Every countable subset ofω1 is bounded inω1, hence α=sup{αn:nN}< ω1. Thus, for allα < β < ω1it holds that f(β)/ Y. In other words, f1[Y]α, and is therefore countable. Thus f is a reduction of᏶to the ideal of count-

able subsets ofω1.

Corollary3.3. The CH implies that all convexity ideals, the meager ideal, and the Lebesgue null ideal are equivalent to the ideal of countable sets, and therefore to each other.

(10)

Proof. The ideal of countable sets is trivially reducible to each convexity ideal, to the meager ideal, and to the Lebesgue null ideal. Since each convexity ideal in question is σ-generated by closed sets, and there are exactly continuum many closed subsets of any perfect Polish space, each of these ideals isσ-generated by continuum many generators, and by the previous theorem is reducible to the ideal of countable sets under CH.

We will argue soon that it is impossible to prove thatᏵdd+1for anyd1. This will necessitate a broadening of the methodology. We will need to make precise what a proof is and how one shows that a certain statement has no proof. We will also introduce the notion of acardinal invariant.

3.1. What is a proof? We adopt the notion of aformal proof from the Zermelo-Fraenkel axioms of set-theory with the axiom of choice (ZFC). A formal proof from a set of axioms in some formal languageᏸis a sequence of formulas, each of which is either an axiom in the set or is derived from earlier formulas in the sequence by some logicalinference rule. A formula with no free variables is asentence. A proof of a sentenceφis a proof whose last formula isφ. This (Hilbertian) notion of formal proof encompasses all proof methods which are accepted by mathematicians. A formal proof itself is afinite string of symbols.

Now that a formal proof is a finite mathematical object, the existence or nonexistence of a certain formal proof can be discussed mathematically.

The ZFC set of axioms are sentences in the language of set theory, which contains, apart from the logical symbols,,,,,¬, the relation symbols=and. ZFC is the standard axiomatization of set theory. Within ZFC all of mathematics can be formalized.

By this we mean the following: every mathematical object and relation can be represented as asetand every proof can be represented as a formal proof from the ZFC axioms.

We need now to clarify how one proves that a proof of a certain sentence from ZFC does not exist. This can be true only if a contradiction cannot be proved from ZFC, since the inference rules easily allow one to produce a proof of any sentence from a proof of a contradiction. A set of axioms from which no contradiction is provable is calledconsis- tent.

However, by G¨odel’s second incompleteness theorem, from ZFC itself there is no proof that ZFC is consistent—unless ZFC is inconsistent, in which case everything is provable from ZFC (including the statement that ZFC is consistent).

We assume from now on that ZFC is consistent. This assumption itself states thatsome sentences do not have a proof from ZFC; now it remains to find out which ones.

3.2. What is a model? Although a proof is a syntactic object, the usual method for show- ing that a certain proof does not exist is semantic. Amodelof ZFC is a set over which the relations=andare interpreted, and which satisfies all the axioms of ZFC.

Kurt G¨odel proved hiscompleteness theoremin his PhD thesis under Hahn in Vienna in 1930.

Theorem3.4. G¨odel[4]A sentenceφis formally provable from a set of axiomsΓif and only ifφholds true in every model ofΓ.

From G¨odel’s completeness theorem, a necessary and sufficient condition for the nonexistence of a proof of a sentenceϕfrom ZFC is the existence of a model of ZFC

(11)

in whichϕdoes not hold. InSection 3.5the method offorcing for constructing models of ZFC is briefly described.

3.3. Infinite cardinals. Recall the notion of an infinite cardinal. An infinite cardinal is an ordinal which does not have a bijection with a smaller ordinal. Thecardinalityof a setA, denoted by|A|is the unique cardinal number with whichAhas a bijection. For two setsA,B, it holds that|A| ≤ |B|if and only if there is an injection fromAtoBif and only if there is a surjection fromB ontoA. Any two infinite cardinals are comparable;

equivalently, for any two setsA,B, either there is a bijection fromAtoBor there is a bijection fromBtoA. The infinite cardinals are well ordered, so every nonempty set of infinite cardinals has a smallest member. All these facts about cardinals are ZFC theorems.

The cardinality ofNis the smallest infinite cardinal, named0. Every infinite cardinal has animmediate successor, and the immediate successor of0is1, its immediate suc- cessor is2and so forth. Cantor proved that|R|>0and conjectured that|R| = ℵ1. The statement|R| = ℵ1 is known asthe continuum hypothesisand was presented as the first problem in Hilbert’s list of problems in 1900. An equivalent formulation of the contin- uum hypothesis is that “every setARis either countable or equinumerous withR.”

In 1936, G¨odel proved that the continuum hypothesis could not be formally refuted from ZFC (see the 1940 monograph [6]), by providing a model of ZFC in which the statement|R| = ℵ1holds true.

In 1963, Paul Cohen invented the method of forcing for constructing models of ZFC, and using forcing he constructed a model in which|R| = ℵ2, namely in which the CH is false. Thus, Cohen showed that CH could not be proved from ZFC.

3.4. Cardinal invariants. A cardinal invariant is a definition of a cardinal number associ- ated with a structure. The simplest example of a cardinal invariant is|R|—the cardinality of the real line. G¨odel’s and Cohen’s results showed that it is impossible to determine|R|

from the ZFC axioms.

There are many cardinal invariants associated withR(a good survey of such invariants is [2]). We will concentrate on the following.

Definition 3.5. SupposeᏵis aσ-ideal over a perfect Polish space. Let cov(Ᏽ) be the least cardinality of a covering familyᏲᏵ.

Claim 3.6. Suppose that᏶is reducible toᏵ. Then cov(Ᏽ)cov(᏶).

Proof. Suppose that f : domᏵdom᏶is a reduction. ByClaim 2.3, for every covering familyᏳ᏶it holds thatᏲ:= {f1[Y] :Y }is a covering family ofᏵ, and clearly

|| ≤ ||.

3.5. The method of forcing andσ-ideals. Cohen’s forcing is a method for extending a given model of ZFC to a larger model of ZFC which contains a new object. A good analogy for forcing is extending a field to a larger field in which a given polynomial gains a new root. The polynomial is a finite description of the new root with coefficients in the old field. After adding a root of a polynomial to the field, one must add all its sums and products with old members of the field to obtain a field.

(12)

In forcing, it is a model of all ZFC which is extended. The description of the new object is not finite, but is a directed set of partial descriptions, calledforcing conditions, which belong to the old model.

In Cohen’s original forcing (which was designed to produce a model with the negation of CH) as well as in many other forcing notions, the forcing conditions are elements of aσ-ideal overR. The new object which the forcing adds is a real number. The partial description which is provided about the new real by a member of the ideal is that the real avoids it. ACohen realis added by the Cohen forcing, whose conditions are all closed and nowhere dense subsets ofRwhich belong to the ground mode, and thus a Cohen real is a new real which avoids all ground model nowhere dense sets.

A later forcing, due to Solovay, adds a new real which avoids all ground model null sets. Such a real is called arandom real.

Recall that the real line is a union of two disjoint sets,R=AB, whereAis meager andBis null. A Cohen real falls always intoBand into all translates ofB, and thus makes, in the extension, the set of old reals contained in a translate of a null set, and it is therefore null. A random real does the opposite: it turns the set of old reals into a meager set.

Thus, starting from a model of CH and adding2Cohen reals iteratively, one obtains a model in whichRis coverable by1Lebesgue null sets, but is not coverable by fewer than2meager sets. Conversely, the iterative addition of2random reals to a model of CH produces a model in whichRis coverable by1meager sets but not by fewer than2

Lebesgue null sets.

Letᏹdenote theσ-ideal of meager subsets ofRand letᏺdenote the ideal of Lebesgue null subsets ofR. The facts in the previous paragraph tell us the following.

Theorem3.7. If ZFC is consistent, there is no proof from ZFC thatis reducible toand there is no proof from ZFC thatis reducible to.

Proof. Suppose there was a proof thatᏺᏹ. Then byClaim 3.6we have a proof that cov(ᏺ)cov(ᏹ). But then this inequality has to be true in all models of ZFC—contrary to the existence of a model in which cov(ᏺ)= ℵ2>1=cov(ᏹ).

Similarly, the other direction is proved.

3.6. Equality, incomparability, inequality, and irreversible inequality. Now comes the main methodological point regarding the comparison of cardinal invariants.

Definition 3.8. Suppose thatᏵand᏶areσ-ideals which areσ-generated by some defin- able collection of closed subsets of a Polish space. Write

cov(Ᏽ)cov(᏶) (3.1)

if

(1) cov(Ᏽ)cov(᏶) inallmodels of ZFC,

(2) there is at least one model of ZFC in which cov(Ᏽ)<cov(᏶).

This relation can be called “irreversible inequality” or “consistently strict inequality.”

We remark that apart from=,, andthere is a fourth relation between cardinal invariants, which, for example, cov(ᏺ) and cov(ᏹ) satisfy:incomparability, namely that

(13)

neither cov(Ᏽ)cov(᏶) nor cov(᏶)cov(Ᏽ) are provable in ZFC, or, equivalently, that there are some models of ZFC in which cov(Ᏽ)<cov(᏶) and other models in which cov(᏶)<cov(Ᏽ).

4. Covering numbers of convexity ideals

We return now from the short guided tour in mathematical logic to convexity ideals and see what can be said about them in the expanded context that was set in the previous section.

We now show that none of the reductions we proved inSection 2.3are reversible. What does this mean in practice? That whatever effort, ingenuity, or technique one may invest in trying to prove, say, thatᏵdd+1, the attempt will not be successful. Why? Because an acceptable proof can be transformed into a formal proof, and there is no such formal proof—if ZFC is consistent.

Theorem4.1. For everyd1, it holds thatcov(Ᏽd+1)cov(Ᏽd).

For establishing this, one should, for everyd, provide a model in which cov(d+1)<

cov(Ᏽd). Something better may be done.

Theorem4.2 [10]. For everyd3, there is a model of set theory in whichc>cov(Ᏽ3)>

···>cov(Ᏽd).

There is also a model [4] in whichc>cov(Ᏽ2) and a model in which cov(Ᏽ2)>cov(I3).

We know thatᏵd+1Ᏽ(S) for all closedSRd, but it could still be the case that there are two convexity ideals of closed subsets ofRd which are incomparable or satisfy the relation. However, we have no example of two incomparable convexity ideals. In other words, we have no evidence that the set of all convexity ideals of closed subsets inRdfor alld1 is not linearly ordered by.

Theorem 4.3 (Geschke [6]). For eachd, there is a model of ZFC in whichcov(Id+1)<

cov(Ᏽ(S))for all closed uncountably convexSRd.

Geschke’s proof utilizes a geometric property common to all convexity ideals inRd to separate them fromᏵd+1.

The results quoted so far, show thatFigure 2.2is indeed the right figure for the relation of irreversible inequality.

It is still open whether there may be inRd a closed set whose convexity ideal is not equivalent toᏵdfor somedd. For all we know, inRdthere may just be thedinequiva- lent convexity ideals we have listed, which are linearly ordered by irreversible reducibility.

Even if there are convexity ideals inRd which were not spotted yet, the following weaker statement, phrased in the language of cardinal invariants and formal consistency, may still be true.

Conjecture 4.4(the dimension conjecture). There may bed, but no more thanddifferent uncountable convexity numbers of closed subsets ofRdin a single model of set theory.

In dimensiond >2, this conjecture is “open at both ends.” First, it is not known if one can get all covering numbers ofᏵ1throughᏵdto be different than each other in a single

(14)

model of ZFC. This is a problem in the technology of forcing. So at the moment only d1 different numbers are attained ford >2.

At the other end, there is no known classification of convexity ideals inRd ford >1.

This problem is geometric. Also, there is no upper bound on the number of different covering numbers of convexity ideals inRdford >2.

5. Convexity ideals inR2, Ramsey ideals, and functions ideals

The dimension conjecture has been proved ford=2. The proof does not determine the structure of convexity ideals inR2 under. It utilizes the fact that convexity ideals in R2which are not equivalent toᏵ1 are sandwiched between Ramsey ideals from above, and ideals of continuous functions on 2N, and the ideal ofσ-compact subsets ofNNfrom below.

The important property of functions ideals is that their covering numbers are either 20 or the immediate predecessor of 20; the important property about Ramsey ideals is that each of them is 1. Apart from settling the dimension conjecture ford=2, Ramsey ideals and functions ideals have very appealing properties and are related to both analysis and graph theory. We will survey now the relations among those types of ideals.

A complete picture of what is known is presented inFigure 5.1.

We begin by introducing the players.

5.1. Ramsey ideals. We start by generalizing the definition of the idealᏵ2. Observe that the two-place function∆is symmetric and satisfies that if∆(x,y)=dand min{∆(x,x),

∆(y,y)} ≥d, then∆(x,y)=d. In particular, if parity(∆(x,y))=i,i∈ {0, 1}andx is sufficiently close tox,ysufficiently close toy, then parity(∆(x,y))=ias well. This is a continuity condition, which we now state precisely.

Definition 5.1. For a topological spaceX let [X]2 denote the quotient of the product topology onX2\ {(x,x) :xX}over the equivalence relation (x,y)(y,x).

A function c: [X]2→ {0, 1}is called a continuous coloring if cis continuous with respect to the topology on [X]2.

Definition 5.2. Suppose thatc: [X]2→ {0, 1}is a continuous coloring. A subsetY X is calledc-homogeneous ifc[Y]2is constant. LetᏵcbe theσ-idealσ-generated by all c-homogeneous subsets ofX.

We definecmin: [2N]2→ {0, 1} bycmin(x,y)=parity(∆(x,y)). This is a continuous coloring. Furthermore, the definition ofᏵ2gives us immediately that

cmin=2. (5.1)

Fact 5.3. SupposeXis a Polish space andc: [X]2→ {0, 1}is a continuous coloring. Then Ᏽcis proper if and only if there is a perfectPXso thatᏹ(P)c.

Proof. One direction is trivial. For the other direction, suppose thatᏵc is proper. Let Abe the union of all open sets which belong toᏵc. ThenAis open and belongs itself toᏵc. LetP=X\A. Clearly,P nonempty and perfect. The continuity ofcimplies that

(15)

(1) (2) (3) (4) (5) (6)

d

covCont(R)=covCont(ωω)=covCont(2ω) covLip(R)covLip(ωω)=covLip(2ω)=cov(cmin)

cov(cmax) 20

covCont(2ω)

+

Figure 5.1

a closure of ac-homogeneous set isc-homogeneous, thus everyc-homogeneous subset ofPis nowhere dense. Now the identity function onPis a reduction ofᏹ(P) toᏵc. From now on we will assume, by replacing a givenc: [X]2→ {0, 1}byc:[P]2, that all continuous colorings we consider satisfy that no open set is homogeneous.

Fact 5.4. SupposeXis a perfect Polish space andc: [X]2→ {0, 1}has no open homoge- neous set. ThenᏵcminc.

The proof is straightforward.

Theorem5.5 [5]. There exists a continuous pair-coloringcmax: 2N→ {0, 1}so that for all continuous pair-coloringc:X→ {0, 1}with no open homogeneous sets on some Polish space X, it holds that

covcmin

covc

covcmax

. (5.2)

It is interesting to point out thatcmaxis defined on a compact space.

Theorem5.6. There is a model of ZFC in whichcov(Ᏽcmax)<20. In particular,cmax1

and consequentlyc1for every continuous pair-coloringcon a Polish space.

5.2. Functions ideals over the square. LetXbe any infinite set. Let Func(X) be the ideal generated overX2by all graphs and inverses of graphs of functions fromXtoX.

A covering collection in Func(X) is a setᏲof functions fromX toX so that for all (x1,x2)X2, there is f Ᏺso that f(x1)=x2orf(x2)=x1.

Theorem5.7 (Sierpi ´nski). For every infinite cardinalα+1, it holds thatcov(Func(α+1))= αand ifαis limit, thencov(Func(α))= ℵα.

(16)

In particular, there are countably many functions fn:1→ ℵ1so that for allα,β∈ ℵ1, there is somenso that fn(α)=βor fn(β)=α. Thus, the following holds.

Corollary5.8. The CH implies thatcov(Func(R))= ℵ0.

In the case CH holds, Func(R) is not contained in a properσ-ideal overR.

The graph of acontinuousfunction fromRtoRis, though, a nowhere dense subset ofR2. Thus the graphs and inverses of graphs of continuous real functions do generate a properσ-ideal overR2.

Definition 5.9. SupposeX is a metric space. Then Cont(X) is the σ-ideal which is σ- generated overX2by graphs and inverses of graphs of continuous functions fromX to X. Lip(X) is theσ-ideal which isσ-generated overX2by graphs and inverses of graphs of Lipschitz continuous functions.

Since Lip(X)Cont(X)Func(X) for every metric spaceX, one has trivially covLip(X)covCont(X)covFunc(X). (5.3) Hence, by Sierpi ´nski’s theorem we have the following important fact.

Fact 5.10. For every perfect Polish spaceX,

covCont(X)+max 2, 20. (5.4) Proof. Since cov(Cont(X))≥ ℵ1, it holds that (cov(Cont(X)))+≥ ℵ2 for every perfect Polish X. That (cov(Cont(X)))+20 follows directly from Sierpi ´nski’s theorem and

|X| =20.

The relation between functions ideals and convexity ideals is set via the following.

Theorem5.11. Lip(2N)and2are equivalent.

By what we have seen so far,Ᏽ2plays three different roles: it is a convexity ideal inR2, it is the bottom (with respect to reducibility) Ramsey ideal, and is also (equivalent to) the Lipschitz ideal Lip(2N). We remark thatᏵ2is actually isomorphic to the ideal Lip1,1/2(2N) which isσ-generated over (2N)2 by all graphs of functions satisfying the Lipschitz con- dition with Lipschitz constant 1 and all inverses of graphs of functions which satisfy the Lipschitz condition with Lipschitz constant 1/2 (see [5]).

We quote the following result from [5].

Theorem5.12. There is a model of ZFC in whichcov(Cont(R))= ℵ1andcov(Lip(R))= 2. ThereforeCont(R)Lip(R).

We remark that by Stepr¯ans’ [15] also theσ-idealσ-generated overR2 byC1 func- tions is not equivalent toᏵ1. However, theσ-ideal which isσ-generated overR2by twice differentiable function is equivalent toᏵ1by the following result from [1].

Theorem5.13 [1]. There exists a differentiable functionf :RRand an infinite perfect setPRsuch that the derivative of f is constantly0onPand no function which is twice differentiable intersects f Pin infinitely many points.

参照

関連したドキュメント

The notions of convexity and convex polytopes are in- troduced in the setting of tropical geometry.. Combinatorial types of tropical polytopes are shown to be in bijection with

We also show that every Noetherian local ring in which every two-element sequence is of linear type is an in- tegrally closed integral domain and every two-generated ideal of it can

(The origin is in the center of each figure.) We see features of quadratic-like mappings in the parameter spaces, but the setting of elliptic functions allows us to prove the

Two important facts about quadratic forms over local fields are these: any non-degenerate quadratic space of dimension five or more is isotropic, and there is, up to isometry, a

To study the existence of a global attractor, we have to find a closed metric space and prove that there exists a global attractor in the closed metric space. Since the total mass

If in the infinite dimensional case we have a family of holomorphic mappings which satisfies in some sense an approximate semigroup property (see Definition 1), and converges to

proof of uniqueness divides itself into two parts, the first of which is the determination of a limit solution whose integral difference from both given solutions may be estimated

Note also that our rational result is valid for any Poincar´e embeddings satisfying the unknotting condition, which improves by 1 the hypothesis under which the “integral” homotopy