Matematik

Forklaring til bevis "analyse 2"

27. august 2017 af Stats - Niveau: Universitet/Videregående

Sætning 2.7 (Cantor-Bernstein)
Lad X, Y være to mængder. Hvis både #X ≤ Y og #Y ≤ X, så er #X = #Y

Bevis:

Ved antagelse,

#X ≤ #Y ⇔ der eksistere en injektion f:X→Y
#Y ≤ #X ⇔ Der eksistere en injektion g:Y→X

For at bevise #X = #Y må vi konstruere en bijektion h:X→Y.

Step 1: Uden tab af generalitet må vi antage at Y⊂X. Faktisk, siden g:Y→g(Y) er bijektiv, så ved vi #Y = #g(Y) og det er tilstrækkeligt at vise #g(X) = #X. Da g(Y)⊂X kan vi simplificere tingene og identificere g(Y) med Y, f.eks antag at g = id eller, ækvivalent, Y⊂X

Step 2: Lad Y⊂X og g = id. Rekursivt kan vi definere

X₀:= X ,..., X_i+1 := f(X_i); Y₀ := Y ,..., Y_i+1 := f(Y_i)

Som sædvanligt, skriver vi fⁱ := f _^o f _^o ... _^o f (i gange) og f⁰ := id. Da har vi

$\begin{matrix} f^{i+1}(X) & = & f^i(f(X)) & \overset{f(X)\subset Y}{\subset} & f^i(Y) & \overset{Y\subset X}{\subset} & f^i(X)\\ \parallel & & & & \parallel & & \parallel\\ X_{i+1} & & \subset & & Y_i & \subset & X_i \end{matrix}$

og vi kan definere afbildningen h:X→Y ved

$h(x)=\left \{ \begin{matrix} f(x) & \textup{hvis }x\in X_i\backslash Y_i \textup{ for nogle } i\in\mathbb{N}_0\\ x & \textup{hvis }x\notin\bigcup_{i\in\mathbb{N}_0} X_i\backslash Y_i \end{matrix} \right .$

Step 3: Afbildningen h er surjektiv: h(X) = Y. Faktisk, så har vi ved definition at

$\\ h(X)=\bigcup_{i\in\mathbb{N}_0}f(X_i\backslash Y_i)\cup\left ( \bigcup_{i\in\mathbb{N}_0}X_i\backslash Y_i \right )^c\\ \overset{2.2}{=}\bigcup_{i\in\mathbb{N}_0}(f(X_i)\backslash f(Y_i))\cup\left ( X\backslash Y\cup\bigcup_{i\in\mathbb{N}_0}X_i\backslash Y_i \right )^c\\ =\underbrace{\bigcup_{i\in\mathbb{N}_0}(X_{i+1}\backslash Y_{i+1})}_{=:A}\cup\left [ (X\backslash Y)^c\cap \left ( \bigcup_{i\in\mathbb{N}_0}X_{i+1}\backslash Y_{i+1} \right )^c \right ]\\ = A\cup[(X^c\cup Y)\cap A^c]=a\cup[Y\cap A^c]=Y\cap X=Y$

Vi har da anvendt at A = ∪_{i∈N_0} X_i+1\Y_i+1 ⊂ ∪_{i∈N_0} X_i+1 ⊂ X₁ = f(X) ⊂ Y

Step 4: Afbildningen af h er injektiv. For at se dette, lad x,x'∈X og h(x) = h(x'). Vi har nu fire muligheder:

(a) x,x'∈X_i\Y_i for nogle i∈N₀. Da har vi f(x) = h(x) = h(x') = f(x') sådan at x = x' siden f er injektiv.

(b) x,x'∉∪_{i∈N_0} X_i\Y_i. Da er x = h(x) = h(x') = x'

$\\ x' = f(x)\in f(X_i\backslash Y_i)\overset{2.2}{=}f(X_i)\backslash f(Y_i) = X_{i+1}\backslash Y_{i+1}$

Hvilket er umuligt da (c) ikke ville kunne forekomme.

(d) x'∈ X_i\Y_i for nogle i∈N₀ og x∉X_k\Y_k for nogle k∈N₀. Dette er analogt til (c)

-----------

Spørgsmål ang. step 1:
• Hvorfor antager vi at Y⊂X?
• Hvordan kan man vide at g : Y→g(Y) er en bijektion?
@ #Y = #g(Y) følger af definition, om at hvis en afbildning er bijektiv så har de samme kardinalitet.
• Hvorfor er det tilstrækkeligt at vise #g(Y) = #X?
@ g(Y) ⊂X giver god mening.
• Hvordan kan man simplificere tingene og identificere g(Y) med Y, og derefter antage at g = id (dermed ækvivalent Y⊂X) på baggrund af g(Y) ⊂X?

Jeg stiller lidt flere spørgsmål efter jeg har fået svar på ovenstående

Svar #1
27. august 2017 af Stats

Ok... Det første punkt af spørgsmål giver god mening - efter at jeg har tegnet både g og f med mængderne X og Y

- - -

Mvh Dennis Svensson

Svar #2
27. august 2017 af Stats

Ok... bijektionen giver også god mening, eftersom f : X→Y og g : Y→X er to funktioner som er injektive...

Derfor:
Hvis f er en injektion som sender en mængde X over i Y hvor f(x) = f(x') _{^{(= y = y')}} ⇒ x = x'
Hvis g er en injektion som sender en mængde Y over i X hvor g(y) = g(y') ⇒ y = y'

Så må der også gælde at g : Y→g(Y) er en bijektion og derfor ved vi at #Y = #g(Y) (følger af definitionen af at hvis der eksistere en bijektion f:X→Y, så har mængderne X, Y samme kardinalitet; #X = #Y)

Men da er det vel også åbentlyst at #Y = #X ?

- - -

Mvh Dennis Svensson

Svar #3
27. august 2017 af Stats

Ok... Fandt ud af den anden også... mængden g(Y) behøver ikke at være den samme mængde som X... Men man ved at g(Y)⊂X

- - -

Mvh Dennis Svensson

Svar #4
27. august 2017 af Stats

Den sidste:

Da g(Y)⊂X kan vi simplificere tingene og identificere g(Y) med Y, f.eks forestil dig at g = id eller, ækvivalent, Y⊂X...

Denne forstår jeg ikke..

- - -

Mvh Dennis Svensson

Skriv et svar til: Forklaring til bevis "analyse 2"

Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk? Klik her for at oprette en bruger.