Chapter 8: Functions

Question 1

How is a function defined?

Answer 1

Intuitively, you can think of the domain as the inputs of f, the range as the
outputs of f, and the codomain as a possibly larger set in which all the outputs live.
* But at the end of the day, all three are just sets. They correspond to each other via f, but they are just sets.

Question 2

As an overview, what does it mean for a function to exist and be unique?

Answer 2

Question 3

When does a function fail existence and uniqueness?

Answer 3

• One line and only one line must emanate from each dot.
• The first fails existences because b does not map to anywhere on the codomain
• the second fails uniqueness as it the bee maps to two different places on the codomain

Question 4

What is the vertical line test for testing if a graph is a function?

Answer 4

Question 5

Example of valid functions?

Answer 5

Question 6

When is a function injective?

Answer 6

• the second fails as f(x) and f(y) equal 2. while x cannot equal y as these are clear two different arrows.
• Interestingly the contrapositive provides another way to think about an injection.
  
  • The contrapositive turns an implication like F(a1)=F(a2) implies a1=a2 into a logically equivalent implication

Question 7

What is the contrapositive statement to an injective function?

Answer 7

• Interestingly the contrapositive provides another way to think about an injection.
  
  • The contrapositive turns an implication like F(a1)=F(a2) implies a1=a2 into a logically equivalent implication

Question 8

When is a function surjective?

Answer 8

Question 9

What is the contrapositive equivalent definition to a subjective function?

Answer 9

Question 10

What does existence and uniqueness have to do with a function being injective and subjective?

Answer 10

Question 11

When is a function bijective?

Answer 11

Question 12

What does existence and uniqueness have to do with a function being bijective?

Answer 12

Question 13

What is the general outline for an injective proof?

Answer 13

Question 14

What is the general outline for surjection proof?

Answer 14

• It is important to remember that when you choose a b ∈ B (at the start of your
  proof), it must be completely arbitrary. If B = R, make sure you are never assuming
  that b is positive or negative or non-zero or an integer or anything like that.
  Your work must be valid regardless of what the b is. Recall that this is what we mean when we say that we chose an arbitrary b ∈ B
• The only exception to this is if you divide
  up your work into cases where you have, say, the negative case and the non-negative case, or the zero and the non-zero case.
• But if you do that, then within each case’s set you must choose an arbitrary b, and collectively the cases must cover all the options in B.

Question 15

Let R + denote the nonnegative real numbers. Prove the following:

(a) f : R → R where f(x) = <sup<2
^{is not injective, surjective or bijective.}

Answer 15

*the injective property is essentially a “horizontal line test.”

Question 16

Let R + denote the nonnegative real numbers. Prove the following:

(b) g : R+ → R where f(x) = <sup<2
^{is not injective, surjective or bijective.}

Answer 16

Question 17

Let R + denote the nonnegative real numbers. Prove the following:

(c) h : R → R+ where f(x) = <sup<2
^{is not injective, surjective or bijective.}

Answer 17

Question 18

Let R + denote the nonnegative real numbers. Prove the following:

(d) k : R+ → R+D where f(x) = <sup<2
^{is not injective, surjective or bijective.}

Answer 18

Question 19

PROOF (injective part):

The function f : (Z × Z) → (Z × Z) where f(x, y) = (x + 2y, 2x + 3y) is a bijection

Answer 19

Question 20

PROOF (Surjective part):

The function f : (Z × Z) → (Z × Z) where f(x, y) = (x + 2y, 2x + 3y) is a bijection

Answer 20

Question 21

When does in/surjectiveness fail when looking at domains and codomains of finite size?

Answer 21

Question 22

THEOREM: What is the “pigeonhole principle” concerning functions?

Answer 22

Question 23

PROOF: What is the “pigeonhole principle” concerning functions?

Answer 23

Question 24

What is the definition of a composition function?

Answer 24

Question 25

Example of a composite function?

Answer 25

Question 26

Answer 26

Question 27

What is the multiplicative and additive identity for the reals?

Answer 27

Question 27

Corollary: Suppose A, B and C are sets, g : A → B is bijective, and
f : B → C is bijective. Then f ◦ g is bijective.

Answer 27

• By Theorem 8.13, f ◦ g is an injection.
  • Suppose A, B and C are sets, g : A → B is injective, and f : B → C is injective. Then f ◦ g is injective.
• By Theorem 8.14, f ◦ g is a surjection.
• Suppose A, B and C are sets, g : A → B is surjective, and f : B → C is surjective. Then f ◦ g is surjective

Thus, by the definition of a bijection (Definition 8.7), f ◦ g is a bijection.

Question 28

What is the definition of the identity function

Answer 28

Question 29

Examples of the inverse of functions in set format?

Answer 29

Question 30

Further examples of the inverse of functions in written format?

1. f R –> R and f(x) = x + 1
2. f R+ –> R+ and f(x) = x^2
3. tan: (-pi/2,pi/2) –> R
4. exp: R –> R+

Answer 30

Question 31

What property does a function need to have an inverse?

Answer 31

needs to be a bijection

Question 32

PROOF:

A function f : A → B is invertible if and only if f is a bijection

Answer 32

Question 33

PROOF:

There does not exist a universal lossless compression algorithm.

(an algorithm that can compress the size of any type of file and then invert it without any loss of data)

Answer 33

Question 34

PROOF:

Prove that the function f : (0, ∞) → (0, 1) where f(x) = 1/(x + 1) is a bijection.

Answer 34

Question 35

PROOF:

Find the inverse of f : R → R where f(x) = 2x + 5.

Answer 35