33

9. Axioma dinfinitud

Amb els axiomes que hem introdut fins ara podem mostrar que hi ha

infinits conjunts, pero` no podem mostar que hi ha cap conjunt infinit, en

particular, no podem demostrar lexiste`ncia del conjunt N dels nombres na-turals. Per a aixo` hem dafegir un nom axioma.

Una manera de fer-ho es afirmant explcitament lexiste`ncia dun conjunt,

una funcio i un objecte que compleixi els axiomes P1P5. Aix es com ho

hem fet al llibre de text (pa`g. 125) Pero` aquesta solucio es massa ad hoc.

Ara en considerem una altra formulacio, deguda a Richard Dedekind (1831

1916), que tambe implica lexiste`ncia de N. Comencem introduint el conceptedinfinitud tal com el va definir Dedekind. Es el concepte de D-infinitud (D

per Dedekind, naturalment).

Un conjunt A es D-infinit sii hi ha una funcio f : A A que es injectivapero` no sobre A. Altrament dit, A es D-infinit sii es bijectable amb un

subconjunt propi de si mateix.

(7) Axioma dinfinitud. Hi ha un conjunt D-infinit.

Amb lajut daquest axioma demostrem lexiste`ncia dun conjunt N , unafuncio : N N , un element e N que compleixen P1P5 (amb N en ellloc de N, en el lloc de S i e en el lloc de 0).

Sigui A un conjunt D-infinit. Sigui f : A A una funcio injectiva pero`no sobre A. Aix, A 6= rec(f). Sigui e A rec(f).

Considerem la colleccioH = {X A : e X i f [X] X}

H no es buida, ja que A H. PosemN =

H.

Finalment, sigui la restriccio de f a N , es a dir, = f (N A). Aix, es la funcio de N en A tal que, per a tot x N , (x) = f(x). Tenim que

(1) e N . Aixo` es aix ja que e pertany a tots els elements de H.(2) : N N . En efecte, sigui a N . Aix, a pertany a tot X H.

Per definicio de H, doncs, f(a) tambe pertany a tot X H. Aix,per definicio de N , f(a) N . Com que (a) = f(a), (a) N .

(3) per a tot X N , si e X i [X] X, llavors X = N . Aixo` es aixja que si e X i [X] X, llavors (com que [X] = f [X]) X Hi, per tant, N X. Aix, si X N , X = N .

(4) e / rec(), ja que e / rec(f).(5) es injectiva, ja que f ho es.

Hem verificat, doncs, que N , i e satisfan els principis P1P5. Compleixen,doncs, les condicions requerides dels nombres naturals. Per tant, podem con-

cloure que laxioma dinfinitud implica lexiste`ncia del conjunt dels nombres

naturals (amb loperacio de successor i el nombre zero).

34

10. Definicio de lordre natural dels nombres naturals

En aquesta seccio treballem nomes amb els principis P1P5, sense fer cap

us dels resultats de la seccio 8 (relatius a lordre natural < de N). Definiremun ordre lineal en N i mostrarem que compleix els principis P6 i P7,que, per tant, son innecessaris com a principis, ja que esdevenen teoremes.

Finalment, mostrarem que lordre es precisament lordre

35

Suposem ara que n m i sigui X un conjunt hereditari tal que Sm X.Hem de veure que Sn X. Com que n m, tenim que n = m o n m. Enel primer cas, Sn = Sm i, aix, Sn X; en el segon, com que m X, tambeSn X. 10.3. Conseque`ncies de (O1) i (O2). Mostrarem ara que la relacio compleix P6 i P7. Que compleix P7 es clar, ja que P7 es precisament (O2).

Nomes ens cal veure, doncs, que es un ordre lineal en N. Veurem que hoes apellant nomes al fet que compleix (O1) i (O2).Lema 10.3.

(1) Per a tot n N, 0 n.(2) Per a tot n N, n Sn.

Demostracio.

(1) Sigui X = {n N : 0 n}. Hem de veure que X = N. Ara be, 0 X(ja que 0 0), i si n X, es a dir, si 0 n, llavors, per (O2), 0 Sn, i aix0 Sn. Per P3, doncs, X = N.

(2) Per (O2), ja que n n. Proposicio 10.4. es transitiva.Demostracio. Siguin n,m N i considerem el conjunt

X = {k N : si n m k, llavors n k} .Hem de veure que X = N, per induccio.Per (O2), 0 X, va`cuament. Suposem inductivament que k X. Hem

de mostrar que Sk X. Suposem, doncs, que n m Sk, amb la intenciode concloure que n Sk, es a dir, que Sk X. Per (O2), n m k, es adir, n m k o n m = k. En ambdos casos (per hipo`tesi inductiva elprimer i trivialment el segon) n k. Per tant, per (O2), n Sk. Lema 10.5. Per a tot n,m N, si n m, llavors Sn m.Demostracio. Sigui n N i considerem el conjunt

X = {m N : si n m, llavors Sn m} .Mostrem que X = N, per induccio.Per (O2), 0 X, va`cuament. Sigui m X (hipo`tesi inductiva) i suposem

que n Sm amb la intencio de concloure que Sn Sm, es a dir, queSm X. Per (O2), n m, o sigui, (i) n m o (i) n = m. Si (i), es a dir,si n m, llavors, per hipo`tesi inductiva, Sn m. Aix, com que (pel lema10.3) m Sm, per transitivitat de , Sn Sm. Si (ii), es a dir, si n = m,Sn = Sm. Per tant, en qualsevol cas, Sn Sm, com havem de mostrar. Proposicio 10.6. es irreflexiva.Demostracio. Sigui X = {n N : n 6 n}. Mostrem que X = N per induc-cio. 0 X, per (O1). Suposem inductivament que n X i, en cerca duna

36

contradiccio, que Sn / X, es a dir, que Sn Sn. Per (O2), doncs, Sn n i(pel lema 10.3) n Sn. Pero` llavors, com que es transitiva, n n, es adir, n / X, en contra de la hipo`tesi inductiva. Proposicio 10.7. Per a tot n,m N, m n o n m o m = n.Demostracio. Sigui m N i considerem el conjunt

X = {n N : m n o n m o m = n} .Mostrem que X = N per induccio. Com que 0 m (lema 10.3), 0 X.

Suposem inductivament que n X amb la intencio de concloure que Sn X.Com que n X, hi ha dos casos possibles: (i) m n i (ii) n m. En el cas(i), m Sn, per (O2), i en el cas (ii), Sn m, per lema 10.5. En qualsevolcas, doncs, m Sn o Sn m o m = Sn, de manera que Sn X, comhavem de mostrar.

Pels lemes 10.6, 10.4 i 10.7, es un ordre lineal en N, i aix compleix P6i P7. Pero` com sabem que es precisament

37

11. Conjunts finits

Un conjunt A es finit sii hi ha un nombre natural n tal que A In, on(vegin (8.2)) In es el segment inicial de N determinat per n.

Lema 11.1. Si A B, a A i b B, hi ha g : A B tal que g(a) = b.Demostracio. Vegin el llibre de text.

Lema 11.2. Si n,m N i In Im, llavors n = m.Demostracio. Sigui

X = {n N : per a tot m N, si In Im, llavors n = m} .Mostrem per induccio que X = N. Pels detalls vegin el llibre de text.

Corollari 11.3. Per a tot conjunt finit A hi ha un unic n N tal queA In.Demostracio. Pel lema 11.2.

Aquest corollari ens permet definir el nombre delements dun conjuntfinit.

Si A es un conjunt finit, el nombre delements de A, o, tambe, la

cardinalitat de A (en smbols, |A|) es lunic n N tal que A In. O sigui,(11.1) |A| = n sii A In.

Com que I0 = i nomes es bijectable amb si mateix, |A| = 0 sii A = .Per mes naturalitat, en lloc de Sn sovint direm n + 1. Ho farem

sobretot en contextos de cardinalitat. Ara be, com que no hem definit la

suma, n+ 1 es un mer sino`nim de Sn.

(11.2) n+ 1 = Sn

Proposicio 11.4. Sigui A un conjunt finit.

(1) Si A B, B es finit i |A| = |B|.(2) Si |A| = n i x / A , llavors |A {x}| = n+ 1.(3) Si |A| = n+ 1 i n A, llavors |A x| = n.

Demostracio. Vegin el llibre de text.

Proposicio 11.5. Si A In, llavors A es finit i |A| < n.Demostracio. Considerem el conjunt

X = {n N : per a tot A In, |A| < n} .Mostrem per induccio que X = N. Va`cuament, 0 X. Sigui ara n N isuposem inductivament que n X. Veurem que n + 1 X. Sigui, doncsA In+1. Hem de concloure que |A| < n + 1. Considerem dos casos, (i)n / A i (ii) n A. En el primer cas, A In i, com que n X, |A| < n iaix |A| < n + 1. En el segon cas, A {n} In i aix |A {n}| < n. Pero`llavors, per (2) de la proposicio 11.4, tambe |A| < n+ 1.

38

Corollari 11.6. Si A es finit i B A, B tambe es finit i |B| < |A|.Demostracio. Per la proposicio 11.5.

Corollari 11.7. Tot subconjunt dun conjunt finit es finit. Aix,(1) si A i B son conjunts finits, tambe ho son A B i AB,(2) si H es una colleccio no buida de conjunts, almenys un dels quals

es finit, la interseccioH es un conjunt finit.

Demostracio. Pel corollari anterior. Proposicio 11.8. La unio de dos conjunts finits es un conjunt finit.

Demostracio. Sigui A un conjunt finit i considerem el conjunt

X = {n N : per a tot conjunt B de n elements, A B es finit}Basta mostrar que X = N. Ho fem per induccio. Com que A = A,

0 X. Sigui n N i suposem inductivament que n X. Vegem quen+ 1 X. Sigui B in conjunt de n+ 1 elements. Hem de mostrar que ABes finit. Sigui b B. El conjunt C = B {b} te n elements i, per tant, comque n X, AC es finit, Pero` llavors (per (2) de la proposicio 11.4) tambeho es A B, ja que A B = (A C) {b}.Proposicio 11.9. La unio de tota colleccio finita de conjunts finits es unconjunt finit.

Demostracio. Sigui X el conjunt dels n N tal que per a tota collecciofinita de conjunts H, si |H| = n, la unio H es finita. Mostrem per induccioque X = N.

Com que = , 0 N. Si n X (hipo`tesi inductiva) i |H| = n + 1,

prenem A H i considerem la colleccio K = H {A}. Com que |K| = n in X, K es finita. Pero` llavors, per la proposicio 11.8, tambe ho es H,ja que

H = K A. Proposicio 11.10. El producte cartesia` de dos conjunts finits es un conjunt

finit.

Demostracio. Vegin el llibre de text.

Proposicio 11.11. El conjunt pote`ncia dun conjunt finit es finit.

Demostracio. Exercici.

Proposicio 11.12. Si f : A B i X es un subconjunt finit de A, llavorsf [X] es finit i |f [X]| |X|.Demostracio. Donat f : A B, sigui D el conjunt dels nombres naturalsn tal que per a tot subconjunt finit X de A, si |X| = n, llavors |f [X]| n.Mostrem per induccio que D = N.

Com que f [] = , es clar que 0 D. Procedint inductivament, suposemque n D amb lobjecte de concloure que n + 1 D. Sigui, doncs, X un

39

subconjunt de A de n+ 1 elements. Hem de veure que |f [X]| n+ 1. Siguia X (aixo` es possible, ja que X 6= ) i sigui Y = X {a}. |Y | = n, i aix,com que n D, |f [Y ]| n. Pero` llavors, com que f [X] = Y {f(a)}, tenimque f [X] n+ 1. Corollari 11.13. Si A es finit i f es una funcio amb domini A, llavorsrec(f) es finit i |rec(f)| |A|.Demostracio. Per la proposicio 11.12.

Proposicio 11.14. Sigui A un conjunt finit i f : A A.(1) Si f es injectiva, llavors f es sobre A.

(2) Si f es sobre A, llavors f es injectiva.

Demostracio. Exercici.

Proposicio 11.15. Si A,