Арифметический набор
-
Определение арифметических множеств
- Арифметическое множество — это множество натуральных чисел, которое может быть описано арифметической формулой.
- Арифметические множества включают множество простых чисел, рекурсивно перечислимые множества и вычислимые функции.
-
Примеры арифметических множеств
- Множество простых чисел является арифметическим.
- Множество рекурсивно перечислимых множеств также является арифметическим.
- Множество, кодирующее проблему остановки, также является арифметическим.
-
Теорема Тарского о неопределимости
- Множество истинных формул арифметики первого порядка не может быть описано арифметически.
-
Свойства арифметических множеств
- Дополнение к арифметическому множеству также является арифметическим.
- Скачок Тьюринга арифметического множества также является арифметическим.
- Совокупность арифметических множеств может быть подсчитана, но последовательность множеств не может быть описана арифметически.
-
Неявно арифметические множества
- Множество Y натуральных чисел является неявно арифметическим, если оно определяется формулой, которая использует Y в качестве параметра.
- Множество истинностей арифметики первого порядка является неявно арифметическим, но не точно арифметическим.
-
Альтернативные понятия определяемости
- Существует понятие определяемости, которое позволяет описать множество, удовлетворяющее арифметическому свойству, а не только входящее в него.
-
Дальнейшее чтение
- Статья содержит ссылки на другие источники, включая книги и статьи, для более глубокого изучения темы арифметических множеств.