арифметика в ТМ

[Z1X]

Нет, я все же до конца не понимаю, в каком смысле арифметика строится в теории множеств. Возможно, аксиомы Пеано рассматриваются как теоремы ТМ, но тогда откуда у нас арифметические операции и само множество $\mathbb{N}$? Знаки этих операций придется добавить в сигнатуру, а сам символ $\mathbb{N}$ войдет как константа. Либо эти символы предназначены для сокращения громоздких теоретико-множественных утверждений, но самих-то утверждений в ТМ нет, откуда и как их вывести — неясно. Вот пример: $\forall x \in \mathbb{N} \ x\cdot 0 = 0$. Чем и как тут заменить умножение, если мы хотим получить то же утверждение, записанное строго в языке ZFC и ограниченное этим языком?

[Xaositect]

Надо определить кроме множества $\mathbb{N}$ еще теоретико-множественные функции $+$ и $\cdot$.
Можно, например, определить $\mathbb{N}$ как множестве конечных ординалов (минимальное транзитивное множество), а $+ = \{(x, y, z) \in \mathbb{N}^3 \mid z \cong x \dot{\cup} y \}$ и $\cdot = \{(x, y, z) \in \mathbb{N}^3 \mid z \cong x\times y\}$, где $\cong$ - равномощность множеств, $x \dot{\cup} y = \{0\} \times x \cup \{1\} \times y $ - дизъюнктное объединение.

[Z1X]

Надо определить — значит надо ввести дополнительные аксиомы, но тогда придется выйти за рамки ТМ. Тогда это уже не построение в ТМ, а построение в более слабой теории.

Чтобы определить именно арифметические операции, необходимо доказать, что все свойства, прописанные в аксиоматике Пеано, для них выполняются. Я не понимаю, к чему все это, если просто отдельно существует арифметика как теория первого порядка. Что-то мешает ей пользоваться?

[Xaositect]

Z1X в сообщении #1237137 писал(а):

Надо определить — значит надо ввести дополнительные аксиомы, но тогда придется выйти за рамки ТМ. Тогда это уже не построение в ТМ, а построение в более слабой теории.

Определить - в смысле ввести сокращения, это не более слабая теория, а консервативное расширение.

Z1X в сообщении #1237137 писал(а):

Чтобы определить именно арифметические операции, необходимо доказать, что все свойства, прописанные в аксиоматике Пеано, для них выполняются. Я не понимаю, к чему все это, если просто отдельно существует арифметика как теория первого порядка. Что-то мешает ей пользоваться?

Да в принципе, ничего не мешает. Просто явное построение модели этой самой арифметики первого порядка, без использования теоремы о полноте. Эта модель называется стандартной моделью арифметики обычно.

[Someone]

Z1X в сообщении #1237125 писал(а):

Нет, я все же до конца не понимаю, в каком смысле арифметика строится в теории множеств.

Не арифметика строится, а её модель.

Про введение новых обозначений уже сказали: их можно вводить сколько угодно, определяя их значение в терминах теории множеств. Это даёт так называемое консервативное расширение языка. При желании их всегда можно исключить, просто заменив их соответствующими определениями.

Стандартная схема построения "стандартной" модели арифметики следующая.

Определяется теоретико-множественная функция последователь, которая каждому множеству $x$ ставит в соответствие множество $x'=x\cup\{x\}$.
Множество $a$ называется индуктивным, если оно удовлетворяет двум условиям: 1) $\varnothing\in a$ и 2) если $x\in a$, то$x'\in a$.
Аксиома бесконечности утверждает, что хотя бы одно индуктивное множество существует.
Доказывается, что существует наименьшее (в смысле включения) индуктивное множество, причём, оно единственное.
Натуральный ряд $\mathbb N$ определяется как наименьшее индуктивное множество, а его элементы называются натуральными числами. Предыдущее утверждение означает, что символ $\mathbb N$ определён корректно (имеет вполне определённый смысл).
Элементы $\mathbb N$ сопоставляются натуральным числам так: $0=\varnothing$, $1=0'=\{0\}$, $2=1'=\{0,1\}$, $3=2'=\{0,1,2\}$, …
Доказываются различные схемы определения по индукции. Например: если заданы функции $g\colon\mathbb N\times\mathbb N\to\mathbb N$ и $f\colon\mathbb N\times\mathbb N\times\mathbb N\to\mathbb N$, то существует и единственна функция $\varhi\colon\mathbb N\times\mathbb N\to\mathbb N$, удовлетворяющая условиям 1) $\varphi(0,a)=g(a)$ и 2) $\varphi(n',a)=f(\varphi(n,a),n,a)$.
Далее мы можем определить сумму и произведение.
Для суммы мы вместо $\varphi(n,m)$ пишем $m+n$, берём $g(m)=m$ и $f(x,n,m)=x'$, то есть, определяем $m+n$ соотношениями 1) $m+0=m$ и 2) $m+n'=(m+n)'$.
Аналогично произведение определяется соотношениями 1) $m\cdot 0=0$ и 2) $m\cdot n'=m\cdot n+m$, то есть, здесь $g(m)=0$ и $f(x,n,m)=x+m$.
Далее доказывается, что выполнены все аксиомы арифметики Пеано.

Где найти подробное построение, я не знаю. В учебнике К. Куратовского и А. Мостовского "Теория множеств" глава III посвящена натуральным числам, но там не ставится задача детального построения модели арифметики. Правда, есть ссылка на цикл работ П. Бернайса.

[Z1X]

Xaositect, Someone, благодарю за ответы. Проще говоря, в ZFC можно доказать теорему, что существует множество (и не одно), для которого выполняются все аксиомы Пеано. После доказательства единственности наименьшего индуктивного множества, думаю, уже можно вводить понятие счетности. А чтобы определить конечность множества, надо выразить $\leqslant$ через сложение и ввести условие равномощности отрезку натурального ряда. Все верно?

Xaositect в сообщении #1237133 писал(а):

$x \dot{\cup} y = \{0\} \times x \cup \{1\} \times y $

Так: $x \dot{\cup} y = (\{0\} \times x) \cup (\{1\} \times y) $. Да?

[Xaositect]

Z1X в сообщении #1237298 писал(а):

Так: $x \dot{\cup} y = (\{0\} \times x) \cup (\{1\} \times y) $. Да?

Да.

[Someone]

Z1X в сообщении #1237298 писал(а):

Проще говоря, в ZFC можно доказать теорему, что существует множество (и не одно), для которого выполняются все аксиомы Пеано.

Точнее, можно определить множество и необходимые структуры на нём.

Z1X в сообщении #1237298 писал(а):

После доказательства единственности наименьшего индуктивного множества, думаю, уже можно вводить понятие счетности.

Можно, но понятие счётности к арифметике отношения не имеет.

Z1X в сообщении #1237298 писал(а):

А чтобы определить конечность множества, надо выразить $\leqslant$ через сложение и ввести условие равномощности отрезку натурального ряда.

В описанном построении конечные множества — это множества, равномощные натуральным числам. Поскольку натуральные числа и есть отрезки натурального ряда. Причём, $m\leqslant n\Leftrightarrow m\subseteq n$\Leftrightarrow m\in n, так что в рассматриваемой модели отношение порядка определяется прямо в теоретико-множественных терминах.

Xaositect в сообщении #1237133 писал(а):

$+ = \{(x, y, z) \in \mathbb{N}^3 \mid z \cong x \dot{\cup} y \}$

Не припомню, чтобы мне где-нибудь такой способ попадался. Стандартно в арифметике арифметические операции определяются индуктивно (в самой арифметике Пеано они должны быть заданы изначально, так как их существование доказать нельзя; в теории множеств существование операций сложения и умножения доказывается).

[Z1X]

Someone в сообщении #1237482 писал(а):

Не припомню, чтобы мне где-нибудь такой способ попадался.

Это хороший способ, но нужно разобраться, как мы меняем термы. Теоретико-множественных термов не существует, а арифметические должны только играть роль сокращений теоретико-множественного языка. Идея такая:
$a+b=c \leftrightarrow a \dot{\cup} b \cong c$
$a+b=c+d \leftrightarrow a \dot{\cup} b \cong c \dot{\cup} d$

-- 01.08.2017, 19:40 --

В принципе так можно складывать любые множества, но операция будет неоднозначной. А однозначность на множестве $\mathbb{N}$ — это отдельный факт, который тоже подлежит доказательству, если строить всё по-честному.

[Someone]

Z1X в сообщении #1237556 писал(а):

Это хороший способ, но нужно разобраться, как мы меняем термы.

Не вижу в нём ничего хорошего. Если $a$ и $b$ — натуральные числа, то $a\dot\cup b=(\{0\}\times a)\cup(\{1\}\times b)$ — не натуральное число, и нужно дополнительное построение, чтобы получить натуральное число. И, боюсь, всё равно не удастся избежать рекурсивного определения суммы.

[Z1X]

Someone, результат операции однозначно выбирается по равномощности. Дополнительного построения не нужно, нужно просто существование биекции.

[Someone]

Z1X в сообщении #1237569 писал(а):

Дополнительного построения не нужно, нужно просто существование биекции.

Я это определение понимаю. Но оно не конструктивно. А для того, чтобы использовать арифметику, нам нужно конструктивное определение суммы и произведения.

-- Ср авг 02, 2017 03:56:13 --

С другой стороны, Вам необходимо доказать, что существует натуральное число, равномощное $a\dot\cup b$. Боюсь, что всё сведётся к тому же индуктивному определению суммы (или другому аналогичному).

[Xaositect]

Someone в сообщении #1237574 писал(а):

С другой стороны, Вам необходимо доказать, что существует натуральное число, равномощное $a\dot\cup b$. Боюсь, что всё сведётся к тому же индуктивному определению суммы (или другому аналогичному).

Конечно сведется, у нас в распоряжении ведь только транзитивность $\mathbb N$, что и есть индукция. Я это определение выбрал исключительно потому, что его просто написать.

[popique]

Уважаемый Someone,

объясните, пожалуйста, для чего вводится функция $g$, если в простейшем случае $\varphi(0) = x$ и какую роль играет дополнительная переменная $a$?

[arseniiv]

Вот вам рекурсия без дополнительной переменной:

Если $g\in A$ и $f\colon A\times\mathbb N\to A$, то существует функция $\varphi\colon\mathbb N\to A$ такая, что $\varphi(0) = g$ и $\varphi(n') = f(\varphi(n), n)$.

Вот определите сложение с помощью неё.

-- Вс апр 26, 2020 14:45:11 --

(Спойлер: это всё равно возможно из-за того что я написал произвольное множество $A$.)