Problem Set 1 Solution

You may not define your own predicates or sets for this problem set; please work with the denitions provided in the questions, or from the course notes.





[4 marks] Truth tables and formulas. Consider the following formula: (p _ q) ) r



[2 marks] Write the truth table for the formula. (No need to show your calculations).



[2 marks] Write a logically equivalent formula that doesn't use ) or ,, in other words it uses only ^; _, or :. Show how you derived the result.



[10 marks] congruence



Find a natural number m congruent to 5 (mod 7), and another natural number n congruent to 2 (mod 7). Find what the product mn is congruent to (mod 7), and then make a statement about the congruence of the product of any pairs of natural numbers that have the same congruences as the m and n you found, (mod 7).




[5 marks] Write a predicate formula that expresses your statement in the form of a universally quantied implication. If you believe the statement, prove it true. If you disbelieve the statement, prove it false.



[5 marks] Write the converse of your formula from the previous part. If you believe the converse, prove it true. If you disbelieve the converse, prove it false.



[4 marks] one-to-one pigeonholes



The pigeonhole principle says, informally, that if n pigeons roost in fewer than n pigeonholes, at least one pigeonhole will be crowded with more than 1 pigeon.




To make this precise, we rst formalize the notion of un-crowded for f : D 7!R:




OneToOne(f): 8x; y 2 D; x 6= y ) f(x) 6= f(y), where f : D 7!R, jDj; jRj 2 N+.




Let F = ff j f : D 7!R ^ jDj 0 ^ jRj 0g The pigeonhole principle says that:




8f 2 F; OneToOne(f) ) jDj µ jRj




[4 marks] Use the pigeonhole principle to prove that if n § 2 people go to the same party, there are at least 2 people who shake hands with the same number of other people. Hint: Take the set of people at the party as your domain, dene a function that evaluates how many people each person shook hands with.



You may also use the pigeonhole principle in subsequent questions in this assignment.




[21 marks] modular arithmetic with primes



Let a; p be natural numbers with p prime and gcd(a; p) = 1. Let T = f1; : : : ; p 1g, the positive integers less than p.




De

ne rp(x) as the remainder after division of x by p.




Prove each of the following claims. You may use the result of an earlier claim to help prove a later claim, for example Claim (e) might help prove Claim (f). You may even use an earlier claim you haven't proven to help prove a later claim.




[3 marks] Claim: frp(an) j n 2 T g T . Hint: Consider the material in Characterizations in the course notes.



[3 marks] Claim: If n1 and n2 are distinct numbers in T , then rp(an1) =6 rp(an2). Hint: Consider the material in Characterizations in the course notes.



[3 marks] Claim: jfrp(an) j n 2 T gj = jT j.



[3 marks] Claim: frp(an) j n 2 T g = T . Hint: For nite sets A and B if A B then jBj = jB nAj+jAj.



[3 marks] Claim: ii==1p 1rp(ai) = ii==1p 1i.



[3 marks] Claim: rp(ap 1) = 1. Hint: You may assume, as a consequence of Example 2.18, that if for



2 f1; 2; : : : ; kg ai bi (mod of Example 2.14, that for any



p), then k1ai k1bi (mod p). You may also assume, as an extension k 1, if prime p - b1 ^ p - b2 ^ ^ p - bk, then p - (b1 b2 bk).



[3 marks] Claim: If a is an arbitrary natural number that isn't divisible by 5, then r5(a100) = 1.



[6 marks] primes



Since, as shown in the course notes, there are innitely many primes, it is not possible for a consecutive sequence of composite (non-prime) natural numbers to stretch on forever. However, arbitrarily long prime-free sequences exist. On the other hand, for any natural number we can always set an upper bound on how far away the next prime can be.




Prove each of the following statements. You may use the Prime predicate.




[3 marks] Claim: For any k 2 N there is some n 2 N such that n; n + 1; : : : ; n + k are composite. Hint: Think about (k + 2)!.



[3 marks] Claim: For any positive natural number n there exists a prime p with n < p < n! + 2. Hint: Think about n!, and the proof of Theorem 2.3, that there are innitely many primes.