Kalkulebla aro

En matematiko, kalkulebla aro estas aro kun la sama kardinala nombro (povo de aro aŭ kvanto de elementoj) kiel iu subaro de la aro de ĉiuj naturaj nombroj. Aro, kiu ne estas kalkulebla estas nomata nekalkulebla. La termino devenas de Georg Cantor. La elementoj de kalkulebla aro povas esti kalkulitaj po unu: kvankam la kalkulado povas neniam finiĝi, tamen ĉiu elemento 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 nefinia por la lasta.

La kardinala nombro de kalkuleble nefinia aro estas skribata kiel $\aleph _{0}$ (la komenca alef-nombro) aŭ $\beth _{0}$ (la komenca beth-nombro).

Difino

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 nefinia.

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

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 nefiniaj 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 nefinia. Ĉ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 nefinia, ĉ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 nefinia subaro de kalkuleble nefinia aro estas kalkuleble nefinia.

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

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:

• 1. S estas kalkulebla, kio estas ke ekzistas enĵeto
• : f : S → N
• 2. S estas malplena aŭ ekzistas surĵeto
• : g : N → S
• 3. S estas finia aŭ tie ekzistas reciproke unuvalora surĵeto
• : h : N → S

Kelkaj normaj propraĵoj sekvas facile el ĉi tiu teoremo. N en la teoremo povas esti anstataŭita kun ĉiu kalkuleble nefinia 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×N → N donita per f(m, n) = 2^m3ⁿ 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 : Z → N donita per f(n) = 2ⁿ se n estas nenegativa kaj f(n) = 3⁻ⁿ se n estas negativa estas enĵeto. La racionalaj nombroj Q estas kalkuleblaj ĉar la funkcio g: Z×N → Q 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:

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 kunaĵo de kalkuleble multaj kalkuleblaj aroj estas kalkulebla. Formale, se A_n 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) = g_n(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 g_n el la ne-malplena kolekto de surĵetoj de N al A_n.

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

Ĉi tiu aro estas la kunaĵo 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 kunaĵo 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 nefiniaj 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

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

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ŭ

• Alef-nombro
• Beth-nombro
• Kardinalo de kontinuumo
• Nekalkulebla aro
• Hilberta paradokso de la Granda Hotelo

Eksteraj ligiloj

• Thomas Jech, Set Theory, Stanford Encyclopedia of Philosophia
• Neil Calkin, Herbert Wilf (2000), Recounting the rationals. American mathematical monthly, 107(4), pp 360–363.
• [1]