'; print ''; ?>

Sergey Nikolenko

Sergey Nikolenko

Main pageBooks'; print '
Research papers'; print '
Talks and posters'; print '
Students'; print '
Popular science'; print '
Other stuff'; print '

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

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

  External links'; print '
Google Scholar profile'; print '
DBLP profile'; print '
LiveJournal account
userinfonikolenko (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.

Selected references

1. Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. В 3-х тт. М., МЦНМО, 2008.
2. D. Marker. Model Theory: An Introduction. Springer-Verlag New York, 2002.
3. H.-D. Ebbinghaus, J. Flum, W. Thomas. Mathematical Logic. Springer-Verlag New York, 1984.