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 ${\displaystyle \aleph _{0}}$ (la komenca alef-nombro ) a? ${\displaystyle \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 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 [ 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 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 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 [ 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:

• 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 ${\displaystyle 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 ${\displaystyle 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 ^m 3 ⁿ 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 ^?n 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 x 0 =0 , ${\displaystyle x_{n+1}={1 \over \lfloor x_{n}\rfloor +1-\{x_{n}\}}}$ kie ?x n ? estas la entjera parto de x n kaj {x n }=x n -?x n ? .

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 ${\displaystyle \bigcup _{n\in \mathbb {N} }A_{n}}$ estas kalkulebla.

Pruvo: ?i tio estas konsekvenco de tio ke por ?iu n ekzistas sur?eto ${\displaystyle g_{n}:\mathbb {N} \to A_{n}}$ kaj de ?i tie la funkcio

${\displaystyle 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 ${\displaystyle \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 [ 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 Lowenheim-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 ]

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

Eksteraj ligiloj [ redakti | redakti fonton ]

• 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]