Центральный Дом Знаний - Арифметическое множество

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Как Вы планируете отдохнуть летом?
Всего ответов: 903

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

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

В теории множеств и математической логике, множество натуральных чисел  называется арифмети́ческим, если оно может быть определено формулой в языке арифметики первого порядка, то есть если существует такая формула  с одной свободной переменной  что  Также можно говорить об арифметических множествахкортежей натуральных чисел, конечных последовательностей натуральных чисел, формул (при любой их фиксированной гёделевской нумерации) и, вообще, об арифметических множествах любых конструктивных объектов, кодируемых натуральными числами.

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

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

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

Свойства

  • Подмножество арифметического множества не обязательно арифметично.

  • Совокупность всех арифметических множеств натуральных чисел является счётным множеством, а совокупность всех неарифметических множеств — несчётным.

  • Множество комплексных арифметических чисел образует алгебраически замкнутое поле.

  • Любое вычислимое число является арифметическим.

  • Множество арифметических чисел (равно как и его дополнение) плотно в \R и в \C.

  • Порядок на множестве действительных арифметических чисел изоморфен порядку на множестве рациональных чисел.

Примеры

  • Пустое множество является арифметическим.

  • Любое перечислимое множество (в частности, любое разрешимое множество и любое конечное множество) являются арифметическими.

  • Дополнение и проекция (англ.) любого арифметического множества являются арифметическими.

  • Объединение и пересечение конечного числа арифметических множеств также являются арифметическими.

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

  • Множество рациональных чисел, больших постоянной Хайтина Ω, арифметично, но неперечислимо.

  • Множество номеров машин Тьюринга, не останавливающихся на пустом входе, арифметично (хотя и не перечислимо).

  • Но множество номеров машин Тьюринга, реализующих операцию сравнения натуральных чисел, вполне упорядочивающую каким-либо образом множество \N, неарифметично.

  • Множество утверждений, недоказуемых в ZFC, является арифметическим, но, при условии непротиворечивости ZFC — неперечислимым.

  • Но множество истинных утверждений в арифметике первого порядка не является арифметическим (что составляет утверждение теоремы Тарского о невыразимости истины в арифметике), хотя множество доказуемых утверждений арифметично и даже перечислимо.

Лит.: Н. К. Верещагин, А. Шень Часть 2. Языки и исчисления // Лекции по математической логике и теории алгоритмов. — 2-е изд.. — М.: МЦНМО, 2002.

Loading

Календарь

«  Сентябрь 2019  »
ПнВтСрЧтПтСбВс
      1
2345678
9101112131415
16171819202122
23242526272829
30

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24