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.