LEKTION 03-31

Definition 0.1. Låt A och B vara två mängder. En funktion från A till B är en regler som till \underline{varje element} a ∈ A ordnar \underline{precis ett element} f(a) = b ∈ B.

Vi använder den följande terminologi:

• f(a) kallas funktionens värde i a.

• A kallas den definitionsmängden.

• V_{f} = {b ∈ B|b = f(a) för något a ∈ A} ⊆ B kallas värdemängden.

• Γ_{f} = {(a, f(a)|a ∈ A} ⊂ A × B kallas grafen av f

Notera att om A, B är ändliga mängder, kan man bilda en bipartit graf G_{f} = (V, E) från f, genom att definera:

• V = V_{1} ∪ V_{2}, där V_{1} = A, V_{2} = D_{f}.

• E = {af(a)}. Så |E| = |Γ_{f}|.

Exempel

• Betrakta funktionen f : ℤ_{n} → ℤ_{n}, f([x]) = f([x + 1]).

– V_{f} = ℤ_{n}.

– Γ_{f} = {([n], [n + 1])} ⊂ ℤ_{n} × ℤ_{n}. Rita grafen!

• Reglen f(x) = y , där x^{2} + y^{2} = 0 inte definerar en funktion.

• Betrakta funktionen f : ℝ^{+} → ℝ defineras av f(x) = \sqrt{x}.

– V_{f} = \{y ∈ ℝ så att y = \sqrt{x} för någotx ∈ ℝ^{+}\} = ℝ^{+}.

– Γ_{f} = \{(x, \sqrt{x})\} ⊂ ℝ^{+} × ℝ^{+} är en kurva.

• Funktionen id_{A} : A → A, defineras av f(a) = a kallas identitets funktionen av A. – V_{id_{A}} = A

– Γ_{id_{A}} = {(a, a)} kallas diagonal av A × A.

Om |A| = n och |B| = m det finns m^{n} funktioner från A till B.

För att bilda en funktion f från A till B vi ska ordna precis ett element i B till varje element i A. Om A = {a_{1}, ..., a_{2}}, definerar f en sekvens (f(a_{1}), ..., f(a_{n})) ∈ B × ... × B (n gånger). Det betyder att det finns |B × ... × B| = m^{n} många funktioner.

Definition 0.2. Låt f : A → B och g : B → C vara funktioner. Den sammansatta funktionen är:

g ∘ f : A → C och defineras av (g ∘ f)(a) = g(f(a))

Notera att ordning är viktig. Betrakta funktioner:

e^{∗} : ℝ → ℝ, sin(∗) : ℝ → ℝ

Funktionen e^{∗} ∘ sin(∗) = e^{sin(∗)} : ℝ → ℝ har värde e^{sin(π)} = 1 i x = π, men funktionen sin(∗) ∘ e^{∗} = sin(e^{∗}) :: ℝ → ℝ har värde sin(e^{π}) ≠ 1 i x = π. Vi säger att två funktioner f, g : A → B är lika, f = g, om f(a) = g(a) för varje a ∈ A. Så

e^{∗} ∘ sin(∗) ≠ sin(∗) ∘ e^{∗}

Definition 0.3. Låt f : A → B vara en funktion. Den kallas injektiv om

f(a_{1}) = f(a_{2}) ⟹ a_{1} = a_{2}

Det betyder att för varje b ∈ B det finns högst en a ∈ A sådan att f(a) = b.

Exempel

• Funktionen f : ℝ → ℝ^{+} som defineras av f(x) = x^{2} är inte injectiv. Vi ser att f(2) = f(−2), men 2 ≠ −2.

• Funktionen f : ℝ → ℝ som defineras av f(x) = x + 1 är injektiv. Vi ser att

f(a) = f(b) ⟹ a + 1 = b + 1 ⟹ a = b. Låt f : A → B vara en injektiv funktion, där |A| = n och |B| = m. Enligt definition

man näste ha att:

f injective ⟹ n ≤ m

För att bilda en injektiva funktion fån A till B ska man välja n element i B, utan upprepning och med ordning. Så det finns \frac{m!}{(m−n)!} många injektiva funktioner från A till B.

Definition 0.4. En funktion f : A → B kallas surjektiv om D_{f} = B. Det betyder att varje element b ∈ B är värde av funktionen i någon a ∈ A. En funktion som är injektiv och surjectiv kallas bijektiv. Om f är bijektiv så är varje element b ∈ B värde av funktionen i precis en element a ∈ A.

Notera att om en function f : A → B, där |A| = n och |B| = m, är surjektive då är n ≥ m. Vi har att: Antalet surjektiva funktioner från A till B är:

∑_{k=0}^{m}(−1)^{k}\binom{m}{k}(m − k)^{n}

Vi ska visa denna formula bara för ett exempel:

Sätt A = {1, 2, 3, 4}, B = {b_{1}, b_{2}, b_{3}}, hur mäanga funktioner som är surjektiva kan man definera?

Vi har 4^{3} funktioner totalt. Om vi bestämmer antalet funktioner som inte är surjektiva kan vi dra det bort från4^{3} och få svaret. Antag att D_{f} ≠ {x, w, y, z} och sätt A_{i} = {f så att b_{i} ∉ D_{F} }. Antalet funktioner som inte är surjektiva är lika med |A_{1} ∪ A_{2} ∪ A_{3}|.

Enligt inklusions-eklusions principen är:

|A_{1} ∪ A_{2} ∪ A_{3}| = |A_{1}| + |A_{2}| + |A_{3}| − |A_{1} ∩ A_{2}| − |A_{1} ∩ A_{3}| − |A_{2} ∩ A_{3}| + |A_{2} ∩ A_{3} ∩ A_{3}|

Man kan se att |A_{i}| = (2)^{4} efetersom vi ska beräkna funktioner från A till B \ {b_{i}}. På samma sätt är |A_{i} ∩ A_{j}| = (1)^{4} och |A_{2} ∩ A_{3} ∩ A_{3}| = 0. Vi har alttså att:

|A_{1} ∪ A_{2} ∪ A_{3}| = 3(2)^{4} − 3(1)^{4} = \binom{3}{1}(m − 1)^{n} − \binom{3}{2}(m − 2)^{n}

och svaret är:

4^{3} − \binom{3}{1}(m − 1)^{n} − \binom{3}{2}(m − 2)^{n} = 4^{3} − \binom{3}{1}(2)^{4} − \binom{3}{2}(1)^{4}

Hur nånga bijektiva funktioner från A till B finns det? Om f : A → B är injektiv (bijektiv+surjektiv) då är

|A| = |B|

Antag att |A| = n. Varje permutation av elementen i A ger en bijektiv funktion. Det finns alltså n! injektiva funktioner från A till B.

Om |A| = n, |B| = m vi har att:

antalet funktioner från A till B  m^{n}
antalet injektiva funktioner från A till B \frac{m!}{(m−n)!}
antalet surjektiva funktioner från A till B ∑_{k=0}^{m}(−1)^{k}\binom{m}{k}(m − k)^{n}
antalet bijektiva funktioner från A till B  n!

Antag att funktionen f : A → B är injektiv då kan man definera en funktion f^{−1} : B → A genom

f^{−1}(b) = a där f(a) = b

Den kallas den inversa funktionen. Man ser att f ∘ f^{−1} = id_{B} och f^{−1} ∘ f = id_{A}

Ibland säger man att en funktion f : A → B är inverterbar, dvs att den har en invers funktion, om och endast om det finns en funktion g : B → A sådan att:

f ∘ g = id_{B} och g ∘ f = id_{A}

Exempel Vi har visat att funktionen f : ℤ → ℤ som defineras av f(x) = x + 1 är injektiv. Inversen defineras av f^{−1}(y) = x där f(x) = x + 1 = y. Så x = y − 1.

En funktion från A till B karaketerseras av grafen Γ_{f}, som är en delmängd av A × B där varje element är av formen (a, f(a)).

Vi ska generalisera definitionen av funktionen genom att betrakta varje delmängd.

Definition 0.5. En relation R mellan A och B är en delmängd av R ⊂ A × B. Ofta skriver man aRb för (a, b) ∈ R och a R̸b för (a, b) ∉ R. Om A = B relationen kallas en binär relation.

Exempel Betrakta mängden A = {2, 3, 4, 5, 6, 7}. Vi definera en relation genom

aRb ⟺ a|b

Vi ser att R = {(2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (5, 5), (6, 6), (7, 7)}.

Definition 0.6. Låt R vara en binär relation på A.

• Den kallas riflexiv om diagonalen Γ_{id_{A}} ⊂ R, dvs

aRa för alla a ∈ A

• Den kallas symmetrisk om

aRb ⟹ bRa

• Den kallas antisymmetrisk om

aRb och bRa ⟹ a = b

• Den kallas transitiv om

aRb och bRc ⟹ aRc

• Den kallas en partiell ordning om den är reflexiv, antisimmetrisk och transitiv.

• En partiell ordning R kallas en total partiell ordning om för alla a, b gäller

någon av:

aRb och bRa

• Den kallas en ekvivalensrelation om den är reflexiv, simmetrisk och transitiv.

Exempel • Betrakta den följande binära relationen på ℝ

xRy ⟺ x ≤ y

Den är en total partiell ordning.

Om vi definera r med x < y den blir inte reflexiv.

• Betrakta den följande binära relationen på ℤ^{+}

xRy ⟺ x|y

Den är en partiell ordning, INTE total!

• Betrakta den följande binära relationen på ℤ

xRy ⟺ x ≡_{n} y

Den är en ekvivalensrelation. Om R är en ekvalensrelation på A, kan man definera ekvivalensklassen:

[x]_{R} = {a ∈ A sådan att xRa}

Man kan visa att för varje ekvivalensrelation R på A utgör ekvivalensklasserna en partition av A.

Definition 0.7. Låt \underline{n} = \{1, 2, ..., n\} och låt A vara en mängd. Vi säger att: • A är ändlig och har kardinalitet n, |A| = n om det finns e bijektion från A till \underline{n}.

• A är oändlig om det inte finns någon n sådan att det finns en bijektion från A till \underline{n}.

• A är uppräkneligt oändlig om det finns en bijektion mellan A och ℕ.

Exempel • ℤ är uppräkneligt oändlig. Betrakta bijetktionen:

f(n) = \{ \begin{matrix}\frac{n+1}{2} & för udda n \\ \frac{−n}{2} & för jämna n \end{matrix}

Övning

(1) Sätt A = {1, 2, 3, 4, 5}, B = {x, w, y, z} oxh A_{1} = {2, 3, 5}. Låt g : A_{1} → B vara

en funktion.

• På hur många sätt kan g utvidgas till en funktion från A till B?

• Hur många funktioner från A till B finns det?

• Hur många injektiva funktioner från A till B finns det?

• Hur många surjektiva funktioner från A till B finns det?

• Hur många bijektiva funktioner från A till B finns det?

(2) Visa att (g ∘ f) ∘ h = g ∘ (f ∘ h).

(3) (Tentamen 20030820) Definira funktionen f : ℤ → ℤ genom:

f(x) = \{ \begin{matrix}2x & för udda x \\ 2x + 1 & för jämna x \end{matrix}

Är f injektiv, surjektiv, bjektiv?

(4) Låt A, B vara två ändliga mängder med samma kardinatiteten. Visa att en funktion från A till B är injektiv om och endast om den är surjektiv. Förklara att det följer att:

∑_{k=0}^{n}(−1)^{k}\binom{n}{k}(n − k)^{n} = n!

(5) Visa att för varje ekvivalensrelation R på A utgör ekvivalensklasserna en partition av A.