Module 5 Homework Problems

Convert the following formally quantified statements to informal statements. Two bonus points are awarded for each if you also correctly convert the statement to an implicitly quantified statement (i.e. plain English).

1. “\(\forall x\in \mathbb{R}, x\) is rational”
2. “\(\exists n\in \mathbb{N}\) such that \(13\vert n\)”
3. “\(\forall x\in \mathbb{R}, \exists y\in \mathbb{R}\) such that \(x<y\).”
4. “\(\exists x\in \mathbb{R}, \forall y\in \mathbb{R}, \exists z \in \mathbb{R}\) so that \(x<y\) and \(x<z\)”

Convert each of the following implicitly quantified statements to their formally quantified statement equivalent.

5. “Every even number is divisible by 2”
6. “There is a natural number that is divisible by \(2,3,5\) and \(7\).”
7. “Every natural number that is a multiple of 10 is a multiple of 5”
8. “There is an integer that is less than every natural number”

Reduce the quantifiers in the following statements so that the quantifiers alternate with no quantifier repeating “in a row.”

9. “\(\forall x\in \mathbb{R}, \forall y\in \mathbb{N}, \exists z \in \mathbb{R}\) such that \(z\cdot y=x\)”
10. “\(\forall n\in \mathbb{N}, \exists m\in \mathbb{N}, \exists q\in \mathbb{N}, \forall r \in \mathbb{Z}, nr<mq\).”

11. Argue whether or not the following statements, who had their quantifiers swapped, express the same idea.
    • “\(\forall n\in \mathbb{N}, \exists m\in \mathbb{N}\) such that \(n<m\)”
    • “\(\exists m \in \mathbb{N}\) such that \(\forall n\in \mathbb{N}, n<m\)”
12. (Bonus +20) Find a statement with two quantifiers \(\exists\) and \(\forall\) that means the same thing as the statement one gets by swapping the quantifiers. Be sure to argue or explain why this is the case for the example you provide. (Be patient and don’t be afraid to just try things and see if you notice a pattern) (Email me for a hint after you’ve struggled a little with this)

Find the negation of the following statements (regardless of whether or not the statement is true)

13. “\(\exists n\in \mathbb{Z}\) such that \(n\leq -20\)”
14. “\(\forall m\in \mathbb{N}, m\vert 20\)”
15. “\(\exists n\in \mathbb{N}\) such that \(\forall m\in \mathbb{N}\), \(6\vert n\ \text{and}\ n\vert m\)”
16. “Every person on earth is less than 10 feet tall.”
17. “There is a natural number that has at least five prime factors”
18. “Every computer program ever written can be represented by a single natural number” (This is actually a true statement)
19. “There is someone for everyone” (be careful and precise with this one! Rephrasing the original helps a lot!)

Prove the following claims! If you need a hint, email me explaining where you are stuck!

Note: If every statement that you write in your proof is either immediately obvious, or states a known true fact to support it, then your proof is sufficiently detailed. Your proof is correct if the statement given in the problem follows logically from the statements you write and any hypotheses given in the statement itself.

Pro-Tip: Try organizing your thoughts and work on scratch paper before writing the final proof. Think of a proof as a formal polished presentation of your argument for why a statement is true.

Another Pro-Tip: BE PATIENT WITH THESE! Take your time and play with ideas on scratch paper until you understand how to form an argument.

20. “There is a natural number \(n\) such that n+5=431”
21. “There is a pair of integers \(n\) and \(m\) such that \(3n+5m=1\).”
22. “Every integer that is divisible by \(12\) is divisible by \(4\)”
23. “There are a pair of natural numbers \(n\) and \(m\) such that \(\gcd(n,m)=2\) and \(\text{lcm}(n,m)=42\)”
24. Let \(D=\{2,4,8\}\). “For every \(x\in D\), \(2\vert x\)”
25. (Bonus +5) Let \(D=\{1,2,4,8\}\). “For every \(x\in D\) , there exists an integer \(n\) such that \(x=2^n\).”
26. “If \(n\) is an odd integer, then \(n^2+n+2\) is even.
27. “If \(n\) is a multiple of \(3\) and \(12\), then \(6\vert n\).”
28. “If \(n\) is a natural number such that \(n \equiv 2 \pmod 4\), then \(n\) is even.” (Hint: by the quotient remainder theorem, \(n \equiv 2 \pmod 4\) implies \(n=4m+2\) for some \(m\in \mathbb{Z}\)).
29. “If \(n\in \mathbb{N}\) so that \(n \equiv 1 \pmod 6\), then \(n\) is odd.” (Similar hint to the above).

Disprove the following. If you need a hint, email me explaining where you are stuck!

30. “For all real numbers \(x\) and \(y\), \( (x+y)^2=x^2+y^2.\)”
31. “If \(n\) is odd, then \(\frac{n-1}{2}\) is even”
32. “For every pair of prime numbers \(p\) and \(q\), the sum \(p+q\) is even”
33. “If \(n\) is prime and \(n\geq 3\), then \((-1)^n=1\)”

Bonus points for HONEST feedback (no matter how brutal). 2pts each

1. On a scale of 1 to 10, where 10 is “I love it/Its great” and 1 is “It’s absolutely terrible”, how enjoyable has PGE been to use?
2. How long did this module take you in total? Did it take more or less time than usual?
3. What was the easiest module so far? Which was the hardest/most confusing?
4. On a scale of 1 to 10, how easy is it to learn from the videos?
5. On a scale of 1 to 10, how clear are the explanations in the videos?
6. (Bonus +5 if answered with a few sentences) Any additional commentary, suggestions, or feedback you’d like to add right now? Anything you suggest will help improve the site!