Неповнота арифметики і теорія діофантових множин
Analysis of Diophantine sets showed that all recursively enumerated sets are Diophantine. Based on the classical results in the theory of computable functions, a simple version of the theorem on the incompleteness of arithmetic can be given: there is a polynomial that does not have positive integer...
Gespeichert in:
| Datum: | 2023 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Schlagworte: | |
| Online Zugang: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/278 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
| Завантажити файл: |  |
Institution
Physico-mathematical modeling and informational technologies| _version_ | 1867479646593875968 |
|---|---|
| author | Hupal, Anatolii Hupal, Mykyta |
| author_facet | Hupal, Anatolii Hupal, Mykyta |
| author_institution_txt_mv | [
{
"author": "Anatolii Hupal",
"institution": "член-кореспондент НАН України, д. ф.- н., професор, Інститут кібернетики імені В.М. Глушкова НАН України, проспект Академіка Глушкова, 40, 03187, Київ-187"
},
{
"author": "Mykyta Hupal",
"institution": "к. ф.-м. н., Інститут кібернетики імені В.М. Глушкова НАН України, проспект Академіка Глушкова, 40, 03187, Київ-187"
}
] |
| author_sort | Hupal, Anatolii |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:32:19Z |
| description | Analysis of Diophantine sets showed that all recursively enumerated sets are Diophantine. Based on the classical results in the theory of computable functions, a simple version of the theorem on the incompleteness of arithmetic can be given: there is a polynomial that does not have positive integer solutions, and for which it is impossible to prove the absence of positive roots |
| first_indexed | 2026-06-09T01:09:35Z |
| format | Article |
| fulltext |
68
doi.org/10.15407/fmmit2023.36.068
Неповнота арифметики і теорія діофантових множин
Анатолій Гупал1, Микита Гупал2
1 член-кореспондент НАН України, д. ф.- н., професор, Інститут кібернетики імені В.М. Глушкова НАН
України, проспект Академіка Глушкова, 40, 03187, Київ-187, e-mail: gupalantol@gmail.com
2 к. ф.-м. н., Інститут кібернетики імені В.М. Глушкова НАН України, проспект Академіка Глушкова, 40,
03187, Київ-187, e-mail: gupalantol@gmail.com
Аналіз діофантових множин показав, що всі рекурсивно перелічені множини є
діофантовими. На основі класичних результатів у теорії рекурсивних функцій наведено
простий варіант теореми про неповноту арифметики: існує поліном, який не має цілих
позитивних рішень, і для якого не можна довести відсутність позитивних коренів.
Ключові слова: діофантова множина, рекурсивно перелічені множини,
неповнота арифметики.
Вступ. Доведення теореми Геделя про неповноту арифметики несе в собі цілий
ряд допоміжних тверджень і в наш час не є простим [1]. На основі класичних
результатів у теорії рекурсивних функцій і діофантових множин надано
достатньо просте доведення неповноти арифметики, яке зовсім відрізняється
від конструкції Геделя.
У 1971 році було отримано видатний результат про нерозв’язність 10-ї
проблеми Гільберта. Було показано, що не існує алгоритму, який за наданим
поліномом розпізнає існування коренів поліному в цілих числах [2].
Основний технічний результат, отриманий при доказі нерозв’яності 10-ї
проблеми Гільберта – це теорема про співпадіння класу діофантових множин та
класу рекурсивно перелічених множин. Було отримано наступний несподіваний
результат: можна явно вказати поліном від багатьох змінних з цілими
коефіцієнтами такий, що множина всіх позитивних значень, яких він приймає
при цілочисленних значеннях змінних, є в точності множина простих чисел.
1.Діофантові множини
Діофантовими рівняннями називаються рівняння виду
1 1( ,..., , ,..., ) 0n mD a a x x , (1)
де D – поліном з цілими коефіцієнтами відносно усіх змінних
1 1,..., , ,...,n ma a x x , які розбито на дві частини: параметри
1,..., na a та невідомі
УДК 519.217.2
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип.36, 68-72
69
1,..., mx x . При фіксації значень параметрів отримуються конкретні діофантові
рівняння.
При різному виборі значень параметрів одержують рівняння, які мають
розв’язки, так і рівняння, які розв’язків не мають. Параметри діофантового
рівняння (1) визначають деяку множину , яка складається з усіх таких
наборів значень параметрів
1,..., na a , для яких існують значення змінних
1,..., mx x , які задовольняють рівнянню (1):
1 1 1 1,..., ... [ ( ,..., , ,..., ) 0]n m n ma a x x D a a x x . (2)
Число n – розмірність множини , а еквівалентність (2) – діофантове
представлення множини . Можна вважати діофантовим представленням не
тільки (2), а також і (1).
Необхідно вирішити наступну задачу: нехай є деяка множина, яка
складається з n -ок натуральних чисел; потрібно встановити, чи являється ця
множина діафантовою і якщо являється, то знайти для неї будь яке діафантове
представлення. Іноді діофантовість множини тривіальна, наприклад, очевидна
діафантовість множини всіх парних чисел. В інших випадках встановити
діафантовість технічно важко, наприклад для простих чисел.
Об’єднання та перетин двох діафантових множин однакової розмірності є
діафантовою множиною. Отримано можливість спеціалізувати вид рівнянь у
діофантових представленнях множиною натуральних чисел у випадку 1n . А
саме, рівняння
1( , ,..., ) 0mD a x x (3)
має розв'язок у невідомих
1,..., mx x тоді і тільки тоді, коли рівняння
2
0 0( 1)(1 ( ,..., )) 1mx D x x a (4)
має розв'язок у невідомих
0 ,..., mx x . Таким чином, множина натуральних чисел
є діафантовою тоді і тільки тоді, коли вона є множиною усіх натуральних
значень, які приймає деякий поліном з цілими коефіцієнтами при натуральних
значенннях змінних [3].
Важливим засобом встановлення діафантовості є поняття діафантової
функції як функції, графік якої є діафантовою множиною. Відповідно
діафантовим представленням функціїї F буде еквівалентність типу
1 1 1 1( ,..., ) ... [ ( , ,..., , ,..., ) 0]n m n ma F b b x x D a b b x x ,
де D – поліном з цілими коефіцієнтами.
Анатолій Гупал, Микита Гупал
Неповнота арифметики і теорія діофантових множин
70
2.Мови опису діофантових множин
Мова 0 , , ,Я , де – квантор існування дає змогу записати будь-
який поліном ( , )p a x та робити висновки у вигляді ( , ) 0xp a x , де
1{ ,..., }ka a a ,
1{ ,..., }mx x x . Тоді можна охарактеризувати діофантові
множини як ті і тільки ті множини, які можна виразити мовою
0Я . Однак
можливості мови
0Я обмежені і на ній не можна висловити багато цікавих з
теоретико-числової точки зору множин. Наприклад, множина простих чисел
виражається формулою
1& [ 1 1]p y p z p yz p y z ,
до якої входить обмежений квантор загальності .
Ю.В. Матіясевич вивчив мови
1 5Я Я з наростаючою можливістю
кожної наступної мови. У сукупності вони містять символи +, , (оператор
зведення у ступінь), =, , >, , | (операція поділу), обмежений квантор
загальності . (mod), &, , , а також деякі функції . Технічно складними
виявилися докази діофантовості функції двох аргументів Cb та обмеженого
квантора загальності. На основі діафантовості функції Cb отримано
діафантовість біноміальних коефіцієнтів і факторіалу та виписано діафантове
представлення простих чисел в іншому виді:
Pr ( ) 1& ( ,( 1)!) 1ime a a GCD a a , де GCD – найбільший загальний
дільник позитивних цілих чисел.
Матіясевич довів рівнооб'ємність мов
0Я і
5Я , тобто будь-яка множина,
що виражається однією мовою, виражається також і в іншій мові. З цього
негайно слідує діофантовість множини всіх простих чисел. З іншого боку, у
теорії рекурсивних функцій встановлено, що клас множин, описаних мовою
5Я , збігається з класом рекурсивно перелічених (р.п.) множин. Таким чином, з
рівнооб'ємності мов
0Я та
5Я доведено, що класс діофантових множин
співпадає з классом р. п. множин. Одним з класичних результатів в теорії
рекурсивних функцій є теорема про існування р.п. множини, для якої не існує
засобу, що дозволяє за скінчене число кроків розпізнати присутність або
відсутність довільного числа у цій множині. Цей результат разом з
діафантовістю р.п. множин дає негативний розв'язок 10-ї проблеми Гільберта
[1].
Відомо у теорії рекурсивних функцій, що проблема «
xx W » є
нерозв’язною, де
xW – область визначення часткової обчислюваної функції
x ,
яка виконується програмою
xP з індексом x. Ця програма завершує роботу на
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип.36, 68-72
71
вході x [4]. Множина xK x x W – рекурсивно перелічена (р. п.), вона є
областю визначеності деякої обчислюваної функції.
Виберемо тепер поліном
1( , ,..., )mp a y y , такий що
1 1,..., ( ( , ,..., ) 0)a m ma W y y p a y y . (5)
Це можна зробити в результаті діофантовості р. п. множини K . В
формулі (5) діафантів предикат
1 1,..., ( ( , ,..., ) 0)m my y p a y y є формальним
аналогом предиката x K , і це є ключовим результатом у теорії. В конструкції
Геделя були присутні квантор загальності та логічна операція «ні», які у теорії
фіофантових множин не використовуються [1].
Розглянемо функцію, яка визначається наступним чином
1 11, ,..., ( ( , ,..., ) 0),
( )
0,
m mякщо y y p a y y
F a
у протилежному випадку
.
Якщо би існувала вирішальна процедура для 10-ї проблеми Гільберта, то можна
було ефективно обчислити значення функції F , тобто проблема «
aa W »
була би розв’язною, але це неможливо.
З теорії діофантових множин випливає простий варіант теореми про
неповноту арифметики. Оскільки діафантові множини є р. п., всі рівняння
1( ,..., )kp x x =0, які мають розв'язки у цілих числах, можна рекурсивно
перелічити.
Непереліченими лишаються твердження про відсутність рішень для
рівнянь
1 1,... ( ,..., ) 0k kx x p x x . (6)
Якщо припустити, що для деякої несуперечливої системи аксіом можна
довести усі факти виду (6), це означало би існування алгоритму, який
перелічує теореми (6). Оскільки будь-які докази є скінченими, всі вони
утворюють рекурсивно перелічену множину [4]. Тобто цей алгоритм перелічує
доповнення до множини поліномів, які мають позитивні розв'язки. Відома
теорема Поста [4] говорить про те, що множина A є рекурсивною (розв'язною)
тоді і тільки тоді, коли множини A та A є р. п. Тобто отримуємо розв'язність
множини поліномів, які мають позитивні корені (в такому випадку множина
поліномів (6) є теж розв'язною). Таким чином маємо суперечність з негативним
рішенням 10-ї проблеми Гільберта.
Анатолій Гупал, Микита Гупал
Неповнота арифметики і теорія діофантових множин
72
Теорема 3. Для будь-якої несуперечної теорії, яка містить арифметику,
існує поліном, який не має цілих позитивних рішень, і для якого не можна
довести відсутність натуральних коренів.
Висновки. Аналіз діофантових множин показав, що всі рекурсивно перелічені
множини є діофантовими. На основі класичних результатів у теорії
рекурсивних функцій можна привести простий варіант теореми про неповноту
арифметики: існує поліном, який не має цілих позитивних рішень, і для якого
не можна довести відсутність натуральних коренів.
Література
[1] Мендельсон Э. Введение в математическую логику. — М.: Наука, 1971. – 320 с.
[2] Матиясевич Ю.В. Диофантовы множества. Успехи математических наук. 1971. т.22.
Вып.5.С.185 – 222.
[3] Матиясевич Ю.В. Десятая проблема Гильберта. – М.: Наука, 1993. – 224 с.
[4] Катленд Н. Вычислимость. Введение в теорию рекурсивных функций: Пер. с англ. – М.:
Мир, 1983. – 256 с.
–
Incompleteness of arithmetic and the Diophantine sets theory
Anatolii Hupal, Mykyta Hupal
Analysis of Diophantine sets showed that all recursively enumerated sets are Diophantine.
Based on the classical results in the theory of computable functions, a simple version of the
theorem on the incompleteness of arithmetic can be given: there is a polynomial that does not
have positive integer solutions, and for which it is impossible to prove the absence of positive
roots
Отримано 30.03.23
https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D1%83%D0%B4%D0%BD%D0%B8%D0%BA%D0%BE%D0%B2,_%D0%90%D0%BD%D0%B0%D1%82%D0%BE%D0%BB%D0%B8%D0%B9_%D0%9F%D0%BB%D0%B0%D1%82%D0%BE%D0%BD%D0%BE%D0%B2%D0%B8%D1%87
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-278 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:09:35Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/bb/22b249308076e76827d6070a29471cbb.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-2782025-02-21T17:32:19Z Incompleteness of arithmetic and the Diophantine sets theory Неповнота арифметики і теорія діофантових множин Hupal, Anatolii Hupal, Mykyta діофантова множина, рекурсивно перелічені множини, неповнота арифметики. Analysis of Diophantine sets showed that all recursively enumerated sets are Diophantine. Based on the classical results in the theory of computable functions, a simple version of the theorem on the incompleteness of arithmetic can be given: there is a polynomial that does not have positive integer solutions, and for which it is impossible to prove the absence of positive roots Аналіз діофантових множин показав, що всі рекурсивно перелічені множини є діофантовими. На основі класичних результатів у теорії рекурсивних  функцій наведено простий варіант теореми про неповноту арифметики: існує поліном, який не має цілих позитивних рішень, і для якого не можна довести відсутність позитивних коренів. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-13 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/278 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 68-72 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 68-72 2617-5258 1816-1545 10.15407/fmmit2023.36 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/278/252 |
| spellingShingle | діофантова множина рекурсивно перелічені множини неповнота арифметики. Hupal, Anatolii Hupal, Mykyta Неповнота арифметики і теорія діофантових множин |
| title | Неповнота арифметики і теорія діофантових множин |
| title_alt | Incompleteness of arithmetic and the Diophantine sets theory |
| title_full | Неповнота арифметики і теорія діофантових множин |
| title_fullStr | Неповнота арифметики і теорія діофантових множин |
| title_full_unstemmed | Неповнота арифметики і теорія діофантових множин |
| title_short | Неповнота арифметики і теорія діофантових множин |
| title_sort | неповнота арифметики і теорія діофантових множин |
| topic | діофантова множина рекурсивно перелічені множини неповнота арифметики. |
| topic_facet | діофантова множина рекурсивно перелічені множини неповнота арифметики. |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/278 |
| work_keys_str_mv | AT hupalanatolii incompletenessofarithmeticandthediophantinesetstheory AT hupalmykyta incompletenessofarithmeticandthediophantinesetstheory AT hupalanatolii nepovnotaarifmetikiíteoríâdíofantovihmnožin AT hupalmykyta nepovnotaarifmetikiíteoríâdíofantovihmnožin |