Formal axiomatic theories on the base of three-valued logic

I. D. Zaslavsky

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VIII, Tome 304 (2003), pp. 19-74

Résumé

Formal axiomatic theories on the base of J. Lukasiewicz's three-valued logic are considered. Main notions connected with these theories are introduced, for example, the notion of a Luk-model (i.e., model of a theory in terms of J. Lukasiewicz's logic), of a Luk-consistent theory, Luk-complete theory. Logical calculi describing such theories are defined; analogues of the classical theorems on compactness and completeness are proved. Arithmetical theories based on J. Lukasewicz's logic and on its constructive (intuitionistic) variant are investigated; the theorem on effective Luk-incompleteness for a large class of arithmetical systems is proved which is a three-valued analogue of K. Goedel's famous theorem on the incompleteness of formal theories. Three-valued analogues of M. Presburger's arithmetical system are defined; it is proved that they are Luk-complete but not complete in the classical sense.

Bibliographie

[1] O. R. Bolibekyan, Teorema kompaktnosti dlya mnogoznachnykh logik, Preprint Instituta problem informat. i avtomat. NAN RA No 02–001, 2002

[2] I. D. Zaslavskii, “O predikatnykh i arifmeticheskikh ischisleniyakh simmetricheskoi konstruktivnoi logiki”, DAN SSSR, 210:3 (1973), 517–520 | MR | Zbl

[3] I. D. Zaslavskii, Simmetricheskaya konstruktivnaya logika, Izd-vo AN Arm.SSR, 1978 | MR

[4] I. D. Zaslavskii, “O simmetricheskoi konstruktivnoi istinnosti arifmeticheskikh formul”, 7-ya Vsesoyuzn. konferentsiya po matem. logike, Tezisy dokladov, Novosibirsk, 1984, 67

[5] I. D. Zaslavskii, Simmetricheskaya konstruktivnaya logika i nekotorye ee prilozheniya, Dokt. diss., Erevan, 1987 | Zbl

[6] I. D. Zaslavskii, “O simmetricheskoi konstruktivnoi arifmetike”, 9-ya Vsesoyuzn. konferentsiya po matem. logike, Tezisy dokladov, Leningrad, 1988, 59

[7] I. D. Zaslavskii, “O bikonstruktivnykh arifmeticheskikh formulakh”, 10-ya Vsesoyuzn. konferentsiya po matem. logike, Tezisy dokladov, Alma–Ata, 1990, 67 | MR

[8] I. D. Zaslavskii, “Ob iteratsiyakh opredelyayuschikh algorifmov simmetricheskoi konstruktivnoi logiki”, 11-ya Mezhrespublikanskaya konferentsiya po matem. logike, Tezisy dokladov, Kazan, 1992, 62

[9] B. A. Kushner, Lektsii po konstruktivnomu matematicheskomu analizu, Nauka, M., 1973 | MR | Zbl

[10] A. I. Maltsev, “Untersuchungen aus der Gebiete der Mathematischen Logik”, Matem. sbornik, 1(43) (1936), 323–336 | Zbl

[11] A. I. Maltsev, Algoritmy i rekursivnye funktsii, 2-e izdanie, Nauka, M., 1986 | MR

[12] A. A. Markov, “Konstruktivnaya logika”, Uspekhi matem. nauk, 5:3(37) (1950), 187–188 | MR

[13] A. A. Markov, “O konstruktivnoi maematike”, Trudy MIAN SSSR, 67, 1962, 8–14 | MR | Zbl

[14] A. A. Markov, O logike konstruktivnoi matematiki, Znanie, M., 1972

[15] N. A. Shanin, “O konstruktivnom ponimanii matematicheskikh suzhdenii”, Trudy MIAN SSSR, 52, 1958, 226–311 | MR | Zbl

[16] N. A. Shanin, “Ob ierarkhii sposobov ponimaniya suzhdenii v konstruktivnoi matematike”, Trudy MIAN SSSR, 129, 1974, 203–266

[17] N. A. Shanin, Eskiz finitarnogo varianta matematicheskogo analiza, Preprint POMI 06/2000, 2000

[18] L. Bolc, P. Borowik, Many-valued Logics. 1: Theoretical Foundations, Springer-Verlag, 1992 | MR | Zbl

[19] K. Gödel, “Die Vollständigkeit der Axiome des logischen Funktionenkalküls”, Monatshefte für Mathematik und Physik, 37 (1930), 349–360 | DOI | MR | Zbl

[20] K. Gödel, “Über formal unentscheidbare Sätze der Principia”, Mathematica und Verwandter Systeme Monatshefte für Mathematik und Physik, 38 (1931), 173–198 | DOI | MR | Zbl

[21] H. B. Enderton, A Mathematical Introduction to Logic, 2nd edition, Academic Press, San Diego, 2001 | MR | Zbl

[22] R. Häenle, G. Escalada–Imaz, “Deduction in Many-Valued Logics: a Survey”, Marthware Soft Computing, 4:2 (1997), 69–97 | MR

[23] D. Hilbert, P. Bernays, Grundlagen der Mathematic, Zweite Auflage. Band 1, Springer-Verlag, Berlin–Heidelberg–New York, 1968 ; Band 2, Springer-Verlag, Berlin–Heidelberg–New York, 1970; D. Gilbert, P. Bernais, Osnovaniya matematiki. T. 1: Logicheskie ischisleniya i formalizatsiya arifmetiki, Nauka, M., 1979 ; Т. 2: Теория доказательств, Наука, М., 1982 | MR | MR

[24] S. C. Kleene, Introduction to Metamathematics, D. van Nostrand Comp., Inc., New York–Toronto, 1952 ; S. K. Klini, Vvedenie v matematiku, IIL, M., 1957 | MR

[25] C. I. Lewis, C. H. Langford, Symbolic Logic, Century Comp, New York–London, 1932 | Zbl

[26] H. R. Lewis, C. H. Papadimitriou, Elements of the Theory of Computation, Prentice–Hall, Upper Saddle River, New Jersey, 1998 | MR

[27] J. Lukasiewicz, “O logice trojwartosciowej”, Ruch Filozoficzny, 5 (1920), 168–171

[28] E. Mendelson, Introduction to Mathematical Logic, D. van Nostrand Comp., Inc., Princeton, New Jersey–Toronto–New York–London, 1963 ; E. Mendelson, Vvedenie v matematicheskuyu logiku, Nauka, M., 1971 | MR | MR

[29] M. Presburger, “Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt”, C. R. Congres Math. Pays slaves, 1930, 92–101 | Zbl

[30] N. Resher, Many-valued logic, McGraw-Hill, New York, 1969

[31] J. B. Rosser, “Extensions of some theorems of Gödel and Church”, Journ. of Symbolic Logic, 1 (1936), 87–91 | DOI

[32] J. B. Rosser, A. R. Turquette, Many-valued logics. Studies in logic and the foundations of mathematics, North–Holl. Publ. Comp., Amsterdam, 1952 | MR | Zbl

[33] J. Rousseau, “Sequents in Many-valued Logics, I”, Fundamenta Mathematicae, 60 (1967), 23–33 | MR

[34] J. Rousseau, “Sequents in Many-valued Logics, II”, Fundamenta Mathematicae, 67 (1970), 125–131 | MR | Zbl

[35] A. S. Troelstra, H. Schwichtenberg, Basic proof theory, Cambridge University Press, Cambridge–New York, 2000 | MR | Zbl

[36] I. D. Zaslavsky, “On the theory of constructive reducibility”, Proc. Internat. Conf. on Computer Science and Information Technologies, CSIT'97 (Yerevan, 1997), 10–11

[37] I. D. Zaslavsky, “On a logicaly but not functionally complete calculus in three-valued logic”, The Tbilisi Symposium on Logic, Language and Computation, CSLI publications, Stanford, California, 1998, 309–313 | MR | Zbl

[38] I. D. Zaslavsky, “On three-valued arithmeti”, Proc. Internat. Conf. on Computer Science and Information Technologies, CSIT'01 (Yerevan, 2001), 133–136

[39] I. D. Zaslavsky, “Dual realizability in symmetric logic”, Annals of Pure and Applied Logic, 113 (2002), 389–397 | DOI | MR | Zbl

[40] I. D. Zaslavsky, On three-valued logical models and their applications to arithmetical theories, Submitted to Denis Richard 60th Birthday Conference, Clermont-Ferrand, France, 2002

[41] I. D. Zaslavsky, “On the Completeness Properties of the Systems of Symetric Constructive and Three-valued Logic”, 21st Days of Weak Arithmetic, Abstracts, International Conference (St. Petersburg, Russia, June 7–9, 2002), St. Petersburg, 2002, 17–18; http://at.yorku.ca/cgi-bin/amca/cail-01