Обчисленна множина (також рекурсивна множина) - множина натуральних чисел, для якої існує алгоритм, що отримує на вхід будь-яке натуральне число і після скінченної кількості кроків (можливо залежної від цього числа) дає відповідь, чи належить це число даній множині, чи ні. Іншими словами, множина є обчисленною, якщо її характеристична функція обчисленна . Множина, яка не є обчисленною, називається необчисленною. Також можна говорити про обчисленну множину, що складається з будь-яких конструктивних об'єктів, що кодуються натуральними числами. Будь-яка обчисливана множина є і . Дозволені множини відповідають рівню [en] .
У загальному випадку, підмножина множини конструктивних елементів називається обчисленною щодо , якщо існує алгоритм, застосовний до об'єктів з та у разі застосування до деякого об'єкту цей алгоритм дає відповідь на запитання, чи належить цей об'єкт .
Існують перераховні множини, які не є обчисленними. Більше того, перераховна множина розв'язна тоді і тільки тоді, коли її доповнення також перераховне. Проєкція обчисленної множини перераховна, але може не бути обчисленною. Підмножина обчисленної множини може не бути обчисленною (і навіть може не бути перераховною).
Сукупність всіх обчисленних підмножин це зліченна множина, а сукупність всіх необчисленних підмножин це незліченна множина, так як множина всіх підмножин позитивних цілих чисел незліченна.
Існує взаємно однозначна відповідність між обчисленними підмножинами та [en] .
Приклади
- Порожня множина є обчисленною.
- Будь-яка скінченна множина та її доповнення є обчисленними множинами.
- Існують нескінченні обчисленні множини з нескінченним доповненням. Наприклад, множина всіх парних чисел і множина простих чисел обчисленні.
- Доповнення обчисленної множини є обчисленним.
- Об'єднання та перетин скінченного числа обчисленних множин також обчисленні.
- Будь-яка перераховна множина, доповнення якої також перераховне, є обчисленною ([en]).
- Множина раціональних чисел, менших числа є обчисленною.
- Множина, єдиний елемент якої дорівнює одиниці, якщо гіпотеза Рімана вірна, і нулю в іншому випадку, є обчисленною (бо вона скінченна).
- Множина номерів нетривіальних нулів ζ-функції, для котрих порушується гіпотеза Рімана, є обчисленною (хоча невідомо, чи вона порожня, скінченна чи нескінченна).
- Множина рядків, які є правильними доведеннями ZFC, є обчисленною. Її проєкція — множина тверджень, що доводяться в ZFC — перераховна, але, за умови несуперечності ZFC — необчисленна.
Примітки
- Эббинхауз, 1972, с. 19.
- Биркгоф Г., Барти Т. Современная прикладная алгебра. — М., Мир, 1976. — с. 375—376
Література
- Эббинхауз Г.Д., Якобс К., Ман Ф.К., Хермес Г. Машины Тьюринга и рекурсивные функции. — М. : Мир, 1972. — 262 с.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Obchislenna mnozhina takozh rekursivna mnozhina mnozhina naturalnih chisel dlya yakoyi isnuye algoritm sho otrimuye na vhid bud yake naturalne chislo i pislya skinchennoyi kilkosti krokiv mozhlivo zalezhnoyi vid cogo chisla daye vidpovid chi nalezhit ce chislo danij mnozhini chi ni Inshimi slovami mnozhina ye obchislennoyu yaksho yiyi harakteristichna funkciya obchislenna Mnozhina yaka ne ye obchislennoyu nazivayetsya neobchislennoyu Takozh mozhna govoriti pro obchislennu mnozhinu sho skladayetsya z bud yakih konstruktivnih ob yektiv sho koduyutsya naturalnimi chislami Bud yaka obchislivana mnozhina ye i Dozvoleni mnozhini vidpovidayut rivnyu D 1 0 displaystyle Delta 1 0 en U zagalnomu vipadku pidmnozhina M 1 displaystyle mathfrak M 1 mnozhini M 2 displaystyle mathfrak M 2 konstruktivnih elementiv nazivayetsya obchislennoyu shodo M 2 displaystyle mathfrak M 2 yaksho isnuye algoritm zastosovnij do ob yektiv z M 2 displaystyle mathfrak M 2 ta u razi zastosuvannya do deyakogo ob yektu M 2 displaystyle mathfrak M 2 cej algoritm daye vidpovid na zapitannya chi nalezhit cej ob yekt M 1 displaystyle mathfrak M 1 Isnuyut pererahovni mnozhini yaki ne ye obchislennimi Bilshe togo pererahovna mnozhina rozv yazna todi i tilki todi koli yiyi dopovnennya takozh pererahovne Proyekciya obchislennoyi mnozhini pererahovna ale mozhe ne buti obchislennoyu Pidmnozhina obchislennoyi mnozhini mozhe ne buti obchislennoyu i navit mozhe ne buti pererahovnoyu Sukupnist vsih obchislennih pidmnozhin N displaystyle mathbb N ce zlichenna mnozhina a sukupnist vsih neobchislennih pidmnozhin N displaystyle mathbb N ce nezlichenna mnozhina tak yak mnozhina vsih pidmnozhin pozitivnih cilih chisel 2 P displaystyle 2 P nezlichenna Isnuye vzayemno odnoznachna vidpovidnist mizh obchislennimi pidmnozhinami S P displaystyle S subset P ta en x 0 1 displaystyle x in 0 1 PrikladiPorozhnya mnozhina ye obchislennoyu Bud yaka skinchenna mnozhina ta yiyi dopovnennya ye obchislennimi mnozhinami Isnuyut neskinchenni obchislenni mnozhini z neskinchennim dopovnennyam Napriklad mnozhina vsih parnih chisel i mnozhina prostih chisel obchislenni Dopovnennya obchislennoyi mnozhini ye obchislennim Ob yednannya ta peretin skinchennogo chisla obchislennih mnozhin takozh obchislenni Bud yaka pererahovna mnozhina dopovnennya yakoyi takozh pererahovne ye obchislennoyu en Mnozhina racionalnih chisel menshih chisla p displaystyle pi ye obchislennoyu Mnozhina yedinij element yakoyi dorivnyuye odinici yaksho gipoteza Rimana virna i nulyu v inshomu vipadku ye obchislennoyu bo vona skinchenna Mnozhina nomeriv netrivialnih nuliv z funkciyi dlya kotrih porushuyetsya gipoteza Rimana ye obchislennoyu hocha nevidomo chi vona porozhnya skinchenna chi neskinchenna Mnozhina ryadkiv yaki ye pravilnimi dovedennyami ZFC ye obchislennoyu Yiyi proyekciya mnozhina tverdzhen sho dovodyatsya v ZFC pererahovna ale za umovi nesuperechnosti ZFC neobchislenna PrimitkiEbbinhauz 1972 s 19 Birkgof G Barti T Sovremennaya prikladnaya algebra M Mir 1976 s 375 376LiteraturaEbbinhauz G D Yakobs K Man F K Hermes G Mashiny Tyuringa i rekursivnye funkcii M Mir 1972 262 s