MATH 2513 - Discrete Mathematical Structures, Section 002 - Spring 2019
TR 10:30-11:45 a.m., 224 PHSC

Instructor: Prof. Nikola Petrov, 1101 PHSC, npetrov AT ou.edu
Office Hours: Mon 2:30-3:30, Wed 10:30-11:30 (subject to change), or by appointment, in 1101 PHSC

Teaching Assistant: Emily Cowie, lecowie AT ou.edu

First day handout

Prerequisite: MATH 2423 or MATH 2924 or concurrent enrollment.

Course catalog description: A course for math majors or prospective math majors. Provides an introduction to discrete concepts such as finite sets and structures, and their properties and applications. Also exposes students to the basic procedures and styles of mathematical proof. Topics include basic set theory, functions, integers, symbolic logic, predicate calculus, induction, counting techniques, graphs and trees. Other topics from combinatorics, probability, relations, Boolean algebras or automata theory may be covered as time permits.

Text: Richard Hammack, Book of Proof, 3rd edition, which Prof. Hammack has generously made freely available on the web at
https://www.people.vcu.edu/~rhammack/BookOfProof/

Homework (due at the beginning of class on the due date):

• Homework 1, due January 24 (Thursday).
• Homework 2, due January 31 (Thursday).
• Homework 3, due February 7 (Thursday).
• Homework 4, due February 14 (Thursday).
• Homework 5, due February 21 (Thursday).
• Homework 6, due March 7 (Thursday).
• Homework 7, due March 14 (Thursday).
• Homework 8, due March 28 (Thursday).
• Homework 9, due April 4 (Thursday).
• Homework 10, due April 11 (Thursday).
• Homework 11, due April 25 (Thursday).
• Homework 12, due May 2 (Thursday).
• "Homework" 13a, not to be turned in.
• "Homework" 13b, not to be turned in.

Course content:

• Logic and proofs: propositional logic, propositional equivalences, predicates and quantifiers, inference, proof methods.
• Basic structures: sets, set operations, functions, sequences and summations.
• Integers: integers and division, primes and greatest common divisors.
• Induction and recursion: mathematical induction, recursive algorithms.
• Counting: basics of counting, pigeonhole principle, permutations, combinations, binomial coefficients, binomial theorem.
• Relations: relations and their properties, equivalence relations.

Content of the lectures:

• Lecture 1 (Tue, Jan 15): Introduction to sets: sets, elements of a set, notations for sets, a∈A; infinite and finite sets, cardinality; important sets: natural numbers N, integers Z, real numbers R, rational numbers Q; empty set; set-builder notation [Sec. 1.1]
  The Cartesian product: origin of the adjective "Cartesian"; ordered pair, Cartesian product of two sets; example: a deck of cards; the plane R²=R×R; generalization: A₁×...×A_n, Cartesian power: Aⁿ [Sec. 1.2]
• Lecture 2 (Thu, Jan 17): Subsets: subsets; equality of two sets; a tree method for listing all the subsets of a finite sets; restating the tree method in terms of binary numbers; a finite set A has 2^|A| subsets; exercises on elements and subsets of sets [Sec. 1.3]
  Power set: definition of a power set of a set; examples [Sec. 1.4]
  Union, intersection, difference: definition of union, intersection, and difference of two sets; exercises [Sec. 1.5]
• Lecture 3 (Tue, Jan 22): Union, intersection, difference (cont.): solving the problem from Handout B about the subsets of the plane [Sec. 1.5]
  Complement: universal set (universe), definition and examples of complement [Sec. 1.6]
  Venn diagrams: examples of Venn diagrams [Sec. 1.7]
  Indexed sets: definition and examples of a family of indexed sets [Sec. 1.8]
  Statements: definition and examples of statements and non-statements; examples of indexed statements [Sec. 2.1]
  And, or, not: conjunction ("and") and disjunction ("or") of two statements; truth tables; remarks about the colloquial usage of the word "or"; negation ("not") of a statement; examples [Sec. 2.2]
  Reading assignment (optional): Russel's paradox [Sec. 1.10]
• Lecture 4 (Thu, Jan 24): Conditional statements: conditional statement (implication, "implies"); antecedent and consequent; truth table; different ways to say that P⇒Q; equivalence of P⇒Q and (∼P)∨Q; examples [Sec. 2.3]
  Biconditional statements: converse Q⇒P of a statement P⇒Q; biconditional P⇔Q ("if and only if", "iff"); truth table; equivalence of P⇔Q and (P⇒Q)∧(Q⇒P); different ways to say that P⇔Q [Sec. 2.4]
  Logical statements and electric circuits: basic logical elements in electronics: NOT, AND, OR; exercises with different logical statements and electronic circuits.
  Logical equivalence: logical equivalence of two statements; examples studied so far: P⇒Q = (∼P)∨Q, P⇔Q = (P⇒Q)∧(Q⇒P); laws for formal manipulation with logical statements: contrapositive law, De Morgan's laws, commutative laws, distributive laws, associative laws; example of using the laws to simplify a complicated statement [Sec. 2.6]
  Reading assignment (mandatory): truth tables for statements [Sec. 2.5]
• Lecture 5 (Tue, Jan 29): Review of the terminology studied so far: statements, logical connectives, unary and binary connectives, negation, conjunction, disjunction, implication, biconditional; tautology, contradiction.
  Quantifiers: universal and existential quantifiers, examples, nested quantifiers [Sec. 2.7]
  More on conditional statements: examples of using quantifiers and translating conversational statements in mathematical notation [Sec. 2.8]
• Lecture 6 (Thu, Jan 31): Translating English to symbolic logic: rewriting the Mean Value Theorem and the Goldbach Conjecture by using mathematical notation; expressing a universally quantified statement as a conditional statement; examples [Sec. 2.9]
  Negating statements: using De Morgan's Laws to negate statements with quantifiers; examples; rewriting the definition of a surjective function by using mathematical notation; writing the definition of a non-surjective function by using mathematical notation; an example [Sec. 2.10]
• Lecture 7 (Tue, Feb 5): Translating English to symbolic logic (cont.): coming up with a definition of a limit of a sequence: lim a_n=a if ∀ε>0 ∃K, ∀n>K, |a_n−a|<ε; proving that the sequence a_n=1/n² converges to 0; defining what it means that the sequence (a_n) does not converge to a; exercise: prove that the sequence a_n=1/n³ does not converge to 1/100.
  Logical inference:
  • modus ponens: [(P⇒Q)∧P] ∴ Q, based on the tautology [[(P⇒Q)∧P]⇒Q] = T;
  • modus tollens: [(P⇒Q)∧(∼Q)] ∴ ∼P;
  • transitivity (hypothetical syllogism): [(P⇒Q)∧(Q⇒R)] ∴ (P⇒R);
  • elimination (disjunctive syllogism): [(P∨Q)∧(∼P)] ∴ Q;
  • specialization (simplification): (P∧Q) ∴ P;
  • generalization (addition): P ∴ (P∨Q);
  • contradiction rule: [(∼P)⇒C] ∴ P;
  • cases: [(P∨Q)∧(P⇒R)∧(Q⇒R)] ∴ R.
  [Sec. 2.11; you do need to know only modus ponens and modus tollens]
• Lecture 8 (Thu, Feb 7): Lists: a list - an ordered sequence of objects; entries of a list, length of a list, an empty list, definition of equality of two lists, a string; examples: finite sequence of coin tosses, finite sequence of tosses of a dime and a quarter, representing numbers in a computer, bits and bytes [Sec. 3.1]
  The Multiplication Principle: example: making a list, using a tree to represent the process; Multiplication Principle; example: licence plates; one has to specify if repetition is allowed or not; more examples [Sec. 3.2]
• Lecture 9 (Thu, Feb 12): The Addition and Subtraction Principles: the Addition Principle; a partition of a set; solving Example 3.3(d) by using the Addition Principle; the Subtraction Principle; solving Example 3.3(d) by using the Subtraction Principle [Sec. 3.3]
  Factorials and permutations: counting the non-repetitive lists of length n; factorial of a non-negative number; permutation; k-permutation of a set of n elements; number of k-permutation of a set of n elements: P(n,k)=n!/(n−k)!; computing P(n,k) in practice (avoiding computations of factorials of large numbers) [Sec. 3.4]
  Reading assignment: Examples 3.9, 3.10 on page 83.
• Lecture 10 (Thu, Feb 14): Counting subsets: definition of "n choose k", denoted C(n,k), as a number of subsets of cardinality k chosen from an n-element set; example of computing C(4,k) for 0≤k≤n; conjecture: C(n,k)=C(n,n−k); proof of the conjecture; deriving a formula for C(n,k) by computing the number of lists that correspond to the same subset, result: C(n,k)=P(n,k)/k!=n!/[k!(n−k)!]; examples (cards, lottery) [Sec. 3.5]
  Pascal's triangle and the binomial formula: Theorem: C(n+1,k)=C(n,k−1)+C(n,k); proofs:
  • Method 1: elementary algebra;
  • Method 2: let the set A consist of (n+1) elements, of which one element is "special" (different from the others);
    • C(n+1,k) can be interpreted as the number of subsets of A of size k;
    • such subsets can either contain the special element or not contain it;
    • the number of ways we can choose a subset that contains the special element is C(n,k−1) [the special element is already chosen, so it remains to choose (k−1) elements from the remaining n "non-special" elements of the set A];
    • the number of ways we can choose a subset that does not contain the special element is C(n,k) [since we have to choose all k elements of the subset out of the n "non-special" elements of A]
  [page 90 of Sec. 3.6]
• Lecture 11 (Tue, Feb 19) Pascal's triangle and the binomial formula (cont.): building Pascal's triangle based on the formula C(n+1,k)=C(n,k−1)+C(n,k); triangular numbers: 1, 3, 6, 10, 15, 21,...; "pyramidal" numbers: 1, 4, 10, 20, 35,...; the symmetry of the Pascal's triangle with respect to interchanging left and right is based on the inequality C(n,k)=C(n,n−k); the Binomial Theorem - statement and examples; elementary examples of using the theorem: proof that the sum over k from 0 to n of C(n,k) is 2ⁿ, proof that the sum over k from 0 to n of (−1)^kC(n,k) is 0; a digression: a formula for (1+x)^α for any α∉{0,1,2,3,...} (the Maclaurin expansion of the function ƒ(x)=(1+x)^α); Stirling's formula: n!=(2π)^1/2n^n+(1/2)e⁻ⁿ [Sec. 3.6]
  The Inclusion-Exclusion Principle: |A∪B|=|A|+|B|−|A∩B|; generalization for the cardinality of the union of n finite sets [Sec. 3.7]
• Lecture 12 (Thu, Feb 21): The Inclusion-Exclusion Principle (cont.): obtaining an upper and lower bound on the cardinality of the intersection of two sets by using the Inclusion-Exclusion Principle [Sec. 3.7]
  The Division and Pigeonhole Principles: statement of the Pigeonhole Principle; example of application (Example 3.24); example of application: prove that there exists a multiple of 7 that can be written with only 1's and 0's (in the decimal system) - (1) observation: if two numbers have the same remainder when divided by 7, then their difference is divisible by 7, (2) strategy: find two numbers that have the same remainder when divided by 7, then take their difference, (3) the remainder in division by 7 can be 0,1,2,3,4,5,6, (4) write the numbers 1, 11, 111, 1111, 11111, 111111, 1111111, and consider their reminders when you divide each of them by 7 [Sec. 3.9]
• Lecture 13 (Tue, Feb 26): Exam 1 (on Sections 1.1-1.8, 2.1-2.11, 3.1-3.6, covered in Lectures 1-11 and Homework 1-5)
• Lecture 14 (Thu, Feb 28): Direct proof: axiomatic structure of Mathematics: definitions, axioms, theorems (also lemmata, propositions); examples of theorems; definitions: even and odd integers, parity of an integer, a divides b, a is a divisor of b, b is a multiple of a, prime and composite numbers, greatest common divisor least common multiple of two integers; the Division Algorithm;
  discussion of the implication P⇒Q and its relation to the direct proof; discussion of the proof of the Proposition: the sum of two even numbers is even; common mistakes:
  • arguing from example,
  • using the same letter for different purposes,
  • jumping to a conclusion (i.e., assuming without a proof that the angles at the base of an isosceles triangle are equal),
  • circular reasoning (historical example: circular reasoning in the "proofs" of Euclid Fifth Postulate),
  • confusion between what is known and what is still to be shown,
  • confusion between "any" and "some";
  remark on the meaning of "arbitrarily chosen" in the proof of a proposition of the type "If P(x), then Q(x) for every x∈D"; proof that for any x>0 and y>0, if x≤y, then x^1/2≤y^1/2 [pages 113-122 of Chapter 4]
  Reading assignment (mandatory): read the examples of simple proofs on pages 120-122 of the book.
• Lecture 15 (Tue, Mar 5): Direct proof (cont.): direct proof that n²−7n is even by considering the two cases: n even and n odd; a historic digression about the proof by cases of the Four Color Theorem by Kenneth Appel and Wolfgang Haken, who reduced the proof of the theorem to 1936 cases that were checked on a computer (this was the first major theorem to be proved with extensive computer assistance); proof that the Geometric Mean of two numbers does not exceed their Arithmetic Mean; a digression on different means in mathematics:
  • Arithmetic Mean AM(x₁,…,x_n)=(x₁+…+x_n)/n,
  • Geometric Mean GM(x₁,…,x_n)=(x₁⋅…⋅x_n)^1/n,
  • Harmonic Mean HM(x₁,…,x_n)=(x₁⁻¹+…+x_n⁻¹)⁻¹,
  • Generalized (p-Power) Mean: for p>0, M_p(x₁,…,x_n)=(x₁^p+…+x_n^p)^1/p
  general inequality between the Arithmetic Mean and the Geometric mean [pages 123-125 of Chapter 4]
  Contrapositive proof: for a statement P⇒Q, definitions of its contrapositive (∼Q)⇒(∼P), converse Q⇒P, and inverse (∼P)⇒(∼Q); equivalence of P⇒Q and its contrapositive; outline of a contrapositive proof; examples; using DeMorgan's laws to prove statements like P⇒(Q∧R) and P⇒(Q∨R) [pages 128-131 of Chapter 5]
  Reading assignment: Treating similar cases [Sec. 4.5 on pages 125, 126]
• Lecture 16 (Thu, Mar 7): Contrapositive proof (cont.): congruence of integers - definition, examples, propositions [pages 131-133 of Chapter 5]
  Proof by contradiction: outline of a proof by contradiction; rational and irrational numbers; proof ot the irrationality of 2^1/2 [pages 137-139 of Chapter 6]
  Digression: famous geometric problems of Greek mathematics:
  • angle trisection,
  • doubling the cube,
  • squaring the circle
  (the first two were proved impossible to solve in 1837 by Pierre Wantzel, the impossibility of the third one follows from the fact that the number π is transcendental).
  Reading assignment (mandatory): Mathematical writing [Sec. 5.3 on pages 133-135]
• Lecture 17 (Tue, Mar 12): Proof by contradiction (cont.): another stunning result: proof that there are infinitely many prime numbers; proving conditional statements by contradiction by using the logical equivalence of ∼(P⇒Q) and P∧∼Q; example: proving that if a³ is even, then a is even; using DeMorgan's laws to prove statements of the form P⇒(Q∨R) by contradiction: ∼[P⇒(Q∨R)] =  P∧(∼Q)∧(∼R); example: proving that if b is an arbitrary integer and a is an integer greater than or equal to 2, then a divides b or b+1; discussion of Quiz 4; discussion of the combinatorial proof of the identity from Exercise 3.6/12 of Hammack's book [pages 140-142 of Sec. 6.1 and 6.2]
  Reading assignment (recommended): pages 142 and 143 of Sec. 6.3 and 6.4 of Hammack's book.
• Lecture 18 (Thu, Mar 14): Proving non-conditional statements: if-and-only-if proof: to prove that P⇔Q, one needs to prove that P⇒Q and Q⇒P; example: proving that n is odd if and only if n³ is odd [direct proof of (n odd)⇔(n³ odd) and contrapositive proof of (n³ odd)⇔(n odd)]; proof that several statements are equivalent: the most economical way to prove that the statements P, Q, R, and S are equivalent is to prove that P⇒Q⇒R⇒S⇒P (the order does not matter); existence proofs - simple examples; constructive vs. non-constructive proofs - example: a non-constructive and a constructive proof that there exist irrational numbers α and β such that α^β is rational
  [Chapter 7 (skip the propositions on pages 152 and 153)]
• Lecture 19 (Tue, Mar 26): Proofs involving sets: refresher on operations on sets: complement, union, intersection, set difference, Cartesian product; how to prove that a∈A: if A={x:P(x)}, then we need to prove that P(a) is true; how to prove that A⊆B: direct proof (prove that a∈A implies that a∈B) or contrapositive proof (prove that a∉B implies that a∉A); examples; how to prove that A=B: prove that A⊆B and that B⊆A; example: proving the distributive property A∪(B∩C)=(A∪B)∩(A∪C)
  [pages 157-165 Chapter 8]
  Reading assignment (strongly recommended): Read all examples from Sec. 8.1-8.3 of Hammack's book.
• Lecture 20 (Thu, Mar 28): Disproof: disproving universal statement: using that ∼[∀x∈S,P(x)] is equivalent to ∃x₀∈S,∼P(x₀), to disprove the statement ∀x∈S,P(x), it is enough to produce a counterexample, i.e., an element x₀∈S for which P(x₀) is false; an example; disproving existence statements; example [Chapter 9]
  Mathematical induction: a geometric observation - bilding a square by adding the consecutive odd integers; conjecture: S_n: 1+3+5+...+(2n−1)=n²; method of mathematical induction: Step 1 (basis step): Prove S₁, Step 2 (inductive step): assume that S_k is true for some k∈N and prove that this implies that S_k+1; proof of our conjecture 1+3+5+...+(2n−1)=n² for any n∈N; another example: proof that 3|(7ⁿ−4ⁿ) by induction [pages 180-183 of Chapter 10]
• Lecture 21 (Tue, Apr 2): Mathematical induction (cont.): example: computing the sum of the squares of the first n natural numbers, using this to compute integral of x² from 0 to 1 by taking the limit of the right Riemann sum; example: Bernoulli identity; example: binomial theorem (sketch of proof by induction); idea of strong induction [pages 180-186 of Chapter 10]
• Lecture 22 (Thu, Apr 4): Mathematical induction (cont.): example: proof of the formula 1+q+q²+q³+⋅⋅⋅+qⁿ =(1−qⁿ)/(1−q) by induction; using this formula to obtain the formula for the sum of the geometric series for |q|<1; strong induction; example: using strong induction to prove that any postage of 12 cents can be made only with 3 cent and 7 cent coins; example: proof of DeMorgan's law for the complement of the intersection of n sets by using strong induction; definition of the Fibonacci numbers; proof that the limit of F_n+1/F_n equals (1+5^1/2)/2 (the golden ratio) [pages 187, 188, 193, 194 of Chapter 10]
• Lecture 23 (Tue, Apr 9) Mathematical induction (cont.): one last example: Exercise 25 from Chapter 10 [page 196 of Chapter 10]
  Relations: motivation of the definition of relation on a set A as a subset of A×A; definition of relation on a set; example: relation < on the set {1,2,3,4}; example: relation = on the set {1,2,3,4}; representing a relation on A by arrows between the elements of A; example: relation > on Z [Sec. 11.1]
• Lecture 24 (Thu, Apr 11) Properties of relations: definition of reflexive, symmetric, and transitive relations; examples: relation < on Z, relation ≤ on Z, relation ≠ on Z, relation = on Z, relation ≡(mod n) on Z [Sec. 11.2]
  Equivalence relations: definition of an equivalence relation; examples: = , ≡(mod n), and "has the same parity as" are equivalence relations on Z; definition of an equivalence class [a] containing an element a∈A (with respect to an equivalence relation) [pages 210, 211 of Sec. 11.3]
• Lecture 25 (Tue, Apr 16): Exam 2 (on Sec. 3.7, 3.9, Ch. 4, Sec. 5.1, 5.2, Ch. 6, 7, Sec. 8.1-8.3, Ch. 9, Sec. 10.1, 10.2, 10.5, covered in Lectures 12, 14-22 and Homework 6-10)
• Lecture 26 (Thu, Apr 18): Equivalence relations (cont.): examples of different equivalent relations on {1,2,3} and the corresponding equivalence classes; equivalence classes on the set of polynomials; equivalence classes corresponding to the equivalence relation ≡(mod n) on Z; equivalence classes of rational numbers with the same value; indefinite integrals as equivalence classes [Sec. 11.3]
  Equivalence classes and partitions: Theorem: [a]=[b] if and only if aRb [page 215 of Sec. 11.4]
  Thinking/reading assignment (mandatory): Finish yourself the proof of Theorem 11.1 started in class; indicate where exactly you used the fact that R is an equivalence relation (i.e., that it is reflexive, symmetric, and transitive).
• Lecture 27 (Tue, Apr 23): Equivalence classes and partitions (cont.): definition of a partition of a set A; examples of partitions and of non-partitions of the set {1,2,3,4}; partitioning Z into odd and even integers; partitioning R into non-zero and zero integers; partitioning Z into three classes depending on the value of the remainder of the division of a number by 3; Theorem: given an equivalence relation R on a set A, the set {[a]}_a∈A of equivalence classes of R forms a partition of A [Sec. 11.4]
  Relations between sets: definition of a relation R between sets A and B as a subset of A×B; example: A={1,2}, B={the power set of A} [Sec. 11.6]
• Lecture 28 (Thu, Apr 25): Functions: motivation of the need for a general definition of a function; definition of a function ƒ:A→B as a relation ƒ, i.e., as a subset ƒ of A×B; domain, codomain, range of a function; examples; definition of equality between two functions (note: the codomain is inconsequential!) [Sec. 12.1]
  Injective and surjective functions: definition of injective, surjective, and bijective functions; pictorial representation of these properties; examples [pages 228-230 of Sec. 12.2]
• Lecture 29 (Tue, Apr 30): Injective and surjective functions (cont.): proving that a function ƒ:A→B is injective by a direct proof (take any a and a' in A such that a≠a' and prove that ƒ(a)≠ƒ(a')) or by a contrapositive proof (assume that a and a' in A are such that ƒ(a)=ƒ(a') and show that a=a'); proving that a function ƒ:A→B not is injective (produce a counterexample, i.e., elements a and a' in A such that a≠a' but ƒ(a)=ƒ(a'); proving that a function ƒ:A→B is surjective (for an arbitrary b∈B, find an element a∈A such that ƒ(a)=b); an example: ƒ:R−{3}→R given by ƒ(x)=5/(x−3) is injective (check the derivative) but not surjective; an example: ƒ:Z×Z→Z×Z given by ƒ(m,n)=(m+n,m+3n) is injective (by a contrapositive proof) but not surjective [Sec. 12.2]
  The Pigeonhole Principle revisited: considering the Pigeonhole Principle in the light of the new concept of a function; an example (the Proposition from page 234) [Sec. 12.3]
• Lecture 30 (Thu, May 2) Composition: definition of composition; examples; the composition associative, but generally not commutative; if both ƒ:A→B and g:B→C are injective, then g∘ƒ:A→C is injective; if both ƒ:A→B and g:B→C are surjective, then g∘ƒ:A→C is surjective [Sec. 12.4]
  Inverse functions: motivation; identity function on a set; definition of an inverse function; examples [Sec. 12.5]
  Just for fun: The Königsberg's bridges problem, solved by Leonard Euler in 1736 - the beginnings of graph theory and the idea of topology.

Good to know:

• The Greek_alphabet.