CIS 160, Fall, 2010

Brief description:

Syllabus:

1. Mathematical Reasoning, Proof Principles and Logic
   • Inference rules, deductions, informal and formal proofs
   • A proof system for implication (natural deduction)
   • A proof system for propositional logic (natural deduction)
   • The "proof-by-contradiction" principle; proof by cases; rules involving negation
     Intuitionistic and classical proofs
   • Clearing up confusions about the rules involving negation
   • De Morgan laws and classical logic; proofs by contrapositive
   • Formal versus informal proofs
   • Truth-value semantics for classical logic
   • Quantifiers; universal and existential premises
   • Proof rules for the quantifiers (natural deduction)
   • First-order theories
   • Basic concepts of set theory
   • Russel's paradox (the set of all sets)
   • The set of natural numbers, N
   • The induction principle on N
2. Relations, Functions, Partial Functions
   • Ordered Pairs, Cartesian Products, Relations
   • The induction principle on N, again
   • Composition of Relations and Functions
   • Recursion on N
   • Inverses of Functions and Relations
   • Injections, Surjections, Bijections, Permutations
   • Direct Image and Inverse Image
   • Equinumerosity
   • Finite and infinite sets
   • Pigeonhole Principle
   • Schroder--Bernstein Theorem
   • An Amazing Surjection: Hilbert's Space Filling Curve
   • Strings, Multisets, Indexed Families
3. Graphs
   • Why Graphs? Some Motivations
   • Directed Graphs
   • Paths in Digraphs; Strongly Connected Components
   • Undirected Graphs, Chains, Cycles, Connectivity
   • Trees and Arborescences
   • (*) Minimum (or Maximum) Weight Spanning Trees
4. Some Counting Problems; Binomial and Multinomial Coefficients
   • Counting Permutations and Functions
   • n!, Stirling's formula
   • f = O(g), f = \Omega(g), f = \Theta(g), f = o(g).
   • Counting Subsets of Size k; Binomial Coefficients
   • Pascal's triangle
   • Binomial formula
   • The number of injections between two finite sets
   • The number of surjections between two finite sets
   • Multinomial coefficients
   • Multinomial formula
   • The number of finite multisets
   • The Inclusion-Exclusion Principle
   • (*) Sylvester's formula and the Sieve formula
5. Partial Orders and Equivalence Relations
   • Partial Orders
   • Lexicographic ordering on strings
   • Divisibility ordering
   • Minimal elements, maximal elements
   • Least elements, greatest elements
   • Least upper bounds, greatest lower bounds
   • (*) Zorn's Lemma
   • Well-orderings
   • Complete Induction on N
   • Prime numbers
   • Prime Factorization in Z
   • There are infinitely many primes
   • Euclidean division
   • Well-founded sets and complete induction
   • (*) Lexicographic ordering on pairs
   • The Bezout identity and GCD's
   • Euclid's lemma
   • Unique Prime Factorization in Z
   • Equivalence Relations and Partitions
   • Transitive Closure, Reflexive and Transitive Closure
   • (*) Applications of arithmetic to cryptography

Back to Gallier Homepage

published by:

Jean Gallier