En matematiko, nombrebla aro estas aro kun la sama kardinaleco ( nombro da elementoj) kiel iu subaro de la aro de naturaj nombroj.
Nombrebla aro estas aŭ finhava aro aŭ nombreble senfina aro.
Ĉu finhave aŭ senfine, la elementoj de nombrebla aro ĉiam povas esti nombritaj unu je fojo kaj, kvankam la nombrado neniam povas finiĝi, ĉiu elemento de la aro estas rilata al natura nombro.
#000001
Kelkaj verkintoj uzas nombreblaj metite signifi nombreble senfinaj sole.
Eviti tiun ambiguecon, la esprimon maksimume nombrebla povas esti uzita kiam finhavaj aroj estas inkluditaj kaj nombreble senfinaj, listigebla, [2] aŭ denumerablaj [3] alie.
#000002
Georg Cantor prezentis la esprimon nombreblajn metitajn, kontrastigajn arojn kiuj estas nombreblaj kun tiuj kiuj estas nenombreblaj (t.e., nelistigeblaj aŭ nondenumerablaj [4] ).
Hodiaŭ, nombreblaj aroj formas la fondon de branĉo de matematiko nomita diskreta matematiko .
#000003
4 Formala superrigardo sen detaloj
6 Minimuma modelo de aroteorio estas nombrebla
#000004
4 Minimuma modelo de aroteorio estas kalkulebla
#000005
Se tia f povas esti trovita tio estas ankaŭ surjektive (kaj tial bijektive), tiam S estas nomita nombreble senfina.
#000006
En aliaj vortoj, aro estas nombreble senfina se ĝi havas ekzaktan korespondadon kun la natura pli sensenta aro, N .
#000007
Kiel notite supre, tiu terminologio ne estas universala.
: Kelkaj verkintoj uzas nombreblaj por signifi kio estas ĉi tie nomita nombreble senfina, kaj ne inkludas finhavajn arojn.
#000008
Alternativaj (ekvivalento) formuliĝoj de la difino laŭ bijektive funkcio aŭ surĵeto ankaŭ povas ricevi.
#000009
En 1874, en lia unua aroteoriartikolo, Kantoro pruvis ke la aro de realaj nombroj estas nenombrebla, tiel montrante ke ne ĉio senfinaj aroj estas nombreblaj.
En 1878, li utiligis ekzaktajn korespondadojn por difini kaj kompari kardinalecojn.
En 1883, li etendis la naturajn nombrojn kun siaj senfinaj ordaj numeraloj, kaj uzis arojn de ordaj numeraloj por produkti senfinecon de aroj havantaj malsamajn senfinajn kardinalecojn.
#000010
Aro estas kolekto de elementoj, kaj povas esti priskribita laŭ multaj manieroj.
Unudirekta estas simple listigi ĉiujn ĝiaj elementoj;
Tio estas nur efika por malgrandaj aroj, aliflanke;
por pli grandaj aroj, tio estus tempopostula kaj erarema.
Anstataŭe de listigado de ĉiu ununura elemento, foje tripunkto (« ...
estas uzita, se la verkisto kredas ke la leganto povas facile konjekti kio maltrafas;
supozeble indikas la aron de entjeroj de 1 ĝis 100. Eĉ en tiu kazo, aliflanke, estas daŭre eble listigi ĉiujn elementojn, ĉar la aro estas finhava.
#000011
tiuj aroj havas pli ol n elementoj por iu entjero n.
, havas senlime multajn elementojn, kaj ni ne povas uzi ajnan normalan nombron por doni ĝian grandecon.
Tamen, ĝi turnas tiujn senfinajn arojn fari havi klare difinitan nocion de grandeco (aŭ pli konvene, de kardinaleco, kiu estas la termino por la nombro da elementoj en aro), kaj ne ĉiuj senfinaj aroj havas la saman kardinalecon.
#000012
Por kompreni kion tio signifas, ni unue ekzamenas kion ĝi ne signifas.
Ekzemple, ekzistas senlime multaj strangaj entjeroj, senlime multaj eĉ entjeroj, kaj (tial) senlime multaj entjeroj totalaj.
Tamen, ĝi turnas ke la nombro da eĉ entjeroj, kio estas la sama kiel la nombro da strangaj entjeroj, estas ankaŭ la sama kiel la nombro da entjeroj entute.
Tio estas ĉar ni aranĝas aĵojn tia ke por ĉiu entjero, ekzistas klara eĉ entjero: ...
aŭ, pli ĝenerale, n → 2n, vidas bildon.
Kion ni faris ĉi tie estas aranĝitaj la entjeroj kaj la eĉ entjeroj en ekzaktan korespondadon (aŭ ensurĵeton ), kio estas funkcio kiu mapoj inter du aroj tia ke ĉiu elemento de ĉiu aro egalrilatas al ununura elemento en la alia aro.
#000013
Tamen, ne ĉiuj senfinaj aroj havas la saman kardinalecon.
Ekzemple, Georg Cantor (kiu lanĉis tiun koncepton) protestis ke la realaj nombroj ne povas esti metitaj en ekzaktan korespondadon kun la naturaj nombroj (ne-negativaj entjeroj), kaj tial ke la aro de realaj nombroj havas pli grandan kardinalecon ol la aro de naturaj nombroj.
#000014
Aro estas nombrebla se: (1)
ĝi estas finhava, aŭ (2) ĝi havas la saman kardinalecon (grandeco) kiel la aro de naturaj nombroj.
Ekvivalente, aro estas nombrebla se ĝi havas la saman kardinalecon kiel iu subaro de la aro de naturaj nombroj.
#000015
De difino aro S estas nombrebla se tie ekzistas enĵeto f:
#000016
Eble ŝajnos nature dividi la arojn en malsamajn klasojn: metu ĉiujn arojn enhavantajn unu elementon kune;
ĉiuj aroj enhavante du elementojn kune;
finfine, ŝovo ekvilibra ĉio senfinaj aroj kaj konsideras ilin kiel havado de la sama grandeco.
Tiu vido ne estas daŭrema, aliflanke, sub la natura difino de grandeco.
#000017
Por ellabori tion ni bezonas la koncepton de ensurĵeto.
Kvankam "ensurĵeto" ŝajnas pli progresinta koncepto ol nombro, la kutima evoluo de matematiko laŭ aroteorio difinas funkciojn antaŭ nombroj, ĉar ili estas bazitaj sur multe pli simplanimaj aktoraroj.
Tio estas kie la koncepto de ensurĵeto envenas: difinu la korespondadon
#000018
, kaj inverse, tio difinas ensurĵeton.
#000019
Ni nun ĝeneraligas tiun situacion kaj difinas du arojn en la sama grandeco ĉu (kaj nur ĉu) ekzistas ensurĵeto inter ili.
Por ĉiuj finhavaj aroj tio donas al ni la kutiman difinon de "la sama grandeco".
Kion laŭ kion ĝi rakontas nin pri la grandeco de senfinaj aroj?
#000020
, la aro de eĉ pozitivaj entjeroj.
Ni asertas ke, sub nia difino, tiuj aroj havas la saman grandecon, kaj ke tial B estas nombreble senfina.
Revoko tio pruvi tio ni devas elmontri ensurĵeton inter ili.
Sed tio estas facila, uzante n ↔ 2n, tiel ke
#000021
Kiel en la pli frua ekzemplo, ĉiu elemento de A estis parigita kun ĝuste unu elemento de B, kaj inverse.
Tial ili havas la saman grandecon.
Tio estas ekzemplo de aro de la sama grandeco kiel unu el ĝiaj bonordaj subaroj, kiu estas malebla por finhavaj aroj.
#000022
Same, la aro de ĉiuj ordaj duopoj de naturaj nombroj estas nombreble senfina, kiel povas esti vidita per sekvado de pado kiel tiu en la bildo:
#000023
La rezulta mapado estas kiel tio:
#000024
Tiu mapado kovras tute tiajn ordajn duopojn.
#000025
Interese: se vi traktas ĉiun paron kiel esti la numeratoro kaj denominatoro de ordinara frakcio, tiam por ĉiu pozitiva frakcio, ni povas elpensi klaran nombron egalrilatantan al ĝi.
Tiu reprezentantaro ankaŭ inkludas la naturajn nombrojn, ĉar ĉiu natura nombro ankaŭ estas frakcio da N /1-a Tiel ni povas fini ke ekzistas same tiel multaj pozitivaj raciaj nombroj kia ekzistas pozitivaj entjeroj.
Tio estas vera ankaŭ por ĉiuj raciaj nombroj, kiel povas esti vidita malsupre.
#000026
La karteza produkto de finhave multaj nombreblaj aroj estas nombrebla.
#000027
Tiu formo de triangula mapanta rekursive ĝeneraligas al vektoroj de finhave multaj naturaj nombroj plurfoje mapante la unuajn du elementojn al natura nombro.
#000028
Foje pli ol unu mapado estas utila.
Tio estas kie vi mapas la aron kiun vi volas montri estas nombreble senfina sur alia aro - kaj tiam mapas tiun alian aron al la naturaj nombroj.
Ekzemple, la pozitivaj raciaj nombroj povas facile esti mapitaj al (subaro de) la paroj de naturaj nombroj ĉar al p / q mapas ( p, q).
#000029
Kio pri senfinaj subaroj de nombreble senfinaj aroj?
Tiuj havu pli malmultajn elementojn ol N?
#000030
Ĉiu subaro de nombrebla aro estas nombrebla.
Aparte, ĉiu senfina subaro de nombreble senfina aro estas nombreble senfina.
#000031
Ekzemple, la aro de primoj estas nombrebla, de mapado de la a primo al n:
#000032
Kio koncerne arojn estantajn nature "pli granda ol" N?
Ekzemple, Z la aro de ĉiuj entjeroj aŭ Q, la aro de ĉiuj raciaj nombroj, kiuj intuicie povas ŝajni multe pli grandaj ol N.
Sed aspektoj povas esti trompantaj, ĉar ni asertas:
#000033
Z (la aro de ĉiuj entjeroj) kaj Q (la aro de ĉiuj raciaj nombroj) estas nombreblaj.
#000034
En simila maniero, la aro de algebraj nombroj estas nombrebla.
#000035
Tiuj faktoj sekvas facile el rezulto ke multaj individuoj trovas ne-intuiciaj.
#000036
Ĉiu finhava unio de nombreblaj aroj estas nombrebla.
#000037
Kun la prudento de scii ke ekzistas nenombreblaj aroj, ni povas scivoli ĉu aŭ ne tiu lasta rezulto povas esti puŝita plu.
La respondo estas "jes" kaj "neniu", ni povas etendi ĝin, sed ni devas supozi novan aksiomon farendaĵo tion.
#000038
(Supozante la aksiomon de nombrebla elekto) La unio de nombreble multaj nombreblaj aroj estas nombrebla.
#000039
Ekzemple, antaŭfiksitaj nombreblaj aroj , b, c
#000040
Uzante variaĵon de la triangula listigo ni vidis supre:
#000041
Notu ke tio nur funkcias se la aroj , b, c, ...
Se ne, tiam la unio estas eĉ pli malgranda kaj estas tial ankaŭ nombrebla de antaŭa teoremo.
#000043
Ankaŭ notu ke ni bezonas la aksiomon de nombrebla elekto por indeksi ĉiujn arojn , b, c, ...
#000044
La aro de ĉiuj finhav-longaj sekvencoj de naturaj nombroj estas nombrebla.
#000045
Tiu aro estas la unio de la longosekvencoj, la longosekvencoj, la longosekvencoj, ĉiu el kiu estas nombrebla aro (finhava karteza produkto).
Tiel ni parolas pri nombrebla unio de nombreblaj aroj, kiu estas nombrebla de la antaŭa teoremo.
#000046
La aro de ĉiuj ne-senlimaj subaroj da la naturaj nombroj estas nombrebla.
#000047
Se vi havas ne-senliman subaron, vi povas ordigi la elementojn en finhavan sekvencon.
Ekzistas nur nombreble multaj finhavaj sekvencoj, do ankaŭ ekzistas nur nombreble multaj ne-senlimaj subaroj.
#000048
La sekva teoremo donas ekvivalentajn formuliĝojn laŭ bijektivefunkcio aŭ surĵeto.
Pruvo de tiu rezulto povas esti trovita en la teksto de Lang.
#000049
La sekvaj deklaroj estas ekvivalentaj:
#000050
S estas nombrebla, t.e. tie ekzistas enĵeto f:
Ĉiu S estas malplena aŭ tie ekzistas surĵeto g:
Ĉiu S estas finhava aŭ tie ekzistas ensurĵeto h:
#000051
Lasu S kaj T esti aroj.
#000052
S → T estas injektivo kaj T estas nombrebla tiam S estas nombrebla.
S → T estas surjektive kaj S estas nombrebla tiam T estas nombrebla.
#000053
Cantor's Theorem asertas ke se A estas aro kaj P ( A) estas it aro de ĉiuj subaroj, t.e. la aro de ĉiuj subaroj de A, tiam ekzistas neniu surĵeto de A ĝis P ( A).
Pruvo ricevas en la artikolo Cantor's Theorem.
Kiel tuja sekvo de tio kaj la Baza Teoremo supre ni havas:
#000054
Por pliprofundigo de tiu rezulto vidas la diagonalan argumenton de Cantor.
#000056
La aro de realaj nombroj estas nenombrebla (vidu Cantor unuan unkountabilecpruvon), kaj tiel estas la aro de ĉiuj senfinaj sekvencoj de naturaj nombroj.
#000057
La pruvoj de la deklaroj en ĉi-supra sekcio fidas sur la ekzisto de funkcioj kun certaj trajtoj.
Tiu sekcio prezentas funkciojn ofte uziten en tiu rolo, sed ne la konfirmoj ke tiuj funkcioj havas la postulatajn trajtojn.
La Baza Teoremo kaj ĝia Konsekvenco ofte estas utiligitaj por simpligi pruvojn.
Observu ke N en tiu teoremo povas esti anstataŭigita kun iu nombreble senfina aro.
#000058
Ĉiu finhava aro estas nombrebla.
#000059
por iu pozitiva natura pli sensenta n.
Tiu funkcio estas injekto de S en N .
#000060
Ĉiu subaro de nombrebla aro estas nombrebla.
#000061
B → N estu injektoj.
2g ( x) + 1 se x estas en B sed ne en A.
#000066
La karteza produkto de du nombreblaj aroj A kaj B estas nombrebla.
#000067
Observu ke N × N estas nombrebla kiel sekvo de la difino ĉar la funkcio f:
N × N → N evoluita per f ( m, n) = 2 m 3 n estas injektivo.
Ĝi tiam sekvas el la Baza Teoremo kaj la Konsekvenco ke la karteza produkto de iuj du nombreblaj aroj estas nombrebla.
Tio sekvas ĉar se A kaj B estas nombreblaj ekzistas surjektion f:
#000068
estas surjektion de la nombrebla aro N × N ĝis la aro A × B kaj la Konsekvenco implicas A × B estas nombreblaj.
Tiu rezulto ĝeneraligas al la karteza produkto de iu finhava kolekto de nombreblaj aroj kaj la pruvo sekvas per indukto sur la nombro da aroj en la kolekto.
#000069
La entjeroj Z estas nombreblaj kaj la raciaj nombroj Q estas nombreblaj.
#000070
La entjeroj Z estas nombreblaj ĉar la funkcio f:
Z → N evoluita per f ( n) = 2 n se n estas ne-negativa kaj f ( n) = 3 − n se n estas negativa, estas enĵeto.
La raciaj nombroj Q estas nombreblaj ĉar la funkcio g:
m /( n + 1) estas surjektion de la nombrebla aro Z × N ĝis la rationals Q .
#000071
Se estas nombrebla aro por ĉiu n en N tiam la unio de ĉiuj estas ankaŭ nombrebla.
#000072
Tio estas sekvo de la fakto ke por ĉiu n ekzistas surĵet gn :
N → kaj tial la funkcio
#000073
donite per G ( n, m
gn ( m) estas surjektion.
Ekde N × N estas nombrebla, la Konsekvenco implicas ke la unio estas nombrebla.
Ni utiligas la aksiomon de nombrebla elekto en tiu pruvo por elekti por ĉiu n en N surjektion gn de la ne-malplena kolekto de surjektions de N ĝis .
#000074
Topologia pruvo por la unkountabileco da la realaj nombroj estas priskribita ĉe finhava intersekciĝposedaĵo.
#000075
Minimuma modelo de aroteorio estas nombrebla
#000076
Se ekzistas aro kiu estas norma modelo (vidu interna modelo) de ZFC-aroteorio, tiam ekzistas minimuma norma modelo ( vidu Konstrueblan universon).
La Löwenheim-Skolem-teoremo povas esti utiligita por montri ke tiu minimuma modelo estas nombrebla.
La fakto ke la nocio de "uncountabileco" sonas racie eĉ en tiu modelo, kaj aparte ke tiu modelo M enhavas elementojn kiuj estas:
#000077
subaroj de M, tial nombrebla,
sed nenombrebla de la perspektivo de M,
#000078
estis vidita kiel paradoksa en la fruaj tagoj da aroteorio, vidas la paradokson de Skolem.
#000079
La minimuma norma modelo inkludas ĉiujn algebrajn nombrojn kaj ĉiujn efike komputeblajn transcendajn nombrojn, same kiel multaijn aliajn specojn de nombroj.
#000080
Nombreblaj aroj povas esti totale ordonitaj laŭ diversaj manieroj, ekz.:
#000081
Nu ordoj (vidu ankaŭ numeron):La kutima ordo de naturaj nombroj (0, 1, 2, 3, 4, 5, ...
Aliaj ( ne bone ordoj):La kutima ordo de entjeroj ( ...
La kutima ordo de raciaj nombroj (ne Povas esti eksplicite skribita kiel ordigita listo!
#000082
La kutima ordo de entjeroj ( ...
La kutima ordo de raciaj nombroj (ne Povas esti eksplicite skribita kiel ordigita listo!
#000083
Notu ke en ambaŭ ekzemploj de bone ordoj ĉi tie, ĉiu subaro havas malplej elementon;
kaj en ambaŭ ekzemploj de ne-putaj ordoj, kelkaj subaroj ne havas malplej elementon.
Tio estas la esenca difino kiu determinas ĉu tuteca ordo ankaŭ estas putordo.
#000084
, it makes no difference whether one considers 0 a natura nombro or not.
En iu kazo, tiu artikolo sekvas ISO 31-11 kaj la normkongreson en matematika logiko, kiu prenas 0 kiel natura nombro.
^ Stillwell, John C. (2010), Roads to Infinity: The Mathematics of Truth and Proof, CRC Press, p. 10, ISBN 9781439865507, Cantor's discovery of uncountable sets in 1874 was one of the most unexpected events in the history of mathematics. Before 1874, infinity was not even considered a legitimate mathematical subject by most people, so the need to distinguish between countable and uncountable infinities could not have been imagined.
#000086
, " Nombrebla aro ", MathWorld .
#000088
La leĝoj de De Morgan
#000089
Povo de aro ( granda)
#000090
En matematiko, kalkulebla aro estas aro kun la sama kardinala nombro (povo de aro aŭ kvanto de eroj) kiel iu subaro de la aro de ĉ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 finiĝi, tamen ĉiu ero de la aro estos asociita kun natura nombro.
#000091
Iuj aŭtoroj uzas la terminon kalkulebla aro por aro kun la sama kardinalo kiel la aro de ĉiuj naturaj nombroj. La diferenco inter la du difinoj estas ke sub la unua, finiaj aroj estas ankaŭ konsiderataj kiel kalkuleblaj, dum sub la lasta difino, ili estas ne konsiderataj kiel kalkuleblaj. Por forigi ĉi tiun multvalorecon, la termino maksimume kalkulebla estas iam uzita por la unua komprenaĵo, kaj kalkuleble malfinia por la lasta.
#000092
La kardinala nombro de kalkuleble malfinia aro estas skribata kiel (la komenca alef-nombro) aŭ (la komenca beth-nombro).
#000093
Aro S estas nomata kiel kalkulebla se ekzistas enĵeto
#000094
Se f estas ankaŭ surĵeto, tial farante f ensurĵeton, do S estas kalkuleble malfinia.
#000095
La bezonata koncepto estas ensurĵeto (reciproke unuvalora surĵeto). Ekzemple, rilato
#000096
Laŭ difino, du aroj estas de la sama amplekso se kaj nur se ekzistas reciproke unuvalora surĵeto inter ili. Por ĉiuj finiaj aroj ĉi tio donas la kutiman difinon de la sameco de amplekso. Por la amplekso de malfiniaj aroj, la aferoj estas jenaj.
#000097
Ĉiu ero de A estas parita for kun precize unu ero de B, kaj reen. De ĉi tie ili havas la saman amplekson, kaj pro tio B estas kalkuleble malfinia. Ĉ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.
#000098
La aro de ĉiuj ordigitaj duopoj de naturaj nombroj estas kalkuleble malfinia, ĉar ekzistas reciproke unuvalora surĵeto inter ĝi kaj aro de ĉiuj naturaj nombroj:
#000099
Ĉi tiu reciproke unuvalora surĵeto estos kovras ĉiujn ĉi tiajn ordigitajn duopojn.
#000100
Ĉiu subaro de kalkulebla aro estas kalkulebla. Ĉiu malfinia subaro de kalkuleble malfinia aro estas kalkulebla malfinio.
#000101
Ekzemple, la aro de primoj estas kalkulebla, per surĵeto de la n-a primo al n:
#000102
Per difino aro S estas kalkulebla se ekzistas enĵeto
#000103
Jena teoremo donas ekvivalentajn formulaĵojn de la difino:
#000104
1. S estas kalkulebla, kio estas ke ekzistas enĵeto
2. S estas malplena aŭ ekzistas surĵeto
3. S estas finia aŭ tie ekzistas reciproke unuvalora surĵeto
#000106
Kelkaj normaj propraĵoj sekvas facile el ĉi tiu teoremo. N en la teoremo povas esti anstataŭita kun ĉiu kalkuleble malfinia aro. Aparta estas jena korolario.
#000107
1. Se funkcio f : S → T estas enĵeta kaj T estas kalkulebla do S estas kalkulebla.
2. Se funkcio g : S → T estas surĵeta kaj S estas kalkulebla do T estas kalkulebla.
#000109
Pruvo: Por (1) observu ke se T estas kalkulebla ekzistas enĵeto h : T → N . Tiam se la funkcio f : S → T estas enĵeta do la komponaĵo estas enĵeta, do S estas kalkulebla.
#000110
Por (2) observu ke se S estas kalkulebla estas surĵeto h : N → S. Tiam se g : S → T estas surĵeta do la komponaĵo estas surĵeta, do T estas kalkulebla.
#000111
Teoremo: Ĉiu subaro de kalkulebla aro estas kalkulebla.
#000112
Teoremo: La kartezia produto de du kalkuleblaj aroj A kaj B estas kalkulebla. Plu, la kartezia produto de ĉiu finia kolekto de kalkuleblaj aroj estas kalkulebla.
#000114
Pruvo: N×N estas kalkulebla ĉar la funkcio f: N×N → N donita per f(m, n) = 2m3n estas enĵ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 ĉiuj du kalkuleblaj aroj estas kalkulebla. Ĉi tio sekvas ĉar se A kaj B estas kalkuleblaj estas surĵetoj f : N → A kaj g : N → B. Do f×g: N×N → A×B estas surĵeto de la kalkulebla aro N×N al la aro A×B kaj la korolario implicas ke A×B estas kalkulebla. Ĉi tiu rezulto ĝeneraligatas al la kartezia produto de ĉiu finia kolekto de kalkuleblaj aroj kaj la pruvo estas per indukto sur la kvanto de aroj en la kolekto.
#000115
Teoremo: La entjeroj Z estas kalkuleblaj kaj la racionalaj nombroj Q estas kalkuleblaj.
#000116
Pruvo: La entjeroj Z estas kalkuleblaj ĉar la funkcio f : Z → N donita per f(n) = 2n se n estas nenegativa kaj f(n) = 3-n se n estas negativa estas enĵeto. La racionalaj nombroj Q estas kalkuleblaj ĉar la funkcio g: Z×N → Q donita per g(m, n) = m/(n+1) estas surĵeto de la kalkulebla aro Z×N al la racionaloj Q. Povas esti konstruita ankaŭ implica ensurĵeto inter N kaj Q:
#000117
Per simila evoluo, la aro de ĉiuj algebraj nombroj estas kalkulebla, kaj la aro de ĉiuj difineblaj nombroj estas kalkulebla.
#000118
Teoremo: (Alprenanta la aksiomon de kalkulebla elekto) La unio de kalkuleble multaj kalkuleblaj aroj estas kalkulebla. Formale, se An estas kalkulebla aro por ĉiu n en N tiam estas kalkulebla.
#000119
Pruvo: Ĉi tio estas konsekvenco de tio ke por ĉiu n ekzistas surĵeto kaj de ĉi tie la funkcio
#000120
donita per G(n, m) = gn(m) estas surĵeto. Pro tio ke N×N estas kalkulebla la korolario implicas ke estas kalkulebla. Oni uzas la aksiomon de kalkulebla elekto en ĉi tiu pruvo por preni por ĉiu n en N surĵeton gn el la ne-malplena kolekto de surĵetoj de N al An.
#000121
Teoremo: La aro de ĉiuj finio-longaj vicoj de naturaj nombroj estas kalkulebla.
#000122
Ĉ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. Ĉiu el ili estas kalkulebla aro ĉ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 antaŭa teoremo.
#000123
Teoremo: La aro de ĉiuj finiaj subaroj de la naturaj nombroj estas kalkulebla.
#000124
Se estas finia subaro, oni povas ordigi la eroj de ĝi en finian vicon. Estas nur kalkuleble multaj finiaj vicoj, tiel ankaŭ estas nur kalkuleble multaj finiaj subaroj.
#000125
Teoremo de Cantor: Se A estas aro kaj P(A) estas ĝia aro de ĉiuj subaroj, do ne ekzistas surĵeto de A al P(A). Senpera konsekvenco de ĉi tio kaj de la baza teoremo pli supre estas:
#000126
Teoremo: La aro P(N) ne estas kalkulebla; kio estas ĝi estas nekalkulebla.
#000127
Por ellaborado de ĉi tiu rezulto vidu en diagonala argumento de Cantor.
#000128
La aro de reelaj nombroj estas nekalkulebla (vidu ankaŭ en unua nekalkulebleca pruvo de Cantor), kaj nekalkulebla estas la aro de ĉiuj malfiniaj vicoj de naturaj nombroj. Topologia pruvo por la nekalkulebleco de la reelaj nombroj estas priskribita en finia intersekca propraĵo.
#000129
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 Löwenheim-Skolem povas esti uzata por montri ke ĉi tiu minimuma modelo estas kalkulebla. Tio ke la komprenaĵo de nekalkulebleco havas senco eĉ en ĉi tiu modelo, kaj aparte ke ĉi tiu modelo M enhavas erojn kiu estas samtempe
#000130
subaroj de M, de ĉi tie kalkuleblaj,
sed nekalkuleblaj de la punkto de vido de M,
#000131
estis vidita kiel paradoksa en la fruaj tagoj de aroteorio, vidu en paradokso de Skolem.
#000132
La minimuma norma modelo inkluzivas ĉiuj algebrajn nombrojn kaj ĉiujn efike komputeblajn transcendajn nombrojn, kaj ankaŭ multajn aliajn specojn de nombroj.
#000133
Kalkuleblaj aroj povas esti tutece ordigitaj diversmaniere, ekzemple:
#000134
la kutima ordo de naturaj nombroj
#000136
la kutima ordo de entjeroj
la kutima ordo de racionalaj nombroj
#000137