Sergey Nikolenko

Books
Research papers
Talks and posters
Students
Popular science
Other stuff

Research
CS and crypto
Bioinformatics
Machine learning
Algebraic geometry
Algebra
Bayesian networks
Earth sciences

Teaching
2014
ML, KFU
Game Theory, HSE
Mech. Design, HSE
ML, CSClub Kazan
Game theory, HSE
Math. logic, AU
Machine learning, STC
Machine learning, AU
2013
Discrete math, HSE
Machine learning, STC
Math. logic, AU
Cryptography, AU
2012
Machine learning, STC
Math. logic, AU
Machine learning II, AU
Machine learning, AU
Machine learning, EMC
2011
Cryptography, AU
Math. logic, AU
Machine learning, AU
2010
Math. logic, AU
Machine learning, AU
Cryptography, AU
2009
Crypto in CS Club
Statistics
Machine learning, AU
Cryptography
2008
Speech recognition
MD for CS Club
ML for CS Club
Mechanism design
2007
Machine Learning
Probabilistic learning

External links
Google Scholar profile
DBLP profile
LiveJournal account
nikolenko (in Russian)

Teaching activities

Mathematical Logic

This one-year course was presented in the fall of 2009 and the spring of 2010 in the «Academic University of Physics and Technology» as part of the recently established Chair of Mathematics and Computer Science. The first semester served as a reminder and/or introduction of the basic notions of mathematical logic, and the second semester was an advanced course primarily centered on model theory.

Semester I

1. Propositional logic, normal forms, complete bases and completeness conditions. Computable functions, decidable and enumerable sets and their properties.
2. Universal functions. The existence of a universal function, but not a total universal function. Uspensky–Rice theorem. Constructing a Godel universal function.
3. Kleene fixed point theorem and its corollaries. Turing machines. The busy beaver problem.
4. Propositionsl calculus. The deduction lemma. Correctness and completeness of propositional calculus. The compactness theorem. Sequent calculus.
5. Language of first-order logic; terms, atomic formulas, formulas. Interpretations. Free and bound occurrences. Estimates and values of the formulas. Predicate calculus. Substitutions and admissible substitutions.
6. Correctness of predicate calculus. The deduction lemma, lemma on constants. Validity and satisfiability. Models. Completeness of predicate calculus. The compactness theorem.
7. Arithmetic hierarchy, Σ_n and Π_n. Herbrand theorem. Skolemization. Definable predicates and definable sets. Arithmetic predicates. Automorphisms. Examples of definable and undefinable predicates.
8. Quantifier elimination. Lemmas for syntactical quantifier elimination. Quantifier elimination in: theory with signature (=,s,0) in the model of integers, theories of linear orders (dense, discrete, with maximal and/or minimal elements), Presburger arithmetic, atomless Boolean algebras, algebraically closed fields.
9. Quantifier elimination in real closed fields. The Tarsky theorem.
10. Basic definitions of model theory. L-structures, substructures, extensions, models and theories. Logical consequences, definable sets, examples of theories and definable sets. Completeness theorem. Compactness theorem. Corollaries: undefinability of the set of torsion points, nonstandard models of natural numbers.

Semester II

Brief lecture notes (in Russian) of the second semester, done by myself, complete with definitions and statements, but with no proofs. A short list of topics is given below.

1. Set theory and ordinals.
2. Types and Stone topology.
3. Ramsey theory and unprovability.
4. Prime models, homogeneous models, and stable theories.
5. Saturated and universal models.
6. (λ, μ)-models and Vaughtian pairs.
7. Eurenfeucht–Mostowsky models.
8. Minimal sets and theories.
9. A classification of uncontably categorical theories (the Baldwin–Lachlan theorem).
10. Nonstandard analysis.
11. Morley rank.
12. Intuitionism and constructive mathematics.