Mathematical Skills

Time: Wednesdays 10:40 - 12:10 (on Dean's Day, 8 November, there will be no lecture)

Place: T5 (T149, Troja OP - 1.patro/1st floor. V Holešovičkách 747/2, 180 00 Praha 8)

Classes for the course Mathematical Skills in the winter semester of 2017 give an introduction to propositional logic and predicate first-order logic, proof techniques such as mathematical induction and proof by contradiction, and a variety of example problems that illustrate different aspects of mathematical proof. Classes also enable students to consolidate their learning and mathematical background to help follow the Mathematical Analysis I, Discrete Mathematics I and Linear Algebra I courses.

Mathematical Skills is an optional course, although credits are awarded for regular participation in classes and performance on the two tests that will be set near the middle and at the end of the semester.

Resources

K.R. Rosen, Discrete Mathematics and Its Applications, 7th ed., 2012.

For those of a logic bent, see e.g. A.G. Hamilton, Logic for Mathematicians, revised ed. 1988

J. D'Angelo and D. West, Mathematical Thinking: Problem-solving and Proofs, 2nd edition, 2000.

Material covered

4 October

Axiom, definition. Statements (either true or false): theorem, proposition, observation; lemma; corollary. Claim, conjecture. Counterexample.

Truth functions. Negation. Conjunction (and). Disjunction (or) - exclusive or, inclusive or. Implication (if ... then...). Equivalence (if and only if). Proof as valid arguments transmitting truth of a set of statements known to be true to another. Tautology, e.g., "a falsehood implies anything"; modus ponens: if ((P implies Q) and P) then Q.

11 October

DeMorgan's laws. Disjunctive normal form (DNF), conjunctive normal form (CNF). Atomic propositions (variables taking truth values). Compound propositions (well-formed formualas - wffs). Logical equivalence.

18 October

Logical equivalences used in proof strategies: contrapositive, proof by contradiction, proof by cases. Examples of each type of proof. "By symmetry", "without loss of generality".

25 October

Examples of proofs by contradiction (irrationality of square root of prime number, infinitude of primes, of primes congruent to 3 modulo 4). Pigeon-hole Principle (proof by contradiction). Ramsey theorem for monochrome triangles in K_6.

1 November

Pigeohole-principle to prove Erdos-Szekeres Theorem. Always find two vertices of the same degree in a graph. Counterexamples (a 2-coloured K_5 with no monochromatic triangles, a sequence of n^2 terms with no monotone subsequence of more than n terms, n^2+n+41 prime until n=40, Fermat primes). Homework: prove (by contrapositive) that if 2^m + 1 is prime then m is a power of 2.

8 November - no class

15 November

Natural numbers and mathematical induction, recurrences, examples of proofs by induction,

22 November

Mathematical induction ctd., recursively defined functions/operations.

29 November

TEST

5 December

Well-ordering (WO) of natural numbers, minimal counterexamples. Examples of proof by WO.

13 December

Further examples of proof by WO. Combinatorial proofs: partitioning, counting in two ways ("double counting"). Examples.

20 December

Sperner's Lemma (ctd.). Further examples of proofs by counting in two ways, and by partitioning.

3 January

Inclusion-exclusion Principle. Examples.

10 January

TEST