Арифметическое множество

Арифметическое множество

18.12.2020

Арифметическое множество — множество натуральных чисел S {displaystyle S} , которое может быть определено формулой в языке арифметики первого порядка, то есть если существует такая формула ϕ ( x ) {displaystyle phi (x)} с одной свободной переменной x , {displaystyle x,} что ∀ x ( x ∈ S ↔ ϕ ( x ) ) {displaystyle forall x(xin Sleftrightarrow phi (x))} . Также можно говорить об арифметических множествах кортежей натуральных чисел, конечных последовательностей натуральных чисел, формул (при любой их фиксированной гёделевской нумерации) и, вообще, об арифметических множествах любых конструктивных объектов, кодируемых натуральными числами.

Связанные определения

Функция N → N {displaystyle mathbb {N} o mathbb {N} } называется арифметической, если её график является арифметическим множеством. Аналогично, можно говорить об арифметичности функций N n → N {displaystyle mathbb {N} ^{n} o mathbb {N} } и, вообще, функций, определённых на множествах любых конструктивных объектов.

Действительное число называется арифметическим, если множество рациональных чисел, меньших него, арифметично (или, что эквивалентно, если множество рациональных чисел, больших него, арифметично). Комплексное число называется арифметическим, если арифметичны и его действительная, и мнимая части.

Свойства

  • Подмножество арифметического множества не обязательно арифметично.
  • Совокупность всех арифметических множеств натуральных чисел является счётным множеством, а совокупность всех неарифметических множеств — несчётным.
  • Множество комплексных арифметических чисел образует алгебраически замкнутое поле.
  • Любое вычислимое число является арифметическим.
  • Множество арифметических чисел (равно как и его дополнение) плотно в R {displaystyle mathbb {R} } и в C . {displaystyle mathbb {C} .}
  • Порядок на множестве действительных арифметических чисел изоморфен порядку на множестве рациональных чисел.

Примеры

  • Пустое множество является арифметическим.
  • Любое перечислимое множество (в частности, любое разрешимое множество и любое конечное множество) являются арифметическими.
  • Дополнение и проекция любого арифметического множества являются арифметическими.
  • Объединение и пересечение конечного числа арифметических множеств также являются арифметическими.
  • Множество чисел, начинающаяся с которых последовательность, определённая в гипотезе Коллатца, завершается единицей — арифметично, а в случае справедливости этой гипотезы — даже разрешимо тривиальным образом (всё множество натуральных чисел).
  • Множество рациональных чисел, больших постоянной Хайтина Ω, арифметично, но неперечислимо.
  • Множество номеров машин Тьюринга, не останавливающихся на пустом входе, арифметично (хотя и не перечислимо).
  • Но множество номеров машин Тьюринга, реализующих операцию сравнения натуральных чисел, вполне упорядочивающую каким-либо образом множество N , {displaystyle mathbb {N} ,} неарифметично.
  • Множество утверждений, недоказуемых в ZFC, является арифметическим, но, при условии непротиворечивости ZFC — неперечислимым.
  • Но множество истинных утверждений в арифметике первого порядка не является арифметическим (что составляет утверждение теоремы Тарского о невыразимости истины в арифметике), хотя множество доказуемых утверждений арифметично и даже перечислимо.