Pambuccian - A Methodologically Pure Proof of a Convex Geometry Problem.pdf

(300 KB) Pobierz
646210646 UNPDF
Beitr¨agezurAlgebraundGeometrie
ContributionstoAlgebraandGeometry
Volume42(2001),No.2,401-406.
AMethodologicallyPureProofof
aConvexGeometryProblem
VictorPambuccian
DepartmentofIntegrativeStudies,ArizonaStateUniversityWest
P.O.Box37100,PhoenixAZ85069-7100,USA
e-mail:pamb@math.west.asu.edu
Abstract. Weprove,usingtheminimalistaxiomsystemforconvexgeometry
proposedbyW.A.Coppel,that,givennredandnbluepoints,suchthatnothree
arecollinear,onecanpaireachoftheredpointswithabluepointsuchthatthen
segmentswhichhavethesepairedpointsasendpointsaredisjoint.
MSC2000:51G05,52A01,52B11,51K05
TheproblemstatedintheabstractappearedasproblemA-4onthe1979NorthAmericanW.
L.PutnamCompetition.Therethe2npointsareconsideredtobeinthestandardEuclidean
plane.Asstatedbyus,asatheoremofCoppel’sminimalistconvexgeometry,thisproblem
isastatementthatdescribesauniversalpropertyofanyreasonablegeometricorderrelation,
whichwebelieveisgeneralandinterestingenoughtojustifyastudyofitspossibleproofs.
HereistheonlyproofIknowtoexistinprint(inboth[8]and[5]):
“Thereisafinitenumber(actuallyn!)ofwaysofpairingeachoftheredpointswithablue
pointina1-to-1way.Hencethereexistsapairingforwhichthesumofthelengthsofthe
segmentsjoiningpairedpointsisminimal.”Itisthenshownthatforsuchapairingnotwo
ofthensegmentsintersect.
Thereisamajordiscrepancybetweenthestatementofthisproblemanditsproof.In
thestatementthereappearonlynotionsofbetweennessandcollinearity,whereastheproof
usesthenotionoflength.Thisgoesagainsttheprincipleof purityofthemethodofproof ,
enunciatedbyHilbertacenturyago:
“Inmodernmathematics[...]onestrivestopreserve thepurityofthemethod,i.e.tousein
0138-4821/93$2.50c2001HeldermannVerlag
402 V.Pambuccian:AMethodologicallyPureProofofaConvexGeometryProblem
theproofofatheoremasfaraspossibleonlythoseauxiliarymeansthatarerequiredbythe
contentofthetheorem .”([7,p.27]) 1
Ascontributionstothisprogramme,ofprovidingmethodologicallypureproofsofimpor-
tantgeometryproblemsweciteH.S.M.Coxeter’sprooffromaxiomsofbetweennessand
incidenceoftheSylvester-Gallaiproblem([3],[4]),andtheproofsfromaneaxiomsofa
generalizedEulerlinetheorembyA.W.Boon[1]andE.Snapper[12].
Theproofthatweshallpresent,whichrespectstheHilbertianpurityrequirement,pro-
ceedsinsidethefollowingaxiomaticframework:
Thereisonekindofindividualvariables, points ,andaternaryrelationamongpointsBof
betweenness (withB(abc)tobereadas‘bliesbetweenaandc(bcouldbeequaltoaorto
c)’).Whenwesay‘segmentabintersectssegmentcd’wemean‘thereisapointx,dierent
froma,b,c,dsuchthatB(axb)andB(cxd)’,andwhenwesaythat‘x,yandzarecollinear’
(forwhichweusetheabbreviationL(xyz))wemeanB(xyz)_B(yzx)_B(zxy).Theaxioms
are:
A1 B(aab)
A2 B(aba)!a=b
A3 B(abc)!B(cba)
A4 B(abc)^B(acd)!B(bcd)
A5 b 6=c^B(abc)^B(bcd)!B(acd)
A6 a 6=b^B(acb)^B(adb)!B(acd)_B(adc))
A7 a 6=b^B(abc)^B(abd)!B(acd)_B(adc)
A8 (8ab 1 b 2 cd)B(acb 1 )^B(cdb 2 )!(9b)B(b 1 bb 2 )^B(adb)
A9 (8ab 1 b 2 c 1 c 2 )B(ac 1 b 1 )^B(ac 2 b 2 )!(9d)B(b 1 dc 2 )^B(b 2 dc 1 )
Thisaxiomsystemisequivalenttotheaxiomsystemconsistingof(L1)–(L4),(C)and(P)
in[2].Themaindierenceconsistsintheadoptionofthebetweennesspredicateasonly
primitivenotion,inthespiritof[14],asopposedtousingpointsandsegmentsandan
incidencerelationbetweenthem,asdonein[2].AxiomsA1–A7areequivalenttotheaxioms
(L1)–(L4),andA8,A9arerestatementsofaxioms(C)and(P)respectively,whichareforms
ofthePaschaxiom,the‘outerform’andthe‘innerform’.ModelsoftheaxiomsA1–A9will
becalled lineargeometries .Let L bealineargeometry.Ifxandyaretwopointsin L ,then
wedenoteby[x,y]the segment xy,thesetofallpointszwithB(xzy),and,forx 6=y,by
hx,yi,the line xy,thesetallpointszwithL(xyz).AsubsetCof L iscalled convex ( ane )
ifitcontains[x,y](respectivelyhx,yi)forallx,y2C.Theconvex(ane)hullofasubset
Aof L isdefinedtobetheintersectionofallconvex(respectivelyane)setscontainingA,
1 “IndermodernenMathematik(wird)solcheKritiksehrh¨aufigge¨ubt,woherdasBestrebenist, dieRein-
heitderMethodezuwahren,d.h.beimBeweiseeinesSatzeswom¨oglichnursolcheH¨ulfsmittelzubenutzen,
diedurchdenInhaltdesSatzesnahegelegtsind. ”
V.Pambuccian:AMethodologicallyPureProofofaConvexGeometryProblem 403
andisdenotedby[A](resp.hAi).Theconvexhullofafinitesetiscalleda polytope .Apoint
eofasubsetSof L iscalledan extreme pointofSifS\{e}isconvex.A face ofaconvex
setCisasetAsuchthatC\hAi=AandC\Aisconvex.Adimensiontheorymaybe
developedforanesets,asshownin[2],andinthecaseofpolytopesalldimensionsinvolved
arefinite.ThenotationdimSreferstodimhSi.AsubsetHofafinitedimensionalane
setAiscalleda hyperplane inAifdimH=dimA−1.AfaceFofapolytopePisa facet
( edge )ifFisahyperplaneinhPi(resp.dimF=1).
Herearesomefactsaboutpolytopes,provedin[2],thatweshalluseinthesequel:
(i)Anytwopointseande 0 intheextremesetSofapolytopePcanbeconnectedinSby
edgesofP(see[2,IV.Prop.23]).
(ii)IfFandGarefacesofapolytopePsuchthatFG,thenthereexistsafinitesequence
F 0 ,F 1 ,...,F r offacesofP,withF 0 =FandF r =G,suchthatF i− 1 isafacetofF i for
i2{1,...,r}(see[2,IV.Cor.16]).
(iii)IfFisafaceofapolytopePwithdimF=dimP−2,thenFiscontainedinexactly
twofacetsofPandistheirintersection(see[2,IV.Prop.15]).
Ourproblemcanberestatedasfollows:
Leta 1 ,...,a n andb 1 ,...,b n bepoints,suchthatnothreeofthemarecollinear.Thenthere
isapermutation 2 of{1,...,n}suchthatnotwosegments[a i ,b ( i ) ]and[a j ,b ( j ) ]withi 6=j
intersect.
Intheformallanguageofouraxiomaticsthiscanbeexpressed,foreveryn2,asthe
sentence' n :
1 i<j<kn (L(a i a j a k )_L(b i b j b k )) W
W
2S n ((8x) V
1 i<jn, 1 kn (L(a i a j b k )_L(a i b j b k ))
1 i<jn ¬(B(a i xb ( i ) )^B(a j xb ( j ) ))).
Wefirstprovethefollowing
Lemma. Givenaset S of n points,withnothreecollinear, p anextremepointofthe
polytope P:=[S] ,andanaturalnumber k with 1k < n ,onecanpartition S intotwo
subsets U k and V k ,suchthat U k contains k points, p2V k ,and [U k ]\[V k ]=; .
Proof. LetdbethedimensionofS.Ifd=2,then,by(ii)and(iii)thereareexactlytwo
edges(whicharefacetsinourcase),hp,q 1 iandhp,rithatcontainp.Weshallconstructa
sequenceofsubsetsQ i ofS,fori=1,...n−1,asfollows:letQ 1 ={q 1 },andsupposethat
Q i with1i < n−1hasalreadybeenconstructed.Denotebyq i +1 thepointinSforwhich
hp,q i iisoneoftheedgesthatcontainpinthepolytope[S\Q i ](theonedierentfromhp,ri,
fori < n−2;fori=n−2wesetq i +1 :=r),andletQ i +1 =Q i [{q i +1 }.Thetwosets
U k =Q k andV k =S\U k havethedesiredproperties(bythedefinitionoffacets,andthe
factthattherearenothreecollinearpoints).
Supposenowthatthestatementofthelemmahasbeenestablishedforalldimensions
< d.LetLbead−2-dimensionalfaceofPcontainingp,andletHandH 0 bethetwo
facetsofPthatcontainL(cf.(ii)and(iii)).WeshallconstructasequenceofsubsetsU i of
Shavingielements,withi=1,...,n−1.WestartwithJ 1 :=((H\S)\L)[{p},whichis
afinitesetofpointscontainingp,ofdimensiond−1,so,byourinductivehypothesis,there
2 Thesetofallpermutationsof{1,...,n}willbedenotedbyS n .
(8a 1 ...a n b 1 ...b n ) W
404 V.Pambuccian:AMethodologicallyPureProofofaConvexGeometryProblem
andsupposethatJ h hasbeendefinedforall1hm.Let= P m h =1 (|J h |−1)andsuppose
U hasbeendefinedaswell.LetJ m +1 be:
(a)thesetofallpointsofScontainedinthefacetcontainingLthatisdierentfromH 0 of
thepolytope[(S\([ m i =1 J i ))[{p}],ifthatpolytopeisd-dimensional;
(b)thesetofallpointsofScontainedinH 0 ,if(S\([ m i =1 J i ))iscontainedinH 0 .
Byourinductivehypothesis,therearepartitionsofJ m +1 intotwosubsetsA m +1 ,j andB m +1 ,j ,
suchthat[A m +1 ,j ]\[B m +1 ,j ]=;,A m +1 ,j hasjelements,andp2B m +1 ,j ,forany1j <
|J m +1 |.LetU + i =U [A m +1 ,i for1i|J m +1 |−1.Since(b)mustoccurafterafinite
numberofsteps,wehavedefinedU i foralli2{1,...,n−1}.ThedesiredpartitionofSis
obtainedbysettingV k =S\U k ([U k ]\[V k ]=;isaconsequenceofthedefinitionoffaces
andfacets).
2
Theorem. Forall n1' n isvalidinalllineargeometries.
Proof. LetSbeasetofnredandnbluepoints(amoresuggestivewaytorefertoa 1 ,...,a n
andb 1 ,...,b n ),nothreeofwhicharecollinear.
Theproofthatthesentences' n holdinlineargeometrywillproceedinductivelyonn.
Forn=1thestatementisvacuouslytrue.Supposenowthatn2andthatthevalidityof
' i hasbeenestablishedforall1in−1.Wewillshowthat' n mustholdaswell.If
therearetwoextremepointsofSofdierentcolour,thenwearedone,sinceby(i)theycan
beconnectedbyedgeswhoseendpointsareextremepointsofS.Oneofthoseedgesmust
havedierentcolouredendpoints,saye 1 ande 2 ,whicharepointsofS,andthusonecan
partitionSintotwosetswithanequalnumberofredandbluepoints,namelyS 0 ={e 1 ,e 2 }
andS 00 =S\S 0 .SinceinS 00 therearen−1pointsofeachcolour,theredonescanbe
pairedwiththeblueonessuchthatthesegmentsthathavethosepairsasendpointsdonot
intersect.Addingtothatpairingthepair(e 1 ,e 2 ),weobtainthedesiredresult,sincethe
segment[e 1 ,e 2 ]isanedge,thuscannotbeintersectedbyanysegmentwithendpointsinS 00 .
Sofromnowon,weshallassumethatthesetofextremepointsofSismonochromatic,
sayblue.LetpbeanextremepointofS.BytheaboveLemma,thereis,foreverykwith
1k2n−1apartitionofSintotwosetsU k andV k suchthatp2V k ,U k haskpointsand
[U k ]\[V k ]=;.Noticethat,bytheconstructionofthesetU k describedintheaboveLemma,
U 1 containsanextremepointofS,thusabluepoint,andthatU 2 n− 1 containsallthepoints
exceptp,somoreredpointsthanbluepoints.Thusthereexistsakwith1kn−1for
whichU 2 k (andthusV 2 k aswell)containsanequalnumberofredandbluepoints.Sinceboth
' k and' n−k havebeenassumedtobetrue,thereisapairingoftheblueandredpointsin
U 2 k andV 2 k suchthattherespectivesegmentsdonotintersect.Giventhat[U 2 k ]\[V 2 k ]=;,
thesegmentswithendpointsinU 2 k cannotintersectthoseinV 2 k ,sowehaveobtainedthe
desiredpairingofthepointsinS.
2
Isourproofofthestatements' n inastrictsense superior totheproofpresentedin[8]and[5]?
Inotherwordsdoesthatproofrequirestrictlystrongerassumptionsthanours?Theanswer
is,surprisingly,No!Thatproofcanbedoneinsideanaxiomsystemthatisincomparableto
ours.Toseethat,noticethatwhatwasneededintheargumentoftheproofin[8]and[5]
arepartitionsofJ 1 intotwosubsetsA 1 ,j andB 1 ,j ,suchthat[A 1 ,j ]\[B 1 ,j ]=;,A 1 ,j hasj
elements,andp2B 1 ,j ,forany1j <|J 1 |.LetU i :=A 1 ,i for1i|J 1 |−1.Letm1,
V.Pambuccian:AMethodologicallyPureProofofaConvexGeometryProblem 405
wasanabilitytoaddthelengthsofsegments,compareanytwosegments,andthetriangle
inequality(whichisusedintheproofthattheblue-redpairingwithminimalsumofthe
lengthsisthedesiredpairing,fortheassumptionofanintersectionoftwosegmentswithred
andblueendpoints[r,b]with[r 0 ,b 0 ],would,viatriangleinequality,leadtotheconclusion
thatthesumofthelengthsof[r,b 0 ]and[r 0 ,b]islessthanthatof[r,b]and[r 0 ,b 0 ],which
contradictstheminimalityofthesumofthepairingthatpairedrwithbandr 0 withb 0 ).An
axiomsystemforatheorythatallowsonetodo just thatwasproposedbyM.Moszy´nska
[10].Thataxiomsystem,say,isformulatedinalanguagewithonesortofindividuals,
points ,andtwoprimitivenotions,aquaternaryoneof equidistance ,,withabcdtobe
readas‘thesegmentsabandcdareequalinlength’,andaternaryonefor betweenness ,B.
Giventhatissomewhatinvolved,weshalldescribeitsmodels,andreferto[10]foritself
(cf.also[9]).LetXbeaset,Gbean(additive)Abelianorderedgroup,and%:X×X!G
a regularmetric ,i.e.afunctionsatisfyingthefollowingproperties:
%(a,b)0;%(a,b)=0$a=b;%(a,b)=%(b,a),%(a,b)+%(b,c)%(a,c);
2S n [ V n i =1 (%(q 0 ,q i− 1 )+%(q i− 1 ,q i )=%(q 0 ,q i )
^%(q i− 1 ,q i )=%(a ( i ) ,b ( i ) ))];
(8abca 0 c 0 )(9b 0 )%(a,b)+%(b,c)=%(a,c)^%(a,c)=%(a 0 ,c 0 )
!%(a,b)=%(a 0 ,b 0 )^%(b,c)=%(b 0 ,c 0 ).
EverymodelofisasetX,equippedwitharegularmetric%,suchthatabcdifandonly
if%(a,b)=%(c,d)andB(abc)ifandonlyif%(a,b)+%(b,c)=%(a,c).OftheaxiomsA1–A9
forB,onlyA1–A4areconsequencesof.Noticethatthetriangleinequalityisessential
forthe' n tobetrueinatheoryofmetricbetweennessandequidistance.Tobeprecise,
evenifallotheraxiomsofplaneEuclideangeometryoverPythagoreanfieldshold,butthe
triangleinequalityfails,' 2 neednothold.Inparticular,thismeansthatsomeformofthe
Paschaxiom,fromwhichthetriangleinequalitymaybededuced(inthepresenceofthe
customaryaxiomsforequidistanceandbetweenness),inouraxiomsystemA8andA9,is
indispensablefortheproofof' 2 .Itwasshownin[6]and[11]thatthetriangleinequalityis
strictlyweakerthanthePaschaxiominacertainaxiomsystemforplaneEuclideangeometry
overPythagoreanfields.Thustherearemodelsofthatarenotlineargeometries,sois
notstrongerthanA1–A9.
Toseethat' 2 doesnotholdinanaxiomsystemforplaneEuclideangeometryinwhich
thetriangleinequalitydoesnothold,weshalluseSzczerba’s[13]methodofconstructing
semi-ordersofthefieldofrealnum b ers.Letab ea transce nden talnumberinR,satisfying
0< a <1.ThenX={1,a,a 2 , a 2 p 2
a +1 },asasubsetofthevector
spaceRoverQislinearlyindependent,soitcanbeextendedtoabaseBofRoverQ.Let
b i withi=0,...,7betheenumerationoftheelementsofXintheorderinwhichthey
arewritteninX,andsupposealltheelementsofBareindexedbyasetIthatincludes
{1,...,7}.Themapping :B!R,definedby (b i )=b i foralli2I,excepti=3and
7,forwhich (b i )=−b i ,canbeextendedbylinearitytoanisomorphismofvectorspaces
f :R!R.LetPbethesetofallpositivenumbersofR.ThenR:=hR,f(P)iisa
semi-orderedfield,withx < yifandonlyify−x2f(P)(theorderrelationisclosedunder
additionbutnotundermultiplication).Then,inR×R,betweennessandequidistancecan
bedefinedasinregularmetricspaces,withthemetric%definedby%((x 1 ,x 2 ),(y 1 ,y 2 ))=
a +1 , a (1 −a ) p 2
a +1 , a ( a− 1) p a 2 +1
(8a 1 ...a n b 1 ...b n )(9q 0 ...q n ) W
a +1 , a p a 2 +1
 

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin