MATH 311-02, Fall 2014

This class has completed. Information on this web page may not be applicable to future semesters.

Quick links:

Blackboard page for MATH 311-02
Course syllabus, in PDF format, formatted for printing
Exams
- Practice Midterm #1 (solutions)
- Midterm Exam #1 (solutions)
- Practice Midterm #2 (solutions)
- Midterm #2 (solutions)
- Practice Midterm #3 (solutions)
- Midterm #3 (solutions)
- Practice Final Exam (solutions)
Miscellany
- Two fun applications of induction
- Proof of the Cantor-Schröder-Bernstein Theorem

Course information
Course schedule
Daily problems

Course information:

Instructor:	Jake Wildstrom Office: Natural Sciences Building 113 Primary office hours: Monday 11:00--13:00, Tuesday 14:30--15:30 Secondary office hours: Wednesday 15:30--16:30, Friday 12:00--14:00, or by appointment Phone number: (502)852-5845 (x5845) E-mail: djwild01@louisville.edu
Lecture:	TR 13:00–14:15 in Speed Hall 002
Prerequisites:	MATH 205 or ENGR 101
Description:	Introduction to abstract mathematics with particular attention to developing proof-reading and proof-writing skills. The basics of set theory, functions, relations, number systems, countability, sequences and their convergence, and the complex plane.
Textbook:	A Transition to Advanced Mathematics by Smith, Eggen, and St. Andre, eighth edition (ISBN 978-1-285-46326-1).
Objectives:	We will learn in this class how to read and write mathematics, and how to craft proofs. We will learn about the fundamental concepts of sets, relations, and functions, and the specific proof tools of direct implication, contradiction, and induction. We will apply our mathematical reasoning to results in set theory, number theory, and combinatorics.
Learning Outcomes:	Student learning outcomes for this course include the practice and development of critical thinking skills, including: identifying the question or problem, analyzing evidence and developing arguments, and drawing conclusions based upon reason, arguments, and evidence.
Responsibilities:	You are responsible for attending class daily and maintaining comprehension of the material presented in class. Short problems will be presented on a roughly daily basis, and posted online after class. You must complete all assigned problems promptly, and attend examinations on the scheduled dates. Extracurricular interaction with your fellow students, and with the instructor, will be very useful in developing your comprehension.
Special needs:	Any scheduled absence during a quiz or examination, or any other special needs, must be brought to my attention during the first week of class. During a scheduled absence, you are expected to complete the daily assignments by e-mail. Absence due to unforseen emergencies will be dealt with on a case-by-case basis and must be documented.
Honesty:	There are many resources available to help you succeed in this class, including consultation during office hours, secondary texts, and cooperation with other students. It is important, however, that all papers handed in be the result of your individual comprehension of the course material. Duplication of others' work is both a disservice to your own education and a serious violation of the university's academic honesty policy.
Grades:	Daily problems will account for 30% of your grade, the three midterm examinations will each be worth 15%, and the final examination will be worth 25%. A 90% overall guarantees a grade of A–, 80% guarantees a B–, and 70% guarantees a C–.
Changes:	The syllabus is subject to change. Changes will be announced in class and updated online.

Course schedule

This schedule is tentative and may not reflect our progress at any particular time in the class; treat this as a rough guide only.

Tuesday	Thursday
1	August 26th Section 1.1	August 28th Section 1.2
2	September 2nd Section 1.3	September 4th Section 1.4
3	September 9th Section 1.5	September 11th Section 1.6
4	September 16th Section 1.7	September 18th Section 1.8
5	September 23rd Section 2.1, 2.2	September 25th Exam #1
6	September 30th Section 2.3	October 2nd Section 2.4
7	October 7th Midsemester break	October 9th Section 2.5, 2.6
8	October 14th Section 3.1	October 16th Section 3.2
9	October 21st Section 3.3	October 23rd Withdrawl date Section 3.4
10	October 28th Section 4.1	October 30th Section 4.2, 4.3
11	November 4th Section 4.4	November 6th Exam #2
12	November 11th Section 4.5	November 13th Section 5.1
13	November 18th Section 5.2	November 20th Section 5.3
14	November 25th Section 5.4	November 27th Thanksgiving break
15	December 2nd Section 5.5	December 4th Exam #3
16	December 9th Reading day	Friday, December 12th Final exam, 14:30–17:00

Solutions to the daily problems should be written in full sentences; while symbolic expressions can be used, they should be connected by written exposition. Solutions should be legible and grammatical, and are due at the beginning of class.

You may find it useful to type your solutions, although doing so is not necessary. In preparation for future mathematical studies, you may find the LaTeX mathematical typesetting tool to be well worth learning; to assist in that process if you elect to do so, a template will be provided for you to write your solutions. For help using LaTeX, please visit Dr. Wildstrom during office hours.

Due Tuesday, September 2 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): For both of the following compound statements, convert the English statement into a symbolic statement in propositional logic, complete a truth table for the symbolic statement, and identify the statement as either a tautology, a contradiction, or neither.
- If both P and Q are true, then P is false.
- Either P is true or the truth of P implies that Q is false.
Due Thursday, September 4 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): The following set of premises are adapted from a logic puzzle devised by Lewis Carroll:
1. The only articles of food that my doctor allows me to eat are not very rich.
2. Nothing that agrees with me is unsuitable for supper.
3. Wedding cake is always very rich.
4. My doctor allows me to eat all articles of food that are suitable for supper.
Let U be the set of all foods, and the propositions P(x), Q(x), R(x), S(x), and T(x) be respectively the claims "food x agrees with me", "food x is allowed by my doctor", "food x is suitable for supper", "food x is very rich", and "food x is wedding cake". In terms of these named propositions, write all four premises symbolically with universal or existential quantifiers.
Taking these premises to be true, if a particular item of food is a wedding cake, what else can be said about it?
Due Tuesday, September 9 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): Prove the following statements.
- For integers a, b, c, and d, if a divides b and c divides d, then ac divides bd.
- For integers a, b, and c, if ab divides c, then a divides c.
Due Thursday, September 11 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): Prove that for real numbers a and b, |a+b|≤|a|+|b|. You may find it useful to use the definition of absolute value, namely that for a real number x, the quantity |x| is equal to x if x≥0 and equal to –x otherwise.
Due Tuesday, September 16 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): Prove the following statements.
- For integers a and b, if a²(b²–2b) is odd, then a and b are odd.
- For positive real numbers a and b, the sum of a and b is at least as large as twice the square root of ab.
Due Thursday, September 18 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): Prove or disprove the following statements.
- There exists a positive real number x such that x²<√x.
- There exists an integer n which is divisible by 6 but is not divisible by 3.
Due Tuesday, September 23 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): Prove that for positive integers a, b, and c, if a divides bc and gcd(a,b)=1, then a divides c.
Due Thursday, September 25: Prepare for the exam! This PotD is ungraded, of course.
Due Tuesday, September 30 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): Let S={1,{1},2,{2,3}}. Find a set satisfying each of the following criteria, or explain why such a set does not exist.
- A set A such that A∈S and A⊆S.
- A set B such that B∈S and B∈P(S).
- A set C such that C∈S and C⊆P(S).
- A set D such that D∈P(S) and D⊆P(S).
Due Thursday, October 2 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source):
- Prove that for any sets A and B, P(A∩B)=P(A)∩P(B).
- Demonstrate that it is not generally true (i.e. disprove) that for any sets A and B, P(A∪B)=P(A)∪P(B).
- Prove that for any sets A and B, P(A)∪P(B)⊆P(A∪B).
Due Thursday, October 9 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): Prove (not with a Venn diagram, but with formal argument) or disprove each of the following statements:
- If A⊆C and B⊆D, then B–C⊆D–A.
- P(A)–P(B)⊆P(A–B).
- If A∪B⊆C∪D, A∩B=∅, and C⊆A, then B⊆D.
Due Tuesday, October 14 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): see attached PDF.
Due Thursday, October 16 (Question PDF, LaTeX template): Prove that for every positive integer n, (1/1)+(1/4)+(1/9)+…+(1/n²)≤2–(1/n).
Due Tuesday, October 21 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): Let a_n be defined by the recurrence a₀=3, a₁=–1, and a_n=2a_n–1+15a_n–2 for n≥2. Prove that a_n=2⋅(-3)ⁿ+5ⁿ for all nonnegative integers n.
Due Thursday, October 23 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): This is a bonus problem, and will earn up to 10 extra points towards your total PotD grade (i.e., in my spreadsheet, it is out of a total of 0 points, but you can earn up to 10 points on it). Let a_n be defined by the terms a₁=3, a₂=7, and a_n=a_n–1+3a_n–2. Prove that, for any positive integer n, a_n is even if and only if n is divisible by 3.
Due Tuesday, October 28 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): On this problem you can score 15 points out of 10 with a correct and complete answer! Let S={1,2,3,4}. Find eight different relations on S possessing each of the eight different combinations of the three fundamental relation properties (a relation can be reflexive or nonreflexive, symmetric or nonsymmetric, and transitive or nontransitive). Indicate which of the eight relations you present falls into each of the eight categories.
Due Thursday, October 30 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): see attached PDF.
Due Tuesday, November 4 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): Produce a multiplication table for Z₈, and use it to answer the following questions:
- Is there an integer n such that 7n≡3 (mod 8)?
- Is there an integer n such that 7n≡2 (mod 8)?
- Is there an integer n such that 6n≡3 (mod 8)?
- Is there an integer n such that 6n≡2 (mod 8)?
- In general, for which a and b does an≡b (mod 8) appear to have an integer solution? Why should this be the case?
Due Thursday, November 13 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): For a nonempty set S, let f:S→S be a function. Note that since f⊆S×S, f can also be regarded as a relation.
- Prove that if f is not the identity function f(x)=x, then f is non-reflexive when considered as a relation on S.
- Prove that f is symmetric when considered as a relation on S if and only if f(f(x))=xfor all x.
- Bonus problem: demonstrate that some functions other than the identity may be transitive when considered as a relation on S. Characterize all such functions.
Due Tuesday, November 18 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source):
- Prove that if f:A→B and g:B→C are both surjective, then g∘f is also surjective.
- Give an example of functions f:A→B and g:B→C which are not both surjective, but such that the composition g∘f is surjective.
- Prove that for functions f:A→B and g:B→C, if g∘f is injective, then f must also be injective.
- Give an example of functions f:A→B and g:B→C such that f is injective but g∘f is not injective.
Due Thursday, November 20 (Question PDF, LaTeX template): Given sets A and B, suppose that f:A→B and g:B→A are functions such that f∘g is the identity function on B (i.e., that for every b∈B, f(g(b))=b).
- Demonstrate an example of functions f and g on some sets A and B satisfying the above description such that g∘f is not the identity function on A, i.e. that there is some a∈A such that g(f(a))\neq a.
- Prove that if g is a surjective function, then g∘f is the identity function on A, i.e. for every a∈A, it is the case that g(f(a))=a.
Due Tuesday, November 25 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): see attached PDF.
Due Tuesday, December 2 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): Formally prove the following statements about the cardinalities of (not necessarily finite) sets—do not appeal to intuition!
- If A⊆B⊆C and |A|≥|C|, then |A|=|B|.
- If |A|≤|B|, then |P(A)|≤|P(B)|.

Return to Jake's teaching.

Quick links:

Course information:

Course schedule

Daily problems: