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).