**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**