Kalkulebla aro

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

En matematiko, kalkulebla aro estas aro kun la sama kardinala nombro (povo de aro aŭ kvanto de eroj) kiel iu subaro de la aro de ĉiuj naturaj nombroj. Aro kiu estas ne kalkulebla estas nomata kiel nekalkulebla. La termino devenas de Georg Cantor. La eroj de kalkulebla aro povas esti kalkulitaj po unu, kvankam la kalkulado povas neniam finiĝi, tamen ĉiu ero de la aro estos asociita kun natura nombro.

Iuj aŭtoroj uzas la terminon kalkulebla aro por aro kun la sama kardinalo kiel la aro de ĉiuj naturaj nombroj. La diferenco inter la du difinoj estas ke sub la unua, finiaj aroj estas ankaŭ konsiderataj kiel kalkuleblaj, dum sub la lasta difino, ili estas ne konsiderataj kiel kalkuleblaj. Por forigi ĉi tiun multvalorecon, la termino maksimume kalkulebla estas iam uzita por la unua komprenaĵo, kaj kalkuleble malfinia por la lasta.

La kardinala nombro de kalkuleble malfinia aro estas skribata kiel \aleph_0 (la komenca alef-nombro) aŭ \beth_0 (la komenca beth-nombro).

Difino[redakti | redakti fonton]

Aro S estas nomata kiel kalkulebla se ekzistas enĵeto

f : S → N

de S al la aro de ĉiuj naturaj nombroj N = {0, 1, 2, 3, ...}.

Se f estas ankaŭ surĵeto, tial farante f ensurĵeton, do S estas kalkuleble malfinia.

Pro tio ke ekzistas reciproke unuvalora surĵeto inter N = {0, 1, 2, 3, ...} kaj N* = {1, 2, 3, 4, ...}, ne estas diferenco ĉu oni konsideras 0 kiel natura nombro aŭ ne. Ĉiuokaze, ĉi tiu artikolo sekvas ISO 31-11 kaj la norman konvencion en matematika logiko ke 0 estas natura nombro.

Enkonduko[redakti | redakti fonton]

La bezonata koncepto estas ensurĵeto (reciproke unuvalora surĵeto). Ekzemple, rilato

"a" ↔ 1, "b" ↔ 2, "c" ↔ 3

estas reciproke unuvalora surĵeto ĉar ĉiu ero de {"a", "b", "c"} estas parita kun precize unu ero de {1, 2, 3 }, kaj reen.

Laŭ difino, du aroj estas de la sama amplekso se kaj nur se ekzistas reciproke unuvalora surĵeto inter ili. Por ĉiuj finiaj aroj ĉi tio donas la kutiman difinon de la sameco de amplekso. Por la amplekso de malfiniaj aroj, la aferoj estas jenaj.

Konsideru la du arojn: aron de ne-negativaj entjeroj A = {0, 1, 2, 3, 4, 5, ...} kaj aron de ne-negativaj paraj entjeroj B = {0, 2, 4, 6, 8, 10, ...}. Ĉi tiuj aroj estas de la sama amplekso, ĉar ekzistas reciproke unuvalora surĵeto inter ili, kiel n ↔ 2n:

1 ↔ 2, 2 ↔ 4, 3 ↔ 6, 4 ↔ 8, ...

Ĉiu ero de A estas parita for kun precize unu ero de B, kaj reen. De ĉi tie ili havas la saman amplekson, kaj pro tio B estas kalkuleble malfinia. Ĉi tio donas ekzemplon de aro kiu estas de la sama amplekso kiel unu el siaj propraj subaroj, situacio kiu estas neebla por finiaj aroj.

La paranta funkcio de Cantor asignas unu naturan nombron al ĉiu paro de naturaj nombroj

La aro de ĉiuj ordigitaj duopoj de naturaj nombroj estas kalkuleble malfinia, ĉar ekzistas reciproke unuvalora surĵeto inter ĝi kaj aro de ĉiuj naturaj nombroj:

0 ↔ (0, 0), 1 ↔ (1, 0), 2 ↔ (0, 1), 3 ↔ (2, 0), 4 ↔ (1, 1), 5 ↔ (0, 2), 6 ↔ (3, 0), 7 ↔ (2, 1), 8 ↔ (1, 2), ...

Ĉi tiu reciproke unuvalora surĵeto estos kovras ĉiujn ĉi tiajn ordigitajn duopojn.

Ĉiu subaro de kalkulebla aro estas kalkulebla. Ĉiu malfinia subaro de kalkuleble malfinia aro estas kalkulebla malfinio.

Ekzemple, la aro de primoj estas kalkulebla, per surĵeto de la n-a primo al n:

2 ↔ 1, 3 ↔ 2, 5 ↔ 3, 7 ↔ 4, 11 ↔ 5, 13 ↔ 6, 17 ↔ 7, 19 ↔ 8, 23 ↔ 9, ...

Bazaj propraĵoj[redakti | redakti fonton]

Per difino aro S estas kalkulebla se ekzistas enĵeto

f : S → N

de S al la aro de ĉiuj naturaj nombroj N = {0, 1, 2, 3, ...}.

Jena teoremo donas ekvivalentajn formulaĵojn de la difino:

Baza teoremo: Estu S aro. Jenaj frazoj estas ekvivalentaj:

Kelkaj normaj propraĵoj sekvas facile el ĉi tiu teoremo. N en la teoremo povas esti anstataŭita kun ĉiu kalkuleble malfinia aro. Aparta estas jena korolario.

Korolario: Estu S kaj T aroj. Tiam:

  • 1. Se funkcio f : S → T estas enĵeta kaj T estas kalkulebla do S estas kalkulebla.
  • 2. Se funkcio g : S → T estas surĵeta kaj S estas kalkulebla do T estas kalkulebla.

Pruvo: Por (1) observu ke se T estas kalkulebla ekzistas enĵeto h : T → N . Tiam se la funkcio f : S → T estas enĵeta do la komponaĵo h \circ f: S \to \mathbb{N} estas enĵeta, do S estas kalkulebla.

Por (2) observu ke se S estas kalkulebla estas surĵeto h : N → S. Tiam se g : S → T estas surĵeta do la komponaĵo g \circ h: \mathbb{N} \to T estas surĵeta, do T estas kalkulebla.

Teoremo: Ĉiu subaro de kalkulebla aro estas kalkulebla.

Pruvo: La limigo de enĵeto al subaro de ĝia domajno estas ankoraŭ enĵeto.

Teoremo: La kartezia produto de du kalkuleblaj aroj A kaj B estas kalkulebla. Plu, la kartezia produto de ĉiu finia kolekto de kalkuleblaj aroj estas kalkulebla.

Pruvo: N×N estas kalkulebla ĉar la funkcio f: N×NN donita per f(m, n) = 2m3n estas enĵeta (estas multaj variantoj de konstruo de la funkcio f; la alian varianton, la parantan funkcion de Cantor vidu pli supre). Tiam sekvas el la baza teoremo kaj la korolario ke la kartezia produto de ĉiuj du kalkuleblaj aroj estas kalkulebla. Ĉi tio sekvas ĉar se A kaj B estas kalkuleblaj estas surĵetoj f : N → A kaj g : N → B. Do f×g: N×N → A×B estas surĵeto de la kalkulebla aro N×N al la aro A×B kaj la korolario implicas ke A×B estas kalkulebla. Ĉi tiu rezulto ĝeneraligatas al la kartezia produto de ĉiu finia kolekto de kalkuleblaj aroj kaj la pruvo estas per indukto sur la kvanto de aroj en la kolekto.

Teoremo: La entjeroj Z estas kalkuleblaj kaj la racionalaj nombroj Q estas kalkuleblaj.

Pruvo: La entjeroj Z estas kalkuleblaj ĉar la funkcio f : ZN donita per f(n) = 2n se n estas nenegativa kaj f(n) = 3-n se n estas negativa estas enĵeto. La racionalaj nombroj Q estas kalkuleblaj ĉar la funkcio g: Z×NQ donita per g(m, n) = m/(n+1) estas surĵeto de la kalkulebla aro Z×N al la racionaloj Q. Povas esti konstruita ankaŭ implica ensurĵeto inter N kaj Q:

CalkinWilf.svg
Ensurĵeto inter N kaj Q de Neil Calkin kaj Herbert Wilf. De ĉiu nombro a/b, maldekstre sube estas a/(a+b) kaj dekstre sube estas (a+b)/b. La rikura formulo estas
x0=0,  x_{n+1}={1\over \lfloor x_n\rfloor + 1 -\{x_n\}}
kie ⌊xn estas la entjera parto de xn kaj {xn}=xn-⌊xn.

Per simila evoluo, la aro de ĉiuj algebraj nombroj estas kalkulebla, kaj la aro de ĉiuj difineblaj nombroj estas kalkulebla.

Teoremo: (Alprenanta la aksiomon de kalkulebla elekto) La unio de kalkuleble multaj kalkuleblaj aroj estas kalkulebla. Formale, se An estas kalkulebla aro por ĉiu n en N tiam \bigcup_{n \in \mathbb{N}} A_n estas kalkulebla.

Pruvo: Ĉi tio estas konsekvenco de tio ke por ĉiu n ekzistas surĵeto  g_n : \mathbb{N} \to A_n kaj de ĉi tie la funkcio

G : \mathbb{N} \times \mathbb{N} \to \bigcup_{n \in \mathbb{N}} A_n

donita per G(n, m) = gn(m) estas surĵeto. Pro tio ke N×N estas kalkulebla la korolario implicas ke  \bigcup_{n \in \mathbb{N}} A_n estas kalkulebla. Oni uzas la aksiomon de kalkulebla elekto en ĉi tiu pruvo por preni por ĉiu n en N surĵeton gn el la ne-malplena kolekto de surĵetoj de N al An.

Teoremo: La aro de ĉiuj finio-longaj vicoj de naturaj nombroj estas kalkulebla.

Ĉi tiu aro estas la unio de la vicoj de longo 1, la vicoj de longo 2, la vicoj de longo 3, kaj tiel plu. Ĉiu el ili estas kalkulebla aro ĉar estas finia kartezia produto de kalkuleblaj aroj. Tiel en la teoremo estas konsiderata la kalkulebla unio de kalkuleblaj aroj, kiu estas kalkulebla per la antaŭa teoremo.

Teoremo: La aro de ĉiuj finiaj subaroj de la naturaj nombroj estas kalkulebla.

Se estas finia subaro, oni povas ordigi la eroj de ĝi en finian vicon. Estas nur kalkuleble multaj finiaj vicoj, tiel ankaŭ estas nur kalkuleble multaj finiaj subaroj.

Teoremo de Cantor: Se A estas aro kaj P(A) estas ĝia aro de ĉiuj subaroj, do ne ekzistas surĵeto de A al P(A). Senpera konsekvenco de ĉi tio kaj de la baza teoremo pli supre estas:

Teoremo: La aro P(N) ne estas kalkulebla; kio estas ĝi estas nekalkulebla.

Por ellaborado de ĉi tiu rezulto vidu en diagonala argumento de Cantor.

La aro de reelaj nombroj estas nekalkulebla (vidu ankaŭ en unua nekalkulebleca pruvo de Cantor), kaj nekalkulebla estas la aro de ĉiuj malfiniaj vicoj de naturaj nombroj. Topologia pruvo por la nekalkulebleco de la reelaj nombroj estas priskribita en finia intersekca propraĵo.

Minimuma modelo de aroteorio estas kalkulebla[redakti | redakti fonton]

Se estas aro kiu estas norma modelo (vidu en ena modelo) de aroteorio de Zermelo-Fraenkel, tiam estas minimuma norma modelo (vidu en konstruebla universo). La teoremo de Löwenheim-Skolem povas esti uzata por montri ke ĉi tiu minimuma modelo estas kalkulebla. Tio ke la komprenaĵo de nekalkulebleco havas senco eĉ en ĉi tiu modelo, kaj aparte ke ĉi tiu modelo M enhavas erojn kiu estas samtempe

  • subaroj de M, de ĉi tie kalkuleblaj,
  • sed nekalkuleblaj de la punkto de vido de M,

estis vidita kiel paradoksa en la fruaj tagoj de aroteorio, vidu en paradokso de Skolem.

La minimuma norma modelo inkluzivas ĉiuj algebrajn nombrojn kaj ĉiujn efike komputeblajn transcendajn nombrojn, kaj ankaŭ multajn aliajn specojn de nombroj.

Tutecaj ordoj[redakti | redakti fonton]

Kalkuleblaj aroj povas esti tutece ordigitaj diversmaniere, ekzemple:

  • bonaj ordoj (vidu ankaŭ en orda numero):
    • la kutima ordo de naturaj nombroj
    • entjeroj en la ordo 0, 1, 2, 3, ..., -1, -2, -3, ...
    • entjeroj en la ordo 0, 1, -1, 2, -2, 3, -3, ...
  • aliaj:
    • la kutima ordo de entjeroj
    • la kutima ordo de racionalaj nombroj

Vidu ankaŭ[redakti | redakti fonton]

Eksteraj ligiloj[redakti | redakti fonton]