MATH 311-02, Fall 2014

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

## 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
Friday, December 12th
Final exam, 14:30–17:00

## Daily problems:

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 a2(b2–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 x2<√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 AS and AS.
• A set B such that BS and BP(S).
• A set C such that CS and CP(S).
• A set D such that DP(S) and DP(S).
• Due Thursday, October 2 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source):
• Prove that for any sets A and B, P(AB)=P(A)∩P(B).
• Demonstrate that it is not generally true (i.e. disprove) that for any sets A and B, P(AB)=P(A)∪P(B).
• Prove that for any sets A and B, P(A)∪P(B)⊆P(AB).
• 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 AC and BD, then BCDA.
• P(A)–P(B)⊆P(AB).
• If ABCD, AB=∅, and CA, then BD.
• 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/n2)≤2–(1/n).
• Due Tuesday, October 21 (Question PDF, LaTeX template, Solution PDF, Solution LaTeX source): Let an be defined by the recurrence a0=3, a1=–1, and an=2an–1+15an–2 for n≥2. Prove that an=2⋅(-3)n+5n 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 an be defined by the terms a1=3, a2=7, and an=an–1+3an–2. Prove that, for any positive integer n, an 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 Z8, 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 anb (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:SS be a function. Note that since fS×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:AB and g:BC are both surjective, then gf is also surjective.
• Give an example of functions f:AB and g:BC which are not both surjective, but such that the composition gf is surjective.
• Prove that for functions f:AB and g:BC, if gf is injective, then f must also be injective.
• Give an example of functions f:AB and g:BC such that f is injective but gf is not injective.
• Due Thursday, November 20 (Question PDF, LaTeX template): Given sets A and B, suppose that f:AB and g:BA are functions such that fg is the identity function on B (i.e., that for every bB, f(g(b))=b).
• Demonstrate an example of functions f and g on some sets A and B satisfying the above description such that gf 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 gf 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 ABC and |A|≥|C|, then |A|=|B|.
• If |A|≤|B|, then |P(A)|≤|P(B)|. 