Final Study Guide

Time: Saturday May 10th from 3:30 - 6:30 pm
Location:  DH 208

• Final Practice Problems

• Finals Definition Sheet

Structure

• 7-8 Problems, 9 pages (+ cover page, + definitions).

  • • One more page than exams 1 and 2.

• All definitions provided. Proof strategies are not.

• White-board proofs, definitions, and justifications

  • • Bullet points are great.

    • Complete sentences optional.

    • Transitions are helpful, but not required.

    • You may skip small steps in arguments, i.e. "Thus g(f(x))=y, and so g o f (x) = y".

    • Figures are acceptable definitions of objects (graphs, sets, etc).

Topics

• Homeworks 6-14, focusing on 8-14

• Proofs

  • • Direct, contraposition, contradiction, cases. Universal and existential.

• Set theory (not emphasized)

  • • Set relations: Subset, equality

    • Set operations: powerset, cross product

    • Relations: Tuples and n-tuples.

• Functions

  • • Properties: Onto, one-to-one, and bijections

    • Operations: Composition, Inverse

    • Not “because there exists an onto function .. the size of A and the size of B”

    • Not "are these two infinite sets the same cardinality"

• Combinatorics

  • • How many ways?

    • Addition, multiplication, division, subtraction rules for counting

      • Be able to justify by explaining your reasoning/showing your work, but I don’t care if you name the rules.

      • I.E. “How many sets of size 2? There are n ways to take the first element, n-1 ways to take the second, but we are counting each set twice, so n(n-1)/2”. 

      • Not “by the multiplication rule, division rule”. It’s okay to include those, but not necessary

    • Pigeonhole principle

• Sequences

  • • Mostly as a mathematical object (for instance, paths in a graph)

    • Proving summations or closed forms by induction.

    • Not finding closed forms or "guess the sequences"

• Induction

  • • Mathematical induction

    • Strong induction (will be explicit)

    • Induction over non-numbers 

      • I.E. sets, tuples, graphs, functions, where each step involves a universal claim such as "every graph of n vertices"

    • But not as complex as HW15

• Graphs

  • • Graphs as models

    • Graph types: Directed, undirected, with loops, without. Not multigraphs.

    • Graph properties: Bipartite, isomorphic, connected, connected components

    • Graph operations: contraction, removing a vertex, removing an edge

    • Paths, Hamiltonian paths, Eulerian paths

• Not Included

  • • Algebra

    • Puzzles

    • Formal logic, connectives, predicates

    • Equivalence proofs, derivations

    • Countability, Completeness, Consistency

Problem Types:

• Answer this question (possibly with justification)

• Model this thing/Translate between model-theoretic and mathematical language.

• Find a flaw in this thing (proof, translation, model)

• Proofs - possibly about numbers, definitely about non-numbers

• Synthesize two concepts:  For instance, stating properties using set-theoretic language.

• Work with a new concept

  • • But not combining synthesis and new concepts.