Assignment 5

In addition to correct answers, please:

  • Show how you derived your answer.
  • Make all proofs, and longer-answer questions, beautifully organized and easy to read. This includes perfect spelling and grammar.

Please see Canvas for instructions on how and when to submit this assignment.

Question 1

Suppose \(A\) and \(B\) are both subsets of \(\mathbb{R}^2\), and \(A=\{(x,y) : y=2x+1\}\), \(B=\{(x,y) : y=3x\}\), and \(C=\{(x,y) : x-y=5\}\).

  1. What is \(A \cap B\)?
  2. What is \(B \cap C\)?
  3. Suppose \(S = \overline{B} \cup \overline{C}\). What is \(\overline{S}\)?

Question 2

Suppose \(f:\mathbb{R} \rightarrow \mathbb{R}\) and \(f(x)=x^2\). Calculate \(f(A)\) for each of the following (all the given sets are subsets of \(\mathbb{R}\)). Make your answers as simple as possible.

  1. \(A=\{3, 5\}\)
  2. \(A=\{-4, -2, 1, 2\}\)
  3. \(A=(-4, 4)\)
  4. \(A=(-2, 3]\)
  5. \(A=[-6, 2]\)
  6. \(A=[5, 6] \cup (-4, -3]\)

Question 3

Suppose \(f:\mathbb{Z} \rightarrow \mathbb{Z}\). For each of the following, determine if \(f\) is onto, and if it is 1-to-1. If the function is not onto, also determine \(f(\mathbb{Z})\).

  1. \(f(x) = x + 5\)
  2. \(f(x) = 3x - 2\)
  3. \(f(x) = 5 - x\)
  4. \(f(x) = x^2\)
  5. \(f(x) = x^3\)
  6. \(f(x) = x^2 - x\)

Question 4

Suppose \(f: \mathbb{R}\times\mathbb{R} \rightarrow \mathbb{R}\), and \(f(a,b)=a-b\).

  1. Is \(f\) commutative? Prove your answer is correct.
  2. Is \(f\) associative? Prove your answer is correct.
  3. Does \(f\) have an identity element? Prove your answer is correct.

Question 5

Let \(g: \mathbb{N} \to \mathbb{N}\) be defined as \(g(n)=3n\). Suppose \(A = \{ 1, 2, 3, 4 \}\), and \(f: A \to \mathbb{N}\) is defined as \(f = \{ (1,2), (2,3), (3,5), (4,7)\}\). What is \(g \circ f\)?

Question 6

Let \(f: A \to B\) and \(g: B \to C\). Prove:

  1. If \(g \circ f: A \to C\) is one-to-one, then \(f\) is one-to-one.
  2. If \(g \circ f: A \to C\) is onto, then \(g\) is onto.

Question 7

Suppose \(A = \{ 1,2,3,4,5,6,7 \}\), \(B = \{ 3,5,7,9,11,13 \}\), and \(f:A \to B\) where \(f=\{ (1,3), (2,7), (3,7), (4,9), (5,7), (6,9), (7,13) \}\). For each of the following, determine the pre-image of \(B_1\) under \(f\):

  1. \(B_1 = \{ 3 \}\)
  2. \(B_1 = \{ 7 \}\)
  3. \(B_1 = \{ 7,9 \}\)
  4. \(B_1 = \{ 7,9,11 \}\)
  5. \(B_1 = \{ 7,9,11,13 \}\)
  6. \(B_1 = \{ 11,13 \}\)

Question 8

Let \(f,g: \mathbb{Z}^+ \to \mathbb{R}\), where \(f(n)=n\) and \(g(n)=n + \frac{1}{n}\). Using the definition of domination, show:

  1. \(f \in O(g)\)
  2. \(g \in O(f)\)

Question 9

Let \(f,g: \mathbb{Z}^+ \to \mathbb{R}\), where \(f(n)=2n+50\) and \(g(n)=n^2\). Using the definition of domination, show:

  1. \(f \in O(g)\)
  2. \(g \notin O(f)\)