Kjapt bevis

[krje1980]

Hei.

Gitt oppgaven:

Prove that the set of all rational numbers, [tex]\mathbb{Q}[/tex], is countable.


Vil dette da være en mulig løsning? (Jeg er redd jeg har gjort det litt for enkelt):


Gitt settet [tex]\mathbb{Q}[/tex] som består av alle rasjonelle tall. Hvert element i dette settet kan skrives som et ordnet par [tex](a, b)[/tex] ettersom hvert element er på formen [tex]\frac{a}{b}[/tex]. Ettersom elementene [tex]a[/tex] og [tex]b[/tex] tilhører settet med heltall, [tex]\mathbb{Z}[/tex], og vi vet at dette settet er tellbart (countable), vil alle elementene i settet [tex]\mathbb{Q}[/tex] bestå av en union av to elementer fra det tellbare settet [tex]\mathbb{Z}[/tex]. Av dette følger det at også [tex]\mathbb{Q}[/tex] må være tellbart.

(Her kan jeg gjerne også referere til Cantors diagonale prosess, men er dette nødvendig?)


Setter stor pris på kommentarer/innspill.

[Integralen]

http://www2.fiu.edu/~storferr/rat.num.ctble%5B1%5D.pdf

[krje1980]

Hei.

Kikket litt på linken, men når jeg innså at det var hele beviset, så lukket jeg det . Har lyst til å prøve litt selv før jeg kikker på hvordan andre har gjort det.

[Charlatan]

Det er riktig, men det er også viktig å påpeke at ethvert rasjonalt tall kan skrives som a/b på en unik måte (f.eks den reduserte formen).

Cantor's diagonalargument har lite å gjøre med dette, da det er hva som viser at de reelle tallene ikke er tellbare.

[espen180]

Tror du er på god vei. Et teorem som kan hjelpe deg er at for to mengder gjelder [tex]|A|\geq |B|[/tex] hvis og bare hvis det finnes en injektiv funksjon fra [tex]B[/tex] til [tex]A[/tex].

[krje1980]

Det er riktig, men det er også viktig å påpeke at ethvert rasjonalt tall kan skrives som a/b på en unik måte (f.eks den reduserte formen).

Cantor's diagonalargument har lite å gjøre med dette, da det er hva som viser at de reelle tallene ikke er tellbare.

Takk skal du ha.

Litt merkelig at man ikke kan bruke Cantor. Jeg har nemlig sett noen forelesningsvideoer i reell analyse fra en professor i USA; og han bruker Cantor til å bevise at Q er tellbart. Dette kan du se på:

http://www.youtube.com/watch?v=mciBPGCv ... grec_index

Fra ca 54 minutter.

Jeg hadde imidlertid lyst til å prøve å bevsie dette på min egen måte .

[krje1980]

Tror du er på god vei. Et teorem som kan hjelpe deg er at for to mengder gjelder [tex]|A|\geq |B|[/tex] hvis og bare hvis det finnes en injektiv funksjon fra [tex]B[/tex] til [tex]A[/tex].

Takk skal du ha.

Jeg har sett i læreboken at det er lett å finne en injektiv funksjon fra N til Z. Og siden elementene i Q består av elementene i Z, så følger vel at Q også må være tellbart.

Den injektive funksjonen er forøvrig at:

[tex]f(n) = \frac{n}{2}[/tex] når [tex]n[/tex] er partall, og:

[tex]f(n) = - \frac{n - 1}{2}[/tex] når [tex]n[/tex] er oddetall.

Her tar vi utgangspunkt i at settet for [tex]\mathbb{Z}[/tex] skrives som:

{0, -1, 1, -2, 2, . ..}.

[Charlatan]

Forresten, du mener vel sannsynligvis at parene er medlemmer av Z * Z (kartesisk produkt) og ikke en union.

Hvis du søker på cantor's diagonalargument så kan du se at det handler om å vise at de reelle tallene ikke er tellbare ved å vise at i enhver liste av reelle tall finnes et reellt tall som ikke er med i listen.

Hvis du vil ha en mer utfordrende oppgave foreslår jeg disse:

En tellbar union av tellbare mengder er tellbar (mengdene trenger ikke være disjunkte).

Et endelig kartesisk produkt av tellbare mengder (som f.eks Z * Z * Q) er tellbart.

[krje1980]

Ja, jeg skulle selvsagt ha skrevet kartesisk produkt opprinnelig! Når det gjelder Cantor, så har jeg sett denne bli brukt både til det du beskriver (å bevise at [tex]\mathbb{R}[/tex] ikke er tellbar), men også at f.eks. [tex]\mathbb{Q}[/tex] er det.

Jeg skal se på oppgavene dine i løpet av uken. Har brukt tiden mest til å lese og se på forelesningsvideoer de siste par dagene. I morgen kveld har jeg tenkt å gå løs på oppgaver.