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

Quick links:

• Blackboard page for MATH 311-01
• Course syllabus, in PDF format, formatted for printing
• Exams
  • Practice Midterm 1 (solutions)
  • Midterm 1 (solutions)
  • Practice Midterm 2 (solutions)
  • Midterm 2 (solutions)
  • Practice Final (solutions)
  • Final Exam (solutions)
• Miscellany
  • A pigeonhole problem discussed in class, fully explained
  • Two fun applications of induction
  • Proof of the Cantor-Schröder-Bernstein Theorem

• Course information
• Daily problems

Course information:

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 praparation 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 September 4 (Question PDF, TeX template, Solution PDF, Solution TeX source): Let A, B, and C, be sets given by A={1,3,5}, B={n∈Z:0<n≤3}, and C={1,2,3,{1,3,5}}. For each of the following questions, briefly explain your reasoning.
  1. Calculate |A|, |B|, and |C|.
  2. Is B⊆A? Is A⊆C? Is B⊆C?
  3. Are any of these sets elements of each other?
  4. Without explicitly listing out the elements of any power sets, find at least one element of P(A)∩P(B).
  5. Without explicitly listing out the elements of any power sets, find at least one element of P(A)–P(B).
  6. Bonus: What, if any, relationship do you believe to hold between the two sets P(A)∩P(B) and P(A∩B)? What about P(A)∪P(B) and P(A∪B)?
• Due September 6 (Question PDF, TeX template, Solution PDF, Solution TeX source):
  1. For each r∈[0,1], let A_r=[r,r+1]. What would ⋃_r∈[0,1]A_r and ⋂_r∈[0,1]A_r be? Explain your reasoning.
  2. Give an example of three finite sets A, B, and C such that B is a partition of A, C is a partition of B, and |C|<|B|<|A|. Note that B will be a collection, and C will be a collection of collections.
• Due September 9 (Question PDF, TeX template, Solution PDF, Solution TeX source): Let A be the statement "Louisville is the capital of Kentucky", B be the statement "Frankfort is the capital of Kentucky", and C the statement "Louisville is the largest city in Kentucky". For each of the following statements, write the statement in symbols, write out a truth table for the symbolically written proposition, and indicate which line of the truth table corresponds to reality.
  1. "Louisville is neither the largest city in Kentucky nor its capital."
  2. "If Louisville is the capital of Kentucky, then so is Frankfort."
  3. "It is not the case that both Louisville and Frankfort are the capital of Kentucky."
  4. "If Frankfort is the capital of Kentucky, then either Louisville is also the capital or it is the largest city."
• Due September 11 (Question PDF, TeX template, Solution PDF, Solution TeX source):
  1. Suppose A and B are nonempty, disjoint subsets of a set S. If x∈S, indicate that each of the following is either always true, sometimes true, or never true (explain your logic):
     1. If x is an element of A, then x is not an element of B.
     2. If x is not an element of A, then x is an element of B.
     3. x is an element of A∪B.
     4. There is a nonempty set C such that both x∈A∪C and x∈B∪C.
  2. Show that, for statements P and Q, the statement (P∨Q)⇔(~P∧~Q) is a contradiction. What does this contradiction tell you, in words?
  3. Show that, for statements P and Q, the statement (P∧(P→Q))⇒Q is a tautology. Then state this expression in words.
• Due September 13 (Question PDF, TeX template, Solution PDF, Solution TeX source):
  1. Translate the following phrases in words into symbolic logic, and determine, with explanation, whether they are true or false.
     1. For every real number x, either x<5 or x≥6.
     2. There is an integer which is its own square.
  2. Translate the following phrases in symbolic logic into words, and determine, with explanation, whether they are true or false.
     1. ∃x∈Z:(x⁴=16)∧(x²-2x=0).
     2. ∀n∈N∃k∈N:k>n.
     3. ∃k∈N∀n∈N:k>n.
• Due September 16 (Question PDF, TeX template, Solution PDF, Solution TeX source):
  1. Prove that for a real number x, if x²+1/x²<2$, then x⁴+1/x⁴<2$. Discuss the extent to which this result is useful.
  2. Prove that for an integer n, if n is odd, then 6n³ is even. Can the statement of this proposition be made stronger?
  3. Prove that for an integer n, if n is even, then 3n²+4n-1 is odd.
• Due September 18 (Question PDF, TeX template, Solution PDF, Solution TeX source):
  1. We will use the following steps to prove that, for odd integers a and b and integer n, if an is even, then bn is even.
     1. First, prove the lemma that for an odd integer b and an integer n, if n is even, then bn is even.
     2. Then, prove the lemma that for an odd integer a and an integer n, if an is even, then n is even.
     3. Using the two previous lemmas, prove that for odd integers a and b and integer n, if an is even, then bn is even.
  2. Using those same two lemmas, prove that for an odd integer k and an integer n, the quantity kn is even if and only if n is even.
• Due September 20 (Question PDF, TeX template, Solution PDF, Solution TeX source):
  1. Prove that for integers a and b, if either a or b is odd, then a+b and ab have different parities.
  2. Prove that for integers m and n, if m and n have opposite parities, then 4|(m²+n²-1).
• Due September 23 (Question PDF, TeX template, Solution PDF, Solution TeX source):
  1. For integers x and y, prove that if 3 does not divide x and 3 does not divide y, then 3|(x²-y²).
  2. Let n be a natural number. Prove that if n≥14, then there are nonnegative integers a and b such that n=7a+3b.
• Due September 25 (Question PDF, TeX template, Solution PDF, Solution TeX source): For even integers x and y, prove that x²≡y² (mod 16) if and only if either both x≡0 (mod 4) and y≡0 (mod 4) or both x≡2 (mod 4) and y≡2 (mod 4).
• Due September 27 (Question PDF, TeX template, Solution PDF, Solution TeX source): For sets A and B, prove the following statements (formally—don't just appeal to a Venn diagram):
  1. A-B is disjoint from B-A.
  2. A∪B=A∩B if and only if A=B.
• Due September 30 (Question PDF, TeX template, Solution PDF, Solution TeX source):
  1. Prove that there are natural numbers a, b, and c, with a<b<c, such that a does not divide b or c and b does not divide c, however a divides bc, b divides ac, and c divides ab.
  2. Disprove the following conjecture: for all real numbers x and y, the square root of xy does not equal the product of the square roots of x and y.
  3. Disprove the following conjecture: for integers a and b, if ab and (a+b)² are of opposite parity, then a²b² and a+ab+b are of opposite parity.
  4. Disprove the conjecture that for integers n, a, and b, n|ab if and only if n|a or n|b.
  5. Bonus: Prove that given a finite set S of natural numbers such that no two distinct elements of S are divisible by each other, there exists a finite set T of natural numbers with |S|=|T| such that no two distinct numbers divide each other and every element of T divides any product of two other elements of T.
• Due October 2 (Question PDF, TeX template, Solution PDF, Solution TeX source):
  1. Prove that there is no largest number in the open interval (3,6).
  2. Demonstrate that the above result is not true of the closed interval [3,6]. What aspect of your proof would not work in this case?
  3. Prove that, for an irrational number α and a nonzero rational number x, their product αx is irrational.
• Due October 4 (Question PDF, TeX template, Solution PDF, Solution TeX source):
  1. Prove that if a²+1=2ⁿ for an integer a and integer n≥1, then a is odd.
  2. Use your result from the previous part to prove that there are no integer solutions to a²+1=2ⁿ for n≥2.
  3. Prove that x³+x²-1=0 has a unique real solution between x=2/3 and x=1.
• Due October 11 (Question PDF, TeX template, Solution PDF, Solution TeX source): These problems are both bonus (worth a total of up to 10 points out of 0) on the Pigeonhole Principle. Let X={1,2,3,4,5,6}. Below we will be working with A being a collection of subsets of X; that is to say, A⊆P(X).
  1. Show that it is possible to construct a collection A⊆P(X) with |A|=32 such that every two elements of A overlap: that is, such that for any S,T∈A, it is the case that S∩T≠∅. You do not need to explicitly list all 32 elements of A; simply describe a construction technique.
  2. Prove that it is not possible to construct a collection A⊆P(X) with |A|≥33 such that every two elements of A overlap: that is, regardless of our choice of A, there are some S,T∈A, such that S∩T=∅.
• Due October 14 (Question PDF, TeX template, Solution PDF, Solution TeX source):
  1. Prove inductively that for any real number a and real number r≠1, and natural number n, a+ar+ar²+…+ar^n-1=a(1-rⁿ)/(1-r).
  2. Prove inductively that for every natural number n, 7|(3⁴ⁿ⁺¹-5^2n-1).
• Due October 16 (Question PDF, TeX template, Solution PDF, Solution TeX source):
  1. The factorial of a natural number n, denoted n!, is the product of all the natural numbers up to that number; for instance, 5!=5×4×3×2×1=120. Prove that, for every integer n≥7, n!>3ⁿ.
  2. Let the function in natural numbers f(n) be given by the specific values f(1)=2 and f(2)=5 and the recursive formula f(n)=7f(n–1)-10f(n–2) for every n≥3. Prove that for all natural numbers n, f(n)=(5^n–1+5(2^n–1))/3.
  3. Briefly justify, based on the previous result, the assertion that 5ⁿ+5(2ⁿ) is divisible by 3 for all non-negative integers n.
• Due October 18 (Question PDF, TeX template, Solution PDF, Solution TeX source): Let F₁=1, F₂=1, and F_n=F_n–1+F_n–2 for n≥3. Prove that 4|F_n if and only if 6|n (hint: prove a stronger statement about F_n's equivalency modulo 4 for various n).
• Due October 21 (Question PDF, TeX template, Solution PDF, Solution TeX source): There are many pairs of primes with a difference of 2: 3 and 5, 5 and 7, 11 and 13, 17 and 19, 29 and 31, 2003663613×2¹⁹⁵⁰⁰⁰–1 and 2003663613×2¹⁹⁵⁰⁰⁰+1, and so forth. There is at least one triple of primes with a difference of 2: 3, 5, and 7. Prove that this is the only such triple, i.e., that if n≥3, then n, n+2, and n+4 are not all prime.
• Due October 23 (Question PDF, TeX template, Solution PDF, Solution TeX source):
  1. Prove that for all positive integers a, b, and c, gcd(gcd(a,b),c)=gcd(a,gcd(b,c)).
  2. Find an example of positive integers a, b, c, and d such that the six values gcd(a,b), gcd(a,c), gcd(a,d), gcd(b,c), gcd(b,d), and gcd(c,d) are all different.
• Due October 25 (Question PDF, TeX template, Solution PDF, Solution TeX source): Prove or disprove each of the following statements:
  1. For the Fibonacci sequence as defined elsewhere in this class (i.e. F₁=1, F₂=1, and F_n=F_n–1+F_n–2 for n≥3), it is the case that for all natural numbers n, F_n and F_n+1 are relatively prime.
  2. For all natural numbers a, b, and c, if gcd(a,b)=gcd(b,c), then gcd(a,b)=gcd(a,c).
• Due October 28 (Question PDF, TeX template, Solution PDF, Solution TeX source):
  1. Prove that, for any polynomial f(x) with non-negative integer coefficients, there is a natural number n such that f(n) is composite. (Historical note: people have proposed "prime-finding" functions like f(x)=x²+x+41; this proof demonstrates that no polynomial function generates only primes)
  2. Find the smallest number with exactly 12 natural-number factors (including itself and 1). Show your work! A calculator may help.
• Due October 30 (Question PDF, TeX template, Solution PDF, Solution TeX source):
  1. Prove that for an integer k, if 2^k–1 is prime, then k is prime (note that the converse is not true, since 11 is prime and 2¹¹–1 is composite).
  2. Prove that for an integer p, 2^p–1 is prime if and only if 2^p–1(2^p–1) is equal to the sum of its proper divisors. (As an example, 2³–1=7 is prime, and 2²(2³–1)=28 is equal to the sum of its proper divisors 1+2+4+7+14, while 2⁴–1=15 is not prime and 2³(2⁴–1)=120 is considerably less than the sum of its proper divisors 1+2+3+4+5+6+8+10+12+15+20+24+30+40+60).
• Due November 1 (Question PDF, TeX template, Solution PDF, Solution TeX source): There are eight different combinations of behaviors for relations which could be described by the three well-known properties: a relation could be either reflexive or non-reflexive, symmetric or non-symmetric, and transitive or non-transitive. For each of the eight possible combinations of properties, describe a relation which has that property. You may either name a set and a standard criterion/relation on that set (e.g. "the set of real numbers with the relation <") or identify a finite set and then explicity write out the relation on that set as a set of ordered pairs.
• Due November 4 (Question PDF, TeX template, Solution PDF, Solution TeX source): For a nonempty set S and relation R thereon, let the negation of R be the relation R described by either of the two following (equivalent) characterizations:
  • Considering relations as subsets of S×S, R=(S×S)-R.
  • For every pair a,b∈S, the statement aRb is true if and only if aRb is false.
  1. Prove that the negation of R is R.
  2. Do whichever of the following three instructions is actually a demonstration of a true statement (indicate which you are doing):
     • Prove that if R is reflexive, then R is reflexive.
     • Prove that if R is reflexive, then R is non-reflexive.
     • Demonstrate that reflexivity of R says nothing about R, by giving two examples where R is reflexive, but where the reflexivity of R is different between the two.
  3. Do whichever of the following three instructions is actually a demonstration of a true statement (indicate which you are doing):
     • Prove that if R is symmetric, then R is symmetric.
     • Prove that if R is symmetric, then R is non-symmetric.
     • Demonstrate that symmetry of R says nothing about R, by giving two examples where R is symmetric, but where the symmetry of R is different between the two.
  4. Do whichever of the following three instructions is actually a demonstration of a true statement (indicate which you are doing):
     • Prove that if R is transitive, then R is transitive.
     • Prove that if R is transitive, then R is non-transitive.
     • Demonstrate that transitivity of R says nothing about R, by giving two examples where R is transitive, but where the transitivity of R is different between the two.
• Due November 6 (Question PDF, TeX template, Solution PDF, Solution TeX source): Let [a]_m represent the congruence class of a modulo m. Prove that, for integers a and b, and natural numbers m and n, the following are equivalent (i.e. that each is true if and only if the others are):
  • [a]_m⊆[b]_n.
  • a≡b (mod n) and a+m≡b (mod n).
  • n|m and a≡b (mod n).
• Due November 8 (Question PDF, TeX template, Solution PDF, Solution TeX source): For a set A and B a proper subset of A, let f be a function from A to B. f is a subset of A×B, and thus a subset of A×A. We may thus consider f as a relation on A, and investigate its properties:
  1. Prove that, considered as a relation on A, f is not reflexive.
  2. Prove that, considered as a relation on A, f is not symetric.
  3. Give an example of two different functions (on different A and B, if you wish) which, when considered as relations on A, demonstrate both transitivity and non-transitivity.
• Due November 11 (Question PDF, TeX template, Solution PDF, Solution TeX source): For sets A, B, and C, and functions f:A→B and g:B→C, prove or disprove each of the following:
  1. If g∘f is injective, then f is injective.
  2. If g∘f is injective, then g is injective.
  3. If g∘f is surjective, then f is surjective.
  4. If g∘f is surjective, then g is surjective.
• Due November 13 (Question PDF, TeX template, Solution PDF, Solution TeX source): 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).
  1. 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.
  2. 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.
• No problem of the day due on November 15. Study up for the exam instead!
• Due November 20 (Question PDF, TeX template, Solution PDF, Solution TeX source): Demonstrate (by explicitly building the necessary functions) the following size-equivalencies:
  1. If S is the set of all finite subsets of N (e.g. {1,6,4,9}∈S, and {7,20,40}∈S, but {1,3,5,7,9,11,…}∉S), show that |S|=|N|.
  2. Show that the two intervals (0,1] and [1,∞) have the same cardinality (i.e. "number of elements", extended to the infinite sense).
  3. Show that Q∩(0,1) --- that is to say, the set of rational numbers between 0 and 1 --- has the same cardinality as N.
• Due November 22 (Question PDF, TeX template, Solution PDF, Solution TeX source): Recall that for sets A and B, the notation A^B describes the set of all functions from B to A.
  1. Demonstrate, with an explicitly described function or pair of functions, that |{1,2,3,4}^N|=|P(N)|.
  2. Demonstrate, with an explicitly described function or pair of functions, that |{1,2,3,4,5,6,7,8}^N|=|P(N)|; generalize the idea you use here and above.
  3. Based on your previous result, prove that for any finite set S with at least two elements, |S^N|=|P(N)|.
  4. Bonus: Prove that |N^N|=|P(N)|.
• Due November 25 (Question PDF, TeX template, Solution PDF, Solution TeX source): Refer to the question PDF for problem statement.
• Due December 4 (Question PDF, TeX template, Solution PDF, Solution TeX source):
  1. Prove that there are infinitely many prime numbers congruent to 5 modulo 6.
  2. 1. Prove that for any sets A and B, P(A∩B)=P(A)∩P(B).
     2. Prove that for sets A and B, P(A∪B)=P(A)∪P(B) if and only if A⊆B or B⊆A.
• Due December 6 (Question PDF, TeX template, Solution PDF, Solution TeX source: See question PDF for problem statement.
• Due December 9 (Question PDF, TeX template, Solution PDF, Solution TeX source: See question PDF for problem statement.