Course syllabus

We will cover the following topics:

Set notation

Sets of objects and numbers, Subsets, Union and intersection

The logical framework

The basic logical operations: not, or, end, Logical equivalence, if-then, The converse statement, The contrapositive statement, Universal and existential quantifiers

Natural numbers

The 'laws of algebra', Putting the natural numbers in order, The principle of induction, Summation formulae, Recursive definitions, Other forms of the principle of induction, Greatest and least members

How to count

Counting as a bijection, The size of a set, A counting problem, Some application of the pigeonhole principle, Infinite sets, Strange properties of infinite sets

Integers

Negative numbers, equivalence relations, Classification, Construction of the integers, Properties of the integers, Bounded subsets of the integers

Divisibility and prime numbers

Divisibility, Quotient and reminder, Representation of integers, The greatest common divisor, Prime numbers, Existence and uniqueness of prime factorization

Fractions and real numbers

Construction and properties of rational numbers, Density of fractions, Decimal representations of fractions, Real numbers, Approximation for real numbers, The greatest lower bound property, The real numbers are more plentiful than the rationals

Principles of counting

The addition principle, Counting sets of pairs, Euler's function, Functions, words, and selections, Injections as ordered selections without repetition, Permutations

Subsets

Binomial numbers, Unordered selections with repetition, The binomial theorem, The sieve principle, Some arithmetical applications

Partition, classification, and distribution

Permutation of a set, Classification and equivalence relations, Distribution and the multinomial numbers, Partitions of a positive integer, Classification of permutations, Even and odd permutations

Modular arithmetic

Congruences, The set of integers mod m and its arithmetic, Invertible elements of the set of integers mod m

Graphs

Graphs and their representation, Isomorphism of graphs, Degree, Paths and cycles, Trees, Colouring the vertices of a graph, The greedy algorithm for vertex-colouring

Bipartite graphs and matching problems

Relations and bipartite graphs, Edge colouring of graphs, Application of edge colouring to latin squares, Matchings, Maximum matchings, Transversal for families of finite sets.

Groups

The axioms for a group, Examples of groups, Basic algebra in groups, The order of a group element, Isomorphism of groups, Cyclic groups, Subgroups, Cosets and Lagrange's theorem, Characterization of cyclic groups

Groups and permutations

Definitions and examples, Orbits and stabilizers, The size of an orbit, The number of orbits, Representation of groups by permutations, Applications to group theory

Error-correcting codes

Words, codes, and errors, Linear codes, Construction of linear codes, Correcting errors in linear codes, Cyclic codes, Classification and properties of cyclic codes

Digraphs, networks, and flows

Digraphs, Networks, Flows and cuts, The max-flow min-cut theorem.