Proszę używać tego identyfikatora do cytowań lub wstaw link do tej pozycji:
http://hdl.handle.net/11320/8128
Pełny rekord metadanych
Pole DC | Wartość | Język |
---|---|---|
dc.contributor.author | Pąk, Karol | - |
dc.date.accessioned | 2019-07-29T08:28:46Z | - |
dc.date.available | 2019-07-29T08:28:46Z | - |
dc.date.issued | 2019 | - |
dc.identifier.citation | Formalized Mathematics, Volume 27, Issue 2, Pages 209 - 221 | - |
dc.identifier.issn | 1426-2630 | - |
dc.identifier.uri | http://hdl.handle.net/11320/8128 | - |
dc.description.abstract | This article is the final step of our attempts to formalize the negative solution of Hilbert’s tenth problem.In our approach, we work with the Pell’s Equation defined in [2]. We analyzed this equation in the general case to show its solvability as well as the cardinality and shape of all possible solutions. Then we focus on a special case of the equation, which has the form x2 − (a2 − 1)y2 = 1 [8] and its solutions considered as two sequences {xi(a)}i=0∞,{yi(a)}i=0∞. We showed in [1] that the n-th element of these sequences can be obtained from lists of several basic Diophantine relations as linear equations, finite products, congruences and inequalities, or more precisely that the equation x = yi(a) is Diophantine. Following the post-Matiyasevich results we show that the equality determined by the value of the power function y = xz is Diophantine, and analogously property in cases of the binomial coe cient, factorial and several product [9].In this article, we combine analyzed so far Diophantine relation using conjunctions, alternatives as well as substitution to prove the bounded quantifier theorem. Based on this theorem we prove MDPR-theorem that every recursively enumerable set is Diophantine, where recursively enumerable sets have been defined by the Martin Davis normal form.The formalization by means of Mizar system [5], [7], [4] follows [10], Z. Adamowicz, P. Zbierski [3] as well as M. Davis [6]. | - |
dc.language.iso | en | - |
dc.publisher | DeGruyter Open | - |
dc.subject | Hilbert’s 10th problem | - |
dc.subject | Diophantine relations | - |
dc.subject | 11D45 | - |
dc.subject | 68T99 | - |
dc.subject | 03B35 | - |
dc.title | Formalization of the MRDP Theorem in the Mizar System | - |
dc.type | Article | - |
dc.identifier.doi | 10.2478/forma-2019-0020 | - |
dc.description.Affiliation | Institute of Informatics, University of Białystok, Poland | - |
dc.description.references | Marcin Acewicz and Karol Pąk. Basic Diophantine relations. Formalized Mathematics, 26(2):175–181, 2018. doi:10.2478/forma-2018-0015. | - |
dc.description.references | Marcin Acewicz and Karol Pąk. Pell’s equation. Formalized Mathematics, 25(3):197–204, 2017. doi:10.1515/forma-2017-0019. | - |
dc.description.references | Zofia Adamowicz and Paweł Zbierski. Logic of Mathematics: A Modern Course of Classical Logic. Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts. Wiley-Interscience, 1997. | - |
dc.description.references | Grzegorz Bancerek, Czesław Byliński, Adam Grabowski, Artur Korniłowicz, Roman Matuszewski, Adam Naumowicz, Karol Pąk, and Josef Urban. Mizar: State-of-the-art and beyond. In Manfred Kerber, Jacques Carette, Cezary Kaliszyk, Florian Rabe, and Volker Sorge, editors, Intelligent Computer Mathematics, volume 9150 of Lecture Notes in Computer Science, pages 261–279. Springer International Publishing, 2015. ISBN 978-3-319-20614-1. doi:10.1007/978-3-319-20615-8_17. | - |
dc.description.references | Grzegorz Bancerek, Czesław Byliński, Adam Grabowski, Artur Korniłowicz, Roman Matuszewski, Adam Naumowicz, and Karol Pąk. The role of the Mizar Mathematical Library for interactive proof development in Mizar. Journal of Automated Reasoning, 61(1):9–32, 2018. doi:10.1007/s10817-017-9440-6. | - |
dc.description.references | Martin Davis. Hilbert’s tenth problem is unsolvable. The American Mathematical Monthly, Mathematical Association of America, 80(3):233–269, 1973. doi:10.2307/2318447. | - |
dc.description.references | Adam Grabowski, Artur Korniłowicz, and Adam Naumowicz. Four decades of Mizar. Journal of Automated Reasoning, 55(3):191–198, 2015. doi:10.1007/s10817-015-9345-1. | - |
dc.description.references | Karol Pąk. The Matiyasevich theorem. Preliminaries. Formalized Mathematics, 25(4): 315–322, 2017. doi:10.1515/forma-2017-0029. | - |
dc.description.references | Karol Pąk. Diophantine sets. Part II. Formalized Mathematics, 27(2):197–208, 2019. doi:10.2478/forma-2019-0019. | - |
dc.description.references | Craig Alan Smorynski. Logical Number Theory I, An Introduction. Universitext. Springer-Verlag Berlin Heidelberg, 1991. ISBN 978-3-642-75462-3. | - |
dc.identifier.eissn | 1898-9934 | - |
dc.description.volume | 27 | - |
dc.description.issue | 2 | - |
dc.description.firstpage | 209 | - |
dc.description.lastpage | 221 | - |
dc.identifier.citation2 | Formalized Mathematics | - |
dc.identifier.orcid | 0000-0002-7099-1669 | - |
Występuje w kolekcji(ach): | Artykuły naukowe (WInf) Formalized Mathematics, 2019, Volume 27, Issue 2 |
Pliki w tej pozycji:
Plik | Opis | Rozmiar | Format | |
---|---|---|---|---|
forma_2019_27_2_011.pdf | 293,65 kB | Adobe PDF | Otwórz |
Pozycja ta dostępna jest na podstawie licencji Licencja Creative Commons CCL