Summer term 2022
Universal Algebra II (NMAG450)
Lecture: Monday 10:40 - 12:10, lecture room K7
Exercise classes: even weeks, Monday 12:20 - 13:50, lecture room K7, given by
Kevin Berg
Syllabus:This course discusses selected topics from Universal Algebra. This includes
- Equational logic: the equational completeness theorem, term rewriting systems, Knuth-Bendix algorithm
- Commutator theory: Abelianness, the term condition commutator, applications
- Finitely based algebras: McKenzie's theorem on algebras with DPC
- Maltsev conditions: Taylor terms, polymorphism clones and CSPs, absorption theory
Evaluation:
Exercises: there will be 3 homework assignments, on which you need to score 60% to get ''Zápočet''
Lecture: oral examination (appointment by mail:
michael@logic.at).
Date |
Topics |
Lecture notes |
Exercises |
Homework |
14/02 | Equational theories, fully invariant congruences; completeness theorem for equational logic. | Section 1.1 | | |
21/02 | term rewrite systems, convergence, Knuth-Bendix | Section 1.2, 1.3 | 1.2,1.3,1.4 | |
28/02 | Abelian and affine algebras Herrmann's fundamental theorem | Section 2.1, 2.2 | | |
07/03 | The term conditions commutator, Examples (groups and lattices) | Section 2.3 | 1.2,1.3,1.4 2.12, 2.13 | HW1: 1.6, 1.8 (first point) 2.10, 2.14 |
14/03 | A characterization of CD varieties by the commutator | Section 2.4 | | |
21/03 | Birkhoff's theorem on Id_n a non-finitely based algebra | Chapter 3 | 2.19,2.20 | HW1 due |
28/03 | Park's conjecture McKenzie's DPC theorem | Section 3.1 | | |
04/04 | Jonsson's lemma DPSC varieties | Section 3.2 | 3.2,3.3, 3.11 | HW2: 3.4, 3.5, 3.6, and 4.1 |
11/04 | Baker's theorem CSPs: Definition and Examples | Section 3.2, 4.1 | | |
18/04 | Easter holiday | | | |
25/04 | Pol-Inv revisited, clone homomorphisms | Section 4.1., 4.2. | | HW2 due |
02/05 | Minion homomorphisms, Taylor's theorem | Section 4.2. | 4.3, 4.13 | HW3: 4.6,4.7,4.8 and 4.12 |
09/05 | Loop lemma (for triangles) Siggers terms | Section 4.3 | | |
16/05 | only Exercise class today! | | | HW3 due |
Consultation:
If you have questions on the material, do not hesitate to ask (either in person or via e-mail)! I have no official office hours, but personal meetings can be arranged. Please make also use of the exercise classes to discuss your questions.
Further reading:
Winter term 2021/22
Algebra 1 (NMAI062)
Please register to the
!! Moodle course !!
Lecture notes
Lecture: Wednesday 10:40 - 12:10, lecture room S4
Exercise classes: Tuesdays 15:40 - 17:10, lecture room S10, given by
Kevin Berg
(
current covid regulations)
Evaluation:
To get ''Zápočet'' (i.e. to pass the exercise classes) you need to score at least 60/100 points. These can be obtained from 3 homework assignments (3*30 points), or weekly quizzed (10 points), which will be posted on the
Moodle course
The final grade will be determined by a written exam. Admission to the exam requires passing the exercise class.
Syllabus:This course aims to give an introduction to algebra for computer science students. It will cover the following topics:
- Number theory: prime factorization, congruences, Euler's theorem and RSA, the Chinese remainder theorem
- Polynomials: rings and integral domains, polynomial rings, irreducibility, GCD, the Chinese remainder theorem and interpolation, the construction of finite fields and applications (error correcting codes, secret sharing,...)
- Group theory: permutation groups, subgroups, Langrange's theorem, group actions and Burnsides's theorem, cyclic groups, discrete logarithm and applications in cryptography
Literature:The course has its own
lecture notes, which are based on
David Stanovsky's material from last year, and will be constantly updated during the semester. Complementary resources are for instance
- J. Rotman, A First Course in Abstract Algebra (available in our library),
- C. Pinter A Book of Abstract Algebra (freely available online),
- or any other undergraduate level textbook on abstract algebra.
Consultation:
If you have open questions, do not hesitate to ask (either in person or via e-mail)! I have no official office hours, but if required, a personal meeting can be arranged. Please make also use of the exercise classes to discuss your questions.
Summer term 2020
Universal Algebra II (NMAG450)
Grading:
Exercises: homeworks (you need to score 60% on the 3 best out of 4 homeworks)
Lecture: oral examination (appointment by mail:
michael@logic.at).
Not available from 17.07.-27.07, 17.08-28.08
Additional literature:
Date |
Topics |
Lecture notes |
Exercises |
Homework |
24/02 | Equational theories, fully invariant congruences; completeness theorem for equational logic. | Section 1.1 | 1.1-1.3 | |
02/03 | Convergent term rewriting systems | Section 1.2 | | |
09/03 | Critical pairs, Knuth-Bendix algorithm; Affine algebras | Section 1.2, 1.3 Section 2.1 | 1.4, 1.8,1.9 | 1.5,1.6,1.7 due on 24/03 |
16/03 | Abelian algebras Herrmann's fundamental theorem | Section 2.1, 2.2 | 2.1-2.9; in particular 2.2, 2.6 | |
23/03 | Centralizer relation and commutator Example: groups | Section 2.3 | 2.11, 2.12 | 2.10, 2.13, 2.14 due on 07/04 |
30/03 | Properties of the commutator Characterization of CD varieties | Section 2.3, 2.4 | 2.15-2.20; in particular 2.18,2.19 | |
06/04 | Nilpotent algebras and open questions | Section 2.5 | Section 2.5 | |
20/04 | Birkhoff's theorem on Id_n(A) Example of a non-finitely based algebra | Chapter 3 | 3.1-3.4 | |
27/04 | McKenzies DPC theorem | Section 3.1 | 3.5-3.8 | |
04/05 | CSPs, pp-definable relations Pol-Inv | Section 4.1 | 4.1-4.5 | 3.5,3.6,4.3 due on 19/05 |
11/05 | Clone and minion homomorphisms | Section 4.2 | 4.6-4.8 | |
18/05 | Taylor operations the CSP dichotomy conjecture/theorem | Section 4.3 | 4.9-4.11 | 4.6,4.7,4.8 until your exam |
Winter term 2019/20
Exercises in Universal Algebra I (NMAG405)
See
Libor's website.
Summer term 2019
Universal Algebra II (NMAG450)
The course will roughly follow
Libor Barto's lecture from 17/18.
Lecture: Thurday 9:00 - 10:30 Seminar room of KA
Exercises: Thurday 10:40 - 12:10 Seminar room of KA (only odd semester weeks = even calendar weeks)
Grading:
Exercises: homeworks (60% from 3 best scores out of 4 homeworks)
Lecture: oral examination (appointment by mail:
michael@logic.at).
next available dates 27/05-07/06; 17/06-20/06; 04/07-
Literature:
Date |
Topics |
Recommended reading |
Exercises |
Homework |
28/02 | Abelian and affine algebras, Fundamental theorem. | Bergman 7.3 | Ex. 1 | |
07/03 | Checking identities, Relational description of Abelianness; Centralizer relation (in general and in groups) | Bergman 7.4 | | |
14/03 | Properties of the commutator Characterization of CD varieties | Bergman 7.4 | Ex. 2 | HW 1 due 28/03 |
21/03 | Equational theories, fully invariant congruences; completeness theorem for equational logic. | Bergman 4.6 Jezek 13 | | |
28/03 | Reduction order, critical pairs Knuth-Bendix algorithm | Jezek 13 | Ex. 3 | |
04/04 | Examples of finitely based and non finitely based algebras | Bergman 5.4 | | HW 2 due 25/04 |
11/04 | McKenzie's result on definable principal congruences | Bergman 5.5 | Ex. 4 | |
18/04 | Constraint satisfaction problems over finite templates Pol-Inv revisited | BKW | | |
25/04 | (h1-)clone homomorphisms Taylor terms | BKW | Ex. 5 | HW 3 due 09/05 |
02/05 | Taylor's theorem | Bergman 8.4. | | |
09/05 | Smooth digraphs, algebraic length 1,absorption | BK | | |
16/05 | Absorption, transitive terms | BK | Ex. 6 | HW 4 |
23/05 | Absorption theorem, LLL (loop lemma 'light', for linked digraphs) | BK | | |
Winter term 2018/19
Exercises in Universal Algebra I (NMAG405)
see David Stanovsky's
website.