Unit 23 Answers

1.

1. Not a functin.  f(0) is not defined.
2. Not a function.  f is not single valued.   For example f(1) = 1 and -1.
3. It is a function.

2.

1. Domain: the set of bit strings. Range: the set of natural numbers.
2. Domain: the set of bit strings. Range: {0, 1, 2, 3, 4, 5, 6, 7}

3.  a) and b) are one-to-one.

1. Suppose that  f(n₁) = f(n₂).  
   Then  n₁ + 2 = n₂ + 2.  Hence n₁ = n₂.
   Hence f in this case is one-to-one.
2. For example   f(1) = 3 = f(-2).   Hence f is not one-to-one.
3. Suppose that   f(n₁) = f(n₂).  
   Then  n₁³ - 1  =  n₂³ - 1.
   Hence n₁³ =  n₂³.
   Since   n₁n₂ > 0,   if   n₁³ = n₂³,   then  n₁ = n₂   follows.
   Hence f in this case is one-to-one.

4.

1. Yes  
2. No. For example nothing in Z is mapped to 0 by f.
3. No. For example nothing in Z is mapped to 1 by f.

5.

1. Yes   If   f(x₁)   =   f(x₁),   then   2x₁ + 3 = 2x₂ + 3.   Hence x₁ = x₂.   Hence f is one-to-one.
   For any  y  in  R,   x = (y - 3)/2   is in  R and it is mapped to y  by  f.  Hence  f  is onto.
   Hence  f  is a bijection.
 
2. This  f  is neither one-to-one nor onto. Hence it is not a bijection.

6.

1. For any x in R, if x > 1, then 10 < 10x. Hence 10 = O(x).
2. For any x in R, if x > 1, then 3x + 7 < 10x. Hence 3x + 7 = O(x).
3. If x² + x + 1 = O(x), then there exist positive numbers C and x₀ such that x² + x + 1 < Cx for all x > x₀.
   However, for any C, if x > C - 1, then x + 1 - C > 0.
   Hence if x > max {0, C - 1}, then x(x + 1 - C) > 0.
   Hence x² + (1 - C)x + 1 > 0. That is, x² + x + 1 > Cx if x > max {0, C - 1}.
   Hence for any C there is no x₀ such that x² + x + 1 < Cx for all x > x₀.
   Hence x² + x + 1 is not O(x).
4. Since e^x > x if x > 0, 5ln x < 5x for all x > 0. Hence 5ln x = O(x).

7. x⁴ + 5x³ + 3x² + 4x + 6 < x⁴ + 5x⁴ + 3x⁴ + 4x⁴ + 6x⁴ = 19x⁴ if x > 1 since x⁴ > x³, x⁴ > x.
Hence x⁴ + 5x³ + 3x² + 4x + 6 is O(x⁴).