Арифметическое множество
Арифметическое множество — множество натуральных чисел <math>S</math>, которое может быть определено формулой в языке арифметики первого порядка, то есть если существует такая формула <math>\phi(x)</math> с одной свободной переменной <math>x,</math> что <math>\forall x (x \in S \leftrightarrow \phi(x))</math>. Также можно говорить об арифметических множествах кортежей натуральных чисел, конечных последовательностей натуральных чисел, формул (при любой их фиксированной гёделевской нумерации) и, вообще, об арифметических множествах любых конструктивных объектов, кодируемых натуральными числами.
Связанные определения
Функция <math>\N \to \N</math> называется арифметической, если её график является арифметическим множеством. Аналогично, можно говорить об арифметичности функций <math>\N^n \to \N</math> и, вообще, функций, определённых на множествах любых конструктивных объектов.
Действительное число называется арифметическим, если множество рациональных чисел, меньших него, арифметично (или, что эквивалентно, если множество рациональных чисел, больших него, арифметично). Комплексное число называется арифметическим, если арифметичны и его действительная, и мнимая части.
Свойства
- Подмножество арифметического множества не обязательно арифметично.
- Совокупность всех арифметических множеств натуральных чисел является счётным множеством, а совокупность всех неарифметических множеств — несчётным.
- Множество комплексных арифметических чисел образует алгебраически замкнутое поле.
- Любое вычислимое число является арифметическим.
- Множество арифметических чисел (равно как и его дополнение) плотно в <math>\R</math> и в <math>\C.</math>
- Порядок на множестве действительных арифметических чисел изоморфен порядку на множестве рациональных чисел.
Примеры
- Пустое множество является арифметическим.
- Любое перечислимое множество (в частности, любое разрешимое множество и любое конечное множество) являются арифметическими.
- Дополнение и проекция любого арифметического множества являются арифметическими.
- Объединение и пересечение конечного числа арифметических множеств также являются арифметическими.
- Множество чисел, начинающаяся с которых последовательность, определённая в гипотезе Коллатца, завершается единицей — арифметично, а в случае справедливости этой гипотезы — даже разрешимо тривиальным образом (всё множество натуральных чисел).
- Множество рациональных чисел, больших постоянной Хайтина Ω, арифметично, но неперечислимо.
- Множество номеров машин Тьюринга, не останавливающихся на пустом входе, арифметично (хотя и не перечислимо).
- Но множество номеров машин Тьюринга, реализующих операцию сравнения натуральных чисел, вполне упорядочивающую каким-либо образом множество <math>\N,</math> неарифметично.
- Множество утверждений, недоказуемых в ZFC, является арифметическим, но, при условии непротиворечивости ZFC — неперечислимым.
- Но множество истинных утверждений в арифметике первого порядка не является арифметическим (что составляет утверждение теоремы Тарского о невыразимости истины в арифметике), хотя множество доказуемых утверждений арифметично и даже перечислимо.
См. также
- Арифметическая иерархия (англ.)
- Гиперарифметическая иерархия (англ.)
- Аналитическая иерархия (англ.)
- Проективная иерархия (англ.)
- Борелевская иерархия (англ.)
Напишите отзыв о статье "Арифметическое множество"
Литература
- Н. К. Верещагин, А. Шень. [www.mccme.ru/free-books/shen/shen-logic-part2.pdf Часть 2. Языки и исчисления] // Лекции по математической логике и теории алгоритмов. — 2-е изд.. — М.: МЦНМО, 2002.
Это заготовка статьи по математической логике. Вы можете помочь проекту, дополнив её. |
Отрывок, характеризующий Арифметическое множество
Забавлявшая прежде Пьера болтовня француза теперь показалась ему противна. И насвистываемая песенка, и походка, и жест покручиванья усов – все казалось теперь оскорбительным Пьеру.«Я сейчас уйду, я ни слова больше не скажу с ним», – думал Пьер. Он думал это, а между тем сидел все на том же месте. Какое то странное чувство слабости приковало его к своему месту: он хотел и не мог встать и уйти.
Капитан, напротив, казался очень весел. Он прошелся два раза по комнате. Глаза его блестели, и усы слегка подергивались, как будто он улыбался сам с собой какой то забавной выдумке.
– Charmant, – сказал он вдруг, – le colonel de ces Wurtembourgeois! C'est un Allemand; mais brave garcon, s'il en fut. Mais Allemand. [Прелестно, полковник этих вюртембергцев! Он немец; но славный малый, несмотря на это. Но немец.]
Он сел против Пьера.
– A propos, vous savez donc l'allemand, vous? [Кстати, вы, стало быть, знаете по немецки?]
Пьер смотрел на него молча.
– Comment dites vous asile en allemand? [Как по немецки убежище?]
– Asile? – повторил Пьер. – Asile en allemand – Unterkunft. [Убежище? Убежище – по немецки – Unterkunft.]
– Comment dites vous? [Как вы говорите?] – недоверчиво и быстро переспросил капитан.
– Unterkunft, – повторил Пьер.
– Onterkoff, – сказал капитан и несколько секунд смеющимися глазами смотрел на Пьера. – Les Allemands sont de fieres betes. N'est ce pas, monsieur Pierre? [Экие дурни эти немцы. Не правда ли, мосье Пьер?] – заключил он.
– Eh bien, encore une bouteille de ce Bordeau Moscovite, n'est ce pas? Morel, va nous chauffer encore une pelilo bouteille. Morel! [Ну, еще бутылочку этого московского Бордо, не правда ли? Морель согреет нам еще бутылочку. Морель!] – весело крикнул капитан.
Морель подал свечи и бутылку вина. Капитан посмотрел на Пьера при освещении, и его, видимо, поразило расстроенное лицо его собеседника. Рамбаль с искренним огорчением и участием в лице подошел к Пьеру и нагнулся над ним.
– Eh bien, nous sommes tristes, [Что же это, мы грустны?] – сказал он, трогая Пьера за руку. – Vous aurai je fait de la peine? Non, vrai, avez vous quelque chose contre moi, – переспрашивал он. – Peut etre rapport a la situation? [Может, я огорчил вас? Нет, в самом деле, не имеете ли вы что нибудь против меня? Может быть, касательно положения?]
Пьер ничего не отвечал, но ласково смотрел в глаза французу. Это выражение участия было приятно ему.
– Parole d'honneur, sans parler de ce que je vous dois, j'ai de l'amitie pour vous. Puis je faire quelque chose pour vous? Disposez de moi. C'est a la vie et a la mort. C'est la main sur le c?ur que je vous le dis, [Честное слово, не говоря уже про то, чем я вам обязан, я чувствую к вам дружбу. Не могу ли я сделать для вас что нибудь? Располагайте мною. Это на жизнь и на смерть. Я говорю вам это, кладя руку на сердце,] – сказал он, ударяя себя в грудь.
– Merci, – сказал Пьер. Капитан посмотрел пристально на Пьера так же, как он смотрел, когда узнал, как убежище называлось по немецки, и лицо его вдруг просияло.
– Ah! dans ce cas je bois a notre amitie! [А, в таком случае пью за вашу дружбу!] – весело крикнул он, наливая два стакана вина. Пьер взял налитой стакан и выпил его. Рамбаль выпил свой, пожал еще раз руку Пьера и в задумчиво меланхолической позе облокотился на стол.
– Oui, mon cher ami, voila les caprices de la fortune, – начал он. – Qui m'aurait dit que je serai soldat et capitaine de dragons au service de Bonaparte, comme nous l'appellions jadis. Et cependant me voila a Moscou avec lui. Il faut vous dire, mon cher, – продолжал он грустным я мерным голосом человека, который сбирается рассказывать длинную историю, – que notre nom est l'un des plus anciens de la France. [Да, мой друг, вот колесо фортуны. Кто сказал бы мне, что я буду солдатом и капитаном драгунов на службе у Бонапарта, как мы его, бывало, называли. Однако же вот я в Москве с ним. Надо вам сказать, мой милый… что имя наше одно из самых древних во Франции.]