Una demostració alternativa de què R no és numerable
Segurament recordau que en la carrera de Matemàtiques vos varen parlar sobre cardinals i sobre un teorema bastant trascendent: els nombres reals no són enumerables.
Segurament també recordeu que aquest teorema de fet demostrava que el conjunt [0, 1] no és enumerable. I supòs que segurament la demostració d’aquest fet es va fer utilitzant l’arxiconegut argument de la diagonal de Cantor.
I segurament n’hi ha haver alguns (una minoria, segurament) a la classe que no el varen acabar d’entendre o que no hi varen estar d’acord.
Almenys a la UIB hi havia un element d’aquest darrer grup (jo; i em pareix recordar que en Félix). L’argument per estar-hi en contra era molt simple: si per hipòtesi es suposa que R es pot enumerar amb 
, < … < 
< …. , ¿com es pot construir un 
amb 
(
no existiria per hipòtesi)?
Bé, fos o no aquesta raó o una altra que teníeu per estar-hi en contra, segurament vos vàreu quedar amb un dubte raonable de la validesa d’aquest teorema (fins a obtenir-ne una altra i “vertadera” demostració). Doncs bé, ahir llegint aquest llibre, en vaig trobar una altra (que de fet, he trobat reproduïda i aclarada a la Wikipedia):
The theorem
Suppose a set R
- is linearly ordered, and
- contains at least two members, and
- is densely ordered, i.e., between any two members there is another, and
- has the following least upper bound property. If R is partitioned into two nonempty sets A and B in such a way that every member of A is less than every member of B, then there is a boundary point c (in R), so that every point less than c is in A and every point greater than c is in B.
Then R is not countable.
The set of real numbers with its usual ordering is a typical example of such an ordered set R; other examples are real intervals of non-zero width, possibly with half-open gaps. The set of rational numbers (which is countable) has properties 1, 2, and 3 but does not have property 4.
The proof
The proof is by contradiction. It begins by assuming R is countable and thus that some sequence x1, x2, x3, … has all of R as its range. Define two other sequences (an) and (bn) as follows:
- Pick a1 < b1 in R (possible because of property 2).
- Let an + 1 be the first element in the sequence x that is strictly between an and bn (possible because of property 3).
- Let bn + 1 be the first element in the sequence x that is strictly between an + 1 and bn.
The two monotone sequences a and b move toward each other. By the completeness of R, some point c must lie between them. (Define A to be the set of all elements in R that are smaller than some member of the sequence a, and let B be the complement of A; then every member of A is smaller than every member of B, and so property 4 yields the point c.) Since c is an element of R and the sequence x represents all of R, we must have c = xi for some index i (i.e., there must exist an xi in the sequence x, corresponding to c.) But, when that index was reached in the process of defining the sequences a and b, c would have been added as the next member of one or the other sequence, contrary to the fact that c lies strictly between the two sequences. This contradiction finishes the proof.
Hola Xavi. Em toca participar, per al·lusions
29 Febrer 2008, 11:24 amRecord perfectament que em va suposar un salt cognitiu haver de comprendre aquesta demostració (com tantes altres coses… això em passa per fer-me preguntes, si m’estigués quiet…)
Però a més de la demostració de R no numerable a primer curs, record que estàvem junts a classe d’anàlisi de segon curs i la professora va emprar el mateix mètode de la diagonal de Cantor per fer la demostració a un altre conjunt numèric on les xifres només eren 0 i 1 (i no sé si també el 2, no ho record exactament). La qüestió que vaig plantejar és que depenent de com estiguessin ordenats els nombre podríem crear un nombre periòdic amb una expressió distinta però que ja estigués inclòs amb una altra expressió no periòdica. Per entendre’ns, ja sé que als real no pot passar si no escollim el 9, però és com si seguint el mètode de la diagonal ens quedés el nombre 0′4999999… que suposadament és distint a tos els de la llista per construcció, però a aquesta llista podria estar el nombre 0′5, que és el mateix i per tant no contradiria res.
No sé si s’ha entès el que volia dir.
Salutacions,
Félix.
Si, i també record que estàvem junts a classe d’Anàlisi Complexa i en Marc el va utilitzar per provar no sé què de complexes… En general aquest argument s’utilitza per altres coses i no només per provar que R no és numerable (per exemple per provar que no totes les funcions són recursivament enumerables….). Per tant si no ens convenç aquest argument hauríem de cercar arguments equivalents distints per a cada demostració (el que és una matada).
Sí, ara que ho dius, record el teu dubte. De fet el teu dubte està contemplat als llibres que demostren més formalment el teorema utilitzant la diagonal de Cantor: 0,5 i 0,499999999…. és el mateix nombre (en tant en quant si computes la sèrie et surt 0,5) El que es fa és elegir un dels dos o bé els dos.
Realment si ho penses bé el que feim és per a cada nombre x real, tenim un conjunt de successions (format per dos nombres si el nombre és periòdic pur i 1 en cas contrari). Podem agafar les dues representacions, ja que el que ens interessa veure és que R no és numerable i per tant és un poc igual si es repeteixen nombres a la seva pressumpte enumeració.
No sé, t’he aclarit el dubte?
Sinó, doncs mira, agafem una altra representació. Per exemple de [0,1] podríem agafar aquesta representació per un nombre x qualsevol: per a x tendria una seqüència de {0,1}: x = (a_1,….., a_r, …..). a_1 seria 0 si x 0,5; a_2 seria 0 si x estaria a la primera meitat de l’interval [0, 1/2] i 1 si està a la segona meitat de [0, 1/2]….. etc.
Està clar que aquesta aplicació és bijectiva. (no ho he provat!)
Doncs amb aquesta ap. no tens aquest problema, ¿o sí?.
Per altra part, aquí convenç l’argument de la diagonal?
Xavi
29 Febrer 2008, 1:35 pmHola Xavi
sí, feia segles que no passava per aquí, estic massa liat i com sempre, lo urgent impedeix que em dediqui a lo important.
A banda que m’agraden els arguments diagonals (i sí, de vegades són més complicats que la versió light que se’n dóna a classe. ho fem per no espantar-vos), aquesta demostració que proposes també té els seus punts foscos. Perquèx no pot anar despres de atotes les as i totes les bs?
Els racionals són numerables, podríem fer una numeració on primer anassin tots els racionals entre 0 i 1 i després la resta (els ordenam primer per valor absolut i per signe, jo què sé).
Considera ara les sucessions
a_0=0, b_0=1
a_{n+1}=(a_n+b_n)/2 b_{n+1}=(a_{n+1}+b_n)/2
i c (que serà no racional) els suprem dels (a_n)_n. Ara canvia a Q el 2 per aquesta c, encara tenim un conjunt numerable. Considera una numeracio de (Q-{2})U{c} que comenci per
a0,b0,a1,b1,a2,b2,a3,b3,….
i després segueixi c i la resta dels racionals. El conjunt es numerable, devem poder-ho fer.
Amb aquesta numeracio de Q, partint de 0 i 1 trobaries les successions (a_n)_n i (b_n)_n descrites, mai no trobaries c, no hi ha contradiccio.
Per què no podem prendre una aordenació de R similar?
Vull dir, si no trob la contradiccio a (Q-{2})U{c}, no veig per què aquest argument dóna contradicció a R.
No ho sé, aquests dies dedicat full time a les xarxes filogenètiques em poden haver embossat el meu sector analista del cervell (que sempre ha estat molt subdesenvolupat).
4 Març 2008, 6:00 amBé Xesc, en primer lloc benvingut de nou.
En segon lloc no t’acab t’entendre: quin problema hi ha a la demostració? Per altra banda si vols agafar una altra ordenació Q i fer el suprem no passarà res. Hi haurà un altre c que no serà de Q (de fet n’hi ha bastants!).
No sé, no acab de veure el que dius. Ho pots dir més clar?
Per altra banda, a la carrera potser ens faria falta assustar-nos i no quedar-nos amb el dubte de si l’argument diagonal és vàlid o no. Si per provar ben provat que [0,1] no és numerable hem de provar que:
1) [0, 1] és isomorf a 2^N (el conjunt de successions amb elements a {0,1}) i que això a la vegada és isomorf a P(N)
2) Card(P(N)) > Card(N) (teorema de Cantor: http://en.wikipedia.org/wiki/Cantor%27s_theorem)
3) Per tant [0, 1] no és numerable
doncs provem-ho!
Moltes vegades es vol “enganyar” als alumnes i pens que és un error. Les simplificacions moltes vegades fan que els alumnes no adquireixin l’essència dels objectes que es tracta (i ho dic a tots els nivells).
D’aquesta manera només s’aconsegueix que es generin dos bitxos raros com en Félix i jo
4 Març 2008, 9:01 am