Uppräkneliga mängder.

K.Ivanovitj skrev:

Hej

jag har kommit till en uppgift som handlar om ifall en mängd är uppräknelig eller inte och skulle behöva lite hjälp.

Uppgiften är:

Bevisa att skärningen av två uppräkneliga mängder är uppräknelig.

Det jag vet är att om en mängd är ändlig så är den uppräknelig samt om man kan mappa mängdens element en-mot-en, mot de naturliga talen.

I denna uppgift vet vi ju att vi har två mängder som uppfyller detta krav men hur ska man bevisa att skärningen också gör det?

Kanske inte ett bevis, men ett resonemang:

Antag motsatsen, dvs antag att det finns en icke uppräknelig mängd C som är sådan att C är skärningen mellan de uppräkneliga mängderna A och B.

Eftersom C är en delmängd av A (alla element som ingår i C ingår också i A) och eftersom C inte är uppräknelig, så skulle det innebära att mängden A inte är uppräknelig, vilket är en motsägelse.

Först en utläggning: Ett bra sätt att tänka på uppräkneliga (som betyder precis  samma sak som 1-till-1-mappning mot naturliga tal) är att det går att "räkna upp den", dvs säga alla element i mängden ett efter ett och veta att man får med alla. För de positiva rationella talen kan man då t.ex. använda metoden att för varje nämnare n räkna upp täljaren till n, och för varje kvot räkna upp inversen direkt efteråt (och inte räkna upp tal som redan räknats):

0/1, 1/1 || 1/2, 2/1 || 1/3, 3/1, 2/3, 3/2 || 1/4, 4/1, 3/4, 4/3 || ...

På så sätt vet vi att alla rationella tal kommer räknas upp, och eftersom det finns en sådan metod är de rationella talen uppräkneliga.

I ditt problem kan vi utnyttja att en sådan metod redan finns för båda dina mängder. Vi kan då helt enkelt använda den ena mängdens uppräkning, fast bara stryka alla tal som inte är med i den andra mängden.

Hej!

En delmängd till en uppräknelig mängd är en uppräknelig mängd. (Bevisa detta.)

Snittmängden $A \cap B$ är en delmängd till den uppräkneliga mängden $A$.

Om jag har förstått det rätt så har vi att eftersom A och B är båda uppräkneliga mängder så blir skärningen en delmängd $A\cap B$och då gäller att $A\cap B\subset A \&A\cap B\subset B$

Men hur ska man göra om man istället vill bevisa att det stämmer genom att ställa upp alla tal från exempelvis A och sedan stryka dom tal i B som inte är med i A? I denna uppgift har vi ju ingen information om vilka element som finns i mängden A eller B?

K.Ivanovitj skrev:

Om jag har förstått det rätt så har vi att eftersom A och B är båda uppräkneliga mängder så blir skärningen en delmängd $A\cap B$och då gäller att $A\cap B\subset A \&A\cap B\subset B$

Nej skärningen är en delmängd oavsett om A och B är uppräkneliga eller inte.

Men hur ska man göra om man istället vill bevisa att det stämmer genom att ställa upp alla tal från exempelvis A och sedan stryka dom tal i B som inte är med i A? I denna uppgift har vi ju ingen information om vilka element som finns i mängden A eller B?

Det här resonemanget är det nog bäst om haraldfreij utvecklar för jag är inte heller på det klara med exakt hur det visar önskat resultat.

Uppräkningen (1-1-mappningen mot N) fås genom att som element 1 ta det första elementet i A som är med i snittet (dvs också ligger i B), som element 2 ta det andra elementet i A som är med i snittet. Som du säger kan du förstås inte skriva ner vilka elementen är, eftersom du inte känner till A eller B (de kan ju vara vilka uppräkneliga mängder som helst), men det enda du behöver visa är att det _finns_ en sådan uppräkning, och det har vi bevisat att det finns nu eftersom vi har visat hur den kan se ut.

Notera att det här är ett specialfall av den mer generella princip som Albiki nämner, och som bevisas på precis samma sätt (vi använder ju aldrig i min diskussion att B också är uppräknelig)

Som jag har förstått det hittills så förstår jag det som att man kan uttrycka det som: 

Låt A och B vara två uppräkneliga mängder och låt delmängden T=$A\cap B$. 

Vi har då att T$\subset \left\{A\&B\right\}$

Delmängder till ändliga mängder är uppräkneliga så vi intresserar oss endast av fallet då A och B är oändliga mängder.

Elementen i A kan vi skriva ned i en ändlig lista A=$a_1,a_2,a_3...$ och B=$b_1,b_2,b_3...$

För att få fram listan av elementen i delmängden T kan vi då ta bort de element ifrån listan $a_1{a}_2{a}_3...$ som inte finns i T.

Sedan är jag väl inte helt med på hur man skriver ihop det riktigt eller om det räcker så.

Delmängder till ändliga mängder är uppräkneliga

Det är iofs sant, men väldigt svagt. Delmängder till uppräkneliga mängder är uppräkneliga, och delmängder till ändliga mängder är ändliga.  Men visst, poängen är riktig, för ändliga mängder är påståendet trivialt så vi kan fokusera på oändliga mängder.

Elementen i A kan vi skriva ned i en ändlig lista

Inte om A är oändlig. Då är listan oändlig (och blir därför svår att skriva ner :)). Men elementen kan räknas upp på ett ordnat sätt: A={a1,a2,...} och motsv för B. Och alltså kan vi konstruera en sådan uppräkning även för snittet, precis som du skriver, och alltså är snittet uppräkneligt.

Formellt hade jag nog skrivit typ såhär:

Snittet T av A och B är en delmängd till A. Om A är ändlig är även T ändlig, och därmed uppräknelig. Om A är oändlig finns en avbildning f från de naturliga talen till A. Låt g(i) vara det i:te minsta naturliga talet n för vilket f(n) ligger i T. Då kommer alla element i T, men inga andra, antas av f(g(i)), som därmed är en en-entydig avbildning av de naturliga talen på T. Om en sådan avbildning finns är T enligt definition uppräknelig. VSV.

Kan man bevisa genom ett exempel som att sätta A=$\mathrm{\mathbb{N}}=\left\{1,2,3,4....\right\}$B=$2\mathrm{\mathbb{N}}=\left\{2,4,6,8....\right\}$

då får vi $B\subset A$ och $C=A\cap B=B$ och C är då uppräknelig

K.Ivanovitj skrev:

Kan man bevisa genom ett exempel som att sätta A=$\mathrm{\mathbb{N}}=\left\{1,2,3,4....\right\}$B=$2\mathrm{\mathbb{N}}=\left\{2,4,6,8....\right\}$

då får vi $B\subset A$ och $C=A\cap B=B$ och C är då uppräknelig

 Det är ett exempel, inte ett bevis. Ett bevis skall gälla för alla uppräkneliga mängder, inte bara de du nämnde.

K.Ivanovitj skrev:

Kan man bevisa genom ett exempel som att sätta A=$\mathrm{\mathbb{N}}=\left\{1,2,3,4....\right\}$B=$2\mathrm{\mathbb{N}}=\left\{2,4,6,8....\right\}$

då får vi $B\subset A$ och $C=A\cap B=B$ och C är då uppräknelig

 Nej. Bara för att påståendet stämmer för just det exemplet så betyder inte det att påståendet gäller generellt

Ett exempel kan däremot användas för att motbevisa ett påstående, det kallas då ett motexempel.

K.Ivanovitj skrev:

Kan man bevisa genom ett exempel som att sätta A=$\mathrm{\mathbb{N}}=\left\{1,2,3,4....\right\}$B=$2\mathrm{\mathbb{N}}=\left\{2,4,6,8....\right\}$

då får vi $B\subset A$ och $C=A\cap B=B$ och C är då uppräknelig

 Nja, jag ser två problem med detta:

1. Du visar det för två mycket specifika mängder (de naturliga talen [nästan, du har glömt 0] och de positiva jämna talen). Bara för att det stämmer för dessa två mängder behöver det inte stämma för alla uppräkneliga mängder.
2. Du använder dig av det faktum att $B \subset A$ för att visa att $A \cap B$ är en uppräknelig mängd. Du skall visa att alla snitt av två uppräkneliga mängder är uppräkneliga, inte bara snitten där den ena mängden är en delmängd av den andra.