Vés al contingut

Aritmètica ordinal

De la Viquipèdia, l'enciclopèdia lliure

En el camp matemàtic de la teoria de conjunts, l'aritmètica ordinal descriu les tres operacions habituals sobre nombres ordinals: addició, multiplicació i exponenciació. Cadascuna d'aquestes operacions es pot definir, bàsicament, de dues maneres: sigui construint un conjunt ben ordenat que representi l'operació, sigui per inducció transfinita. La forma normal de Cantor proporciona una manera estàndard d'escriure ordinals. Les així anomenades operacions aritmètiques "naturals" preserven la commutativitat a expenses de la continuïtat.

Addició

[modifica]

La unió de dos conjunts disjunts ben ordenats S i T pot ser ben ordenada. El tipus d'ordre de la unió és l'ordinal que resulta de sumar els tipus d'ordre d'S i de T. Si dos conjunts ben ordenats no són disjunts, llavors es poden substituir per conjunts disjunts isomorfs respecte de l'ordre, per exemple substituint S per {0} × S i T per {1} × T. Així, el conjunt ben ordenat S es pot escriure "a l'esquerra" del conjunt ben ordenat T, la qual cosa vol dir que es pot definir un ordre en en el qual tot element d'S sigui més petit que qualsevol element de T. Els conjunts S i T conserven l'ordenació que tenen. L'addició dels tipus d'ordre és associativa i generalitza l'addició dels nombres naturals.

El primer ordinal transfinit és ω, el conjunt de tots els nombres naturals. Per exemple, l'ordinal ω + ω s'obté per dues còpies dels nombres naturals ordenats de la manera habitual, i on la segona còpia s'escriu completament a la dreta de la primera. Per exemple, si escrivim 0' < 1' < 2' < ... per a la segona còpia, ω + ω té la forma

0 < 1 < 2 < 3 < ... < 0' < 1' < 2' < ...

Això és diferent de ω perquè, a ω, l'únic element que no té un predecessor directe és 0, mentre que a ω + ω tant 0 com 0' no tenen predecessors directes. Un altre exemple: escrivim 3 + ω i ω + 3:

0 < 1 < 2 < 0' < 1' < 2' < ...
0 < 1 < 2 < ... < 0' < 1' < 2'

Després d'un canvi de notació, el primer conjunt té la mateixa forma que ω, és a dir, 3 + ω = ω, mentre que el segon conjunt és diferent: ω + 3 no és igual a ω perquè ω + 3 té un element màxim (en aquest cas, 2') mentre que ω no en té, de màxim. Per tant, aquesta addició no és commutativa. De fet, en general α+β és diferent de β+α: només són iguals si i només si α=γm, β=γn per a algun ordinal γ i per a alguns nombres naturals m i n. Addicionalment, la relació α+β = β+α és una relació d'equivalència sobre el conjunt d'ordinals no-nuls, i totes les seves classes d'equivalència són infinites numerables.

Tot i això, l'addició així definida és associativa; per exemple, hom pot veure que (ω + 4) + ω = ω + (4 + ω) = ω + ω.

Hom pot definir l'addició de forma inductiva (la següent definició utilitza inducció sobre β):

  • α + 0 = α,
  • α + (β + 1) = (α + β) + 1 (aquí, "+ 1" denota el successor d'un ordinal),
  • i si β és un ordinal límit llavors α + β és el límit de α + δ per a tot δ < β.

Amb aquesta definició, es pot interpretar ω + 3 com un ordinal successor (és el successor de ω + 2), mentre que 3 + ω és un ordinal límit, concretament el límit de 3 + 0 = 3, 3 + 1 = 4, 3 + 2 = 5, etc., que és simplement ω.

Propietats

El zero és una identitat additiva: α + 0 = 0 + α = α.

L'addició és associativa: (α + β) + γ = α + (β + γ).

L'addició és estrictament creixent i contínua en l'argument de la dreta:

però el mateix no és vàlid per a l'argument de l'esquerra; només es pot afirmar que

L'addició ordinal és cancel·lativa per l'esquerra: si α + β = α + γ, llavors β = γ. Addicionalment, hom pot definir una subtracció per l'esquerra per a ordinals βα: existeix un únic γ tal que α = β + γ. Per altra banda, la cancel·lació per la dreta no funciona:

però

La substracció per la dreta tampoc no funciona, encara que βα: per exemple, no hi ha cap γ tal que γ + 42 = ω.

Si els ordinals més petits que α formen un conjunt tancat per addició i conté el 0, llavors hom diu que α és un γ-nombre. Aquests són exactament els ordinals de la forma ωβ.

Multiplicació

[modifica]

El producte cartesià S×T de dos conjunts ben ordenats S i T pot definir-se com ben ordenat mitjançant una variant de l'ordre lexicogràfic que col·loqui en primer lloc la posició menys significativa. A la pràctica, cada element de T es pot substituir per una còpia disjunta de S. El tipus d'ordre del producte cartesià és l'ordinal que resulta de multiplicar els tipus d'ordre d'S i de T. De nou, aquesta operació és associativa i generalitza la multiplicació dels nombres naturals.

Aquest és ω·2:

00 < 10 < 20 < 30 < ... < 01 < 11 < 21 < 31 < ...

que té el mateix tipus d'ordre que ω + ω. En canvi, 2·ω s'escriu com:

00 < 10 < 01 < 11 < 0₂ < 1₂ < 0₃ < 1₃ < ...

que, després de reanomenar, és equivalent a ω. Per tant, ω·2 = ω+ωω = 2·ω, la qual cosa il·lustra que la multiplicació d'ordinals no és commutativa. En general, un nombre natural més gran que 1 mai no commuta amb cap ordinal infinit, i dos ordinals infinits α, β commuten si i només si αm = βn per a alguns nombres naturals positius m i n. La relació "α commuta amb β" és una relació d'equivalència sobre els ordinals més grans que 1, i totes les classes d'equivalència són infinites numerables.

En aritmètica ordinal es compleix una distributivitat parcial: R(S+T) = RS+RT. En canvi, no es compleix, en general, l'altra llei distributiva (T+U)R = TR+UR: (1+1)·ω = 2·ω = ω mentre que 1·ω+1·ω = ω+ω, que és diferent. Per tant, els nombres ordinals formen un quasisemianell per l'esquerra, però no formen un anell.

Hom pot donar també la definició de la multiplicació de forma inductiva (la següent inducció és sobre β):

  • α·0 = 0,
  • α·(β+1) = (α·β)+α,
  • i si β és un ordinal límit, llavors α·β és el límit de α·δ per δ < β.

Les propietats principals del producte són:

  • α·0 = 0·α = 0.
  • L'u (1) és una identitat multiplicativa: α·1 = 1·α = α.
  • La multiplicació és associativa: (α·βγ = α·(β·γ).
  • La multiplicació és estrictament creixent i contínua en el segon argument: (α < β i γ > 0) γ·α < γ·β
  • La multiplicació no és estrictament creixent en l'argument de l'esquerra; per exemple, 1 < 2 però 1·ω = 2·ω = ω. Tot i això, és creixent (de forma no estricta), és a dir, αβ α·γβ·γ.
  • Existeix una llei de cancel·lació per l'esquerra: si α > 0 i α·β = α·γ, llavors β = γ.
  • La cancel·lació per la dreta no funciona, és a dir, 1·ω = 2·ω = ω, però 1 i 2 són diferents.
  • α·β = 0 α = 0 o β = 0.
  • Llei distributiva per l'esquerra: α·(β+γ) = α·β+α·γ
  • No es compleix la llei distributiva per la dreta, per exemple, (ω+1)·2 = ω+1+ω+1 = ω+ω+1 = ω·2+1 la qual cosa és diferent de ω·2+2.
  • Divisió per l'esquerra amb residu: per a qualssevol α i β, si β > 0, llavors existeixen γ i δ únics tals que α = β·γ+δ i δ < β. (Això no significa que els ordinals siguin un domini euclidià, ja que ni tan sols formen un anell, i la "norma" euclidiana està avaluada sobre els ordinals.)
  • La divisió per la dreta no funciona: no existeix cap α tal que α·ωωω ≤ (α+1)·ω.

Un δ-nombre és un ordinal més gran que 1 tal que αδ=δ sempre que 0<α<δ. Aquests són exactament els ordinals de la forma ωωβ.

Exponenciació

[modifica]
Representació visual de ω², «omega còpies d'omega». Cada línia vertical és un ordinal de la forma ω·m + n, és a dir, l'element n-sim de la «còpia» m-sima de ω.

La definició d'exponenciació ordinal per a exponents finits és bastant senzilla. Si l'exponent és un nombre finit, la potència és el resultat d'una multiplicació iterada. Per exemple, ω² = ω·ω usant l'operació de multiplicació ordinal. Notem que es pot definir ω·ω mitjançant el conjunt de funcions de 2 = {0,1} en ω = {0,1,2,...}, en ordre lexicogràfic, col·locant en primer lloc la posició menys significativa:

(0,0) < (1,0) < (2,0) < (3,0) < ... < (0,1) < (1,1) < (2,1) < (3,1) < ... < (0,2) < (1,2) < (2,2) < ...

Per brevetat, s'ha substituït la funció {(0,k), (1,m)} pel parell ordenat (k, m).

Anàlogament, per a qualsevol exponent finit n, hom pot definir emprant el conjunt de funcions d'n (el domini) en els nombres naturals (el codomini). Aquestes funcions es poden abreujar com n-ples de nombres naturals.

Però per a exponents infinits, la definició no és tan òbvia. Un ordinal límit, com ara ωω, és el suprem de tots els ordinals menors. Pot semblar natural definir ωω emprant el conjunt de totes les successions infinites de nombres enters. Però resulta que qualsevol ordre definit absolutament sobre aquest conjunt resulta no ser un bon ordre. Per tal de resoldre aquest problema, es pot utilitzar la variant de l'ordre lexicogràfic que hem vist abans. Restringim ara el conjunt a les successions que són no-nul·les per a un nombre finit d'elements. Això té una relació natural amb el límit de les potències finites de la base (semblant al concepte algebraic de coproducte). També podem pensar que és la unió infinita .

Cadascuna d'aquestes successions correspon a un ordinal menor que com ara , i és el suprem d'aquests ordinals menors.

L'ordre lexicogràfic definit sobre aquest conjunt és un bon ordre, que recorda l'ordre habitual dels nombres naturals escrits en notació decimal, en ordre invers, i amb nombres naturals arbitraris en comptes de només els dígits 0–9:

(0,0,0…) < (1,0,0,0…) < (2,0,0,0…) < ... <
(0,1,0,0,0…) < (1,1,0,0,0…) < (2,1,0,0,0…) < ... <
(0,2,0,0,0…) < (1,2,0,0,0…) < (2,2,0,0,0…)
< ... <
(0,0,1,0,0,0…) < (1,0,1,0,0,0…) < (2,0,1,0,0,0…)
< ...

En general, qualsevol ordinal α es pot elevar a la potència d'un altre ordinal β de la mateixa manera, per tal d'obtenir αβ. Per explicar això, emprarem la definició de Von Neumann de nombre ordinal com el conjunt de tots els ordinals menors que ell. Per tal de construir un conjunt de tipus d'ordre αβ, considerem totes les funcions de β en α tals que només un nombre finit d'elements del domini β s'apliquin sobre un element no-nul d'α (essencialment, estem considerant les funcions amb suport finit). L'ordre és lexicogràfic amb la posició menys significativa primer. Trobem que

  • 1ω = 1,
  • 2ω = ω,
  • 2ω+1 = ω·2 = ω+ω.

També es pot donar una definició inductiva per a l'exponenciació (la següent inducció és sobre β, l'exponent):

  • α0 = 1,
  • αβ+1 = (αβα, i
  • si δ és límit, llavors αδ és el límit de αβ per a tot β < δ.
Propietats
  • α0 = 1.
  • Si 0 < α, llavors 0α = 0.
  • 1α = 1.
  • α¹ = α.
  • αβ·αγ = αβ + γ.
  • (αβ)γ = αβ·γ.
  • Existeixen α, β, i γ per als quals (α·β)γαγ·βγ. Per exemple, (ω·2)² = ω·2·ω·2 = ω²·2 ≠ ω²·4.
  • L'exponenciació d'ordinals és estrictament creixent i contínua en el segon argument: si γ > 1 i α < β, llavors γα < γβ.
  • Si α < β, llavors αγβγ. Notem, per exemple, que 2 < 3 però 2ω = 3ω = ω.
  • Si α > 1 i αβ = αγ, llavors β = γ. Si α = 1 o α = 0 això no és cert.
  • Per a qualssevol α i β, si β > 1 i α > 0 llavors existeixen γ, δ, i ρ únics tals que α = βγ·δ + ρ amb les propietats que 0 < δ < β i ρ < βγ.

Cal ressaltar que l'exponenciació d'ordinals és ben diferent de l'exponenciació de cardinals. Per exemple, en l'exponenciació d'ordinals 2ω = ω, però en l'exponenciació de cardinals, és la cardinalitat del continu, que és més gran que . Per tal d'evitar confondre l'exponenciació d'ordinals amb l'exponenciació de cardinals, hom pot emprar uns símbols en el cas d'ordinals (per exemple, ω) i uns altres símbols en el cas de cardinals (per exemple, ).

Ernst Jacobsthal va demostrar que les úniques solucions de αβ = βα amb αβ són α=β, o bé α=2 i β=4, o bé α qualsevol ordinal límit i β=εα, on ε és un ε-nombre més gran que α.

Forma normal de Cantor

[modifica]

Tot nombre ordinal α es pot escriure de forma única com , on k és un nombre natural, són enters positius, i són nombres ordinals. Aquesta descomposició d'α s'anomena forma normal de Cantor d'α, i es pot considerar com un sistema de notació posicional en base ω. L'exponent major, , s'anomena grau d', i satisfà . La igualtat es dona si i només si . En aquest cas, la forma normal de Cantor no expressa l'ordinal en termes d'ordinals menors; això pot passar com s'explica més endavant.

Una variació menor de la forma normal de Cantor, que és una mica més senzilla de treballar, és forçar que tots els nombres ci siguin iguals a 1, i permetre que els exponents siguin iguals. En altres paraules, tot nombre ordinal α es pot expressar unívocament com , on k és un nombre natural, i són nombres ordinals.

Una altra variació de la forma normal de Cantor és l'"expansió en base δ", on se substitueix ω per qualsevol altre ordinal δ>1, i els nombres ci són ordinals positius menors que δ.

La forma normal de Cantor ens permet expressar, de forma unívoca (i també ens permet ordenar), els ordinals α construïts a partir de nombres naturals mitjançant un nombre finit d'addicions, multiplicacions i exponenciacions en base : en altres paraules, si suposem que en la forma normal de Cantor, també podem expressar els exponents en forma normal de Cantor, i fent la mateixa suposició pels com hem fet per α, i així successivament de forma recursiva, obtenim un sistema de notació per a aquests cardinals. Per exemple,

denota un ordinal.

L'ordinal ε0 (èpsilon zero) és el conjunt de valors ordinals α de les expressions aritmètiques de longitud finita de la forma normal de Cantor que són no-trivials de forma hereditària; aquí, no-trivial significa que β1<α quan 0<α. És l'ordinal més petit que no té una expressió aritmètica finita en termes de ω, i l'ordinal més petit tal que , és a dir, tal que, en forma normal de Cantor, l'exponent no és més petit que el propi ordinal. És el límit de la successió

La forma normal de Cantor ens permet també calcular sumes i productes d'ordinals: per calcular la suma, per exemple, només cal saber que

si (si es pot escriure de forma trivial com , i si l'expressió ja està en forma normal de Cantor); i per calcular productes, només cal tenir en compte que, quan està en forma normal de Cantor, i , llavors

i

si n és un nombre natural no-nul.

Per comparar dos ordinals escrits en forma normal de Cantor, primer comparem , després , després , després , etc. A la primera diferència, l'ordinal que tingui el component més gran és l'ordinal més gran. Si tots són iguals fins que un acaba abans que l'altre, l'ordinal que s'acaba abans és el més petit.

Factorització en primers

[modifica]

Ernst Jacobsthal demostrà que els ordinals satisfan una variant del teorema de factorització única: tot ordinal no-nul es pot escriure com a producte d'un nombre finit d'ordinals primers. Aquesta factorització en ordinals primers no és única, en general, però existeix una factorització "mínima" en primers que és única llevat de canvis d'ordre dels factors primers finits (vegeu Sierpiński 1958).

Un ordinal primer és un ordinal més gran que 1 que no es pot escriure com a producte de dos ordinals més petits. Alguns dels primers ordinals primers són 2, 3, 5, ..., ω, ω+1, ω²+1, ω3+1, ..., ωω, ωω+1, ωω+1+1, ... Hi ha tres tipus d'ordinals primers:

  1. Els nombres primers finits 2, 3, 5, ...
  2. Els ordinals de la forma ωωα per a qualsevol ordinal α. Aquests són els ordinals primers que són límits, i són els nombres delta.
  3. Els ordinals de la forma ωα+1 per a qualsevol ordinal α>0. Aquests són primers successors infinits, i són els successors dels nombres gamma, els ordinals no descomponibles de forma additiva.

La factorització en primers no és única: per exemple, 2×3=3×2, 2×ω=ω, (ω+1)×ω=ω×ω i ω×ωω = ωω. Tot i això, existeix una factorització única en factors primers que satisfà les següents condicions addicionals:

  • Tot primer límit apareix abans de qualsevol primer successor
  • Si dos primers consecutius de la factorització són ambdós límits o ambdós finits, llavors el segon és almenys el primer.

Aquesta factorització en primers es pot interpretar de forma senzilla emprant la forma normal de Cantor:

  • Primer, hom escriu l'ordinal com un producte αβ, on α és la menor potència de ω en la forma normal de Cantor, i β és un successor.
  • Si α=ωγ, llavors la forma normal de Cantor de γ proporciona una expansió de α en producte de primers límit.
  • Hom examina ara la forma normal de Cantor de β. Si β = ωλm + ωμn+ termes menors, llavors β = (ωμn+ termes menors)·(ωλμ + 1)m és un producte d'un ordinal menor i un enter primer m. Si repetim aquest procediment i factoritzem els enters en nombres primers, obtenim la factorització en primers de β.

Així, la factorització de l'ordinal en forma normal de Cantor

(amb )

en un producte mínim de primers infinits i enters és

on cada ni s'hauria de substituir per la seva factorització en una successió no-creixent de primers finits, i

amb .

Ordinals comptables grans

[modifica]

Com hem vist abans, la forma normal de Cantor dels ordinals menors que es poden expressar en un alfabet que contingui només els símbols per a les funcions d'addició, multiplicació i exponenciació, així com símbols constants per a cada nombre natural i per a . Podem obviar els símbols pels nombres naturals (dels quals n'hi ha un nombre infinit), i escriure'ls mitjançant el símbol constant 0 i l'operador successor, (per exemple, l'enter 4 es pot expressar com ). Això descriu una notació ordinal: un sistema d'expressar els ordinals sobre un alfabet finit. En particular, aquest sistema de notació ordinal rep el nom de col·lecció d'expressions ordinals aritmètiques, i és capaç d'expressar qualsevol ordinal menor que , però no pot expressar . Existeixen altres notacions ordinals que poden descriure ordinals majors que , però com que només hi ha una quantitat numerable de cadenes sobre qualsevol alfabet finit, sempre hi haurà ordinals menors que que no es puguin expressar mitjançant cap notació ordinal. Aquests ordinals reben el nom d'ordinals comptables grans.

Les operacions d'addició, multiplicació i exponenciació són exemples de funcions ordinals recursives primitives, i hom pot emprar funcions ordinals recursives primitives més generals per tal d'expressar els ordinals més grans.

Operacions naturals

[modifica]

Gerhard Hessenberg definí, l'any 1906, les operacions sobre ordinals anomenades suma natural i producte natural, de vegades conegudes com a suma (o producte) de Hessenberg (Sierpiński 1958). Aquestes són les mateixes operacions que l'addició i multiplicació (restringida a ordinals) del cos dels nombres surreals de John Conway. Les operacions així definides tenen l'avantatge que són associatives i commutatives, i el producte natural és distributiu sobre la suma natural. Com a contrapartida per ser commutatives, no són contínues en l'argument de l'esquerra, com succeïa en la suma i producte ordinaris. La suma natural d'α i β es denota per , i el producte natural per una espècie de signe × doble: . (Una altra notació habitual és αβ i αβ).

Per definir la suma natural de dos ordinals, considerem de nou la unió disjunta de dos conjunts ben ordenats, amb aquest tipus d'ordre. Comencem per establir un ordre parcial en aquesta unió disjunta, prenent els ordres sobre S i T de manera separada, però no imposant cap relació entre S i T. Considerem ara els tipus d'ordre de tots els bons ordres sobre que estengui aquest ordre parcial: el suprem de tots aquests ordinals (que, de fet, no és només un suprem, sinó un màxim) és la suma natural.[1] Alternativament, podem definir la suma natural d'α i β de forma inductiva (per inducció simultània sobre α i β) com el menor ordinal més gran que la suma natural d'α i γ per a tot γ < β i de γ i β per a tot γ < α.

La suma natural és associativa i commutativa. Sempre és més gran o igual a la suma ordinària, però pot ser més gran. Per exemple, la suma natural de ω i 1 és ω+1 (la suma ordinària), però aquesta és també la suma natural d'1 i ω.

Per definir el producte natural de dos ordinals, considerem de nou el producte cartesià S × T de dos conjunts ben ordenats amb aquests tipus d'ordre. Comencem establint un ordre parcial en aquest producte cartesià, emprant l'ordre producte (comparem dos parells si i només si cadascuna de les dues coordenades és comparable). Considerem ara els tipus d'ordre de tots els bons ordres sobre S × T que estén aquest ordre parcial: el suprem d'aquests ordinals (que, de fet, no és només un suprem, sinó un màxim), és el producte natural. Existeix també una definició inductiva del producte natural (per inducció mútua), però és un procediment feixuc de descriure.

El producte natural és associatiu i commutatiu, i és distributiu sobre la suma natural. Sempre és més gran o igual al producte ordinari, però pot ser més gran. Per exemple, el producte natural de ω i 2 és ω·2 (el producte ordinari), però aquest és també el producte natural de 2 i ω.

Una altra forma de definir la suma natural i el producte natural de dos ordinals α i β és fer servei de la forma normal de Cantor: podem trobar una successió d'ordinals γ1 > … > γn i dues successions (k1, …, kn) i (j1, …, jn) de nombres naturals (incloent-hi el zero, però satisfent ki + ji > 0 per a tot i) tals que

i es defineix

Amb l'addició natural, hom pot identificar els ordinals amb els elements del grup abelià lliure amb base als nombres gamma ωα que tenen coeficients enters no-negatius. Amb la suma natural i el producte natural, hom pot identificar els ordinals amb els elements de l'anell (commutatiu) de polinomis generat pels nombres delta ωωα que tenen coeficients enters no-negatius.

Els ordinals no tenen una factorització única en primers amb el producte natural. Mentre que la totalitat de l'anell de polinomis sí que té una factorització única, el subconjunt de polinomis amb coeficients no-negatius no la té: per exemple, si x és qualsevol nombre delta, llavors

té dues expressions incompatibles com a producte natural de polinomis a coeficients no-negatius que no es pot tornar a descompondre.

Referències

[modifica]
  1. Carruth, Philip W. «Arithmetic of ordinals with applications to the theory of ordered Abelian groups» (pdf). Bulletin of the American Mathematical Society, 48, 4, 1942, pàg. 262-271 [Consulta: 31 octubre 2015]., vegeu Teorema 1

Bibliografia

[modifica]
  • Jech, Thomas. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer, 2003. ISBN 3-540-44085-2. 
  • Kunen, Kenneth. Set Theory: An Introduction to Independence Proofs, 1980, p. Elsevier. ISBN 0-444-86839-9. 
  • Sierpiński, Wacław «Cardinal and ordinal numbers». Polska Akademia Nauk Monografie Matematyczne. Państwowe Wydawnictwo Naukowe [Varsòvia], 34, 1958.

Enllaços externs

[modifica]