Conway-számok és kétszemélyes játékok

Eötvös Loránd Tudományegyetem Természettudományi Kar

Conway-számok és kétszemélyes játékok diplomamunka

Szerz®: Tóth Gábor, matematika BSc, matematikus szakirány

Témavezet®: Fialowski Alice, egyetemi docens Algebra és Számelmélet Tanszék

Budapest, 2010

Tartalomjegyzék

0. Bevezetés

2

0.1.

El®ismeretek, fogalmak és jelölések

. . . . . . . . . . . . . . . . . . . .

3

0.2.

Betekintés a Conway-számok világába . . . . . . . . . . . . . . . . . . .

4

1. Kétszemélyes játékok

11

1.1.

Deníció, példák

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.2.

Nyer® stratégiák . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

1.3.

Játékok ellentettje és összege . . . . . . . . . . . . . . . . . . . . . . . .

14

1.4.

Részben rendezés játékok között . . . . . . . . . . . . . . . . . . . . . .

16

1.5.

Kapcsolat a Conway-játékokkal

17

. . . . . . . . . . . . . . . . . . . . . .

2. A Conway-számok teste

20

2.1.

Rendezés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

2.2.

Összeadás

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

2.3.

Szorzás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

Irodalomjegyzék

28

1

0. fejezet Bevezetés

Célom ezen szakdolgozattal, hogy bemutassak egy halmazelméleti számkonstrukciót, melyet John Horton Conway angol matematikus dolgozott ki az 1970-es években. Ez a módszer néhány egyszer¶ rekurzív denícióból kiindulva, egyetlen lépésben hoz létre a valós számoknak, a rendszámoknak és az innitezimálisan kicsiny értékeknek megfelel® elemeket, s®t, rendezett testbe ágyazza ®ket. Így Conway számai között ugyanúgy lehet összeadni, kivonni, szorozni, osztani és gyököt vonni, mint ahogyan azt a valós számoknál megszoktuk, olyan objektumokat teremtve ezzel, melyeknek a matematika klasszikus ágaiban aligha lehetne értelmet adni. Például:

√

ω−3+

π . ω

Persze amilyen egyszer¶ek és tömörek az alapdeníciók, olyannyira nehéz és munkaigényes a fenti tulajdonságok igazolása és az elmélet többi részének felépítése. Nem triviális például, hogy bármely két szám összehasonlítható, vagy hogy számok összege szám. De éppen ett®l lesz szép és hasznos az elmélettel való foglalkozás, mert közelebb hozza az emberhez a tiszta, absztrakt matematikát, és a pusztán logikai alapokon nyugvó gondolkodást. E szellemi kincsen túl a Conway-számoknak más, gyakorlatiasabb alkalmazásuk is van, nevezetesen a játékelméletben. Szoros kapcsolatban állnak a kétszemélyes, teljes információs, felváltva lép®s stratégiai játékokkal, mint a sakk vagy a gó. Conway erede-

2

tileg ilyen játékok nyer® stratégiáit vizsgálta, így jutott el az új számfogalomhoz. A témát az [1] és [2] irodalmak alapján fogom feldolgozni.

Szeretnék köszönetet mondani témavezet®mnek, Fialowski Alice-nak, aki által megismerhettem ezt az elméletet, és tanácsaival sokat segített a szakdolgozat elkészítésében.

0.1. El®ismeretek, fogalmak és jelölések A diplomamunka megértéséhez elegend® a halmazelmélet és logika alapjainak, a f®bb algebrai struktúrák denícióinak, illetve a rendszámok legfontosabb tulajdonságainak ismerete. Most néhány kiegészítés következik ezekkel kapcsolatban. Az Az

L és R halmazok alkotta x rendezett pár

L-et x

bal oldali, az

R-et

x = hL, Ri := {{L}, {L, R}}.

deníciója:

L

pedig a jobb oldali tagjának hívjuk. Az

tetsz®leges vagy tipikus elemét

xL -lel,

az

R

halmazét

xR -rel

jelöljük, és

halmaz egy

x

bal illetve

jobb oldali összetev®inek nevezzük ®ket. A továbbiakban egy rendezett párt legtöbbször

L = {a, b, c} x = xL xR .

az összetev®ivel adunk meg. Például ha

{a, b, c |d, e} ,

vagy általánosan:

R = {d, e},

és

akkor

hL, Ri =



A halmazelmélet ZermeloFraenkel-féle axiómarendszeréb®l (ZF) különösen fontos lesz számunkra az egyetlen nem intuitív axióma:

Regularitási axióma. minden nemüres

x

   ∀x ∃u(u ∈ x) → ∃v v ∈ x ∧ ∀w(¬(w ∈ x ∧ w ∈ v)) .

halmaznak van olyan

v

eleme, hogy

x

és

v

Azaz

diszjunktak.

A számokkal kapcsolatos deníciók rekurzívak, ezért az állítások többségét kénytelenek leszünk indukcióval bizonyítani. Ennek legitimizálásához nélkülözhetetlen az axióma alábbi következménye:

0.1.1. Állítás. x0 , x1 , x2 , . . .

A regularitási axiómából következik, hogy nem létezik halmazok olyan

végtelen sorozata, melynek tagjaira

xi+1 ∈ xi

minden

i∈N

Bizonyítás. Tegyük fel, hogy van ilyen sorozat. Ekkor elkészíthetjük az halmazt, ami nyilván ellentmond a regularitási axiómának.

3

esetén.

{x0 , x1 , x2 , . . .}

Megjegyezzük, hogy a kiválasztási axiómát feltéve 0.1.1 megfordítása is igaz. Nevezetes tétel, hogy ZF többi axiómáját feltéve a regularitási axióma ekvivalens azzal, hogy minden halmaz eleme a kumulatív hierarchia valamely alkalmas

Vα

halmazának,

α rendszámra. A kumulatív hierarchia transznit rekurziós deníciója: V0 = ∅,

Vα+1 = P(Vα ), S β<α Vβ [4].

azaz a

Vα

hatványhalmaza, illetve ha

α

limeszrendszám, akkor

Vα =

Bevezetjük néhány algebrai struktúra rendezett, illetve részben rendezett változatát:

0.1.2. Deníció.

Egy csoportot rendezett (részben rendezett) csoportnak hívunk, ha

értelmezve van rajta egy teljes rendezés (részben rendezés), mellyel a csoportm¶velet eltolásinvariáns, azaz tetsz®leges és

a, b

és

c

csoportelemekre, ha

a ≤ b,

akkor

a+c ≤ b+c

c + a ≤ c + b.

0.1.3. Deníció.

Egy kommutatív gy¶r¶t, illetve testet rendezett gy¶r¶nek, illetve ren-

dezett testnek hívunk, ha értelmezve van rajtuk egy teljes rendezés, mellyel az additív csoport rendezett, és a szorzásra igaz, hogy ha

a

és

b

elemekre

0≤a

és

0 ≤ b,

akkor

0 ≤ ab. Az algebrai struktúrák bevezetésénél általában kikötik, hogy halmazok legyenek. Itt ehhez nem tarthatjuk magunkat, mert számos, vizsgálatunk tárgyát képz® objektum  köztük maga a számok összessége is  nem halmaz, hanem valódi osztály lesz. Conway nagy kezd®bet¶t használ, ha a struktúra osztályon értelmezett (például Group, Field ). Mi ezt nem fogjuk külön kiemelni, egyszer¶en csoportnak, testnek stb. nevezzük elemek (halmazok) tetsz®leges olyan összességét, melyben az adott m¶veletekkel, relációkkal és kitüntetett elemekkel teljesülnek a struktúra axiómái. Bátran megtehetjük, hiszen az algebrai állítások igazsága független a struktúrák halmazelméleti mivoltától.

0.2. Betekintés a Conway-számok világába Miel®tt deniálnánk a Conway-számokat, érdemes bevezetni egy náluk általánosabb fogalmat:

4

0.2.1. Deníció (Conway-játék).

Egy

x

rendezett pár Conway-játék, ha minden össze-

tev®je Conway-játék. Minden Conway-játék így áll el®. Ez rekurzív deníció: ha már ismerünk néhány Conway-játékot, akkor e szabályt követve teremthetünk bel®lük újakat; és csak azok az objektumok Conway-játékok, amelyek így születtek. Kezdetben egyetlen Conway-játékunk sincs, mégis elkezdhetjük a konstrukciót az Ezt a

{|}

h∅, ∅i párral, hiszen erre triviális a feltétel: egyetlen összetev®je sincs.

jelsorozattal is leírható Conway-játékot nevezzük

három újabb Conway-játékot állítunk el®: Az els®t iterálva:

0-nak.

1 := {0|}, −1 := {|0}

és

A

0

ismeretében

∗ := {0|0}.

2 := {0, 1|}, 3 := {0, 1, 2|}, minden n természetes számra, melynek

már feleltettünk meg Conway-játékot, a következ® Conway-játék

ω := {0, 1, 2 . . . |}, ω + 1 := {0, 1, 2, . . . , ω|}

n+1 := {0, 1, 2, . . . , n|},

és így tovább. Transznit rekurziót alkal-

mazva az összes rendszám reprezentálható olyan párként, melynek bal oldali összetev®i a nála kisebb rendszámok, hasonlóan a Neumann-féle denícióhoz. A Conway-számokat két rekurzív szabály határozza meg, íme az els®:

0.2.2. Deníció

(Conway-szám)

.

Egy

x

rendezett pár Conway-szám, hogyha minden

összetev®je Conway-szám, és nincsenek olyan

xL , xR

összetev®i, melyekre

xR ≤ xL .

Minden Conway-szám így áll el®. Egy rendezett pár biztosan Conway-szám, ha az egyik tagja üres, a másik pedig Conway-számok tetsz®leges halmaza, hiszen ekkor a második feltétel semmitmondó. Ezért a Conway-számok konstrukcióját is indíthatjuk a a

0-val,

és transznit indukcióval

∗ kivételével minden eddig bevezetett Conway-játékról kiderül, hogy Conway-szám is. A második szabály kétváltozós rekurzióval adja meg a kisebb vagy egyenl®t: az

x≤y

igazságát az dönti el, hogy egyszer¶bb számpárokra igaz-e a reláció. A deníció

Conway-játékokra is alkalmazható.

0.2.3. Deníció (Rendezés). olyan

xL

összetev®je, melyre

Pontosan akkor teljesül

y ≤ xL ,

és nem létezik

x ≤ y,

y -nak

hogyha nem létezik

olyan

yR

x-nek

összetev®je, melyre

y R ≤ x.

Jelölés. x ≥ y ⇔ y ≤ x, x = y ⇔ x ≤ y y < x. A továbbiakban x ≡ y

és

jelöli azt, hogy

x ≥ y, x < y ⇔ x ≤ y

x és y

5

és

x  y, x > y ⇔

halmazelméleti értelemben azonosak.

A 0.2.2 és 0.2.3 szabályok együtt deniálják tehát a Conway-számokat, melyeket a Donald Knuth által alkotott szürreális számok elnevezéssel is szoktak illetni. Mi ezután egyszer¶en számok nak hívjuk ®ket. A deníciók mögött az a szemlélet húzódik meg, hogy a számok összetev®ik között helyezkednek el a képzeletbeli számegyenesen, a konstrukció el®rehaladtával egyre s¶r¶bben kitöltve azt. Ha

x-nek

nincs bal oldali,

teljesül. Ezért

1

1≤1

és

pedig nincs jobb oldali összetev®je, akkor

0 ≤ 0, 0 ≤ 1, −1 ≤ 0

megállapítható, hogy pedig:

y -nak

∗

−1 ≤ 1.

és

nem szám, továbbá

−1 ≤ −1.

mondjuk, hogy a

{0}

Ezekb®l az egyenl®tlenségekb®l

0  −1, 1  0, 1  −1.

Ez utóbbiakból

Eddigi ismereteinket összefoglalhatjuk úgy, hogy a

számok mindegyike egyenl® önmagával, és

−1 < 0, 0 < 1, −1 < 1

halmaz a számok nulladik, a

x≤y

{−1, 1}

−1, 0

és

teljesülnek. Azt

pedig az els® nemzedéke,

azaz ezek a nulladik nemzedék ismeretében el®állítható, újonnan született számok. A

0≤0

egyenl®tlenség következményei

0∗

és

∗0

is. A relációnkról még nem

tudjuk, valóban rendezés-e, de a Conway-játékok között már biztosan nem lesz teljes. A fentiek alapján a második nemzedék tagjai:

{−1|}, {1|}, {−1, 0|}, {0, 1|}, {−1, 1|}, {−1, 0, 1|}, {|−1}, {|1}, {|−1, 0}, {|0, 1}, {|−1, 1}, {|−1, 0, 1}, {−1|0}, {−1|1}, {−1|0, 1}, {0|1}, {−1, 0|1}. Végiggondolható, hogy az, amelyiknek több összetev®je van valamelyik oldalén, a bal oldalon csak a nagyobb, a jobb oldalon pedig csak a kisebb összetev®t meghagyva, vele egyenl® számmá alakítható. A maradék hét számból

{−1|}, {|1}

és

{−1|1} 0-val

egyenl®ek, míg a többi négy új ekvivalenciaosztályokat határoz meg, nevezetesen:

• {1|}

egyenl® a már deniált

2-vel,

• −2 := {|−1}, •

1 2

:= {0|1},

• − 12 := {−1|0}. 6

Miel®tt folytatnánk a konstrukciót, bevezetjük a legfontosabb m¶veleteket  természetesen rekurzív úton. A Conway-játékok között is m¶ködnek ezek a deníciók.

0.2.4. Deníció (m¶veletek). • x

és

• x

ellentettje:

• x

és

y

y

összege:

 x + y ≡ xL + y, x + y L xR + y, x + y R ,

 −x ≡ −xR −xL , x − y

szorzata:

azt jelenti, hogy

x + (−y),

 xy ≡ xL y + xy L − xL y L , xR y + xy R − xR y R L x y + xy R − xL y R , xR y + xy L − xR y L .

A formulákban megjelen® összetev®k az összes ugyanolyan típusú összetev®re utalnak; tehát például

x+y

bal oldalához az

xL + y

és

x + yL

összegeket

x és y

minden bal

oldali összetev®jével el kell készíteni. Néhány példán keresztül ellen®rizhetjük a számok elnevezésének jogosságát. Conway-féle rendszámra

0 + 0 ≡ 0,

és transznit indukcióval világos, hogy bármely

α

α + 0 ≡ 0 + α ≡ α. 0 + 1 ≡ 1 + 0 ≡ 1 alapján ismét indukcióból

következik, hogy minden

n

összeadva ®ket, azonos az

természetes számra

n + 1-nek

n

és

1

összege, bármilyen sorrendben

megfelel® számmal. E gondolatmenetet folytatva

kiderül, hogy az új természetes számok összeadása ugyanúgy megy, mint a régieké.

0.2.5. Állítás. 21 + 12 = 1. 1 Bizonyítás. A természetes számokról tett megállapításainkból levezethet®, hogy 2 +0

0+

1 2

≡

Jelöljük

1

1 . 2

x-szel

  1 1 1 1 1 1 + ≡ 0 + , + 0 1 + , + 1 ≡ 2 2 2 2 2 2   1 1 1 ≡ {0 + , 1 + 0|1 + 1}, {0 + 1, + 0|1 + 1} ≡ 2 2 2   1 1 ? ≡ { , 1|2} ={0|}. 2 2 1 1 az , 1 |2} számot. |x} ≤ 1-hez pusztán annyit kell 2 2

1 , ami viszont következik 2

feleltetve meg.

1

1 ≤ 1-bél,

|x} ≥ 1-hez 2

az els®

1-est

az

igazolni, hogy

1 jobb oldali összetev®jének 2

pedig egyrészt szükséges, hogy

7

≡

1 2

|x}  0,

másrészt

pedig hogy

x  1.

ahol a második

Az el®bbit

1-es x

10⇒0≤

1 támasztja alá, az utóbbit pedig 2

1 ≤ 1,

bal oldali elemét jelenti.

A bevezet® fejezet hátralév® részében bizonyítás nélkül mutatom be a számok további nemzedékeit. A most elkezdett, születésnap szerinti elemi felépítés lehet®ségeit részletesen tárgyalja [3], de a lentiek igazolásához felhasználható a kés®bbi 2.1.3 állításunk, az els®szülöttségi lemma is. A második konstrukciós lépés után a számok alábbi, a rendezés szerint növekv® sorrendbe állított ekvivalenciaosztályait ismerjük:

1 1 −2, −1, − , 0, , 1, 2. 2 2 A harmadik nemzedékkel kiegészülve:

3 3 1 1 1 1 3 3 −3, −2, − , −1, − , − , − , 0, , , , 1, , 2, 3. 2 4 2 4 4 2 4 2 Majd a negyedikkel:

5 7 3 5 7 3 5 1 3 1 1 −4, −3, − , −2, − , − , − , −1, − , − , − , − , − , − , − , 2 4 2 4 8 4 8 2 8 4 8 1 1 3 1 5 3 7 5 3 7 5 0, , , , , , , , 1, , , , 2, , 3, 4. 8 4 8 2 8 4 8 4 2 4 2 Általában az

x1 , . . . , x m ,

n-edik

és az

lépés után

n + 1-edik

nél eggyel nagyobb

m := 2n+1 − 1

számunk van, növekv® sorrendben

lépésben megszületik az

x1 -nél

eggyel kisebb

{|x1 },

az

xm -

{xm |}, valamint az {xi |xi+1 }, i = 1, . . . , m − 1 alakú számok, melyek

a rendezésben összetev®ik között, t®lük egyenl® távolságra állnak  vagyis

{xi |xi+1 } +

{xi |xi+1 } = xi + xi+1 . Így állíthatóak tehát el® a diadikus törtek. Az összes diadikus tört ismeretében pedig megkonstruálhatjuk az  ω -adik nemzedéket, melynek számai szükségképpen végtelen sok összetev®vel bírnak. A már deniált

ω

1 ω

−ω = {|0, −1, −2, . . .},

0-tél különböz®, de hozzá minden diadikus törtnél  1 1 1  = 0 1, 2 , 4 , 8 , . . . és − ω1 = −1, − 12 , − 41 , − 18 , . . . |0} . S®t,

valamint az els® innitezimális, azaz közelebb fekv® számok:

mellett létrejön

8

minden diadikus törthöz készíthetünk hozzá innitezimálisan közeli számot, például

1 ω

1+

 = 1 2, 23 , 54 , 98 , . . . .

Végül ide tartoznak a nem diadikustört-alakú valós számok

is, melyek természetes felírását a kettes számrendszerbeli alakjuk szolgáltatja:

1 = 3



 1 3 1 5 0, , , . . . 1, , , . . . , 4 16 2 8

√ 2=

  1 23 5 11 1, , , . . . 2, , , . . . , 4 8 2 16   7 13 51 25 201 , . . . 4, , , , . . . . π = 3, , 8 64 2 4 16 Megjegyezzük, hogy az

ω -adik

nemzedék tagjait bevezethettük volna úgy is, mint a

diadikus törtek Dedekind-szeletei, azaz olyan

L

tört pontosan

ω -t,

ha

L

üres,

vagy

−ω -t

R

egyikében van, és

{L|R}

párok, melyekre minden diadikus

xL < x R

minden összetev®re. Ha

R

üres,

kapjuk, a többi esetben pedig diadikustól innitezimálisan eltér®t

vagy valósat, annak függvényében, hogy valamelyik oldalon van-e maximális elem, vagy sem. Az itt tárgyalt elmélet szemléletéhez azonban jobban illeszkedik, és könnyebben is kezelheté az el®bbi konvergens sorozatos megadás. További nevezetes számok:

ω − 1 = {0, 1, 2, . . . |ω},

ω − n = {0, 1, 2, . . . |ω, ω − 1, . . . , ω − (n − 1)},

ω = {0, 1, 2 . . . |ω, ω − 1, ω − 2, . . .}, 2 ω n o ω ω ω = 0, 1, 2, . . . , − 1, − 2, . . . , n−1 n−1 2n 2 2 2n−1   ω ω n o √ 2 1 1 1 ω = 0, 1, 2, . . . ω, , , . . . , = 1, , , . . . , 2 4 ω ω 2 4     1 1 1 1 1 1 = 0 , = 0 , , ,... stb. 2ω ω ω2 ω 2ω 4ω F® kutatási eszközünkr®l, az indukció ról szóló tétellel zárom a fejezetet.

0.2.6. Tétel (indukció). Ha T

egy tulajdonság, és Conway-játékok (számok) tetsz®leges

X = (x1 , . . . xn ) n-esére T (X)

következménye annak, hogy

9

T

teljesül minden

X -t®l

eltér®

(x01 , . . . x0n )-re,

akkor

T

ahol minden

i-re x0i

vagy maga

xi ,

vagy valamelyik összetev®je,

teljesül minden Conway-játékokból (számokból) álló

Ekkor van olyan

X1 =

nem igaz, ebb®l pedig az következik, hogy van olyan

X2 =

Bizonyítás. Tegyük fel, hogy valamely

(x01 , . . . x0n ),

amelyre

T

(x001 , . . . x00n ), amelyre T

X -re

n-esre.

nem teljesül

T.

szintén nem igaz, és így tovább. A kapott

X, X1 , X2 , . . . végtelen

sorozat minden i-re meghatároz egy összetev®i viszonyra nézve csökken® sorozatot. Ezek közül legalább az egyik végtelen, és így halmazok végtelen leszálló sorozatát adja meg, ellentmondásban a 0.1.1 állítással.

Indukcióval válik világossá, hogy minden szám Conway-játék, illetve hogy a

0-ból

induló konstrukció minden Conway-játékot el®állít. A tételt rugalmasan alkalmazzuk majd a bizonyításokban, néhol még ennél is általánosabb indukciós feltételt használva, de vigyázva arra, hogy a módszer korrekt maradjon.

10

1. fejezet Kétszemélyes játékok

Most  látszólag  teljesen más vizekre evezünk. Bevezetjük a kétszemélyes, teljes információs, véges lefutású játékok egy modelljét, a nyer® stratégiák segítségével rendezett csoportstruktúrát értelmezünk rajtuk, végül pedig rámutatnunk a stratégiai játékok és a Conway-játékok közötti kapcsolatra.

1.1. Deníció, példák A játék koncepciója a következ®: Adott egy bal- és egy jobb oldali játékos, az el®bbit

L-lel,

az utóbbit

R-rel

jelöljük. Adott a játék állapotainak

lapot, illetve az állapotok közötti

→L

és

→R

S

halmaza, az

s0

kezd®ál-

relációk. A játékosok megállapodnak, ki

kezdje a játékot

s0 -bél indulva, ezután felváltva lépnek. Ha a játék s állapotban van, és

L-en

L

L

van a sor,

bármely olyan

elvesztette a játékot.

R-re

s0

állapotba léphet, melyre

Ha nincs ilyen

s0 ,

hasonló áll.

Kikötjük továbbá, hogy ne létezzék állapotok olyan melyre

s →L s0 .

s0 → s1 → s2 → . . . ,

s0 , s1 , s2 , . . .

ahol  → azt jelenti, hogy

→L

és

végtelen sorozata,

→R

közül valamelyik

teljesül. Ez garantálja, hogy a játék véges sok lépésben befejez®dik, és valaki biztosan nyer. Végül még egy  technikai jelleg¶  kikötést teszünk: minden legyen elérhet® valamilyen meghatározott Minden

g

s0 → s1 → . . . → sn = s

játék jelölése:

s ∈ S

állapot

úton a kezd®állapotbél. Az így

(S, s0 , →L , →R ).

s állapotra létezik g -nek egy (S 0 , s, →L , →R ) részjátéka, ahol S 0 = {s}∪{s0 ∈ 11

S : s0

elérhet®

s-b®l}.

Ha

s0 →L s,

akkor a részjátékot

g

s0 →R s,

bal oldali, ha pedig

akkor jobb oldali opciójának nevezzük, és az ilyeneket a számoknál bevezetett jelöléshez hasonlóan,

g L -lel illetve g R -rel jelöljük. Két játék izomorf, és ezt  ∼ =

szimbólummal

jelöljük, ha állapotaik között relációtartó bijekció létesíthet®. Most néhány példa következik, amelyekre kés®bb hivatkozni fogunk: A

dominójáték

kezd®állapota a síkbeli koordinátarendszer rácsnégyzeteinek egy

véges részhalmaza. Egy lépésben a soron következ® játékos elvehet a négyzetek közül két szomszédosat, azaz egy dominóformát, de ges állású dominót vehet el. A számok

(k1 , k2 , . . . , kn )

(m1 , m2 , . . . , mn ), tetsz®leges

L

csak vízszintes,

R

csak függ®le-

kupac- vagy NIM-játékban az állapotok természetes

n-esei, ahol

ki ≤ mi

rögzített

mi

számokra. A kezd®állapot

és mindkét játékos egy lépésében valamelyik

ki -t

megváltoztathatja

ki -nél kisebb természetes számra  egyetlen kupacból kell elvennie, de abból

bármennyit elvehet. Értelemszer¶en az nyer, aki el®bb eljut a

0

állapotba. Ismeretes

a játéknak olyan változata is, ahol éppen az veszít, aki az utolsó elemet kényszerül

w

elvenni. Ilyenkor be kell vezetni még egy Egy

0 →L w, 0 →R w

relációkat.

x Conway-játék is felfogható a fenti értelemben vett játékként. A kezd®állapot x, minden xL -re x →L xL , minden xR -re x →R xR , x minden x0

legyen maga re

állapotot és a

x0 →L x0L

illetve

x0 →R x0R

összetev®jé-

és így tovább. Az így deniált állapotok halmazt alkotnak

(a kumulatív hierarchiát lehet felhasználni ennek bizonyításához, lásd 0.1), a játék végességét pedig 0.1.1 biztosítja. A tartalmazási viszony miatt kézenfekv® az a szemlélet is, hogy

x-et

magával a játékkal, az összetev®it az opciókkal stb. azonosítsuk.

1.2. Nyer® stratégiák Egy

g = (S, s0 , →L , →R )

W : {s ∈ S : ∃s0 (s →L s0 )} → S

játékban a

stratégiája, ha az értelmezési tartomány minden elemére

R

kezdése melletti nyer® stratégiája, ha

kezd és

L

minden lépésében

W -t

jelöljük. Hasonlóan deniáljuk

LgR

és

RgR,

vagy hogy

LgL

követi,

L

LgL, RgL

és

RgL

g

s →L W (s).

A

függvény

W

az

L-nek

tetsz®leges olyan lejátszásában, amikor

nyer. Ilyen nyer® stratégia létezését

és

RgR

R

LgR-rel

teljesülését. Nyilván lehetetlen, hogy

egyszerre igazak legyenek.

12

L

Ha

F : g → h

F (W (F −1 ))

izomorzmus, és

W

bizonyos típusú nyer® stratégia

ugyanolyan típusú nyer® stratégia

h-ban;

g -ben,

akkor

ezért izomorf játékok nyer® stra-

tégiák szempontjából ugyanúgy jellemezhet®k.

1.2.1. Állítás. (1) Ha

g -nek

(2) Ha

g

minden bal oldali opciójára

Bizonyítás. (1) Legyen hogy el®ször

g

WL

az

L-nek

nincs bal oldali opciója,

L

Rg L R,

LgL.

akkor

akkor

RgL.

Lg L R-et igazoló nyer® stratégia. Ha L úgy játszik g -ben,

kezd®állapotából

biztosan nyer. Tehát

valamilyen

Lg L R,

valamely bal oldali opciójára

gL

kezd®állapotába lép, ezután pedig

van nyer® stratégiája

g -ben,

W L -et

követi,

amikor ® kezd. (2) Ha

g -nek

már a kezd®lépésnél elveszti a játékot. Ha bele tud lépni

g L -be, R játszhatja az ehhez az opcióhoz tartozó W R

megnyeri a játékot. Az ilyen

W R -ek

egyesítése adja tehát

R

nyer® stratégiáját, így

nyer® stratégiáját az egész

g -ben. Természetesen az

1.2.2. Tétel. esetén

T (g)

L

és

R

szerepét felcserélve kapott duális állítás is igaz.

[indukció játékokra] Legyen

következménye annak, hogy

T g

T

egy tulajdonság. Ha tetsz®leges

g

játék

T

minden

g1

opciója,

minden opciójára teljesül, akkor

játékra teljesül. Bizonyítás. Ha van olyan amelyre nem igaz tovább. A

g0 ,

T , g1 -nek

amelyre nem igaz

pedig van olyan

g2

T,

akkor

g0 -nak

van olyan

opciója, hogy arra sem igaz

T,

és így

gi játékok si kezd®állapotai egy tiltott s0 → s1 → s2 → . . . végtelen sorozatot

adnak. Ellentmondás.

A tétel általánosítható játékok

n-eseire, a 0.2.6-hoz hasonló módon. Most indukcióval

igazoljuk, hogy valakinek mindig van nyer® stratégiája:

1.2.3. Tétel.

Minden

g

játékra igaz a következ® formula:

(LgL ∨ RgL) ∧ (LgR ∨ RgR).

Bizonyítás. A formula els® felét igazoljuk, a másik fele ennek a duálisa. Az indukciós feltevés szerint minden

g L -re

igaz a formula, tehát

13

Lg L R

vagy

Rg L R

teljesül. Ha van

olyan bal oldali opció, melyre

Rg L R,

Lg L R,

akkor 1.2.1 miatt

akkor ismét 1.2.1 következtében

LgL.

Ha pedig mindegyikre

RgL.

A játékok tehát a következ® négy osztályba sorolhatók:

Osztály

L R S F

Tulajdonság

Jelölés

LgL ∧ LgR,

a játék

L-nek

RgL ∧ RgR,

a játék

R-nek

RgL ∧ LgR,

a játék a másodiknak jó

g=0

LgL ∧ RgR,

a játék az els®nek jó

gk0

g>0

jó

g<0

jó

Az utolsó oszlop jelölései egyel®re csak szimbólumok, de rövidesen értelmet nyernek. Ha

LgR

írunk,

igaz, akkor a

g

játék az

L-hez vagy az S-hez tartozhat, ezért ilyenkor g ≥ 0-t

RgL helyett pedig hasonló megfontolásból g ≤ 0-t. Az 1.2.1 állítás átfogalmazása

az új írásmódunkkal és ismereteinkkel:

• g≥0

pontosan akkor, ha minden

g R -re g R  0.

• g≤0

pontosan akkor, ha minden

g L -re g L  0.

Példák. Egy NIM-játékban a két játékos lépéslehet®ségei megegyeznek, ezért az csak F-beli, vagy S-beli lehet. Az el®bbire példa, ha egyetlen nemüres, vagy ha két eltér® elemszámú kupac van, az utóbbira pedig, ha két megegyez® elemszámú. A dominójátékok között mind a négy osztályhoz könnyen találunk reprezentánsokat. A Conwayjátékok közti legegyszer¶bb példák az osztályokra, a fenti táblázat sorrendjét követve:

1, −1, 0, ∗.

1.3. Játékok ellentettje és összege 1.3.1. Deníció. Zérójátéknak nevezzük a 0 Conway-játéknak megfeleltetett ({0}, 0, ∅, ∅) játékot. Amennyiben nem okoz félreértést, ezt is

A zérójáték az

S

0-val

jelöljük.

osztályba tartozik, hiszen bárki is kezdje a játékot, veszít, mert

nincs szabályos nyitó lépése. Részben ezt el®legezte meg az  =

14

0

szimbólum.

1.3.2. Deníció. A g = (S, s0 , →L , →R ) játék ellentettje: −g = (S, s0 , →R , →L ), vagyis a két játékos lépéslehet®ségeinek felcserélésével kapott játék. Nyilvánvalóan

−0 ≡ 0,

tetsz®leges

g

játékra pedig

azaz ha A

g ≥ 0,

−g -beli nyer® stratégiává, ezért LgR-b®l következik R(−g)L,

−g ≤ 0;

akkor

(az  ≡ szimbólum

g -beli nyer® stratégiát a szerepek felcse-

játékok között is azonosság ot fog kifejezni). Egy rélésével át lehet alakítani

−(−g) ≡ g

és fordítva.

g1 és g2 játékok g1 +g2 összegén olyan játékot értünk, amiben L és R párhuzamosan

játsszák a két játékot, oly módon, hogy a soron következ® játékosnak

g1 -ben vagy g2 -ben

kell megtennie egy számára szabályos lépést, de csak az egyikben; ha egyik játékban sincs lehet®sége lépni, akkor veszít. Formálisan:

1.3.3. Deníció. (S, s0 , →L , →R )

gi = (Si , s0i , →Li , →Ri ) (i ∈ {1, 2})

A

S = S1 × S2 , s0 = (s01 , s02 ),

játék, ahol

s1 →L1 s01

pontosan akkor, ha vagy

játékos lépéseire is hasonló áll. A

valamint a

−(g + h) ≡ −g − h

1.3.4. Állítás. (1)

és

s2 = s02 ,

g1 − g2

Tetsz®leges

g

vagy

és

továbbá

s1 = s01

azt jelenti, hogy

g+0 ∼ = g, g + h ∼ = h+g

Triviálisak a

játékok összege az a

és

g1 + g2 =

(s1 , s2 ) →L (s01 , s02 )

s2 →L2 s02 ,

és az

R

g1 + (−g2 ).

(g + h) + k ∼ = g + (h + k)

izomorák,

azonosság.

és

h

játékokra

g − g = 0,

(2) ha

g≥0

h ≥ 0,

(2) ha

g+h≥0

és

Bizonyítás. (1) A

és

akkor

h ≤ 0,

g−g = 0

g + h ≥ 0,

akkor

g ≥ 0.

azt jelenti, hogy

g−g

az

S osztályban van, azaz mindig

a másodjára lép®nek van nyer® stratégiája. Valóban, a gy®zelemhez a másodiknak csak másolnia kell a kezd® játékos lépéseit az ellenkez® komponensben, mint amelyikben a partnere lépett. (2) Tudjuk, hogy megnyeri amiben

g + h-t

R

L-nek g -ben és h-ban is van nyer® stratégiája, ha R kezd. Ekkor L

is, ha

R

minden lépésére ugyanabban a komponensben válaszol, mint

lépett, az ottani nyer® stratégiáját követve.

15

(3) Indirekt bizonyítunk: azt fogjuk belátni, hogy ha vagyis

RgR

és

RhL

ha els® lépését a

g

következménye

komponensben, a

további részében pedig amelyikben

L

R(g + h)R.

L

Az

R

g  0 és h ≤ 0, akkor g +h  0,

játékos valóban megnyeri

g + h-t,

g -beli nyer® stratégiáját követve teszi meg, a játék

minden lépésére ugyanabban a komponensben válaszol, mint

lépett, méghozzá az ottani nyer® stratégiája szerint.

1.4. Részben rendezés játékok között 1.4.1. Deníció.

A

g ≥ h

reláció pontosan akkor teljesül, ha

g−h ≥ 0

a Nyer®

stratégiák részben bevezetett jelöléssel. A nagyobb vagy egyenl® reláció segítségével

értelemszer¶en deniáljuk a kisebb vagy egyenl®, nagyobb, kisebb és egyenl® relációkat.

1.4.2. Állítás. g ≥ 0 is és g ≤ 0 is ugyanazt jelentik a régi és az új értelemben. Bizonyítás. El®ször azt kell igazolnunk, hogy a régi értelemben vett ekvivalensek. A

−0 ≡ 0

Hivatkozhatunk a akkor

0≥0

g + 0 ≥ 0.

a régi jelöléssel. A

0+g ∼ = g+0

g + 0 ≥ 0.

izomorára, de használhatjuk az 1.3.4 állítást is: Ha

Az új értelemben vett jelöléssel

0−g ≥ 0

g−0 ≥ 0

és

azonosság miatt az utóbbi ugyanazt jelenti, mint

g+0 ∼ =g

és (2) miatt

g≥0

Ha pedig

g≤0

g + 0 ≥ 0,

akkor

azt jelenti, hogy

0≤0

0 ≥ g,

−(0 − g) ≡ −0 + g ≡ 0 + g

izomorából következik, hogy

0−g ≥ 0

és (3) miatt

g ≥ 0.

ami deníció szerint

ekvivalenciákból és a

ekvivalens azzal, hogy

g + 0 ≤ 0.

Arra jutottunk tehát, hogy az állítás másik részéhez a régi értelemben vett

g+0 ≤ 0

g ≥ 0,

g ≤0

és

ekvivalenciáját kell igazolnunk. Ehhez az 1.3.4-beli (2) és (3) állítások duális

megfelel®it használhatjuk, a már látott módon. A Nyer® stratégiák rész táblázatát tanulmányozva látható, hogy az állítás következményeképpen a

g > 0, g < 0

és

g =0

szimbólumok is egybevágnak a 1.4.1 deníció

szerinti, zérójátékkal való összehasonlítással.

1.4.3. Állítás.

A  ≥ reláció reexív és tranzitív a játékokon.

Bizonyítás. A reexivitás 1.3.4/(1) közvetlen következménye. Az kell még, hogy és

h≥k

következménye

g≥h

g ≥ k . A feltevés azt jelenti, hogy g − h ≥ 0 és h − k ≥ 0. Ebb®l 16

1.3.4/(2) miatt Mivel

(g − h) + (h − k) ≥ 0,

izomorf átalakítással pedig

(g − k) + (h − h) ≥ 0.

h − h ≤ 0, ezért 1.3.4/(3) következtében g − k ≥ 0, vagyis g ≥ k , amit bizonyítani

kellett. Az állítás fontos következménye, hogy az  = valóban ekvivalenciareláció, és a  ≥ részben rendezés az ekvivalenciaosztályokon.

1.4.4. Állítás.

Tetsz®leges

g, h

és

k

(1) ha

g ≥ h,

akkor

−h ≥ −g ,

(2) ha

g ≥ h,

akkor

g + k ≥ h + k.

játékokra

Bizonyítás.

De

(1) Mivel

g−h∼ = −h + g ,

(2) Mivel

g − h ≥ 0 a feltétel szerint, és k − k ≥ 0 is igaz, ezért (g − h) + (k − k) ≥ 0.

ezért

g ≥ h ⇒ g − h ≥ 0 ⇒ −h + g ≥ 0 ⇒ −h ≥ −g .

(g − h) + (k − k) ∼ = (g + k) − (h + k),

ami az állítást igazolja.

Ennek következtében az ellentettképzés és az összeadás zárt az ekvivalenciaosztályokra. Az utóbbi belátásához még annyit kell megjegyezni, hogy ha akkor

g1 ≥ g2

és

h1 ≥ h2 ,

g1 +h1 ≥ g2 +h2 . Valóban, 1.4.4/(2) miatt g1 +h1 ≥ g2 +h1 , illetve h1 +g2 ≥ h2 +g2 ,

innen pedig már csak izomorf felcserélés és tranzitivitás kell. Eddigi ismereteinket jól összefoglalja a következ® tétel:

1.4.5. Tétel.

A játékok ekvivalenciaosztályai részben rendezett Abel-csoportot alkotnak

az összeadással és a  ≥ relációval, ahol a semleges elem az

S osztály, az inverz pedig

az ellentett.

1.5. Kapcsolat a Conway-játékokkal 1.5.1. Állítás.

Tetsz®leges

gR,

g ≥ gR.

olyan

melyre

g

játékra igaz, hogy nincs olyan

gL,

melyre

gL ≥ g,

és nincs

Bizonyítás. Csak az els® állítás igazolását részletezzük, a másiké hasonlóan megy. Azt kell belátnunk, hogy minden

g L -re g L − g  0, vagyis R(g L − g)R. Az R játékos valóban 17

gy®zhet

(g L − g)-ben, ha el®ször a −g

−g L

komponensnek a

opciójába lép, majd a már

látott másolási stratégiát követi.

1.5.2. Tétel hogy

h ≥ gR,

.

(induktív jellemzés)

és nincs olyan

hL ,

Bizonyítás. Tegyük fel, hogy miatt

Pontosan akkor teljesül

ha nincs olyan

gR,

hL ≥ g .

hogy

g ≥ h.

g ≥ h,

Ha bizonyos

g R -re h ≥ g R ,

akkor a tranzitivitás

g ≥ g R . Ha pedig van olyan hL , hogy hL ≥ g , akkor hL ≥ h. Mindkett® ellentmond

az el®z® állításnak. A másik irányhoz tegyük fel, hogy

g  h,

azaz

nyer® stratégiája kétféleképp kezd®dhet. Vagy a azt kapjuk, hogy valamely azaz

h ≥ gR.

R(g − hL )L,

Ha viszont

g R -re R(g R − h)L,

−h-ban

amib®l pedig

R(g − h)R. g

R

játékos

g − h-beli

komponensben lép el®ször, és így

ami azzal ekvivalens, hogy

kezdi a játékot, akkor

hL ≥ g

Az

h

L(h − g R )R,

egy bal oldali komponensére

vezethet® le.

Megjegyezzük, hogy a bizonyításhoz használhattuk volna a  ≥

0

szimbólum Nyer®

stratégiák részben megismert induktív jellemzését is.

1.5.3. Tétel. Ekkor

x≥y

és

y  xR

és

(y L )G  xG .

ak pedig a

Conway-játékok,

pontosan akkor teljesül, amikor

Bizonyítás. Az v®re

x, y

Legyenek

x≥y

yG -nak

pedig a nekik megfelel® játékok.

xG ≥ y G .

egyenl®tlenség deníció szerint azt jelenti, hogy minden összete-

y L  x. De az

xG , y G

Ekkor a 0.2.6 szerinti indukciós feltételt használva

(xR )G

alakú játékok

xG -nek

az összes jobb oldali, a

yG  (xR )G

(y L )G

alakú-

az összes bal oldali opcióit adják, így az induktív jellemzés alapján

xG ≥ y G . Fordítva, legyen

(xG )R egy

és

yL,

xG ≥ yG .

(yG )L  xG .

Minden

Ekkor az induktív jellemzés szerint minden opcióra

(xG )R -hez

tartozik egy

és minden

(yG )L -hez

tartozik

melyek meghatározzák ezeket a játékokat. Ezért használhatjuk a játékpárokra

általánosított 1.2.2 szerinti indukciós feltételt:

y  xR

xR ,

yG 

és

y L  x,

tehát

x

és

x ≥ y.

Megjegyzés. (xR )G ≡ (xG )R és (xL )G ≡ (xG )L . 18

y

minden érintett összetev®jére

Egy

g

játékhoz természetes módon hozzárendelhet® egy

gC

Conway-játék, melyet

rekurzívan deniálhatunk:

 gC ≡ (g L )C (g R )C . Megmutatható, hogy minden giai játékra

(gC )G = g .

x

Conway-játékra

(xG )C ≡ x,

illetve minden

g

straté-

Ezen összefüggéseken keresztül megfeleltethet®k egymásnak a

stratégiai és Conway-játékok addíciói, és így átvihetjük az ebben a fejezetben kapott eredményeket Conway-játékokra, azt kapva, hogy a Conway-játékok ekvivalenciaosztá-

lyai rendezett Abel-csoportot alkotnak, a

0

osztályával mint zéróelemmel.

A fentiek szemléletesen elfogadhatók, precíz bizonyításuk pedig az 1.5.3 tételéhez hasonlóan technikai jelleg¶. Az átvitel részletes felépítése megtalálható [2]-ben, itt nem közöljük. A Conway-játékok gyakran könnyebben kezelhet®k, ha stratégiai játékokként tekin-

x

tünk rájuk. Például adott arra, hogy az

xG − yG

és

játék az

y

Conway-játékok egyenl®ségének kérdése lefordítható

S

egyenl®séget ezzel a módszerrel! A

1 2

+ 12 − 1

osztályba tartozik-e. Igazoljuk most az

−1 ≡ {|0}

Conway-játéknak megfelel®

g

és az

1 2

≡ {0 |1}

1 2

+

1 2

= 1

alakokat használva a

játék így szemléltethet®:

d-be vezet, akkor L valamelyik 21 -es komponensben tud válaszolni, lépjen mondjuk a-ba. Ezután R-nek b'-be, majd L-nek c'-be kell lépnie, így L nyeri meg a játékot. Ha R valamelyik 12 -es komponensben kezd, Tegyük fel, hogy

az

L

R

a játéknyitó. Ha els® lépése

játékos pedig a másik

® nyer; tehát

LgR

1 -es komponensben válaszol a kezd® lépésre, végül akkor is 2

igaz. Ha viszont

nyer® stratégiát; így

RgL

L

kezd, akkor

is áll, a játék valóban

19

R

követhet az el®bb leírthoz hasonló

S osztálybeli.

2. fejezet A Conway-számok teste

Ebben a fejezetben a Conway-számokat meghatározó rekurzív szabályokból kiindulva kezdünk el kutatni. Megmutatjuk, hogy a számok rendezés szerinti ekvivalenciaosztályai rendezett testet alkotnak. Igyekszünk majd kiemelni, mely állítások igazak csak számokra, és melyek teljesülnek minden Conway-játékra, melléktermékként megkapva ezzel a Conway-játékok rendezésével és összeadásával kapcsolatos, az el®z® fejezetben játékelméleti eszközökkel igazolt eredményeket is. Szinte mindent indukcióval fogunk belátni, ezért az indukciós feltételt hallgatólagosan mindig eleve feltesszük. Emlékeztet®ül gy¶jtsük össze a számokról szóló, már szerepelt deníciókat:

•

Az

x

rendezett pár pontosan akkor szám, ha minden összetev®je szám, és nincse-

nek olyan

• x≤y

xL , x R

összetev®i, melyekre

xR ≤ xL .

pontosan akkor, ha nincs olyan

xL ,

hogy

y ≤ xL ,

és nincs olyan

yR,

hogy

y R ≤ x.  • x + y ≡ xL + y, x + y L xR + y, x + y R .  • −x ≡ −xR −xL .  • xy ≡ xL y + xy L − xL y L , xR y + xy R − xR y R L x y + xy R − xL y R , xR y + xy L − xR y L . Szükségünk lesz még a

0 ≡ {|}

és az

1 ≡ {0|} 20

kitüntetett elemekre.

2.1. Rendezés 2.1.1. Állítás. (1)

tetsz®leges

x, y , z

esetén igazak:

x ≤ x,

(2) minden

xL , xR -re xL  x

(3) ha

x≤y

(4) ha

x, y

és

y ≤ z,

akkor

számok, akkor

Bizonyítás. Ha

x  x,

és

x R  x,

x ≤ z,

x≤y

akkor vagy

és

x≥y

közül legalább az egyik teljesül.

∃xR ≤ x,

vagy

∃xL ≥ x

igaz. El®bbi esetben

nincs olyan jobb oldali összetev®je, ami kisebb vagy egyenl®, mint

xR ,

az utóbbiból pedig hasonló módon

xL  xL

x-nek

xR , speciálisan xR 

következik, így indukcióval belátható

(1). A (2) állítás nem más, mint a reláció deníciója (1)-re felírva. A tranzitivitás bizonyításához tegyük fel indirekt, hogy els®b®l és

x ≤ y -b®l

indukció alapján

x  z.

zR ≤ y,

Ekkor vagy

tehát

y  z,

∃z R ≤ x

vagy

∃xL ≥ z .

Az

a másikból pedig hasonlóan

x  y , mindkett® ellentmondás. Végül tegyük fel, hogy x, y számok, és x  y , x  y . Ha ∃y R ≤ x

és

∃y L ≥ x,

akkor (3) szerint

Amennyiben a második helyett

∀y R ≥ xR .

Mivel

egyenl®, mint feltétel helyett

x,

y -nak (3)-b®l

yR ≤ yL,

∃xR ≤ y

ellentmondásban a szám deníciójával.

igaz, akkor ebb®l

@y R ≤ xR ,

így indukcióval

van jobb oldali összetev®je, amir®l tudjuk, hogy kisebb vagy

xR ≤ x,

∃xL ≥ y -t

ami (2)-nek mond ellent. Ha az elején a

∃y R ≤ x

teszünk fel, ugyanúgy okoskodhatunk, így igazoltuk (4)-et

is.

2.1.2. Következmény.

Az  = valóban ekvivalenciareláció, és  ≤ részben rendezés

az ekvivalenciaosztályokon, számokra megszorítva ráadásul teljes is. Ezért ha

x

szám, akkor (2) írható

xL < x < xR

osztályainak összességét Conwayt követve

alakban is. A számok ekvivalencia-

No-val jelöljük. Ezután ha számról esik szó,

No-beli objektumot értünk majd alatta. Megjegyzés. No fenti meghatározása nem a

sokszor

legszerencsésebb, ugyanis nem biz-

tos, hogy minden ekvivalenciaosztály halmaz (igazából egyik sem az), és így

No nem

lesz osztály, vagyis halmazok összessége. Ezt a problémát kiküszöbölhetjük úgy, hogy

21

minden

x

számra elkészítjük az

sebb olyan

α

rendszám, hogy

összességét hívjuk

2.1.3. Tétel mely

[x] ≡ {y : y = x, y ∈ Vαx }

Vα

tartalmaz

z -re xR  z  xL

Bizonyítás. Az

αx

a legki-

egyenl® számot (lásd 0.1); és ezek

No-nak.

(Els®szülöttségi lemma)

ugyanezt. Ekkor

x-szel

halmazt, ahol

minden

xL , xR

.

Legyen

 x = xL xR ,

esetén, de

és tegyük fel, hogy vala-

z -nek egyetlen összetev®je sem teljesíti

x = z.

x≤z

egyenl®séghez az kell, hogy

z  xL

és

zR  x

minden szóba jöv®

összetev®re. Az el®bbi közvetlenül megjelenik a lemma feltételében, az utóbbi pedig azért igaz, mert minden

z R -hez van olyan xR , hogy xR ≤ z R . A fordított egyenl®tlenség

hasonlóan igazolható.

A tétel számokra alkalmazva szemléletesen azt jelenti, hogy egy és

xR -ek

x

szám az

xL -ek

között álló számok közül a legegyszer¶bb, vagyis a legkorábban konstruált.

Könnyen meggondolható speciális esetei:

2.1.4. Következmény.

Ha

x

és

y

összetev®i között olyan bijekció létesíthet®, hogy

az egymásnak megfeleltett összetev®k ugyanazon az oldalon állnak és egyenl®ek, akkor

x = y.

2.1.5. Következmény.

Ha

x

szám, és

x0

úgy keletkezik

x-b®l,

hogy

x

bal oldaláról

elhagyunk néhány számot, melyeknél van nagyobb szám a bal oldalon, illetve a jobb oldaláról néhányat, melyeknél van kisebb a jobb oldalon, akkor

x0

is szám, és

x = x0 .

Ez

akkor is igaz, ha nem elhagyunk, hanem hozzáírunk ilyen összetev®ket.

2.2. Összeadás Triviális, hogy cióval:

−0 ≡ 0,

a következ® azonosságok pedig könnyen igazolhatók induk-

x+y ≡ y +x, (x+y)+z ≡ x+(y +z), x+0 ≡ x, −(−x) ≡ x, −(x+y) ≡ −x−y .

Példának álljon itt az asszociativitás bizonyítása:

(x+y)+z ≡ {(x+y)L +z, (x+y)+z L | . . .} ≡ {(xL +y)+z, (x+y L )+z, (x+y)+z L | . . .} ≡

22

≡ {xL + (y + z), x + (y L + z), x + (y + z L )| . . .} ≡ ≡ {xL + (y + z), x + (y + z)L | . . .} ≡ x + (y + z).

2.2.1. Állítás. (1) Ha

x≤y

és

z ≤ w,

akkor

x + z ≤ y + w.

(2) Ha

xy

és

z ≤ w,

akkor

x + z  y + w.

Bizonyítás. (1) Itt többek között azt kell ellen®rizni, hogy fennáll. Ehhez elég lenne az, hogy minden

yL,

vagy van olyan mert

hogy

∃xL R ≤ y ,

xL + z  y + w . (2) Az

∃y L ≥ xL .

vagy

minden

xL -re

xL -hez van olyan xLR , hogy xLR + z ≤ y + w,

xL + z ≤ y L + w .

x ≤ y -ból deníció szerint xL  y

xL + z  y + w

A kett® közül az egyik valóban teljesül,

minden bal oldali összetev®re, innen pedig vagy

Ezután pedig

z ≤ w-t

felhasználva indukcióval igazolható

A másik három szükséges feltétel bizonyítása hasonlóan megy.

x+z  y+w teljesüléséhez az kell, hogy ∃(y+w)L ≥ x+z és ∃(x+z)R ≤ y+w

közül valamelyik teljesüljön. Az igaz. A el®bbib®l

xy

yL + w ≥ x + z,

biztosítja, hogy vagy

az utóbbiból pedig

∃y L ≥ x,

xR + z ≤ y + w

vagy

∃xR ≤ y

vezethet® le (1)

felhasználásával.

Speciálisan

x ≤ y ⇒ x + z ≤ y + z,

ami az additív csoport rendezettségéhez

kell. Triviális következmény az is, hogy egyenl® Conway-játékok összege egyenl®, így ekvivalenciaosztályokra is értelmes az összeadás és igazak az azonosságok. Azt viszont még nem tudjuk, hogy

2.2.2. Állítás.

Ha

x

No zárt-e az összeadásra.

és

y

számok, akkor

Bizonyítás. Az indukciós feltevés miatt

yL < y < yL

x+y

x+y

is szám.

összetev®i számok. Az

egyenl®tlenségekb®l 2.2.1 szerint következnek:

x + y R , x + y L  xR + y

2.2.3. Állítás.

és

Minden

x

(1)

x ≤ y ⇒ −x ≥ −y ,

(2)

x = y ⇒ −x = −y ,

y

Conway-játékra

23

és

xL + y  xR + y , xL + y 

x + y L  x + y R , azaz (x + y)L  (x + y)R és

xL < x < x R

mindig teljesül.

(3) ha

(4)

x

szám, akkor

−x

szám,

x − x = 0.

Bizonyítás. Ha indirekt

−x  −y ,

∃ − xL ≤ −y ,

els® azt jelenti, hogy

akkor vagy

∃(−x)R ≤ −y ,

amib®l indukcióval

vagy

∃(−y)L ≥ −x.

xL ≥ y ⇒ x  y .

Az

A másodikból

hasonlóan jön ki az ellentmondás, (1) kész. (1)-b®l (2) nyilvánvaló. Az indukciós feltevés szerint

−xR ≥ −xL

−xR

és

−xL

számok. Ha indirekt feltesszük, hogy

el®fordul, akkor ebb®l (1) szerint

xR ≤ xL ,

tehát

x

nem szám, ellent-

mondás; ezzel igazoltuk (3)-at. Az

x − x ≥ 0-hoz

xR ≥ xR

és

az kell, hogy

−x  −xR

xR − x  0

x − xR  0,

x − xL  0.

egyenl®tlenségekb®l, 2.2.1 és az

miatt. A másik hasonlóan igazolható. Az és

és

x ≤ 0-hoz

Az el®bbi következik az

xR − xR = 0

indukciós feltevés

szükséges feltételek:

xL − x  0

de ezek (1) miatt ekvivalensek az el®bb bizonyított kett®vel. Tehát

x − x = 0.

2.2.4. Következmény. A Conway-játékok osztályai részben rendezett, No pedig rendezett Abel-csoport az összeadásra. Az ellentett valóban a m¶veletre vonatkoztatott inverz.

2.3. Szorzás Nyilván

x0 ≡ 0,

x(−y) ≡ −xy

továbbá indukcióval beláthatók az

x1 ≡ x, xy ≡ yx

és

(−x)y ≡

azonosságok. A disztributivitást és az asszociativitást azonban csak

egyenl®ség formájában írhatjuk fel, ugyanis az el®bbi igazolásához

x−x = 0

típu-

sú egyszer¶sítés kell, az utóbbiéhoz pedig a disztributivitás. Például a disztributivitás bizonyítása:

(x + y)z ≡ {(x + y)L z + (x + y)z L − (x + y)L z L , . . . | . . .} ≡ ≡ {(xL + y)z + (x + y)z L − (xL + y)z L , (x + y L ) + (x + y)z L − (x + y L )z L , . . . | . . .} = = {(xL z + xz L − xL z L ) + yz, xz + (y L z + yz L − y L z L ), . . . | . . .} ≡ xz + yz.

24

Két szám szorzatát felírhatjuk a következ®, a deníció mögötti szemléletet megvilágító alakban is:

xy = {xy − (x − xL )(y − y L ), xy − (xR − x)(y R − y)| |xy + (x − xL )(y R − y), xy + (xR − x)(y − y L )}.

2.3.1. Tétel. (1) Ha

Számokra teljesülnek a következ®k:

x1 ≤ x2

és

y1 ≤ y2 ,

akkor

x1 y2 + x2 y1 ≤ x1 y1 + x2 y2 .

Amennyiben mindkét

feltételben szigorú egyenl®tlenség van, úgy a következményben is. (2) Ha

x 1 = x2 ,

(3) Ha

x

és

y

y

akkor tetsz®leges

számok, akkor

xy

számra

x1 y = x2 y .

is szám.

Bizonyítás. A részállításokat egyetlen egységként, közös indukciós feltétellel bizonyítjuk, ami gyakorlatilag azt jelenti, hogy egynek az igazolásához felhasználhatjuk a másik kett®t. Jelöljük az (1)-beli egyenl®tlenség teljesülését hogy

x1 ≤ x2 ≤ x 3

P (x1 , x2 : y1 , y2 )-b®l

esetén

és

ségek összeadásával és egyszer¶sítéssel levezethet® (1) Ha

x1 = x2

vagy

P (x1 , x2 : y1 , y2 )-vel. Vegyük észre,

P (x2 , x3 : y1 , y2 )-b®l P (x1 , x3 : y1 , y2 ).

y1 = y2 , akkor (2) miatt a két oldal tagjai páronként egyenl®ek.

Elég tehát csak a szigorú egyenl®tlenségek esetével foglalkozni. Ha

x1 < x1 R ≤ x2 ,

vagy

x1 ≤ x2 R < x2

hogy az el®bbi igaz. Ekkor a szigorú és a szigorú

az egyenl®tlen-

P (x1 , x1 R : y1 , y2 )-b®l.

bizonyos

x1 R

vagy

P (x1 , x2 : y1 , y2 )

x2 L

x1 < x2 ,

akkor vagy

összetev®re. Tegyük fel,

következik

P (x1 R , x2 : y1 , y2 )-b®l

Az els® indukciós feltevés, a második igazolásához

pedig még egy szinttel lejjebb kell ereszkedni

y1 < y2

segítségével. Összességében arra

jutunk, hogy ilyen alakú egyenl®tlenségeket kell ellen®riznünk:

P (xL , x : y L , y),

P (xL , x : y, y R ),

Ezek éppen azt fejezik ki, hogy

xy

P (x, xR : y L , y),

P (x, xR : y, y R ).

nagyobb a bal oldali és kisebb a jobb oldali összete-

v®inél, ami (3) miatt igaz.

25

(2) Vegyük mondjuk azt a szükséges feltételt, hogy Indukcióval

x1 y L = x2 y L

x1 L < x2

yL < y

és

és így azt kapjuk, hogy

x1 L y + x1 y L − x1 L y L  x2 y .

x1 L y + x2 y L  x1 L y L + x2 y ,

ami

miatt következik (1)-b®l. A többi hét feltétel ugyanígy igazolható.

(3) Az indukciós feltevés miatt

xy

összetev®i számok. Most is csak az egyik összete-

v®páron mutatjuk be a bizonyítás menetét:

? xL1 y + xy L − xL1 y L < xL2 y + xy R − xL2 y R . Ha

x 1 ≤ x2 ,

P (xL1 , xL2 : y L , y)

akkor

és

P (xL2 , x : y L , y R )

következtében

xL1 y + xy L − xL1 y L ≤ xL2 y + xy L − xL2 y L < xL2 y + xy R − xL2 y R , ha pedig

x2 ≤ x1 ,

akkor

P (xL1 , x : y L , y R )

és

P (xL2 , xL1 : y, y R )

miatt

xL1 y + xy L − xL1 y L < xL1 y + xy R − xL1 y R ≤ xL2 y + xy R − xL2 y R .

A számok osztályai tehát zártak a szorzásra, továbbá ha

P (0, x : 0, y)

következtében

xy ≥ 0.

x ≥ 0

és

y ≥ 0,

akkor

Eddigi ismereteinket összefoglalhatjuk úgy, hogy

No rendezett gy¶r¶. Ez nem általánosítható Conway-játékokra. Vegyük például a játékot és a vele egyenl®

{0|0, 1}-et.

két szorzat nem egyenl®, hiszen

Ekkor

∗ · ∗ ≡ ∗,

illetve

∗ ≡ {0|0}

Conway-

∗ · {0|0, 1} ≡ {0, ∗|0, ∗}.

∗ = ∗.

A 2.3.1/(1) szigorú változatából levezethet® a nullosztómentesség. Ezért ha és

xz = yz ,

x-nek

és

akkor

y 6= 0-nak

A

xz − yz = 0 ⇒ x(y − z) = 0 ⇒ y − z = 0 ⇒ y = z . létezik hányados a, vagyis olyan

z

szám, melyre

yz = x,

x 6= 0

Tehát ha akkor az

egyértelm¶. A létezéshez elég az, hogy minden pozitív számnak van reciproka. Egy pozitív számot pedig felírhatunk

x = {0, xL |xR }

közül csak a pozitívak szerepelnek. Ezt

∃xL ≥ 0

alapján a következ® tétel biztosítja, hogy

alakban, ahol

bal oldali összetev®i

és 2.1.5 miatt tehetjük meg. A fentiek

No rendezett test :

26

x

x

2.3.2. Tétel. Legyen x {0, xL |xR } alakú, ahol az xL -ek pozitívak. Ekkor létezik pontosan egy olyan

y

szám, melyre

xy = 1,

nevezetesen

 1 + (xR − x)y L 1 + (xL − x)y R y = 0, , xR xL

 1 + (xL − x)y L 1 + (xR − x)y R . , xL xR

Ezt a tételt nem bizonyítjuk; a bizonyítás megtalálható [1]-ben. A formula m¶ködését azonban meg kell magyaráznunk, hiszen ilyet még nem láttunk. Az képlet egyrészt rekurzív reciprokait. Másrészt

y

x

szerint, mert feltételezzük, hogy ismerjük

0-ból

ezért

y = 0, 21 (1 − y R ) 21 (1 − y L ) . 

ebb®l képzett bal oldali összetev®

1 (1 2

− 14 ) =

összetev®inek

indítva a rekurziót.

Hogy ezt illusztráljuk, legyen például

2,

adott

összetev®iben is rekurzív: új összetev®ket már megadottak fel-

használásával gyárthatunk, a

a

x

y -ra

1 (1 2

x = {0, 2|} = 3.

Egyetlen pozitív összetev®je

Az els® jobb oldali összetev®

− 12 ) =

1 (1 2

− 0) =

1 , az 2

1 , majd egy újabb elem a jobb oldalon 4

3 1 . Ezt iterálva az -nak a Bevezetés ben már látott alakját kapjuk meg. 8 3

27

Irodalomjegyzék

[1] J. H. Conway: On Numbers and Games. A K Peters Ltd., 2000

[2] H.-D. Ebbinghaus és tsai., J. H. Ewing (szerk.): Numbers. Springer, Readings in Mathematics, Vol. 123, 1991.

[3] D. E. Knuth: Számok valóson innen és túl. Gondolat, 1987.

[4] Hajnal A., Hamburger P.: Halmazelmélet. Nemzeti Tankönyvkiadó, 3. kiadás, 1994.

28