 
\magnification\magstephalf
\centerline{Megold\'asok a Bolyai Koll\'egium szemin\'arium\'an}
\centerline{1999 m\'arcius 4-\'en r\'eszben megbesz\'elt feladatokhoz}
\bigskip
A John H. Conway ``On numbers and games '' c\'\i m\H u k\"onyve 6.
fejezete alapj\'an.
\bigskip
 
Definici\'o:
 
Legyen $L(H)$ a $H$ halmazban nem szerepl\H o legkisebb rendsz\'am
(legkisebb kiz\'art).
 
Defini\'aljuk rekurzi\'oval a rendsz\'amokon a
k\"ovetkez\H o \"osszead\'ast \'es szorz\'ast:
$$a+b=L(\{a'+b|a'<a\}\cup\{a+b'|b'<b\})$$
$$ab=L(\{(a'b+ab')+a'b'|a'<a,b'<b\}).$$
 
Jel\"ol\'es: Egyszer\H us\'\i tj\"uk a jel\"ol\'est, $a'$ mindig
az $a$-n\'al kisebb rendsz\'amokon fut v\'egig, $b'$ a $b$-n\'el
kisebbeken, stb., \'\i gy a fenti definici\'o egyszer\"ubben:
$$a+b=L(a'+b,a+b')$$
$$ab=L(a'b+ab'-a'b').$$
Itt a $-$ m\'asik jel a $+$-ra, a z\'ar\'ojelez\'est az
asszociativit\'as miatt hagyhattuk el, amit majd igazolunk.
 
A feladatok arra vonatkoztak, hogy l\'assuk be, a rendsz\'amok \'\i gy
testet alkotnak, \'es tudjunk meg min\'al t\"obbet err\H ol a testr\H ol.
\bigskip
 
Egy soros bizony\'\i t\'as egy \'all\'\i t\'asra olyan indukt\'\i v
bizony\'\i t\'as, ahol form\'alis \'atalak\'\i t\'asok sor\'an
kor\'abban bizony\'\i tottakat haszn\'alunk, \'es a bizony\'\i tand\'ot
egyszer\H ubb esetben. Ilyen majdnem minden al\'abbi bizony\'\i t\'as.
Itt egyszer\H ubbnek akkor tekint\"unk egy rendsz\'am $k$-ast,
egy m\'asikn\'al, ha minden eleme kisebb vagy egyenl\H o, \'es
az egyik kisebb. Ez a r\'eszben rendez\'es van a rekurz\'\i v
definici\'o m\"og\"ott, \'es a 13--14 egyszer\H u kiterjeszt\'esek is
erre hivatkoznak. \bigskip
 
I. \"Osszead\'as
 
1. Nullelem: $a+0=a$
 
Biz: $a+0=L(a'+0)=L(a')=a$.
 
2. Kommutativit\'as: $a+b=b+a$
 
Biz: $a+b=L(a'+b,a+b')=L(b+a',b'+a)=b+a$.
 
3. Technikai: Ha $a=L(H_a)$ \'es $b=L(H_b)$, akkor
$a+b=L(a''+b,a+b'')$ ahol $a''$ $H_a$ elemein fut v\'egig, $b''$
pedig $H_b$ elemein.
 
Biz: $H_a$-ban szerepel minden $a$-n\'al kisebb rendsz\'am \'es esetleg
n\'eh\'any $a$-n\'al nagyobb, \'es hasonl\'o $H_b$ \'es $b$ viszonya.
Teh\'at el\'eg bel\'atni, hogy $a''>a$, illetve $b''>b$ eset\'en
$a''+b\ne a+b$ illetve $b''+b\ne a+b$. De $a''+b$ definici\'oja
szerint a legkisebb kiz\'art egy olyan halmazban, ami tartalmazza
$a+b$-t, \'\i gy az els\H o \'all\'\i t\'as igaz. A m\'asodik
hasonl\'oan bel\'athat\'o, vagy k\"ovetkezik a kommutativit\'asb\'ol.
 
4. Asszociativit\'as: $a+(b+c)=(a+b)+c$.
 
Biz: $a+(b+c)=L(a'+(b+c),a+(b'+c),a+(b+c'))=L((a'+b)+c,(a+b')+c,
(a+b)+c')=(a+b)+c$. Itt az $a+(b+c)$ \'es $(a+b)+c$ fel\'\i
r\'as\'ahoz nem a definici\'ot haszn\'altuk, hanem 3-at a
$b+c=L(b'+c,b+c')$ \'es az $a+b=L(a'+b,a+b')$ halmazokkal.
 
5. Az exponens $2$: $a+a=0$
 
Biz: $a+a=L(a'+a,a+a')$, \'\i gy az kell, hogy
$a'+a\ne 0\ne a+a'$, ami igaz, hisz mind a kett\H o legkisebb kiz\'art
egy halmazban, amiben szerepel $a'+a'=0$.
 
1--5: A rendsz\'amok a $+$-ra kett\H o exponens\H u Abel-csoportot
adnak, melynek $0$ a null\-e\-le\-me.
\bigskip
 
II. Szorz\'as
 
6. Nullelem: $a\cdot0=0$
 
Biz: $a\cdot0=L(\emptyset)=0$. Nem is k\'ene bizony\'\i tani, mert
k\"ovetkezik 10-b\H ol.
 
7. Egys\'egelem: $1\cdot a=a$
 
Biz: $1\cdot a=L(0\cdot a+1\cdot a'-0\cdot a')=L(1\cdot a')=L(a')=a$.
 
8. Kommutativit\'as: $ab=ba$.
 
Biz: $ab=L(a'b+ab'-a'b')=L(ba'+b'a-b'a')=L(b'a+ba'-b'a')=ba$.
 
9. Technikai, mint 3: Ha $a=L(H_a)$ \'es $b=L(H_b)$, akkor
$ab=L(a''b+ab''-a''b'')$ ahol $a''$ $H_a$ elemein fut v\'egig, $b''$
pedig $H_b$ elemein.
 
Biz: Mint 3-n\'al, itt is el\'eg bel\'atni, hogy $a''\ne a$, $b''\ne b$
eset\'en $a''b+ab''-a''b''\ne ab$. Legyen $a_0$ a kisebb, $a_1$ a
nagyobb $a$ \'es $a''$ k\"oz\"ul, hasonl\'oan legyen $b_0$ a kisebb,
$b_1$ a nagyobb $b$ \'es $b''$ k\"oz\"ul. Az $a_1b_1$ szorzat
definici\'oja szerint a legkisebb kiz\'art egy halmazban, melyben
szerepel $a_0b_1+a_1b_0-a_0b_0$, \'\i gy $a_1b_1\ne
a_0b_1+a_1b_0-a_0b_0$, amib\H ol \'atrendez\'essel ad\'odik
$a''b+ab''-a''b''\ne ab$.
 
10. Disztributivit\'as: $a(b+c)=ab+ac$
 
Biz: $a(b+c)=L(a'(b+c)+a(b'+c)-a'(b'+c),a'(b+c)+a(b+c')-a'(b+c'))=
L((a'b+a'c)+(ab'+ac)-(a'b'+a'c),(a'b+a'c)+(ab+ac')-(a'b+a'c'))=
L((a'b+ab'-a'b')+ac,ab+(a'c+ac'-a'c'))=L(ab+ac)$. Itt az $a(b+c)$
fel\'\i r\'as\'ahoz nem a definici\'ot haszn\'altuk, hanem 9-et,
$ab+ac$-hez 3-at.
 
11. Asszociativit\'as: $a(bc)=(ab)c$.
 
Biz: $a(bc)=L(a'(bc)+a(b'c+bc'-b'c')-a'(b'c+bc'-b'c'))=
L(a'(bc)+a(b'c)+a(bc')-a(b'c')-a'(b'c)-a'(bc')+a'(b'c'))=
L((a'b)c+(ab')c+(ab)c'-(ab')c'-(a'b')c-(a'b)c'+(a'b')c')=
L((a'b+ab'-a'b')c+(ab)c'-(a'b+ab'-a'b')c')=L((ab)c)$. Itt haszn\'aljuk
9-et, 10-et, \'es persze 1--5-\"ot is.
 
12. Nulloszt\'omentess\'eg: Ha $a\ne0\ne b$, akkor $ab\ne0$.
 
Biz: $ab$ a legkisebb kiz\'artja egy halmaznak, melyben szerepel
$0\cdot a+a\cdot0-0\cdot0=0+0-0=0$.
 
1--12. a rendsz\'amok az \'uj m\H uvelettekkel egy kett\H o
karakterisztik\'aj\'u integrit\'asi tartom\'anyt adnak. A nullelem $0$,
az egys\'egelem $1$.
\bigskip
 
III. Egyszer\H u kiterjeszt\'esi szabalyok
 
Jel\"olj\"uk az $x$-n\'el kisebb rendsz\'amok halmaz\'at (mint
halmazelm\'eletben szok\'as) $x$-szel (\'es rem\'enykedj\"unk, hogy ez
nem okoz f\'elr\'ert\'est).
 
13. Ha $x$ nem z\'art az \"osszead\'asra, akkor $x=a+b$
minden minim\'alis $(a,b)$ p\'arra, melynek nincs \"osszege $x$-ben.
 
Biz: Feltett\"uk, hogy $a+b\ge x$, \'\i gy $a+b=L(a'+b,a+b')$ miatt
el\'eg bel\'atni, hogy $a'+b\ne x$ \'es $a+b'\ne x$, de mindk\'et
bal oldal a minimalit\'as miatt $x$-n\'el kisebb.
 
14. Ha $x$ z\'art az \"osszead\'asra, de nem a szorz\'asra,
akkor $x=ab$ minden minimalis $(a,b)$ p\'arra, amelynek nincs szorzata
$x$-ben.
 
Biz: Mint az el\H obb, itt is el\'eg bel\'atni, hogy $a'b+ab'-a'b'\ne
x$. A baloldal itt a minimalit\'as \'es az \"osszeg-z\'arts\'ag miatt
$x$-beli.
 
15. Ha $x>1$ gy\H ur\H u, de nem test, akkor $x=1/a$
a minim\'alis $a>0$-ra, melynek nincs reciproka $x$-ben.
 
Biz: Kell, hogy $ax=L(a'x+ax'-a'x')=1$.
Nyilvan $a'=x'=0$ v\'alaszt\'as $0$-t ad, \'\i gy csak az kell, hogy
$a'x+ax'-a'x'=1$ nem lehet. Ha $a'=0$, akkor ez $ax'=1$ lenne, ami nem
lehet, mert $a$-nak nincs reciproka $x$-ben. Ha $a'\ne0$, akkor
a minimalit\'as miatt van $b<x$, hogy $a'b=1$, \'es ezzel szorozva
$a'x+ax'-a'x'=1$-et $x=b+x'-abx'$ ad\'odna, ami nem lehet, mert a jobb
oldal az $x$ gy\H ur\H uben marad.
 
16. A rendsz\'amok testet alkotnak az \'uj m\H uveletekkel.
 
Biz: 1-12 ut\'an csak a reciprok l\'etez\'ese kell.
Ha $x$-nek nem
lenne reciproka, akkor 13--15 szerint minden rendsz\'am az $x$-n\'el
kisebbek \'es azok reciprokai \'altal gener\'alt gy\H ur\H uben lenne,
ami sz\'amoss\'agi okokb\'ol nem megy (``t\"obb rendsz\'am van'').
 
17. Technikai: Ha $x$ test, akkor $x$ polinomjai $x$-beli
egy\"utthat\'okkal lesznek az els\H o rendsz\'amok, m\'eghozz\'a
lexikografikus sorrendben, eg\'eszen addig, am\'\i g a polinomok
\'ert\'eke p\'aronk\'ent k\"ul\"onb\"oz\H o. (A lexikografikus
sorrendben k\'et polinom k\"oz\"ul az a kisebb, aminek a legnagyobb
fok\'u elt\'er\H o egy\"utthat\'oja kisebb, \'\i gy p\'eld\'aul kisebb
fok\'u polinom kisebb. Vegy\"uk \'eszre, hogy ez j\'olrendez\'es.)
 
Biz: Term\'eszetesen indukci\'oval:
 
Konstansokra, \'es $x$-re trivi\'alis. Legyen most $y>x$, \'es
tegy\"uk fel, hogy $y=\{p(x)|p<r\}$, ahol $p$ az $x$-beli
egy\"utthat\'os $r$-n\'el (lexikografikusan) kisebb polinomokon fut
v\'egig. Feltessz\"uk, hogy $r(x)$ nem szerepel $y$-ban, \'es
bizony\'\i tani kell, hogy $y=r(x)$.
 
Ha $r$ nem monom, akkor $r(t)=at^l+s(t)$ alak\'u, ahol $l\ge1$,
$s\ne0$, \'es $s$ foka $l$-n\'el kisebb. $y$ nem z\'art
\"osszead\'asra, \'es $(ax^l,s(x))$ 14 szerinti minim\'alis p\'ar
$y$-ban, \'\i gy $y=ax^l+s(x)=r(x)$.
 
Ha $r(t)=ax^t$, ahol $a$ nem z\'art az \"osszead\'asra, akkor
14 szerint $a=b+c$ tetsz\H oleges minim\'alis $a$-ban alatt
\"osszeadhatatlan $(b,c)$ p\'arra. Ekkor $(bx^l,cx^l)$ minimalis
$y$-ban nem \"osszedhat\'o p\'ar, \'\i gy ugyancsak 14 szerint
$y=bx^l+cx^l=ax^l=r(x)$.
 
Ha $r(t)=at^l$, ahol $a>1$ \'es $a$ z\'art az \"osszead\'asra,
akkor $y$ is z\'art az \"osszead\'asra, \'es $(a,x^l)$ minim\'alis
p\'ar, melynek nincs szorzata $y$-ban, \'\i gy 15 szerint
$y=ax^l=r(x)$.
 
Ha $r(t)=t^l$, ahol $1<l$, akkor $y$ z\'art az \"osszead\'asra, \'es
$(x,x^{l-1})$ minim\'alis p\'ar, melyek szorzata nincs $y$-ban,
\'\i gy 15 szerint $y=x\cdot x^{l-1}=r(x)$.
 
18. Ha $x$ test, de nem algebrailag
z\'art, akkor $x$ minim\'alpolinomja $x$ felett lexikografikusan
legkisebb polinom $x$ felett,
aminek nincs gy\"oke $x$-ben.
 
Biz: Legyen $x$ felett a  legkisebb gy\"okmentes polinom $p(t)$. Ennek
f\H oegy\"utthat\'oja nyilv\'an $1$ (egy\'ebk\'ent egy konstanssal
megszorozva kisebb polinom ad\'odna), \'\i gy $p(t)=t^l-q(t)$,
ahol $l\ge 2$ \'es $q$ foka kisebb $l$-n\'el.
 
Nyilv\'an $x$ transzcendens $x$ felett vagy minim\'alpolinomja
legal\'abb $l$-ed fok\'u, \'\i gy az $l$-n\'el kisebb fok\'u $r$
polinomokra $x$ felett $r(x)$ mindig k\"ul\"onb\"oz\H o, \'\i gy 17
szerint ezek $r$ szeinti lexikografikus sorrendben adj\'ak az els\H o
valah\'any rendsz\'amot, mondjul az $y$-n\'al kisebbeket
(nyilv\'an $y$ az $x$ rendsz\'am szok\'asos --- r\'egi --- \'ertelemben
vett $l$-edik hatv\'anya lesz).
 
Legyen $z=x^{l-1}$. Ekkor $x^l=xz=L(x'z+xz'-x'z')$, \'es itt $z'$
az $r(x)$ \'ert\'ekeken fut v\'egig, ahol $r$ $(l-1)$-n\'el kisebb
fok\'u polinom $x$ felett. N\'ezz\"uk meg, hogy fix $x'$ \'es
$l$-n\'el kisebb fok\'u $x$ feletti $s$ polinom eset\'en mikor
oldhat\'o meg $x'z+xz'-x'z'=s(x)$ valamely $z'=r(x)$-szel. Mivel itt
v\'egig az $y[t]$ polinomgy\H ur\H u $l$-n\'el kisebb fok\'u polinomjai
k\"ozt mozgunk, ez\'ert akkor, ha
$x't^{l-1}+tr(t)-x'r(t)=s(t)$ megoldhat\'o, vagyis ha
$x't^{l-1}-s(t)$-t osztja $t-x'$, ami viszont akkor teljes\"ul, ha
$t=x'$ gy\"oke $x't^{l-1}-s(t)$-nek azaz $x'^l=s(x')$, azaz $x'$
gy\"oke a $t^l-s(t)$ polinomnak. A fentiek szerint $x^l$ az els\H o
$s(x)$ \'ert\'ekkel egyezik meg, amit nem kapunk meg \'\i gy, azaz
amelyre $t^l-s(t)$-nek nincs gy\"oke $x$-ben. Ez $q$ definici\'oja
\'es 17 alapj\'an pont $q(x)$, teh\'at $p(x)=x^l-q(x)=0$,
ahogy \'all\'\i tottuk.
 
19. A rendsz\'amok algebrailag z\'art testet alkotnak.
 
Biz: Pont, mint 16-n\'al. Ha ugyanis az $x$ beli $p$ polinomnak nem
lenne gy\"oke, akkor 13--15 \'es 18 alapj\'an az \"osszes rendsz\'am
$x$ algebrai lez\'artj\'aba esne, ami sz\'amoss\'agi okokb\'ol nem megy.
 
20. Ha $x$ algebrailag z\'art testet alkot, akkor
$x$ transzcendens $x$ felett.
 
Biz: Jobb h\'\i j\'an\dots Csak a kereks\'eg kedv\'e\'ert \'\i rtam
ide. \bigskip
 
IV. Term\'eszetes sz\'amok
 
Sz\"ogletes z\'ar\'ojelen bel\"ul a r\'egi
m\H uveletek \'erv\'enyesek.
 
21. \"Osszead\'asra z\'art $n<\omega$ akkor \'es csak akkor, ha
$n=[2^k]$ alak\'u. P\'aronk\'ent k\"ul\"onb\"oz\H o $[2^k]$ alak\'u
sz\'amok \"osszege \'es [\"osszege] egyenl\H o (sok tag\'u \"osszeg is).
De persze $[2^k]+[2^k]=0$.
 
Biz: 13-b\'ol folyik. Az utols\'o \'all\'\i t\'as 5 speci\'alis esete.
Egy\'ebk\'ent rendsz\'amhatv\'anyoz\'as szerinti magasabb
$2$-hatv\'anyokra is igaz.
 
22. $n<\omega$ test akkor \'es csak akkor, ha $n=[2^{2^k}]$ alak\'u.
P\'aronk\'ent k\"ul\"onb\"oz\H o ilyen sz\'amok szorzata \'es [szorzata]
egyenl\H o (sok t\'enyez\H os szorzat is). De $[2^{2^k}][2^{2^k}]=
[(3/2)2^{2^k}]$.
 
Biz: A pr\'\i mtest $2$, tegy\"uk fel indukt\'\i van, hogy $[2^{2^k}]$
test ($k<\omega$). Ez v\'eges test, \'\i gy t\"ok\'eletes, teh\'at a
18 szerinti legkisebb gy\"okmentes polinomja legal\'abbm\'asodfok\'u
\'es nem $t^2-a$ alak\'u $a<[2^{2^k}]$-ra. Teh\'at $[2^{2^k}]$
minim\'alpolinomja $t^2-t-a$ alak\'u a legkisebb $a<[2^{2^k}]$-ra,
amire ez gy\"okmentes ha van ilyen $a$. Kis sz\'amol\'as adja, hogy ez
az $a$ pont $[2^{2^k-1}]$, \'\i gy a gener\'alt testb\H ov\'\i t\'es
n\'egyzetes (a k\"ovetkez\H o test $[2^{2^{k+1}}]$), \'es a szorz\'asi
szab\'alyok is folynak.
 
21--22, (valamint a gy\H ur\H u-tulajdons\'agok) megadj\'ak a m\H
uveleteket $\omega$-n. Pr\'ob\'alj\'atok pl. $4$ hatv\'anyait ennek
alapj\'an v\'egigsz\'amolni. \bigskip
 
V. $\omega$
 
23. $\omega$ kvadratikusan z\'art. (Minden m\'asodfok\'u polinomnak
van gy\"oke.)
 
Biz: Legyen $p$ m\'asodfok\'u polinom $\omega$ felett. Ekkor $p$
m\'ar $[2^{2^k}]$ felett is polinom el\'eg nagy $k$-ra, \'\i gy mivel
ez ut\'obbi $GF([2^{2^k}])$ gy\"oke m\'ar $GF([2^{2^{k+1}}])$-ben
megjelenik, ami persze maga $[2^{2^{k+1}}]$.
 
24. $\omega^3=2$
 
Biz: 18 alapj\'an $\omega$ minim\'alpolinomja a legkisebb gy\"okmentes
polinom $\omega$ felett. 23 alapj\'an ez minimum harmadfok\'u, \'es
persze nem $t^3$ vagy $t^3-1$, mert azok gy\"oke $0$, illetve $1$.
El\'eg bel\'atni, hogy $t^3-2$-nek nincs gy\"oke $\omega$-ban. Ha volna
$n<\omega$ gy\"ok, akkor $n$ multiplikat\'\i v rendje $9$ lenne, mert
$n^9=2^3=1$, de $n^3=2\ne1$. De $n$ egy $[2^{2^k}]$ elem\H u test
eleme, \'\i gy rendje osztja, $[2^{2^k}-1]$-et, ami ellentmond\'as.
\bigskip
 
VI. Tov\'abbiak
 
15--18 alapj\'an sok\'aig k\"ovethet\H o a test szerkezete.
Sz\"ogletes z\'ar\'ojelben a szok\'asos rend\-sz\'am\-m\H
u\-ve\-le\-tek \'erv\'enyesek, imm\'ar a rendsz\'amhatv\'anyoz\'ast
is haszn\'aljuk.
 
Els\H o rendsz\'amok, amik testet adnak:
$$2,4,16,\ldots,[2^{2^k}],\ldots$$
$$\omega, [\omega^3],[\omega^9],\ldots,[\omega^{3^k}],\ldots$$
$$[\omega^\omega],[\omega^{\omega\cdot5}],[\omega^{\omega\cdot25}],
\ldots, [\omega^{\omega\cdot5^k}],\ldots$$
$$[\omega^{\omega^2}],[\omega^{\omega^2\cdot7}],
[\omega^{\omega^2\cdot49}], \ldots,[\omega^{\omega^2\cdot7^k}],
\ldots$$
Azaz el\H osz\"or az \"osszes kvadratikus b\H ovit\'es, majd az
\"osszes harmadrend\H u, stb. V\'eg\"ul $[\omega^{\omega^\omega}]$ a
pr\'\i mtest algebrai lez\'artja.
 
Ezut\'an 17 \'es 20 alapj\'an
$\left[\left(\omega^{\omega^\omega}\right)^\omega
\right]=\left[\omega^{\omega^{\omega+1}}\right]$ a k\"ovetkez\H o
gy\H ur\H u, de ez m\'eg nem test. Ez az els\H o eset, hogy 15
``alkalmaz\'odik'', azaz
$$\left[\omega^{\omega^{\omega+1}}\right]={1\over
\left[\omega^{\omega^\omega} \right]}.$$
 
A k\"ovetkez\H o test hirtelen nagy ugr\'assal m\'ar
$\left[\omega^{\omega^{\omega^\omega}}\right]$ (sz\'amolj ut\'ana).
Ez nem t\"ok\'eletes test, \'\i gy
$$\left[\omega^{\omega^{\omega^\omega}}\right]^2=
\left[\omega^{\omega^\omega}\right].$$
Stb.
 
\bye
 
