Q = tællelig mængde?

Vis at der findes en bijektion mellem Q og N.

Vi har ikke beskæftiget os med bijektion, men hvad går det ud på?

#:
En afbildning er bijektiv, såfremt den både er surjektiv (på) og injektiv (én-til-én).


For en surjektiv afbildning f:A-->B gælder der, at for alle x,y E A, er

x != y => f(x) != f(y)

og tilsvarende

f(x) = f(y) => x = y


En afbildning f:A-->B siges at være surjektiv, såfremt der

for alle y E B eksisterer et x E A, således at y = f(x).


Notation:
``x E A'' skal forstås som at ``x er element i mængden A''.

#3:
Rettelse: Indlægget er skrevet til #2, hvilket jeg ikke lige fik med.

#3
Det er nok nærmere en bijektion disse ækvivalnser gælder for.

#2
Udtrykt i daglig tale en er afbildning f:A->B surjektive hvis og kun hvis ethvert element i mængden B er billedet af mindst eet element i A. Det kan godt hænde, at samme element i B er billedet af flere elementer i A.

En afbilding f:A->B kaldes injektiv hvis og kun hvis ethvert element i B er billedet af højst eet element i A. Det kan godt hænde, at der findes elementer i B, der ikke er billedet af noget element i A.

Som Dominik rigtigt påpeger, kaldes en afbildning bijektiv såfremt den både er surjektiv og injektiv.

Sammenholdes de to definitioner ovenfor ser man, at en afbilding f:A->B er bijektiv hvis og kun hvis ethvert element i B er billedet af netop eet element i A. Som nævnt i #3 gælder derfor

x != y => f(x) != f(y)

og tilsvarende

f(x) = f(y) => x = y

Det ses altså, at hvis man kan redegøre for, at der findes en bijektion mellem to mængder, A og B, så har disse mængder samme kardinalitet.

Det er derfor et bevis for at Q er tælleligt uendelig kan føres ved at finde en bijektion mellem Q og N. N er nemlig tælleligt uendelig per definition.

Tak for hjælpen.

Har lige et enkelt spørgsmål..

x!=y => f(x)!=f(y)

Hvordan skal "!" forståes?

"!=" betyder 'forskellig fra' eller 'ikke lig med'.