Introduction to Mathematical Reasoning

Fall 2011

 Lectures: M-W-F 1:00 PM--1:50 PM Office Hour: M-W 2:00 PM--3:00 PM

Book

• Peter J. Eccles, An Introduction to Mathematical Reasoning: numbers, sets, and functions. (The main textbook)
• R. B. Maddox, Mathematical Thinking and Writing: A Transition to Abstract Mathematics.
• D. Smith, M. Eggen and R. St. Andre, A Transition to Advanced Mathematics.
• D. Solow, How to Read and Do Proofs.

Schedule

This is a tentative schedule for the course. If necessary, it may change.

• Sep 23: Language of mathematics: e.g. mathematical statement; Logical connectives; Table of truth; Implication;
Reading: Chapter 1 and Section 2.1
• Sep 26-Sep 30: More on implications; Mathematical truth; Proof;
Reading: Chapters 2, 3 and Section 4.1 and 4.2
• Oct 3-Oct 7: Well-ordering principle; Division algorithm; Proof by induction; Language of set theory;
Reading: Chapters 4, 5, 6 and 15.
• Oct 10-Oct 14: More on Language of set theory; Quantifiers; Functions;
Reading: Chapters 6, 7 and 8.
• Oct 17-Oct 21: Special classes of functions; The greatest common divisor; Congruences;
Reading: Chapters 9, 15, 16 and 18.
• Oct 24-Oct 28: More on Congruences; Primes and The Unique Factorization; There will be a take home midterm exam.
Reading: Chapters 18, 19 and 23.
• Oct 31-Nov 4: Euclid algorithm; Linear Diophantine Equations; More on Congruences;
Reading: Chapters 16, 17, 18 and 19.
• Nov 7-Nov 9: More on Congruences; Invertible elements mod m;
Reading: Chapters: 19, 20 and 21.
• Nov 14-Nov 18: Euler's theorem; Partition; Counting;
Reading: Chapters 24, 22 and 12.
• Nov 21-Nov 23: More on Counting; Different infinities!
• Nov 28-Nov 30: More on different infinities; Review.

Here are more information on the course, including the name and the e-mail address of the TAs. pdf

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
• a=bq+r,
• 0≤ r< b.
• 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 .
• 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
• Let f be an onto function from X to Y. Let R be the following relation on X: aRb iff f(a)=f(b). Prove that
• R is an equivalence relation.
• Let π:X→ X/R, π(x)=[x]R. Prove that there is a unique function g from X/R to Y with the following properties
• The composite of π and g is equal to f.
• g is a bijection.
• Page 269, Exercises, 22.1 and 22.3.
• Page 271, Problems, 6, 7, 13, 18, 19.
• Let X=R2\{(0,0)}. Let R be the following relation on X: pRq iff ∃ a ∈ R+, ap=q. Prove that
• R is an equivalence relation.
• Let f([x]R)=x/||x||. Prove that
• f is a well-defined function from X/R to the circle S1 of radius one centered at the origin.
• f is a bijection.
• Let X=R2. Let R be the following relation on X: pRq iff p-q∈ Z2. Let Y=[0,1]×[0,1] and let S be the following relation on Y:
• For any p in Y, pSp.
• For any y in [0,1], (0,y)S(1,y) and (1,y)S(0,y).
• For any x in [0,1], (x,0)S(x,1) and (x,1)S(x,0).
Prove that R and S are equivalence relations and find a bijection between X/R and Y/S.

(Correction: the above relation S is not an equivalence relation. You can check that it is not trasitive! In order to make it transitive, one has to add the following elements to S:

• (0,0)S(1,1) and (1,1)S(0,0),
• (1,0)S(0,1) and (0,1)S(1,0).
After this correction, the rest of the problem holds!)

Midterm.

• You have 3 hours to finish this exam. This means as soon as you open the pdf file the clock starts! So first prepare the needed tools, e.g. enough paper, pen or pencil, etc.
• Till the end of my lecture on Monday, you are not allowed to talk about the exam with anyone.
• During the exam (the three hours), you are not allowed to use any (e-)book, any (e-)note, or internet.
• If a problem is unclear, send me an e-mail.
• Please write and sign that you honored the UCSD honor code for this exam!
• You should give me your exam on Monday before the lecture.
• Good Luck! Here is the exam

Outline of the solutions to some of the problems.

• Here you can find solutions of some of the problems in the midterm.
• Here you can find solutions of some of homework problems (due Nov. 14)
• Here you can find a solution of the last problem in the last homework

A summary of this course.

• Here you can find a short summary of most of the topics that we discussed during the semester.
• This should not be treated as a complete list of the topics that you have to study for the final. Nevertheless I hope that it can help you to study in a systematic way for the final.
• Good Luck!

Final.

Here is the final exam and here is its rough solutions.