Basic set theory

finite sets, notation, empty set, element vs. subset

set operations (union, intersection, complement)

set constructions (cartesian product, separated sum, function space, power set)

properties and relations

properties of relations (equivalence relations, partitions)

transitive closure?

partial and total orderings

functions (composition, one-one, onto, isomorphism)

partial functions vs. total functions

functions distinguished from algorithms and programs

infinite sets (countable, uncountable)

cardinality related to operations

paradoxes of naive set theory (Russell's)

Numbers

natural numbers (maybe induction first here?)

integers: divisibility, primes, modular arithmetic

rational numbers

real numbers

complex numbers

Propositional logic

truth values

boolean operators

inter-definability

semantics (via truth tables)

formal deductions (as trees)

First-order logic

predicates and relations (formally)

quantifiers and variables

schematic proof

semantics

Proof techniques

direct proof

introducing and eliminating hypotheses

case analysis

contrapositive

counterexample

contradiction

reduction

induction

Combinatorics

combinations and permutations

closed formulas

binomial coefficient

recurrence relations?

generating functions?

inclusion-exclusion?

Recursion and induction

definition by recursion

dangers of vacuous definition

primitive recursive functions

general recursive functions, minimization

proof by induction (base cases, inductive step)

relation to hypothetical proof

structural induction (on e.g. trees)

Discrete structures

sequences and strings

length, concatenation, reversal, substrings, ??

trees

node relationships, height, traversals

graphs

definition, cycles, connectedness, rootedness, directed versus undirected, planarity

spanning trees, shortest paths, ??

colorings, weighted graphs

finite automata

symbols and alphabets, states, transitions, acceptance and languages, determinacy

connection to regular expressions?