uni/inf1080/hw4.md

Innlevering 4

6.3

• S\sub{1} = {(a, a), (a, b), (b, b), (b, c)}
• S\sub{2} = {(a, a), (a, b), (b, b)}
• S\sub{3} = {(a, a), (a, b), (b, b), (b, c)}
• S\sub{4} = {(a, a), (a, b), (b, a), (b, b), (c, c)}
• S\sub{5} = {(a, a), (b, c), (c, b)}

A) (c, c) mangler B) (b, a) mangler C) (a, c) mangler D) (b, a) eller (a, b) må fjernes E) (a, a) må fjernes F) S\sub{2} og S\sub{4} er refleksive. S\sub{4} og S\sub{5} er symmetrisk. S\sub{2} og S\sub{4} er transitive.

\pagebreak

7.8

A) f: {1, 2, 3} \to {1, 2, 3, 4} slik at f(x) = x + 1: Bijeksjon

Dette er en injeksjon (en-til-en) fordi at for hver input er det en ny output. Det er også en surjeksjon (på), fordi alle outputs har en gyldig input.

B) Funksjonen {(a, 1), (b, 2), (c, 3)} fra {a, b, c} til {1, 2, 3, 4}: Injeksjon

Dette er en injeksjon fordi at for hver input er det en ny output. Det er ikke en surjeksjon; det er ingen lovlige inputs som gir 4, selv om 4 er en lovlig output.

C) Funksjonen {(a, 1), (b, 2), (c, 3), (d, 3)} fra {a, b, c, d} til {1, 2, 3, 4}: Ingenting

Dette er ikke en injeksjon, fordi det er to inputs som gir outputen 3. Det er heller ikke en surjeksjon; det er ingen lovlige inputs som gir 4, selv om 4 er en lovlig output.

D) Funksjonen {(a, 4), (b, 2), (c, 3), (d, 1)} fra {a, b, c, d} til {1, 2, 3, 4}: Bijeksjon

Dette er en injeksjon, fordi hver input gir en ny output. Det er også en surjeksjon, fordi alle outputs har en gyldig input.

E) f: \R \to \R slik at f(x) = 2x + 1: Bijeksjon

Dette er en injeksjon, fordi hver input gir en ny output. Det er også en surjeksjon, fordi alle outputs har en gyldig input.

F) f: \N \to \N slik at f(x) = x + 2: Injeksjon

Dette er en injeksjon, fordi hver input gir en ny output. Det er ikke en surjeksjon, fordi det finnes outputs i \N som ikke er en gyldig input; outputen 1 vil for eksempel kreve inputen -1, som ikke er et element i $\N$.