Докажите трихотомический закон сложения в $\mathbb{N}$ (Аксиомы Пеано).

Aug 20 2020

Мне нужна помощь в моем доказательном законе сложения трихотомии в $\mathbb{N}$(Аксиомы Пеано). Я уже доказал, что сложение ассоциативно и коммутативно. Также я доказал закон сокращения и несколько полезных лемм. Теперь у меня возникли проблемы с доказательством следующего утверждения:

Позволять $m,n \in \mathbb{N}$. Тогда верно ровно одно из следующих утверждений:

  1. $m=n$
  2. Есть натуральное число $p \neq 0$ такой, что $ m = n + p$.
  3. Есть натуральное число $q \neq 0 $ такой, что $n = m + q$.

Моя попытка

Во-первых, я доказал, что два из этих утверждений не могут происходить одновременно.

Если $1), 2)$ верны, тогда $m=m+p$ и по закону об отмене, $p=0$, противоречие. Это аналогично для$1),3)$. Тогда предположим$2),3)$. Потом,$m = m + q + p$, и по закону об отмене, $ 0 = q + p \implies q=p=0$Противоречие (последнее утверждение я доказал ранее). Тогда не более 1 утверждения может быть верным.

Теперь мне нужно доказать, что по крайней мере $1$из утверждений верно, чтобы завершить доказательство, но я не знаю, что делать дальше. Я знаю, что это простой / классический вопрос, но я не нашел сообщений об этом в MSE. Если такая публикация существует, дайте мне знать и извините за перепост.

Любые подсказки приветствуются.

Ответы

1 DoctorWho Aug 20 2020 at 05:35

Сначала мы докажем, что для всех $n, m$, или $\exists p (n + p = m)$ или же $\exists p (m + p = m)$. Будем действовать индукцией по$m$.

Базовый вариант $m = 0$: тогда у нас есть $m + n = 0 + n = n + 0 = n$.

Индуктивный корпус $m = S(k)$: мы разбиваем на три подслучая на основе индуктивной гипотезы и того факта, что каждое число является либо преемником, либо нулем.

Подслучай $k + p = n$ где $p = S(p')$: тогда у нас есть $n = k + S(p') = S(k + p') = S(p' + k) = p' + S(k) = p' + m = m + p'$.

Подслучай $k + p = n$ где $p = 0$: тогда $k + 0 = k = n$. потом$m = S(k) = S(n)$. потом$m = S(n + 0) = n + S(0)$.

Подслучай $n + p = k$: тогда $n + S(p) = S(n + p) = m$.

Таким образом, мы доказали, что для каждого $n$, $m$, или $\exists p (n + p = m)$ или же $\exists p (m + p = n)$.

Теперь мы хотим доказать, что для каждого $n, m$, у нас есть хотя бы один из $n = m$, $\exists p (n + S(p) = m)$, и $\exists p (m + S(p) = n)$.

Теперь предположим, что WLOG $\exists p (n + p = m)$. Мы разделились на два случая. Во-первых, предположим, что$p = 0$. Тогда у нас есть$n = m$. Во-вторых, предположим, что мы можем написать$p = S(p')$. Тогда у нас есть$n + S(p') = m$. Дело$\exists p (m + p = n)$ похож.

Очевидно, этого достаточно, чтобы показать, что хотя бы один из вариантов вашей трихотомии верен.