Eine Beweisanalyse durch Abstraktion

Math. Semesterber. (1993) 40: 159-172

Eine Beweisanalyse durch Abstraktion

Günter Pickert

Eichdorffring 39, D-35394 GieBen

Eingegangen am 21.3.1992, angenommen am 17.6.1992

MathematischeSemesterberichte

© Springer-Ver1ag 1993

Zusammenfassung. Die Bestimmung einer unteren Schranke fiir die Anzahl der auseiner endlichen ebenen Punktmenge zu bildenden Mittelpunkte wird durch Abstraktionzu einer entsprechenden Aufgabe fiir eine angeordnete abelsche Gruppe. Dadurch wirdder Beweis fiir die ermittelte Schranke analysiert und durchsichtiger.

Einleitung

"AlI right" said the cat, and this time it vanished quite slowly, beginning with theend of the tail and ending with the grin, which remained sorne time after the rest ofit had gone. Lewis Carroll (in "Alice in Wonderland")

Mit dem Übergang von der grinsenden Katze zum reinen Grinsen hat nach Meinung von M. Gardner [2, S.91] der Mathematiker Dogdson (= Carroll) wohl dengerade in der Mathematik üblichen AbstraktionsprozeB beispielhaft beschreiben wollen. Man muB allerdings dazu bemerken, daB - um im Bild zu bleiben - die Katzedurchaus nicht wirklich verschwinden muB; nur wird ihr - yom Grinsen eben abgesehen - keine Beachtung mehr geschenkt. Der so verstandene AbstraktionsprozeBsollte didaktisch nicht als Erschwerung, sondern als Vereinfachung des Beweisens angesehen werden: Man arbeitet das wirklich beim Beweis Benôtigte heraus und wirddurch Nebensâchliches nicht mehr abgelenkt. Implizit entstehen bei einer derart vereinfachenden Beweisanalyse neue mathematische Begriffe (s. hierzu [4]), in denen diefiir die Beweise benëtigten Voraussetzungen zusammengefaBt sind und die dadurchmotiviert werden.

Eine Aufgabe der Asian Pacifie Mathematics Olympiad 1991 lautet [3, S.49]:Suppose there are 997 points given on a plane. If every two points are joined by aline segment with its mid-point coloured in red, show that there are at least 1991 redpoints on the plane. Can you find a special case with exactly 1991 red points?

lm folgenden son nun anhand einer Lôsung dieser Aufgabe beispielhaft eine Beweisanalyse durch schrittweise Abstraktion durchgeführt werden. In Abschn. 2 ist dabei als Durchgangsstufe eine nicht so zweckmâêige Abstraktion gewâhlt, die dann in

160 G. Pickert

Abschn.3 sinnvoll modifiziert wird, wobei der Beweis von Satz 3 eine von Abschn. 2vëllig unabhângige Darstellung Iiefert; in ibm wird fur (additiv geschriebene) angeordnete abelsche Gruppen zu jeder natürlichen Zahl n ~ 2 das Minimum der Anzahlder Summen von je zwei Elementen aus einer n-elementigen Teilmenge bestimmt.Es ergibt sich dadurch eine bessere Einsicht in die beim Beweis benôtigten Voraussetzungen und ihren Einsatz. Die Abschn.4, 5 zeigen Verbindungen mit der Theorieder angeordneten Gruppen auf und motivieren so den Einstieg in diese Theorie. Dabei wird in Abschn.4 fur eine angeordnete abelsche Gruppe (A, +) gezeigt, daB auch(Ad, +)(d E N) angeordnet werden kann, bei archimedischer Anordnung von (A, +) sogar ebenfalls archimedisch. Satz 4 in Abschn. 5 stellt fest, daB die Minimum-Aussagevon Satz 3 für eine abelsche Gruppe genau dann gilt, wenn diese torsionsfrei oderaber die direkte Summe einer dreielementigen Gruppe mit einer torsionsfreien Gruppeist. In Abschn.6 verallgemeinert Satz 5 den Satz 3 auf Anzahlen der Summen von kElementen.

1

Zuerst wird man von den offenbar lediglich kalendarisch bestimmten Zahlen 997,1991 wegkommen wellen. Ersetzt man die erste von ihnen durch eine Variable n(fur natürliche Zahlen ;::: 2), so fragt sich, welcher Term (in n) an die Stelle derzweiten Zahl zu treten hat. Für n = 2 oder = 3 muB er offenbar den Wert 1 bzw.3 annehmen. AIs einfachsten ganzrationalen Term mit diesen beiden Eigenschaftenerhâlt man 2n - 3, und dieser liefert fur n =997 auch tatsachlich den Wert 1991.Man vermutet daher als Verallgemeinerung der Aufgabe (in Abstraktion von den indieser gewâhlten Zahlen) den

Satz, FUr n (;::: 2) Punkte in der euklidischen Ebene gilt, wenn m die Anzahl derMittelpunkte von je zweien von ihnen ist,

(1) m ~ 2n- 3;

zu jeder natürlichen Zahl n (~ 2) kann man in der Ebene n Punkte so wâhlen, dajJ in(1) das Gleichheitszeichen. gilt.

Beweis. N sei die Menge der n Punkte. Wegen

2n - 3 =(n - 1) + (n - 1) - 1

liegt es nahe, zu jedem x E N die Menge Mx der Mittelpunkte der Strecken xy mityEN" {x} zu bilden, fur die also

IMxl=n-l

gilt. Dm fur zwei Punkte, a, b,E N nun

zu erreichen und damit (1) zu beweisen, braucht man wegen

nur a, b so zu wâhlen, daB

Eine Beweisanalyse durch Abstraktion 161

IManMbl = 1

gilt. Der Mittelpunkt von ab gehôrt natürlich zu Man Mb. Damit diese Menge keinenweiteren Punkt enthâlt, sich Ma, Mb also mëglichst wenig "sWren", wird man diePunkte a, b môglichst weit auseinander wâhlen. Für den Abstand labl der Punktea, bEN bedeutet das

(2) labl =max{lxyll x,y E N, x #- y}.

Wegen INI EN" {1} ist eine solche Wahl stets môglich. Man hat jetzt nur noch zuzeigen, daB cE Man Mb der Mittelpunkt von ab sein muB. Nach der Voraussetzungüber e gibt es a' EN" {a}, b' EN" {b} derart, daB e sowohl Mittelpunkt von aa'

-r-z-]

wie von bb , also

(3)

ist. Nach (2) hat man also

laa'i =2lael, Ibb'l =21ebl

21ael , 21ebl ~ labl .

Damit reduziert sich der Beweis des ersten Teiles von Satz 1 auf den

Hilfssatz. 2lael, 21ebl ~ labl :::;. eMittelpunk! von ab.

Beweis. Addition der beiden Ungleichungen liefert nach Multipllkation mit 112 wegender Dreicksungleichung (Iael + lebl ~ labl)

(4) lael + lebl = labl ,

d.h. e liegt auf der Strecke ab. Da wegen (4) in keiner der beiden Ungleichungen das<-Zeichen gelten kann, hat man ferner

[ec] =! labl = lebl .

Daher ist e Mittelpunkt von ab.Zum Beweis des zweiten Teils von Satz 1 wâhlt man einen Punkt ao sowie einen

Vektor e> #- cl beliebig und bestimmt dazu die Punkte aie i = 1, ... n - 1) durch

Für den Mittelpunkt eij von aiaj (0 ~ i < j ~ n - 1) hat man dann

a.Ai =!(i + j). e> mit 1 ~ i + j ~ 2n - 3.

Es gibt also hëchstens 2n - 3 Mittelpunkte, wegen des ersten Teils des Satzes alsogenau 2n - 3.

2

Die wesentlich geometrische Überlegung beim Beweis von Satz 1 steckt in demHilfssatz. Wir versuchen diese Überlegung auf die folgende Tatsache zu reduzieren:Nach Wahl eines (beliebigen) Nullpunktes 0 wird die Punktrnenge der Ebene mit derdurch

162

(5)~ ~

a+b=c ~ oa= be

G. Pickert

bestimmten Addition eine abelsche Gruppe, die zudem eindeutig halbierbar ist (d.h.zu jedem a gibt es genau ein a' mit a' + a' = a; dieses wird mit ~a bezeichnet).Wir arbeiten demgemiill im folgenden mit einer solchen abelschen Gruppe (A, +)(neutrales Element 0). AIs Mittelpunkt eines Paares (a, b) E A x A ist dann ~(a + b)zu bezeichnen, und man setzt fur x E N(Ç A; INI = n EN" {l j)

Mx =B(x + y)ly EN" {x}}

Bei der durch (5) definierten Addition ist

labl = lb - al~

(= Lange des Vektors ab) .

Das beim Beweis von Satz 1 erforderliche Vergleichen von Abstânden kann also auchmittels der durch

x ~ y ~ Ixl ~ Iylin der Punktrnenge der Ebene erklârten Relation ~ erfolgen; der Einfachheit halberwird fur diese dasselbe Zeichen benutzt wie fur die Relation "kleiner aIs oder gleich"in JR. Wie letztere ist sie linear und transitiv, jedoch anders als diese nicht identitiv (s.(12) in Abschn. 3). Daher nehmen wir in A eine Relation ~ an, welche diese beidenEigenschaften besitzt, also die Linearitat

(6)

und die Transitivitat

(7)

"ix,YEA x ~ yVy ~ x

"ix,y,zEA x ~ y 1\ Y ~ z =? x ~ z

(mit "i, V, 1\ als Zeichen fur "fur alle", "oder" bzw. "und"). Mittels (6, 7) beweistman dann leicht fur jede nichtleere endliche Teilmenge M von A durch vollstândigeInduktion nach IMI die Existenz eines grëûten Elementes, also eines a E M mit"iXEM x :::; a; dabei benôtigt man fur den Induktionsanfang (IMI =1) noch die aus(6) (mit i =y) folgende Refiexivitai

(6') "iXEA x ~ x.

Übrigens folgt umgekehrt (6) unmittelbar aus der Existenz eines grôûten Elementes in{x, y}, und die Existenz eines grëûten Elementes von {x, y, z} liefert (7), allerdingsnur mit der zusàtzlichen Voraussetzung .weder y, z ~ x noch z ~ y" (die beiVorliegen der Identivitât (12) aber weggelassen werden kann). Mit b - a als einemgrëûten Element (bez. ~) in der Menge

{y - x 1x, yEN 1\ x :f:. y}

erhalt an nun in Verallgemeinerung von (2) die Existenz von a, bEN mit a:f:. b und

(2') "ix,YEN x:f:. y =? Y - x ~ b - a .

Aus c= ~(a+a') = ~(b+b') (mit a' EN" {a}, b' EN" {b}) ergibt sich stan (3)nach (2') also

2(c - a), 2(b - c) ~ b - a .


Daraus müssen wir die Behauptung des Hilfssatzes (in Abschn.l), also e =4(a + b)herleiten. Mit x = e- a, y = b - e und daher x+y = b - a, y - x = a+b -2e erhaltenwir so die Forderung

(8) Vx,yEA 2x, 2y ~ x+y =} x =y.

Ebenso wie (6), (7) ist auch diese erfüllt, wenn im Fall der euldidischen Ebene a ~ bals lai ~ Ibl definiert wird; denn mit a = -x, b = y, e= a liefert der Hilfssatz -

21al, 21bl ~ lb - al =} a + b=a ,

also gerade (8).Damit ergibt sich nach dem Verfahren in Abschn. 1 der erste Teil des folgenden

Satzes in Verallgemeinerung des erstens Teils von Satz 1:

Satz 2. Ist (A, +) eine eindeutig halbierbare abelsche Gruppe, N eine Teilmenge vonA mit INI = n E 1':1 -, {l} und ~ eine Relationin A mit (6, 7, 8), so gilt

(9) IH(x+y)lx,YENl\x#y}1 ~2n-3;

ist lAI> 1, so gibt es zujeder natürlicheti Zahln ~ 2 eineMenge N C A mit INI = nderart, dajJ in (9) das Gleichheitszeichen gilt.

Zum noch ausstehenden Beweis des zweiten Teils dieses Satzes wâhlen wir ein vomneutralen Element a verschiedenesElement e E A und nehmen an, e habe die endlicheOrdnung n (E 1':1 -, {l}), d.h. ne = a und

n > i E 1':1 =} ie #a .

Dann gehëren bekanntlich alle me(m E ;Z) zu

N = {a, e, ... (n - l)e} .

Wegen der Endlichkeit von N kann man i mit

(10)

wâhlen, Für

VxEN X ~ ie E N

x = 4(i - 1) e, y = 4(i + 1) e

hat man 2x, 2y E N, nach (10) daher 2x, 2y ~ ie = x+y, nach (8) also 2e = y-x = aim Widerspruch zur eindeutigen Halbierbarkeit. Daher hat kein Element # a von Aendliche Ordnung, und es ist daher (wieder mit e E A ~ {a})

me # (m + n) e fur aIle mE;Z, nE 1':1 .

Die Abbildung m 1-+ me von ;Z in A ist somit injektiv, und die Menge

N ={2ie 1 i =0, ... n - l}

hat daher genau n Elemente, Für °~ i < j ~ n - 1 gilt

!(2ie+2je)=(i+j)e mit 1~i+j~2n-3.

164 Go Pickert

Daher gibt es hôchstens 2n - 3 E1emente ~(x + y) mit x, y E N, x i= y, nach demersten Teil des Satzes aber mindestens so viele, Damit ist auch der zweite Teil vonSatz 2 bewiesen.

3

Satz 2 ist wegen der etwas "undurchsichtigen" Voraussetzung (8) und des verhâltnismâûig umstândlichen Beweises des zweiten Teils unbefriedigend. Das lâêt sichverbessern, indem man ~ mit + starker "koppelt", als das in (8) geschieht, nâmlichmit dem Monotoniegesetz

(11) Vx,y,ZEA x ~ y ::} x + z ~ y + Z 0

Aus diesem ergibt sich insbesondere

2x~x+y {::} x~y,

2y ~ x + y {::} y ~ x ,

so daB (8) zur Identuiviun (von ~) wird:

(12) Vx,yEA x ~ y 1\ Y ~ x ::} x =y 0

Das Beispie1 der in der euklidischen Ebene durch Ixl ~ Iyl erklârten Relation zeigt,daB (12) und damit auch (11) noch nicht aus (6, 7, 8) folgt. Aber auch (6, 7, 8, 12)ergeben (bei abelscher Gruppe mit eindeutiger Halbierbarkeit) noch nicht (11), wie dasfo1gende Gegenbeispiel zeigt, In der additiven Gruppe der rationalen Zahlen (MengeQ) bestimmt man eine lineare Ordnungsre1ation ~ dadurch, daB man die negativenZahlen gewissermaêen im .Reiêverschluêvertahren" zwischen die positiven Zahleneinfügt: Für s> 0 wird -8 unmittelbar vor 8, aber nach allen Zahlen r < 8 mit r ~ 0eingefügt. Formai lâêt sich ~ so beschreiben (r, 8 E Q):

-r<8= , -r~ - 8, falls 0 ~ r ~ 8 ;

r< - 8 falls 0 < r < 8 °= ,Das ist gleichbedeutend mit

r~8 {::} (0 ~ 81\ Irl ~ 8) V (8 < 01\8 ~ r < -8) °

Man stellt 1eicht fest, daB (6, 7, 8, 12) mit ~ statt ~ erfüllt sind. Dazu ist es hilfreich,sich in einem Koordinatenkreuz die Menge & der Paare (x, y) mit x~y darzustellen:Sind G+,G- die obere bzw. untere (offene) Halbebene zur Geraden gmit Gleichungy =x sowie H+, H- die zur Geraden h mit Gleichung y =-x, so ist & Vereinigungder Mengen G+n H+, G- n H-, g und der oberen Halfte von h. Da O~ 1, aber auchO~ - 1 und daher nicht 0 - 1~1 - 1 gilt, wird das Monotoniegesetz (11) verletzt.

- (6, 7, 12) besagen, daB :::;;-eine (refiexive) lineare Ordnungsrelation ist, und fureine solche mit (11) sowie lAI> 1 bezeichnet man (A, +, ~) als angeordnete abelsche Gruppe (zu diesem Begriff s.z.B. [1, S. 121], wo eine abe1sche Gruppe ais Modulbezeichnet wird; dort und auch in [5] wird auf die Einschrânkung lAI> 1 verzichtet).Bei einer solchen ist die Abbildung x f-+ 2x injektiv, so daB man statt der "Mitte1punkte ~(x + y) einfach die Sumen x + y(x i= y) zâhlen kann. Man benôtigt also die


Halbierbarkeit nicht, erhâlt aber durch Spezialisierung doch wieder Satz 1. Dazu muBman allerdings noch wissen, daB in der euk1idischen Ebene die durch (5) definierteabelsche Gruppe zu einer angeordneten Gruppe gemacht werden kann (s. Abschn.4).Dm den Beweis des zweiten Teils von Satz 1 verwenden zu kënnen, braucht man nurnoch zu beachten, daB

i, j E N 1\ e E A -, {o} 1\ i 1j :::} ie 1 je

und damitI{ie 1i =0, ... , n - 1}1 =n

gilt; dabei benôtigt man das mit y + z, x + Z, -z statt x, y, z aus (11) mitteis (6, 12)durch Kontraposition hervorgehende strenge Monotoniegesetz

(11') "ix,y,zEA x < y :::} x + z < y + Z ,

wobei wie üblich x < y aIs x :S y 1\ x 1 y definiert ist, was nach (6, 6', 12) geradedie Verneinung von y ~ x besagt.

Wir haben damit aIs eine befriedigende Verallgemeinerung und zugleich Vereinfachung (hinsichtlich des Beweises) von Satz 1 den

Satz 3. Ist (A, +, :S) eine angeordnete abelsche Gruppe und N c A mit INj = n EN" {1}, so gilt -

(13) I{x + y 1x, yEN 1\ x 1 y}1 ~ 2n - 3,

und zu jedem n EN" {1} gibt es N c A mit INI = n derart, daj3 in (13) dasGleichheitszeichen gilt.

Beweis. Ein soicher ist zwar in den vorigen Überiegungen unter Rückgriff auf Abschn. 1 und z-enmatten, soll aber im folgenden noch einmal zusammenhângend dargestellt werden, um die gegenüber Abschn. 1 erreichte Beweisvereinfachung deutlichzu machen.

Wegen INI EN" {1} kann man a, b, EN mit a 1 b und

(14) Vx,YEN x 1y:::} y - x ~ b - a

wâhlen; wegen (12) darfman anders als in (2') wieder stattdessenden Maximum-Termverwenden:

(14') b - a =max{y - x 1x, yEN 1\ x 1 y} .

Mitteis (11) zeigt man leicht, daB (14) gleichwertig Ist mit

(14") a =minN 1\ b =maxN·.

Wir führen fur x E N die Menge

Sx ={x + y 1yEN" {x}}

ein und haben also

(15) ISxl =n -1.

Zur Bestimmung von Sa n Sb sei mit a' EN" {a}, b' EN" {b}

166

(16)

Nach (14) hat man

(17)

und nach (16)

a + a/ = b+ b' E Sa n Sb .

b - b' ~ b - a , a/ - a ~ b - a

G. Pickert

(b - b') + (a/ - a) = (b - a) + (a/ - b') = 2(b - a) .

Nach (11, 11/) ist daher wegen (17) sowohl b - b' < b - a wie auch a - a/ < b - aunmôglich, so daB b' =a, a/ =b sein muB. Damit hat man

SanSb={a+b},

und wegen (15) ist daher die linke Seite in (13)

~ ISa U Sbl = ISal + ISbl-ISa n Sbl =2(n - 1) - 1 =2n - 3.

Mittels (14") kann man diesen Beweis noch etwas vereinfachen:

a/ EN" {a}, b' EN" {a, b} =} a/ ~ b /\ a < b' =} a + a/ < b+ b' ,

also Sa n (Sb" {a + b}) =0; daher ist die linke Seite in (13)

~ ISal+ ISb" {a + b}1 =n - 1+ n - 2 =2n - 3.

Zum Beweis des zweiten Teils von Satz 3 wâhlt man e E A -, {o} (wegen lAI> 1môglich). Wegen (11/) enthâlt dann für n EN" {1}

N = {ie 1 i = 0, ... , n - 1}

genau n Elemente. Weiter hat

{x+y 1 x,y E N/\x1=Y} ={(i+j)e 1O~ i <i ~ n-1} ~ {ke Il ~ k ~ 2n-3}

hëchstens 2n - 3 Elemente, nach (13) aber mindestens so viele.

4

DaB die durch (5) zu einer abelschen Gruppe gemachte Punktemenge der affinenEbene über einem angeordneten Kërper (insbesondere über JR) angeordnet werdenkann, ergibt sich aus der folgenden Konstruktion:

Ist (A, +, ~) eine angeordnete abelsche Gruppe, sa HiBt sich die Gruppe (A2, +)mit der durch

(x, y) + (x/,y/) =(x +x/,y + yi)

definierten Addition zu einer angeordneten abelschen Gruppe machen, indem manin A2 die (einfachheitshalber wieder so wie die Ordnungsrelation in A bezeichnete)Relation ~ durch

(18) (x,y)~(x/,y/) ~ x<x/V(x=x//\y~y/)

definiert (lexikographische Anordnung der Paare).


Die Bedingungen (6, 7, Il, 12) lassen sich mit Hilfe dieser in (A, +,~) erfiilltenBedingungen Ieicht als erfiillt nachweisen. -

Entsprechend kann man die lexikographische Anordnung in Ad fiir jede natürliciheZabl d ~ 2 definieren:

(Xl,"" Xd) ~ (x~, ... x~H:::} Es gibtj E {l, ... , d+ 1} mit Xi = x~ für

(18') 1 ~ i < j und Xj < xj, falls j ~ d,

für d =2 geht (18') mit Xl = X, X2 = y, xi =X', x~ = y' offenbar in (18) über. Daalso auch (Ad, +) zu einer angeordneten Gruppe gemacht werden kann, zeigt Satz 3,daB Satz 1 für Punktmengen in einem affinen Raum beliebiger endlicher Dimensionüber einem angeordneten Kôrper gilt. Übrigens ergibt sich schon aus dem Beweis inAbschn. 1 die Gültigkeit von Satz 1 in einem euklidischen Raum beliebiger endlicherDimension.

Wegen (0,0) < (0, e) für 0 < e und

n· (0, e) =(0, n . e) < (e,o) für alle nE N

ist die durch (18) erklârte Anordnung allerdings nichtarchimedisch (s. hierzu [1,S.141]). Nimmt man aber für (A, +,~) die angeordnete additive Gruppe eines echtenUnterkôrpers K von JE., so kann man (A2, +) sogar archimedisch anordnen: WegenK C JE. gibt es e E JE. -, K, und 1, e sind dann über K linear unabhângig (x + ye = 0mit x, Y E K zieht X =Y =0 nach sich, da sonst e =_xy-l E K wâre); durch

f(x, y) =x + ye für alle x, y E A(= K)

wird daher ein Isomorphismus f von (A2, +) in (JE., +) bestimmt, und die gernâê

(x,y) ~ (X', y') {:::} f(x,y) ~ f(x', y')

von JE. auf A2 .zurückübertragene" Relation ~ macht dann (A2, +) zu einer archimedisch angeordneten Gruppe.

lm Fall K =JE. versagt dieses Verfahren. Man kann aber trotzdem einen Isomorphismus f von (JE.2, +) in (und sogar auf) (JE., +) und damit (wie eben) eine archimedische Anordnung von (JE.2, +) gewinnen, indem man eine Vektorraumbasis B vonJE. über Q benutzt (zu deren Existenz s.z.B, [1, S.542]) sowie injektive Abbildungeng, g' von B in sich mit gB U g' B =B, gB n g' B =0, die es wegen der Unendlichkeitvon B gibt. f wird nun durch

f (L xbb, LYbb) = L xbg(b) + LYb9'(b) mit Xb,Yb E QbEB bEB bEB bEB

definiert, wobei in den Summen nur jeweils endlich viele Koeffizienten f 0 sind. Danach O. HOlder (1901; s. [5, S. 8]) jede archimedisch angeordnete (abelsche) Gruppeisomorph in (JE., +,~) abgebildet werden kann, hat man damit den Satz: Ist (A, +,~)eine archimedisch angeordnete Gruppe, so lâût sich auch (A 2 , +) archimedisch anordnen.

Auch dieser Satz gilt bei jeder natürlichen Zabl d ~ 2 für Ad (stan A2 ) . Manbraucht dabei nur die archimedische Anordnung von (JE.a ,+) herzustellen (wie auchschon bei d = 2); doch hat die bei d = 2 im FaU K C JE. durchgefiihrte und imfolgenden auf beliebige d(?, 2) veraIlgemeinerte Konstruktion den Vorteil, auf eine

168 G. Pickert

(nient explizit angebbare) Basis B von lll? über Qi zu verzichten. Hat lll? über demUnterkërper K endlichen Grad (Dimension von ~ als Vektorraum über K), so ist derGrad von te, dem algebraischen Abschluê von K, über K ebenfalls endlich. Darausfolgt (s. [5, S.27, Satz 13]), daB K reell abgeschlossen ist. Nach Definltion diéserEigenschaft (s. [5, S.23 unten]) kann daher lll? nicht echter Oberkërper von K sem'.Damit gibt es also im Fall K C Iœ. zu jeder natürlichen Zahl d ~ 2 ein über K lînearunabhângiges d-tupel (el, ... , ed) reeller Zahlen. Wie im Fall d =2 (dort mit el =I,e2 =e) bestîmmt man den Isomorphismus f von (Kd

, +) in (Iœ., +) durch

d

f(X1, ... ,Xd) = LXiei (Xl, ... ,Xn E K)i=l

und mittels diesem dann eine archimedische Anordnung in K d •

lm FaU K = lll? kann man wieder zu einer (unendlichen) Basis B von JR überQi injektive Abbildungen gi(i = 1, ... , d) von B in sich derart angeben, daB ihreBildmengen giB eine Zerlegung von B in disjunkte Teilmengen lîefern; denn beiMultiplikation mit einer natürlichen Zahl bleibt jede unendliche Kardinalzahl fest.Der die gewünschte archimedische Anordnung von (Iœ.d , +) liefemde Isomorphismusf von (Iœ.d, +) auf (Iœ., +) wird dann bestimmt durch

d

f(X1,' .. , Xd) = L L xibgi(b) mit Xi = z= Xibb , Xib E Qi(i = 1, ... , d; b E B) .i=l bEB bEB

5

Nach Satz 3 gîlt (13) fur alle N ~ A mit INI = n EN" {l} bei einer abelschenGruppe (A, +\ falls diese anordnungsflihig ist, d.h. wenn sie durch eine lineare Ordnungsrelation ~ zu einer angeordneten abelschen Gruppe gemacht werden kann. WieF.W. Levi 1913 bewiesen hat (s.z.B. [5, S.12]), ist eine abelsche Gruppe mît mehr alseinem Element genau dann anordnungsfâhig, wenn sie torsionsfrei ist (diese Bezeichnung bezieht sich auf die Bedeutung dieser Gruppen in der algebraischen Topologie),d.h. wenn nur das neutrale Element endliche Ordnung hat. Es fragt sich nun, obauch bei einer nichttorsionsfreien abelschen Gruppe (A, +) (13) fur alle N ~ A mitINI =nE N" {l} gültig sein kann. -

lm FaU lAI = 2 gilt (13) offenbar (N = A, n = 2). Hat aber A ein Elemente der Ordnung 2 und ist lAI > 2, sa gilt (13) nicht fur jede Teilmenge N: Mannehme a E A" {D, e} und setze N = {o, e, a,a + el; wegen e + e =° erglbt sichdie linke Seite von (13) zu 3 oder 4, wâhrend die rechte Seite =5 ist. Besitzt A einElement a der Ordnung n > 3, sa ist (13) fur N = {o, a, ... ,(n - l)a} nicht erfüllt(n < 2n-3). Gibt es in A zwei Elemente der Ordnung 3, so hat die von ihnen erzeugteUntergruppe bekanntlich die Ordnung 9; nimmt man diese als N, sa ist wieder (13)(mit n = 9) nicht erfüllt, da die linke Seite wegen der Gruppeneigenschaft von Neinen Wert ~ 9 (sogar =9) hat. Nicht erfaBt wurde bisher lediglich der Fall, daBA genau ein Element e der Ordnung 3, aber sonst kein Element :f: ° von endlicherOrdnung besitzt, Bekanntlich ist A dann direkte Summe einer Gruppe der Ordnung3, nâmlich {D, e, -e}, und einer torsionsfreien Gruppe A' (man wâhlt fur A' eine

1 Diesen Beweis verdanke ich einern Hinweis von Fran Prieê-Crarnpe


maximale, e nicht enthaltende Untergruppe). lm Fall IA'I =1, also A={o, e, -el lst(13) (mit n E {2, 3}) offenbar erfüllt. lm Fall IA'I > 1 gilt (13) ebenfalls (Beweisweiter unten). Damit haben wir also den

Satz 4. Bei einer abelschen Gruppe (A, +) mit lAI ~ 3 gilt genau dann fur jedeTeilmenge N von A mit INI =nE N" {l} die Ungleichung (13), wenn die Gruppeentweder torsionsfrei oder aber die direkte Summe einer dreielementigen Gruppe miteiner torsionsfreien Gruppe ist.

Zu beweisen ist nur noch, daB (13) im Fall IA'I > 1 gilt.Es sei f die durch

fN~A', VxEN x-f(X)ED={o,e,-e}

bestimmteProjektion von N in A' und N' =fN ihre Bildmenge mit n' =IN'I. lmFaIl n' =1 gibt es a E A mit N ç a + D, und (13) folgt dann daraus, daB dieseUngleichung für jede Teilmenge voÏÏ D gilt. Also kann im folgenden n' > 1 angenommen werden. A' wird nun durch eine geeignete Relation ~ zu einer angeordnetenGruppe gemacht, und mit

(18) a =minN' 1\ b =maxN'

hat man dann (14) mit N' statt N. Die Menge

S' ={x + y 1 x, y E N' 1\ x ;l: y}

enthâlt nach dem Beweis von Satz 3 also die (2n' - 3)-elementige Menge

{a + x 1 x E N' -, {a}} U {b + x 1 x E N' -, {a, b}} .

Setzt man

so enthâlt

(19)

S ={x + y 1 x, yEN 1\ x;l: y}

daher die 2n' - 3 untereinander elementefremden Mengen

(XE N'" {a})(x E N'" {a,b}).

Sa,x =(Da + Dx) + (a + x)

Sb,x =(Db + Dx) + (b + x)

Wegen der Folgerung aus (18)

(20)

2a < x + y < 2b für alle x, y E N' mit x;l: y

(und daher 2a,2b fi. S') enthâlt S aber auch die untereinander und zu den Mengen(19) elementefremden Mengen

Sa,a ={d + d' 1 d, d' E Da 1\ d;l:d'} + 2a ,

Sb,b ={d + d' 1 d, d' E Db 1\ d ;l: d'} + 2b .

Zur Bestimmung der Elementeanzahlen der Mengen (19, 20) fiihren wir die

Ni = {x 1 x E N' 1\ IDxl = i} (i = 1,2,3)

ein, für deren Elementeanzahlen ni =INil demnach

170 G. Pickert

(21)

gilt. Da fur 0 CD', D" ~ D

{

3 faIls ID'I = 3 oder ID'I = ID"I = 2ID' + D"I = 2

1faIls ID'I = 1, ID"I = 2faIls ID'I =1 =ID"I

sowie

{

3 faUs ID'I = 3I{d+d' 1 d, d' E D' 1\ d;f d'}1 = 1 falls ID'I =2

o falls jD'1 =1

gelten, erhâlt man

{

3 falls a E N 3 oder x E N 3 oder a, x E N21Ba,., 1= 2

1faIls a E NI, x E N2 oder a E N 2, x E NIfalls a, x E NI

{

3 falls a E N3

IBa,al = 01 faIls a E N2

falls a E NI

(entsprechend fur b statt a).Addition dieser Elementeanzahlen ergibt dann unter Benutzen von (21) die

gewünschte untere Schranke 2n - 3 fur IBI, wobei (wegen der Symmetry in a, bnur) 6 Fâlle zu unterscheiden sind:

1) a, b ENI,IBI ~ ni - 1 + 2n2 + 3n3 + ni - 2 + 2n2 + 3n3

=2(nl + 2n2 + 3n3) - 3 =2n - 3.

2) a ENI, se N2 (also nl,n2 ~ 1):

IBI ~ ni - 1 +2n2 + 3n3 + 2(nl -1) + 3(n2 - 1) + 3n3 + 1

=2(nl + 2n2 + 3n3) + ni + n2 - 5 ~ 2n - 3 .

3) a ENI, b E N 3 (also ni ~ 1).

JBI ~ ni - 1 +2n2 +3n3 +3(nl -1)+3n2 + 3(n3 - 1)+3

=2(nl + 2n2 + 3n3) + 2nl + n2 - 4 > 2n - 3 .

4) a, b E N 2 (aIso n2 ~ 2).

IBI ~ 2nl + 3(n2 - 1) + 3n3 + 2nl + 3(n2 - 2) + 3n3 + 2

=2(nl + 2n2 + 3n3) + 2nl + 2n2 - 7 ~ 2n - 3 .

5) a E N 2, b E N3 (also n2 ~ 1).

IBI ~ 2nl + 3(~ - 1) + 3n3 + 3nl + 3(n2 - 1) + 3(n3 - 1) + 4

=2(nl + 2n2 + 3n3) + 3nl + 2n2 - 5 ~ 2n - 3 .

6) a, b E N 3•

IBI ~ 3nl + 3n2 + 3(n3 - 1)+3nl +3n2 + 3(n3 - 2) +6

= 2(nl + 2n2 + 3n3) + 4nl + 2n2 - 3 ~ 2n - 3 .

Eine Beweisanalyse durch Abstraktion

6

171

Satz 3 legt es nahe, in einer angeordneten abelschen Gruppe (A, + :::;) auch dieAnzahl der Summen von k Elementen (0 ~ k ~ n) einer n-elementigen TeilmengeN nach unten abzuschâtzen, Zur bequemeren Formulierung werden die folgendenAbkürzungen (mit M C A) eingeführt:

L(M)=def LX,xEM

(221)

Man hat dann also sn,o = 1, sn,! = n sowie (nach Satz 3) Sn,2 = 2n - 3. Für die beimBeweis des 2. Teils von Satz 3 benutzte Menge N ={o, e, ... , (n - l)e} erhâlt mannach dem dortigen Verfahren for 0 < k ~ n:

k k-1

ISk(N)1 ~ L(n - i) - Li + 1=nk - k - k(k - 1)+ 1 =(n - k)k + 1 ,i=l i=l

hat also

(23) ISk({O, e, ... (n - l)e})1 ~ (n - k)k + 1 .

Das HiBt die folgende Verallgemeinerung von Satz 3 vermuten:

Satz 5. FUr n"E N, k ENa, k ~ n gilt

(24) Sn,k =(n - k)k + 1 .

Beweis. Für jedes h E No beweist man (24) mit k = n - h durch vollstândigeInduktion nach n (~ h). Der Induktionsanfang (n = h) ergibt sich aus Sn, a = 1. AIsInduktionsvoraussetzung dient

(24') Sn-1,k-1 = (n - k)(k - 1) + 1

mit k = n - h > O. Für den Induktionsschritt wird mit (14") das zweite (nicht in a, bsymmetrische) Verfahren aus dem Beweis von Satz 3 verallgemeinert, indem man {b}zu einer Menge BeN mit

IBI =k - 1 A 'r/xEN ..... B 'r/YEB X < y

erweitert; die einzige derartige Menge erhâlt man offenbar, indem man rekursiv für1 ~ i < n die Mengen Bi durch

BI = {b}, Bi+1 = Bi U {max(N" Bi)}

bestimmt und dann B =Bk-1 setzt,In Sk(N), definiert in (22t), bildet man nun (entsprechend dem Beweis von Satz

3) die Teilmengen

172

s ={a +L(M)I M ~ N <, {a} 1\ IMI =k - 1} ,S' ={a' + L(B)I a' EN" (B U {a})}

Für die Elemente von diesen hat man

G. Piekert

a + L(M) ~ a + L(B) < a' + L(B)

und daher Sn S' =0. Da wegen (24') ISI ~ (n - k)(k -1)+ 1 gilt und IS'I =n - kist, folgt

(25) ISk(N)1 ~ ISI + IS'I ~ (n - k)k + 1 .

Daher muB in (23) das Gleichheitszeichen gelten, und (222) , (25) liefern dann (24).Ergânzend zu Satz 5 sei noch bemerkt, daB die triviale obere Schranke (~) der

ISk(N)1 auch erreicht wird:

max{ISk(N)1 IN c A 1\ INI =n} = (~) .

Denn fur N = {2i el i E {D, ... ,n - 1}} mit e E A" {D} gilt ISk(N)1 = (~), weildie Abbildung

der Potenzmenge von No in N bekanntlich injektiv ist.

Literatur

1. Behnke, H. u.a, (Hrsg.): Grundzüge der Mathematik I. Gëttingen: Vandenhoeek u. Ruprecht 19662. Gardner, M.: The annotated Alice. Harmondsworth: Penguin Books 19653. Lauseh, H., O'Halloran, P.J.: A healthy growth - the Asian Pacifie Mathematies Olympiad in its third

year. Math. Compet. 4,47-55 (1991)4. Piekert, G.: Erzeugung mathematiseher Begriffe dureh Beweisanalyse. J. Math. Did. 5, 167-187 (1984)5. Prieê-Crarnpe, S.: Angeordnete Strukturen: Gruppen, Kôrper, projektive Ebenen. (Ergeb. Math. Grenzg.

Bd. 98) Berlin Heidelberg New York Tokio: Springer 1983

Documents

Eine Beweisanalyse durch Abstraktion