CS280 Spring 1990

1 admin., goals of course--language--math maturity
  set theory--sets--ways to denote sets--Russell's
  paradox--relations member, subset--operations
  union, intersection, set difference, symm diff--
  representation of natural numbers.
2 subsets--power set--cardinality--Cantor's diagonal
  argument--1-1 correspondence--real numbers and P(N)--
  functions, domain, range
3 Cantor's argument (picture with infinite matrix)--
  mention Goedel's & Turing's results--ex with N^2:
    g(i,j) = (i+j+1)(i+j)/2 + j
  inverse image of functions in context of g
  binary relations
4 eq relations
    def ref, sym, trans
    partitions, eq classes [a]
    examples:
      =, A^2 smallest and largest
      cardinality f:A-->B 1-1, onto on P(C)
      x-y even on Z, mult of 3
      P(N), A (triangle) B finite
    proof that a==b iff [a]=[b]
    domain of function, quotient construction
5 partial orders
    ref, antisym, trans
    ex:
      subset on P(A)
      <= on N, R, Z
      | on N-{0} (*not* on Z-{0}!)
      "refines" on eq relations
      lex order (dictionary order)
  total order--trichotomy
      ex N, Z, R, Q    
  strict partial order--trans, irref
      1-1 correspondence with partial order
6 thm: every partial order extends
  thm: partial order determined uniquely by
           set of extensions
  thm: quotient of quasi-order --> partial order
  construction of rational numbers      
7 induction
  not "inductive" vs. "deductive" reasoning,
      but mathematical induction
    induction over N
      strong: (m m in S) --> n in S / S = N
      weak: 0 in T, n in T --> n+1 in T / T = N
    induction over inductively defined structures
    induction over well-founded relations
  strong induction over N
    ex: sum from i=0 to n of i = n(n+1)/2
    ex: pizza and cheese cutting
8   ex: sum from i=0 to n of i^2 = n(n+1)(2n+1)/6
    towers of hanoi
  def: weak induction, well-ordering principle
    ex: division algorithm
9   ex: Euclidean algorithm
     (a,b) = sa + tb
     uniqueness of gcd
10 equivalence of weak, str induction and well-ordering princ
     (every nonempty subset of N has least elt)
     wi --> si: take T = {n | all m <= n m in S}
11 structural induction
     induction on trees
     balanced parens
12 closure
     transitive closure
     def of well-foundedness
     induction principle on well-fdd relation
13 equiv of induction principle & well-foundedness
14 rings and modular arithmetic
     a invertible mod n iff (a,n)=1
     def of group of units
     Euler phi function
     Fermat's little theorem
15 Wilson's theorem
   stmt that (m,n)=1 --> phi(mn)=phi(m)phi(n)
16 RSA cryptosystem
   Chinese Remainder Theorem
     informal discussion Z_15 == Z_3 x Z_5
     informal notion of isomorphism
     application to bignums
17 Chinese Remainder Theorem
     formal def of ring homo & isom
     proof (m,n)=1 --> Z_mn == Z_m x Z_n
     how to invert
18 intro combinatorix--science of counting
     n!
     permutations
     law of sum, product
     arrangements of n objects k at a time
       = P(n,k) = n!/(n-k)!
     multinomial coefficients
     binominal coefficients
     Pascal's triangle
     statement of binomial theorem
19 "Intuitive" proof of Binomial Theorem
     (similar to that in the book)
     proof by induction, using Pascal's
     triangle equation
          n      n     n+1
        (   ) + ( ) = (   )
         i-1     i      i
20 for i:=1 to 12
     for j:= 1 to i
       for k:=1 to j
         writeln ("Hi there!");
    exercise in 4 different ways:
      1) counting sum of sum of sum of ones;
      2) chosing j first and counting sum of j(12-j+1);
      3) putting 11 ones into 3 boxes, interpreting 1 1 k 1 1 1 1 j 1 i 1...
         as k=2, j=6, i=7
      4) 12 days of Xmass: i= current day, j=type of the present, and so on
    clinking wine glasses exercise in 3 ways:
      1) count (n-1)+(n-2)+...+1;
      2) graph n*(n-1)/2;
      3) chose 2 out of n;
21 inclusion/exclusion
22 discrete probability
23 random variables, expectation, independence
24 prob. expectation of sum, product
25 generating functions
26 exam review
27 generating functions
     linear recurrences
     Fibonacci numbers
28 graphs
     basic defs--directed, undirected,
       connected, multigraphs, trees
     Konigsberg bridges, Euler circuits
29 graph isomorphism
   planar graphs
     4 color theorem
     Euler's formula
     triangulation
     e <= 3v - 6
30 planar duality
   Hamiltonian circuits
   tournaments
31 logic
     classical syllogisms
     propositional logic
     truth tables
     satisfaction, validity, tautology
32 laws of propositional logic
     Boolean algebra
     deductive completeness
33 Stone representation
34 first-order logic
     syntax and semantics
     expressibility
35 deductive systems & completeness
36 equational logic