Transcribed TextTranscribed Text

1. For the following functions determine if they are (i) injective, (ii) surjective and (iii) bijective. Prove your answers. (a) f : R → R defined by f(x) = 17x − 4. (b) f : Z → Z defined by f(x) = 17x − 4. (c) f : R → Z defined by f(x) = bxc. (Recall that bxc is the floor of x, this is the largest integer that is less than or equal to x.) (d) f : Zm → Zm with f([x]) = [x] 2 . (Be careful with this one, it depends on m) (e) f : Z10 → Z10 f([a]) = [a] −1 if [a] is invertible; [a] otherwise. (You can use question 3 for this.) (f) f : Z × Z → Z defined by f(x, y) = 3x + 2y. 2. or each function in Question 1 that is a bijection give the inverse of the function. 3. Let Pn be the set of integers {1, 2, . . . , n}. Let f : Pn→ Pn. (a) Prove that if f is injective then it is also surjective. (b) Prove that if f is surjective then it is also injective. (So this means that if f is a function from a finite set X to a finite set Y where the size of X and Y are them same, then f is injective if and only if it is surjective. 4. Let P be the set of all positive integers. Find a map f : P → P that is injective but not surjective. Find a map g : P → P that is surjective but not injective. (So the result in Question 3 only holds for finite sets!) 5. Prove that the set of even positive integers (E +) has the same cardinality as the set of all positive integers (P). Also prove that the set of odd positive integers (O+) also has the same cardinality. 6. Let A4 = {1, 2, 3, 4} and let S4 = {(x1, x2, x3, x4) | xi = 1 or xi = 0} (set of all binary sequences of length 4). i) Show that if P(A4) is the set of all subsets of A4, then we can find a bijection between A4 and S4. ii) If An = {1, 2, . . . , n} where n ∈ P, define a function from P(A) to Sn that is a bijection.(You do not need to prove it is a bijection!) iii) What is the cardinality of P(An)?

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

    $25.00 for this solution

    PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

    Find A Tutor

    View available Discrete Math Tutors

    Get College Homework Help.

    Are you sure you don't want to upload any files?

    Fast tutor response requires as much info as possible.

    Upload a file
    Continue without uploading

    We couldn't find that subject.
    Please select the best match from the list below.

    We'll send you an email right away. If it's not in your inbox, check your spam folder.

    • 1
    • 2
    • 3
    Live Chats