| Assignments.
- Due Sep. 30:
- Make truth tables for each of the following propositional forms:
- P∧ ∼P
- P∧(Q∨R)
- (P∧Q)∨(P∧R)
- ∼(P∧Q)
- ∼P∨∼Q
- (P⇒Q)∧(Q⇒R)
- P⇒R
- ∼P∨R
- Exercise 2.1: (ii), (iii), (iv), (v), (ix).
- Use the first problem to conclude that P⇒Q and ∼P∨Q are equivalent. Then conclude that P⇒Q and ∼Q→∼P are equivalent.
- As we discussed in class, in English, or is used as the exclusive or: meaning "one or the other but not both". The exclusive or is denoted by ⊻. Make the truth table of P⊻Q. Find a propositional form using only P, Q, ∧, ∨ and ∼ which is equivalent to P⊻ Q.
- Aliens have a strange "logical connective" between three statements. Its truth table is as follows
| P | Q | R | f(P,Q,R) |
| T | T | T | T |
| T | T | F | F |
| T | F | T | F |
| T | F | F | T |
| F | T | T | F |
| F | T | F | T |
| F | F | T | T |
| F | F | F | F |
Is there a propositional form expressed only in terms of P, Q, R, ∧, ∨ and ∼ which is equivalent to f(P,Q,R)? If yes, find it and say why they are equivalent. If not, say why.
- Due Oct. 10:
- For any proposition P, let χ(P)=1 if P is true and χ(P)=0 if P is false. Prove that for any two propositions P and Q we have
- χ(∼P)=1-χ(P).
- χ(P ∧ Q)=χ(P) χ(Q).
- χ(P ∨ Q)=χ(P)+χ(Q)-χ(P)χ(Q).
- P ⇒Q if and only if χ(P)≤ χ(Q).
- P is equivalent to Q if and only if χ(P)=χ(Q).
- χ(P⇒Q)=χ(χ(P)≤ χ(Q)).
- χ(P⇔Q)=χ(χ(P)=χ(Q)).
-
- Prove that n2 is even if and only if n is even.
- Prove that √ 2 is irrational.
- Let a ∈ Z and b ∈ N. Show that there is a unique pair (q,r) of integers such that
- Exercises 3.1, 5.4, 5.6.
- Problems I: 10, 17, 18, 19.
- Due Oct. 14:
- Let f0=0, f1=1 and fn+1=fn+fn-1 for any integer n.
- Prove that for any non-negative integers n and m, we have fn+m=fnfm+1+fn-1fm.
- Prove that fn divides fnk for any natural numbers n and k.
- Let fn be as in the previous problem. Show that any natural number can be written as a sum of distinct fn's. (Hint: use the strong induction.)
- By induction on n, prove that an n-polygon has exactly n(n-3)/2 diagonals.
- Prove that 1+(1/√ 2 )+…+(1/√ n ) ≤ 2√ n , for any natural number n.
- Let A and B be two subsets of X. The symmetric difference of A and B is the set of elements which are either in A or in B but not in both of them and it is denoted by A Δ B. For instance {1,2} Δ {1,3}={2,3}. Prove that
- A Δ B=(A∖B)∪(B∖A).
- A Δ B=(A∪B)∖(A∩B).
- A Δ B=B Δ A.
- A Δ A=∅
- A Δ ∅=A
- A Δ (B Δ C)=(A Δ B) Δ C.
- If A Δ B=A Δ C, then B=C.
- Prove that for any ε>0 there is δ>0 such that, if |x-5|<δ, then |x2-25|<ε.
Due Oct. 21 :
- Exercises 7.4, 7.8, 8.3.
- Problems II: 14, 15.
- Write in mathematical language what it means to say that there is a unique a in A such that P(a).
-
- Write in mathematical language what it means to say:
- limx→ af(x) does not exist.
- any real number can be approximated by rational numbers.
- any real number can be approximated by irrational numbers.
- Let f(x)=1 if x ∈ Q and f(x)=0 if x ∈ R ∖ Q. Prove that for any real number a, lim x → af(x) does not exist.
- Define what it means to say that limx→+∞ f(x)=L.
Let A be a finite set and f and g be two functions from A to itself. Prove that the composite of f and g is bijective if and only if f and g are bijective.
Due Oct. 28:
- Exercises: 9.1, 9.2, 9.3, 9.4, 9.6
- Let f:R→ R, f(x)=√ x2+1 . A (sloppy) student wrote f as the composite function of functions g1, g2 and g3. He defined gi's this way:
- g1(x)=x2.
- g2(x)=x+1.
- g3(x)=√ x .
His answer is not complete. Why? Complete his answer.
- Let Sn be the set of all the invertible functions from A={1,...,n} to itself.
- Find the order of S3 and S4.
- Let f and g be two functions from {1,...,n} to itself. Prove that the compsite of f and g is in Sn if and only if f and g are in Sn. (You are allowed to use problems from previous homework.)
- If f is in Sn, then f(-1) is also in Sn.
- Let f(1)=f and recursively let f(m) be the composite of f(m-1) and f. Prove that there is a natural number m such that, for any f in Sn, f(m)=IA.
- Let f:A→B and g:B→A. Determine whether the following statements are true or false. If a statement is ture, then prove it. If it is not true, then provide a counterexample.
- If the composite of f and g is the identity function of A, then the composite of g and f is invertible.
- If the composite of f and g is the identity function of A and the composite of g and f is invertible, then g is the inverse (function) of f.
- Prove that there is a bijection between the power set of {1,...,n} and {0,1}n={(e1,...,en)| for any i, ei=0 or 1}. (Hint: use one of the previous week's problems!)
Due Nov. 4:
- Write down the details of the proof of the Unique Factorization, which was presented in the class.
- For any non-zero integer n and prime p, let vp(n)=d if pd divides n and pd+1 does not
divide n. For instance, v2(4)=2, v3(6)=1 and v5(6)=0. Notice that we have
n=∏p pvp(n),
where p is running through primes. Let m and n be two non-zero integers.
- Prove that vp(mn) = vp(m)+vp(n).
- Prove that vp(m+n) ≥ min{vp(m),vp(n)}.
- Prove that m|n if and only if for any prime p we have vp(m) ≤ vp(n).
- Prove that vp(gcd(n,m)) = min{vp(n),vp(m)}.
- Let lcm(m,n) be the least common multiple of m and n. Prove that
vp(lcm(m,n)) = max{vp(m),vp(n)}.
- Prove that |mn|=lcm(m,n).gcd(m,n).
- Prove that the number d(n) of the positive divisors of n is equal to ∏p(vp(n)+1).
- Prove that d(n) is odd if and only if n is a perfect square.
- Prove that d(mn)=d(m)d(n) if gcd(m,n)=1.
- Let fn be the Fibonacci sequence. Prove that gcd(fm,fn)=fgcd(m,n) for any positive integers m and n.
Due Nov. 14:
- In the following questions, if the answer is yes, find all the possible solutions, and if the answer is no, prove your claim.
- Is there x such that 14x≡1(mod 29)?
- Is there x such that 7x≡4 (mod 18)?
- Is there x such that 14x≡8(mod 36)?
- Is there x such that 14x≡1(mod 36)?
- Find the min value of |x|+|y| such that x and y are integers and 53x+29y=3. Prove your claim.
- Prove that gcd(22n+1,22m+1)=1 if m and n are distinct positive integers.
-
- Prove that if p is prime and x2-1≡0 (mod p), then x is congruent to either 1 or -1 mod p. Is it true mod m where m is not prime?
- Prove that if p is prime and a is not congrunet to zero mod p, then there is a' such that a'a≡1 (mod p).
- (Wilson's theorem) Prove that (p-1)!≡-1(mod p) if p is prime. Hint: Group any number a in {1,..., p-1} with a' in {1,...,p-1} such that a'a≡1 (mod p). (n!=1.2.3. ... .n.)
- Prove that there is no positive integer n for which 2n + 1 is divisible by 7.
- Prove that gcd(2n-1,2m-1)=2gcd(m,n)-1.
Due Nov. 21:
-
Let m and n be two integers. Assume that gcd(m,n)=1. Let f:Z/(mn)Z → Z/mZ × Z/nZ
f(x+(mn)Z)=(x+mZ,x+nZ).
- Prove that f is a bijection. (Hint: it is enough to show that it is an injection.)
- (Chinese Remainder Theorem) Prove that for any integers a and b there is a unique x modulo mn such that x≡ a (mod m) and x≡ b (mod n).
- Prove that for any x and y in Z/(mn)Z we have f(xy)=f(x)f(y).
- Prove that f(U(Z/(mn)Z))=U(Z/mZ)× U(Z/nZ), where as we defined in the class U(R) is the set of invertible elements in R.
- Prove that φ(mn)=φ(m)φ(n), where φ is the Euler's phi function.
- Prove that φ(pk)=pk-1(p-1) for any prime p and positive integer k.
- Prove that φ(n)=∏p|np(vp(n)-1)(p-1), where p runs through all the prime divisors of n and vp(n) is defined as in the previous week's problem set.
- Prove that, if p and q are distinct prime numbers, then pq-1+qp-1≡ 1 (mod pq).
- Page 296, Problems VI, problems 12, 13, 14, 16.
Due Nov. 28
|
