COURSE PROGRESS ON PREVIOUS WEEKS


WEEK 6
M: Midterm.
W: Completion of the proof of the division algorithm. Greatest common divisor. Proof of the existenced of the greatest common divisor using well-ordering of N -- beginning.
F: Completion of the proof of the existence of the greatest common divisor. Congruence modulo n. Criterion: a,b are congruent modulo n iff n is a divisor of a-b. Theorem: if n is nonzero a,a' are congruent modulo n and b,b' are congruent modulo n then a+b is congruent with a'+b' modulo n, ab is congruent modulo a'b' modulo n, and a^k is congruent modulo a'^k modulo n for every integer k>0. Recommended practice problems: Book, Page 45, Exercise 3.1.1 -- 3.1.5 and Page 46, Exercise 3.1.7 -- 3.1.10.

WEEK 5
M: Proof (with a wrinkle) by induction of: If $n\ge 5$ then a set with n elements has precisely n!/5!(n-5)! 5-element subsets. Correction of the wrinkle is a Homework 3 problem. Strong induction. Sketch of a proof by strong induction of: Every integer >1 is divisible by a prime. Recommended practice problems: Book, Page 95, Exercise 5.4.1, 5.4.3, 5.4.4 and Page 96, Exercise 5.4.5 and 5.4.6 Please work through Section 5.3 from the book.  
W: Discussion of the base step in connection with strong induction. Well-ordering principle. Lemma: if d is a common divisor of a,b then d is a divisor of any linear combination of a,b with integral coefficients. Example of the use of well-ordering principle: The division algorithm -- the existence part. Recommended practice problems: Book, Page 89, Exercise 5.3.3 and 5.3.5
F: Midterm review.

WEEK 4
M: (1) Example of a direct proof: Division algorithm for base 5, that is the statement: If 5k+r = 5k'+r' and 0\le r,r' < 5 then k=k' and r=r'. Task for thinking at home: Rewrite the proof for a general basis b>1. (2) Proof by contradiction: The square root of 3 is not rational. Task for thinking at home: Prove by cases (the case split is according to what is the remainder after dividing m by 3) that if m is an integer and m^2 is divisible by 3 then m is divisible by 3. Recommended practice problems: Book, Page 31, Exercises 2.2.7 -- 2.2.13 Please work through Sections 5.1 and 5.2 from the book.  
W: Proof of : There exit infinitely many primes. Lemma: Every integer >1 is divisible by a prime. Proof of the Lemma will come later. Discussion on how to read proofs with understanding and how to approach writing proofs. Recommended practice problems: Book, Page 83, Exercises 5.2.2, 5.2.3, 5.2.4, 5.2.6 Please work through Section 5.4 from the book.  
F: Examples on induction: (a) The sum of the first n squares is equal to n(n+1)(2n+1)/6, and (b) A set with n elements has 2^n subsets.

WEEK 3
M: Examples on statements with quantifiers:
(1) x is a prime (3 various ways)
(2) The equation x^2=1 has at least/most two distinct solutions
(3) The set A has at least/most two distinct elements
(4) The empty set and some statemtnes about the empty set.
(5) x is the largest element of set A\subseteq\matbb{R}
Alternating quantifiers. First exmple: (1) A\subseteq\mathbb{R} has/does not have a largest element.
W: Recap of example (1) on alternating quantifiers. More examples on alternating quantifiers: (2) A\subseteq\mathbb{Z}: (a) A has at least two even numbers. (b) A has arbitrarily large (unboundedly many) even numbers. (Several ways of expressing this.) (3) Between any two rational numbers there is another rational number. General rules for variables in quantified statements. Negation of the expression x < z < y. Please work through Section 2.3 from the book.  
F: Wrap up on formal logic: (a) Allowed/now allowed abbreviations for quantifiers, (b) Do not use the popular symbols for therefore and because, Syntax of the symbolic language. Types of proofs: (i) Direct: If n is even then n^3 is even. (ii) Indirect - proof of a contraposition: If n^3 is even then $n$ is even. (iii) Proof by cases: If n is an integer then n^2 divided by 3 gives remainder 0 or 1. Recommended practice problems: Book, page 30, Problems 2.2.1, 2.2.2, 2.2.3, 2.2.5 and page 31, Problem 2.2.6.

WEEK 2
M: Sentential connection equivalence. Set difference, symmetric difference. Tautology, contradiction, contrapositive, converse, de Morgan laws. Negating sentential connectives. Recommended practice problems: Book, p.16 Exercise 2.1.1, 2.1.2, 2.1.3,2.1.5, 2.1.8, 2.1.9, p.59 Exercise 4.2.3, p.64 Exercise 4.3.1 and p.65 Exercise 4.3.2
W: Statements with variables, Existential and universal quantifiers. Specifying domains: abbreviated and unabbreviated forms. Resemblance existential quantifier <--> disjunction, universal quantifier <--> conjunction. Examples of quantified statements with one variable. Please read Section 2.3 from the book.   Recommended practice problems: Book, p.38, Exercise 2.3.2, 2.3.8, 2.3.9 and 2.3.11
F: Negating quantifiers, both abbreviated and unabbreviated variant. Examples on statements with quantifiers: (1) There exists an integer larger than 1. (2) x is an even integer. (3) x is divisible by 3. To think about: (4) x is a prime.

WEEK 1
M: Basic course information. Sentential connectives conjunction, disjunction and negation. Sets.
W:More about membership relation. Inclusion. Operations intersection, union and complementation and their mirroring of conjunction, disjunction and complementation. Commutativity, associativity and distributivity of set operations and the corresponding sentential connectives. Please read the following from the book: Chapter 1 (this is Introduction), Section 2.1 and Sections 4.1 - 4.3.
F: Distributivity of conjunction and disjunction: Example. Implication and examples. Checking equality of sets using truth tables.

WEEK 0    
F: Informal discussion of mathematical proofs.

HOME   MATH 13