Mathematical
Skills
Classes for the course Mathematical Skills in the winter semester of
2016 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 test
that will be set near the end of the semester.
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.
Classes are held at 15:40 on Tuesdays (excepting holidays) in
Room S11 in the MFF building at Mala Strana.
Overview of topics covered. The material on propositional logic in the first pages expands a little on what was covered in classes. In the class on Tuesday 3 January a complement to this set of notes was given.
There will be a basic test on Tuesday 10 January, which will take place in the usual class period. (Definitions and elementary examples to illustrate proof methods only.)
Material covered
4 October
Axioms (e.g for
natural numbers, Euclidean geometry), definition (notation,
terminology), theorem, proposition, lemma, corollary, claim,
counterexample.
11 October
Propositions and truth. Implication (if... then).
18 October
Propositional logic. Truth tables for unary functions (negation) and
binary (and, inclusive or, implication, equivalence). Tautologies.
Logical equivalences underlying contrapositive, proof by contradiction,
proof by cases. Logical implication and direct proof.
25 October
No class (Matriculation Day).
1 November
Contrapositive and proof by contradiction (examples).
Tim Gowers
discussion of logical implication.
Robert Bartle and Donald Sherbert, Introduction to real analysis, 3rd. ed. Appendix A (pp. 335-342) looks at proof techniques (this is a useful alternative textbook for Mathematical Analysis I)
8 November
No class (Dean's Day)
15 November
Double counting: Handshaking Lemma (even number of vertices of odd degree), average number of divisors of a natural number
22 November
Double counting: applications of Handshaking Lemma - Sperner's Lemma
29 November
Pigeonhole Principle: colouring with 2 colours the edges of a complete graph on 6 vertices contains a monochromatic triangle
6 December
Pigeonhole Principle: lossless compression, Erdos-Szekeres Theorem
13 December
Minimum counterexample: prime factorization, irrational square root of positive integer
s (not a perfect square), n^4-n^2 a multiple of 12, equation x^2+y^2=3(z^2+w^2) no non-zero solution
in integers
20 December
Well Ordering of natural numbers equivalent to Principle of
Mathematical Induction. Examples of 'strong' induction: factorization
into primes, binary representation, factorial representation
10 January
TEST on the following topics: Truth tables, validity of arguments ("P therefore Q" is valid when P logically implies Q), tautologies (by truth table check), quantifiers for all/there exists and their negation, direct proof, contrapositive, converse, counterexample, pigeonhole principle, induction, proof by contradiction, double counting.
