Dependence logic, Spring 2011
Material discussed in the lectures
The page numbers below refer to the course textbook "Dependence logic".
Monday 14.3: pages 5-6.
- Relations, structures, assignments, formulas of first-order logic
Thursday 17.3: pages 7-9 and 16-19.
- Semantics of first-order logic, negation normal form
- teams and formulas of dependence logic
Monday 21.3: pages 20-23.
- Semantics of dependence logic
Thursday 24.3: pages 23-24.
- Semantics of dependence logic with further examples
- Downward closure property of formulas (Closure Test)
Monday 28.3: pages 29-31.
- Concepts of logical consequence and equivalence
- Examples of propositional equivalences in dependence logic
Thursday 31.3: pages 32 and 35.
- More examples of logical equivalences in dependence logic
- "Change of free variables" and "Preservation of equivalence under substitution" lemmas
Monday 4.4: pages 33-35.
- Negation normal form for dependence logic,
- Lemmas 3.27 3.29;
-- truth of a formula depends only on the interpretations of the variables occurring free in the formula
-- Isomorphism preserves truth
Thursday 7.4: pages 37-39, 42-43, and 48-50.
- A characterization for first-order formulas of dependence logic,
- Flatness Test and the Flattening Technique,
- How to express "even cardinality" in dependence logic
Monday 11.4: pages 86-89.
- Existential second-order logic,
- Thm 6.2: a translation of dependence logic into existential second-order logic
Thursday 14.4: pages 90-95.
- Model theoretic properties of dependence logic: Compactness Theorem, Separation Theorem, Failure of the Law of Excluded Middle,
- Determined and non-determined sentences,
- Skolem Normal Form Theorem for existential second-order logic
Monday 18.4: pages 96-98.
- Thm 6.15: A translation of sentences of existential second-order logic into logically equivalent sentences of dependence logic
Thursday 28.4: We began to study the complexity of quantifier-free formulas of dependence logic (based on the doctoral thesis of Jarmo Kontinen).
- Basics of computational complexity theory: complexity classes L, NL, P, and NP, reductions and completeness,
- The notion of k-coherence for quantifier-free formulas of dependence logic (Def. 3.0.9. on page 14 in the doctoral thesis of Jarmo Kontinen)
Monday 2.5: pages 15-17 and 27 from the doctoral thesis of Jarmo Kontinen.
- Propositions 3.1.1, 3.1.2, 3.1.3, 3.1.5, 3.1.6
- Theorem 3.2.5
Thursday 5.5: pages 37-42 from the doctoral thesis of Jarmo Kontinen.
- Theorems 4.3.1, 4.3.3, and 4.3.5 (we did not go through the proof Thm 4.3.5).