CIS 260, Fall, 2008

Brief description:

Syllabus:

• Mathematical Reasoning, Proof Principles and Logic
• Inference rules, deductions
• Direct proofs
• Indirect proofs
• Proofs by contradiction
• Proofs by contrapositive
• The use of counter-examples
• Disjunctive premises
• Quantifiers, existential premises
• Basic concepts of set theory
• Russel's paradox (the set of all sets)
• The set of natural numbers, N
• The induction principle on N
• 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
• 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
• 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
• 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
• Incidence and Adjacency Matrices of a Graph
• Eulerian and Hamiltonian Cycles

Back to Gallier Homepage

published by:

Jean Gallier