MTH4000 Home

MTH 4000: Practice Midterm 2

Problem 1. Which of the following statements are true?
  • (A) If \( R \) is a relation on \( A \), then \( R\times R = \left(A\times A\right)\times\left( A\times A\right) \).
  • (B) A transitive relation on a set \( S \) must be a subset of \( S\times S \).
  • (C) If \( f:A\to A \) is a function then the set \( V=\left\{\left.\left(x,f(x)\right)\right|x\in A\right\} \) is a relation on \( A \).
  • (D) If \( P \) is a reflexive relation on \( Q \) then \( Q \) is a symmetric relation on \( P \).
  • (E) If \( P \) is a relation on \( Q \) then \( P\times Q \) is also a relation on \( Q \).

Problem 2. Provide an example of a set \( S \) of \( 3 \) elements and a function \( f:S\times S\to S \) that is not surjective.

Problem 3. Let \(f:S\to T\) be a function. Prove that for every \(A\subseteq S\) the following holds: \[A\subseteq f^{-1}\left(f(A)\right).\] Prove that if \(f\) is injective then \(A=f^{-1}\left(f(A)\right)\).

Problem 4. Let \(f:S\to T\) be a function. Prove that for every \(A\subseteq T\) the following holds: \[f\left(f^{-1}(A)\right)\subseteq A.\] Prove that if \(f\) is surjective then \(f\left(f^{-1}(A)\right)\subseteq A.\)

Problem 5. Assume that \(f:\mathbb R\to\mathbb R\) is a function that satisfies \[\left(\forall x\in\mathbb R\right)\left(f(f(x))=f(x)+x\right).\] Determine all real numbers \(x\) for which \(f(x)=0\).

Problem 6. Determine the total number of functions \(f:\mathbb N\to \mathbb N\) such that for all \(n\in\mathbb N\) the following holds: \(f(n) > 1\) and \[f(n+3)f(n+2)=f(n)+f(n+1)+36.\]

Problem 7. Determine the smallest positive integer \(k\) for which there exists a set \(A\) with \(k\) elements and a function \(f:\mathbb N\to A\) with the following property: For every two natural numbers \(m\) and \(n\) such that \(|m-n|\) is prime, the numbers \(f(m)\) and \(f(n)\) are different.

Problem 8. If \(A\), \(B\), and \(C\) are three sets with finitely many elements, prove that \[\left|A\cup B\cup C\right| = \left|A\right|+\left|B\right|+\left|C\right|-\left|A\cap B\right|-\left|B\cap C\right|-\left|C\cap A\right|+\left|A\cap B\cap C\right|.\]

Problem 9. What is the largest number of subsets of the set \(\{1,2,\dots, n\}\) that can be chosen in such a way that every two of the chosen subsets have a non-empty intersection?

Problem 10. Determine the number of subsets of {1, 2, 3, 4, ..., 50} whose sum of elements is larger than or equal to 638.