Grunnlagsstoff

Tre måter å bevise en påstand på

Se på påstanden «hvis $n^2$ er et partall, så er $n$ et partall». Et direkte bevis starter fra det du vet er sant og regner seg fram til konklusjonen — men her er det ikke opplagt hvordan du kommer direkte fra «$n^2$ er partall» til noe om $n$ selv.

Da er kontrapositivt bevis bedre egnet: i stedet for å vise $A\Rightarrow B$, viser du $\neg B\Rightarrow \neg A$, altså ƒkontrapositivt bevis. Anta at $n$ er et oddetall, $n=2k+1$. Da er $n^2=4k^2+4k+1=2(2k^2+2k)+1$, som selv er et oddetall. Vi har vist $\neg B\Rightarrow \neg A$, og dermed gjelder $A\Rightarrow B$.

Den tredje veien er bevis ved motsigelse: anta at påstanden er feil, og vis at antagelsen fører til noe umulig. Dette blir kapittelets viktigste verktøy — både Cantors argument om at de reelle tallene ikke er tellbare og det klassiske beviset for at det finnes uendelig mange primtall, er motsigelsesbevis. Alle tre teknikkene beviser nøyaktig samme type påstand, en implikasjon $A\Rightarrow B$ — forskjellen ligger bare i hvilken vei du angriper den fra.

Mengder og mengdeoperasjoner

En mengde er en samling objekter. mengdeoperasjoner lar deg bygge nye mengder av gamle: unionen $A\cup B$ tar med alt som er i minst én av mengdene, snittet ƒmengdesnitt tar bare med det som er i begge, differansen $A\setminus B$ fjerner $B$-elementene fra $A$, og det kartesiske produktet $A\times B$ danner alle par $(a,b)$ med $a\in A$ og $b\in B$.

Eksempel: la $A=\{1,2,3\}$ og $B=\{2,3,4\}$. Da er $A\cup B=\{1,2,3,4\}$, $A\cap B=\{2,3\}$, $A\setminus B=\{1\}$, og $A\times B$ har 9 par, ett for hver kombinasjon av et element fra $A$ og et fra $B$. Legg merke til at $A\setminus B$ og $B\setminus A$ sjelden er like — her er $B\setminus A=\{4\}$, ikke $\{1\}$. Delmengde-symbolet $\subseteq$ sier at hvert element i den ene mengden også er med i den andre: $A\subseteq C$ betyr at absolutt alt i $A$ finnes i $C$, og $A$ kan godt være lik $C$.

Supremum, infimum og typer av mengder

Ta mengden $(0,1)$ — alle reelle tall strengt mellom $0$ og $1$. Den har verken et største eller et minste element: uansett hvor nær $1$ du kommer, finnes det et tall til som er enda nærmere. Likevel har mengden en klar øvre grense: $1$. Vi kaller $1$ for supremum til $(0,1)$ — den minste øvre skranken, tallet som er $\ge$ alle elementene og som ikke kan byttes ut med noe mindre uten å miste den egenskapen. Tilsvarende er infimum til $(0,1)$ lik $0$. For den lukkede mengden $[0,1]$ er sup og inf de samme to tallene, men nå faktisk med i mengden — den har både et største og et minste element.

Rundt et punkt $a$ kan vi definere en omegn: et lite åpent intervall $(a-\epsilon ,a+\epsilon )$. Med det begrepet på plass kan vi klassifisere mengder som åpen og lukket mengde: en mengde er åpen hvis hvert punkt i den har en omegn som ligger helt inni mengden, og lukket hvis den inneholder alle sine opphopningspunkter — punkter der enhver omegn treffer uendelig mange av mengdens elementer. $(0,1)$ er åpen, $[0,1]$ er lukket, og $[0,1)$ er verken åpen eller lukket.

Et beslektet begrep er det isolerte punktet: et punkt som er med i mengden, men som har en omegn uten andre punkter fra mengden i seg. Mengden $\{1,2,3\}$ består utelukkende av isolerte punkter — hvert tall står alene, med god avstand til naboene. Sammenlign med $(0,1)$: der er hvert eneste punkt et opphopningspunkt, fordi du uansett hvor liten omegn du velger, alltid finner flere punkter fra mengden inni den. Denne sondringen mellom «tett pakket» og «spredt» blir viktig senere når vi skal snakke om kontinuitet og grenseverdier.

Tallmengder og tellbarhet

Tallmengdene er nøstet i hverandre: $\mathbb{N}\subseteq \mathbb{Z}\subseteq \mathbb{Q}\subseteq \mathbb{R}$ — naturlige tall er hele tall er brøker er reelle tall. Et naturlig spørsmål er om disse mengdene er «like store» selv om de alle er uendelige. Svaret er overraskende: nei.

$\mathbb{Q}$ er tellbar mengde — du kan faktisk liste opp ALLE brøker i én uendelig rekke, for eksempel ved å gruppere dem etter summen av absoluttverdien til teller og nevner og telle gjennom hver gruppe. Gruppe 2 ($\text{sum}=2$) inneholder bare $\frac{1}{1}$. Gruppe 3 ($\text{sum}=3$) inneholder $\frac{1}{2}$ og $\frac{2}{1}$. Gruppe 4 ($\text{sum}=4$) inneholder $\frac{1}{3}$, $\frac{2}{2}=1$ og $\frac{3}{1}$. Hver gruppe er endelig, det finnes uendelig mange grupper, og listen du får ved å gå gjennom gruppe etter gruppe treffer til slutt hver eneste brøk. Siden hver brøk til slutt dukker opp på en bestemt plass i lista, er $\mathbb{Q}$ tellbar, akkurat som $\mathbb{N}$ — selv om $\mathbb{Q}$ «virker» mye tettere befolket.

$\mathbb{R}$ er det ikke. Beviset er cantors diagonalargument, et motsigelsesbevis av nøyaktig den typen vi innførte innledningsvis. Anta — for motsigelse — at du HAR klart å lage en fullstendig liste over alle reelle tall mellom $0$ og $1$: $r_1,r_2,r_3,\dots$. Bygg nå et nytt tall $d$ ved å velge desimal nummer $n$ i $d$ ulikt desimal nummer $n$ i tallet $r_n$, for hver $n$. Da avviker $d$ fra $r_1$ i minst én desimal, fra $r_2$ i minst én desimal, og så videre — $d$ kan ikke være lik noen av tallene på listen. Men $d$ er selv et tall mellom $0$ og $1$, så det skulle stått på listen. Motsigelse. Konklusjonen er at ingen liste kan romme alle reelle tall: $\mathbb{R}$ er ikke tellbar, og dermed en «større» uendelighet enn $\mathbb{N}$.

Induksjonsprinsippet

induksjonsprinsippet beviser en påstand $P(n)$ for ALLE naturlige tall $n$ på én gang, uten å sjekke hvert tall for seg. Prinsippet er ƒfullstendig induksjon: vis basissteget $P(1)$, vis induksjonssteget $P(k)\Rightarrow P(k+1)$ for en vilkårlig $k$, og konkluder at $P(n)$ gjelder for alle $n\ge 1$. Tenk på det som dominobrikker — faller den første, og velter hver brikke garantert den neste, faller de alle.

Klassisk eksempel: påstanden $P(n)$ er «$1+2+\cdots +n=\frac{n(n+1)}{2}$». Basissteg: $P(1)$ sier $1=\frac{1\cdot 2}{2}=1$, sant. Induksjonssteg: anta $P(k)$, altså $1+2+\cdots +k=\frac{k(k+1)}{2}$. Legg til $(k+1)$ på begge sider: $1+2+\cdots +k+(k+1)=\frac{k(k+1)}{2}+(k+1)=(k+1)\left(\frac{k}{2}+1\right)=\frac{(k+1)(k+2)}{2}$. Det er nøyaktig $P(k+1)$-formelen med $n=k+1$ satt inn. Siden basissteget holder og induksjonssteget alltid fører fra $k$ til $k+1$, holder formelen for alle $n\ge 1$.

Motsigelsesbevis og induksjon møtes i et av matematikkens eldste resultater: Euklids bevis for at det finnes uendelig mange primtall. Anta — for motsigelse — at $2,3,5,\dots ,P$ er ALLE primtallene som finnes. La $T=(2\cdot 3\cdot 5\cdots P)+1$. Enten er $T$ selv et primtall — men da er $T$ et primtall større enn $P$, i strid med antagelsen om at $P$ var størst. Eller $T$ har en primtallsfaktor $q$; men $q$ kan ikke være noen av $2,3,\dots ,P$, for divisjon av $T$ med hvert av disse gir rest $1$. Uansett hvilket alternativ, sitter vi igjen med en primtallsfaktor som ikke sto på listen — motsigelse. Det finnes uendelig mange primtall.

Sum-notasjon

Når du skal skrive en lang sum kompakt, bruker du $\Sigma$. Uttrykket ƒsum-notasjon, eksempel betyr: sett $k=3$, $k=4$, $k=5$ og $k=6$ inn i $4^k$, og legg sammen resultatene. Bokstaven under $\Sigma$ er startverdien til indeksen, bokstaven over er sluttverdien, og uttrykket til høyre for $\Sigma$ regnes ut for hver verdi av $k$ og summeres. Denne notasjonen ligger under overflaten i både induksjonsformlene i forrige avsnitt og binomialteoremet i neste.

Kombinatorikk og binomialteoremet

Hvor mange måter kan du stille opp 5 personer i en kø på? Første plass har 5 kandidater, andre plass 4, og så videre — $5\cdot 4\cdot 3\cdot 2\cdot 1=5!=120$ permutasjoner. Hvor mange måter kan du derimot VELGE 2 av de 5 personene til et utvalg, uten å bry deg om rekkefølge? Det tallet er en binomialkoeffisient: $C(5,2)=\frac{5!}{2!\cdot 3!}=10$.

Binomialkoeffisientene dukker opp igjen når du utvider en potens av en to-ledds-sum: ƒbinomialteoremet. For eksempel er $(a+b{)}^3=a^3+3a^{2}b+3a{b}^2+b^3$, og koeffisientene $1,3,3,1$ er nettopp $C(3,0)$, $C(3,1)$, $C(3,2)$ og $C(3,3)$. Det samme tallet $C(n,i)$ er også antall delmengder med akkurat $i$ elementer i en mengde med $n$ elementer. Ta $A=\{x,y,z\}$: den har $C(3,0)=1$ delmengde med $0$ elementer (den tomme mengden), $C(3,1)=3$ delmengder med $1$ element $(\{x\},\{y\},\{z\})$, $C(3,2)=3$ delmengder med $2$ elementer $(\{x,y\},\{x,z\},\{y,z\})$, og $C(3,3)=1$ delmengde med alle tre. Summerer du over alle $i$, teller du hver delmengde nøyaktig én gang — enten den er med eller ikke er med hvert element — og totalt blir det $1+3+3+1=8=2^3$ delmengder, akkurat som ƒantall delmengder sier.

Analytisk geometri

Til slutt litt verktøy for planet. En rett linje har stigningstall $a=\frac{y_2-y_1}{x_2-x_1}$ mellom to punkter, og likningen $y=ax+b$. Stigningstallet forteller hvor mye $y$ øker per skritt i $x$-retning: $a=2$ betyr at linjen stiger 2 enheter for hver enhet du beveger deg til høyre. To linjer er parallelle nøyaktig når de har samme stigningstall, og står normalt på hverandre når produktet av stigningstallene er $-1$.

Avstanden mellom to punkter er ƒavstand mellom punkter — Pythagoras satt på koordinater: differansen i $x$-retning og differansen i $y$-retning er katetene i en rettvinklet trekant, og avstanden er hypotenusen. En sirkel med sentrum $(x_0,y_0)$ og radius $r$ har likningen ƒsirkellikning — den samler nøyaktig alle punkter som ligger $r$ unna sentrum, og er faktisk avstandsformelen satt lik en konstant $r$. Disse tre verktøyene — linjer, avstand og sirkler — går igjen gjennom resten av boken, blant annet når vi senere skal beskrive kurver og flater i flere dimensjoner.