Decidable and undecidable prime theories in infinite-valued logic

✍ Scribed by Daniele Mundici; Giovanni Panti

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 106 KB
• Volume: 108
• Category: Article
• ISSN: 0168-0072
• DOI: 10.1016/s0168-0072(00)00051-8

✦ Synopsis

In classical propositional logic, a theory T is prime (i.e., for every pair of formulas F; G, either T F → G or T G → F) i it is complete. In Lukasiewicz inÿnite-valued logic the two notions split, completeness being stronger than primeness. Using toric desingularization algorithms and the ÿne structure of prime ideal spaces of free '-groups, in this paper we shall characterize prime theories in inÿnite-valued logic. We will show that recursively enumerable (r.e.) prime theories over a ÿnite number of variables are decidable, and we will exhibit an example of an undecidable r.e. prime theory over countably many variables.