MVL
Course on Many-Valued Logics (Autumn 2014)
Contents of the page
- News
- Contents of the classes
- Course material
- Practicalities
- Grading and homework assignments
- Course Description and Prerequisites
Contents
The course covers the following topics:
- Basic Logic and Monoidal t-norm Logic.
- Substructural logics and residuated lattices.
- Cut elimination and completions.
- Lukasiewicz logic.
More specifically, this is the content of each single class:
- September, 1: Introduction, motivations, t-norms and their residua. Section 2.1 (up to Lemma 2.1.13) of the Course Material 1.
- September, 5: Basic Logic, Residuated lattices, BL-algebras, linearly ordered BL-algebras. Section 2.2 and 2.3 (up to Lemma 2.3.16) of the Course Material 1.
- September, 8: Lindenbaum-Tarski algebra of BL, algebraic completeness. Monodical t-norm logic, MTL-algebras, standard completeness. The rest of Course Material 1 (excluding Section 2.4) and Course Material 2.
- September, 12: Ordinal decomposition of BL-algebras. Mostert and Shield Theorem. Course Material 3.
- September, 15: Ordinal decomposition of BL-algebras (continued). Algebrizable logics and equivalent algebraic semantics. Course Material 4.
- September, 19: Algebrizable logics and equivalent algebraic semantics (continued). Course Material 4.
- September, 22: Algebrizable logics and equivalent algebraic semantics (continued): Leibniz operator and implicit characterisations of algebraizability. Course Material 4.
- September, 26: Leibniz operator and implicit characterisations of algebraizability (continued). Course Material 4. Gentzen calculus and the substructural hierarchy. Course Material 5 (to be continued).
- September, 29: Structural quasi-equations and $N_2$ equations. Residuated frames. Course Material 5 (Continued).
- October, 3: Analytic quasi-equations, dual frames, and MacNeille completions. Course Material 5 (Continued).
- October, 9: Atomic conservativity, closing the circle of equivalencies. Course Material 5 (Continued).
- October, 10: Lukasiewicz logic and MV-algebras. Mundici’s equivalence. Course Material 6.
- October, 17: The duality between semisimple MV-algebras and Tychonoff spaces. Course Material 7.
Course material
The material needed during the course can be found below.
- Course material 1
- Course material 2
- Course material 3
- Course material 4
- Course material 5
- Course material 6
- Course material 7
- An example of a possible final exam can be downloaded here.
The homework due during the course can be found below.
- Homework 1 (Deadline 12th September)
- Homework 2 (Deadline 19th September)
- Homework 3 (Deadline 26th September)
- Homework 4 (Deadline 3d October)
- Homework 5 (Deadline 10th October)
- Homework 6 (Deadline 17th October)
Practicalities
Staff
- Lecturer: Luca Spada
Dates/location:
- Classes run from the 1st of September until the 17th of October; there will be 14 classes in total.
- There are two classes weekly.
- Due to the high number of participants classrooms will change weekly, datanose.nl will always be updated with the right classrooms.
Grading and homeworks
- The grading is on the basis of weekly homework assignments, and a written exam at the end of the course.
- The homework assignments will be made available weekly through this page.
- The final grade will be determined for 2/3 by homeworks, and for 1/3 by the final exam.
- In order to pass the course, a score at least 50/100 on the final exam is needed.
More specific information about homework and grading:
- You are allowed to collaborate on the homework exercises, but you need to acknowledge explicitly with whom you have been collaborating, and write the solutions independently.
- Deadlines for submission are strict.
- Homework handed in after the deadline may not be taken into consideration; at the very least, points will be subtracted for late submission.
- In case you think there is a problem with one of the exercises, contact the lecturer immediately.
Course Description
Many-valued logics are logical systems in which the truth values may be more than just “absolutely true” and “absolutely false”. This simple loosening opens the door to a large number of possible formalisms. The main methods of investigation are algebraic, although in the recent years the proof theory of many-valued logics has had a remarkable development.
This course will address a number of questions regarding classification, expressivity, and algebraic aspects of many-valued logics. Algebraic structures as Monoidal t-norm based algebras, MV-algebras, and residuated lattices will be introduced and studied during the course.
The course will cover seclected chapters of the following books.
- P. Hájek, ‘Metamathematics of Fuzzy Logic‘, Trends in Logic, Vol. 4 Springer, 1998.
- P. Cintula, P. Hájek, C. Noguera (Editors). ‘Handbook of Mathematical Fuzzy Logic‘ – Volume 1 and 2. Volumes 37 and 38 of Studies in Logic, Mathematical Logic and Foundations. College Publications, London, 2011
- R. L. O. Cignoli, I. M. L. D’Ottaviano e D. Mundici, ‘Algebraic Foundations of Many-Valued Reasoning‘, Trends in Logic, Vol. 7 Springer, 2000
- D. Mundici. ‘Advanced Lukasiewicz calculus and MV-algebras‘, Trends in Logic, Vol. 35 Springer, 2011.
Prerequisites
It is assumed that students entering this class possess
- Some mathematical maturity.
- Familiarity with the basic theory of propositional and first order (classical) logic.
Basic knowledge of general algebra, topology and category theory will be handy but not necessary.
Tags: Amsterdam, categorical duality, Chang’s completeness theorem, Course, Free algebra, ILLC, Łukasiewicz logic, Many-Valued Logic, MV-algebras, rational polyhedra
I wonder what does “continuous” means in Exercise 3 in HW2. In HW1, the definition of left-continuous is given which does not seem like the usual sense, so I wonder what kind of continuity should we use in the exercise.
Dear Haoqian,
The definition of left continuity in HW1 is equivalent to the “classical” one in the context of t-norms. In HW2 continuity is just classical continuity, or, if you prefer, the fact that the t-norm commutes with infinite infima and suprema.
Regarding exercise 3 on homework sheet 3: I think we will have to exchange the domain and the codomain for the functions H and Omega in order for the definitions to make sense.
Sure! Thank you, I have updated the exercises.
Regarding exercise 2 on homework sheet 3: In which sense should we understand the largest algebraic semantics. Do we mean
A) A quasi-variety which is an algebraic semantics for the deductive system and which contains all quasi-varieties that are algebraic semantics for the deductive system, (with possibly different defining equations).
Or
B) A quasi-variety which is an algebraic semantics for the deductive system and which contains all quasi-varieties which are algebraic semantics for the deductive system with the same defining equations as the algebraic semantics we intially assumed to exist for the deductive system.
I am inclined to think that we should take largest in the sense of B) as A) seems to strong, but I could be wrong.
Dear Frederik,
It is enough to prove B). I guess that A) is false in general, but at the moment I cannot come up with a counterexample.
For ex.3 of the 4th homework, should we prove that the classes we find are indeed the lowest to which these inequalies belong?
Dear Tingxiang,
No you do not need to prove that they are the lowest. You just need to show that they belong some class, this should be as low as you can.
I have two questions about exercise 3 of HW5:
1. to calculate the minimal class of X=Y, where X and Y are formulas, does it suffice to find the minimal class of which both X and Y live in?
2. For a formula like (x/y)v(y/x), is it demanded that both x(y) should be assigned the same class, or they can be assigned different classes?
Dear Haoqian,
1. No, you should use residuation to transform the equation in something of the form $1\leq t$ where $t$ is a term.
2. Variables belong both to $P_0$ and $N_0$, so they belong to all classes. In one case you can use that they belong to some $P_n$ in other that they belong to some $N_k$.
I have a question about homework 6, exercise 3. What does “complete” mean here?
Dear Moritz,
A theory $T$ is complete when for any formula $\varphi$, either $T\vdash \varphi$ or $T\vdash \neg\varphi$.
Dear Luca,
I’m a bit confused about which completeness results we’ve actually seen, maybe you can tell me if I get it right:
-We’ve seen completeness of BL with regard to linearly ordered BL-algebras
-We’ve seen standard completeness of MVL (completeness w.r.t left-continuous t-norms)
-We’ve seen completeness of of BL w.r.t Wajsberg hoops (by showing that every l.o. BL-algebra can be decomposed into Wajsberg hoops, don’t know if that’s considered completeness)
-We’ve seen the Mostert & Shield theorem, that every t-norm can be decomposed into Wajsberg t-norms (i.e. Goedel and Product)
So if I understand it correctly, there is another step required to show standard completeness of BL (w.r.t continuous t-norms) that we haven’t seen. Is it a direct corollary of Mostert & Shield, or does it require more work?
Dear Ur,
Yes, I remember Tingxiang asked the same question in class. There is a step in the standard completeness for BL that we have not covered. We have seen its equivalent for MTL (what you call MVL), but not for BL. It is not an immediate corollary of the ordinal decomposition or the Mostert&Shield theorem, but these results play a crucial role in the proof.
Point 3 in your list is not a real completeness, as you do not get from the ordinal decomposition that an equation holds in a l.o. BL algebra iff it holds in a Wajsberg hoop.
Finally point 4 is inaccurate, Mostert&Shield theorem says that every *continuos* t-norm is locally isomorphic to either Lukasiewicz, Product or Goedel t-norm.
I hope this clarifies a bit.
Luca
Thank you, I does clear things up. My apologies for the inaccuracies, I got a bit mixed with the names (and in 4 I just forgot to write the “continuous”)