Demostrar la conmutatividad del producto en números naturales.

Question

El objetivo de este ejercicio es demostrar el resultado conocido como conmutatividad en$\mathbb{N}.$

Para eso se define la función p:$\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N} $

$ p(m,n) = m + ... + m $ (n veces)

La definición inductiva formal es la siguiente:

$$ p (m, n) = \ left \ {\begin{array}{l l} m & \quad \text{if n = 1,}\\ p(m,n-1) +m & \quad \text{other case.} \end {array} \ right. $$

Demuestre que por cada par de números naturales:$$ p(m,n) = p(n,m)$ $

como sugerencia, me dicen que haga inducción en$max(n,m).$

¿Alguna duda sobre cómo empezar?

Answer 1

Realmente no sé cómo usar $\text{max}$ función - yo lo he hecho de otra manera - puede ser que le ayude.

Tiene dos axiomas:
$p(a,1)=a$ - número uno,
$p(a,n+1)=p(a,n)+a$ - el número dos.

Lema 1: $$p(1,a)=a.$$

De inducción.
Base: $p(1,1)=1$ - el primer axioma.

Inducción de la hipótesis: $p(1,n)=n$

Inducción paso:
$p(1,n+1)=p(1,n)+1$ - el segundo axioma,
$p(1,n)+1=n+1$ - hipótesis de inducción.

Por eso, $$p(1,n+1)=n+1$$ y el Lema 1 se demuestra.

Lema 2 - derecho-propiedad distributiva, $$p(a+b,c)=p(a,c)+p(b,c)$$

Base: $p(a+b,1)=a+b=p(a,1)+p(b,1)$ - el primer axioma.

Inducción de la hipótesis: $p(a+b,n)=p(a,n)+p(b,n)$

Paso:
$p(a+b,n+1)=p(a+b,n)+(a+b)$ - el segundo axioma,
$p(a+b,n)+(a+b)=p(a,n)+p(b,n)+(a+b)$ - inducción, hipótesis,
$p(a,n)+p(b,n)+(a+b)=(p(a,n)+a)+(p(b,n)+b)$ - el asociativa y conmutativa leyes para la adición,
$(p(a,n)+a)+(p(b,n)+b)=p(a,n+1)+p(b,n+1)$ - el segundo axioma.

Por eso, $$p(a+b,n+1)=p(a,n+1)+p(b,n+1)$$ demostrado.

Ahora su Teorema: $$p(m,n)=p(n,m).$$

Base: $p(m,1)=p(1,m)$ - Lema 1 y el primer axioma.

Inducción de la hipótesis: $p(m,n)=p(n,m)$.

Paso: $p(m,n+1)=p(m,n)+m$ - el segundo axioma,
$p(m,n)+m=p(n,m)+m$ - inducción, hipótesis,
$p(n,m)+m=p(n,m)+p(1,m)$ - Lema 1,
$p(n,m)+p(1,m)=p(n+1,m)$ - Lema 2.

Tenemos $p(m,n+1)=p(n+1,m)$ y eso es todo.

Answer 2

* Asumiendo las leyes asociativas y conmutativas para su adición.

Lema: Para todos los$n,m \in \mathbb{N}$:$p(m+1,n)=p(m,n)+n$.
Prueba :$p(m+1,n)=\sum_{i=1}^{n}m+1=\sum_{i=1}^{n}m + \sum_{i=1}^{n}1 = p(m,n)+n.$

Dejar $n \in \mathbb{N}$. Por $k=0$:
$$p(n,n+k)=p(n,n)=p(n+k,n)$ $ Hipótesis de inducción ($k \in \mathbb{N} \cup \{0\}$):$$p(n,n+k)=p(n+k,n)$ $ Paso a$k+1$ (usando el lema anterior en la 3ª igualdad):$$p(n,n+k+1) = p(n,n+k) + n = p(n+k, n) + n \\ = p(n+k+1,n) + n - n = p(n+k+1,n)$ $

Ya que para todos los$m,n \in \mathbb{N}$ existe$k \in \mathbb{N} \cup \{0\}$ tal que$(m=n+k) \lor (n=m+k)$ retiene, hemos terminado. (Tenga en cuenta que $k=max(m,n)+max(-m,-n)$ :-)

Answer 3

RESUMEN: Demuestre que$P(u,1)$ es conmutativo, y$P(u,2)$ es conmutativo ... La estrategia es proceder por inducción en el segundo argumento de$P(u,n)$

Obviamente$P(u,1)=u=\underbrace{1+\ldots+1}_\text{u times}=\Sigma_{1}^{u}\,1=P(1,u)$
Supongamos que para algunos$n \in \mathbb{N}$,$P(u,n)=P(n,u)$ para todos$u\in \mathbb{N}$. Considerar $n+1$. $P(u,n+1)=\Sigma_{1}^{n+1}\,u=\Sigma_{1}^{n}\,u+u=P(u,n)+u=P(n,u)+u=\Sigma_{1}^{u}\,n+\Sigma_{1}^{u}\,1$. Y así, por la conmutación de la adición (espero que haya demostrado esto), el LHS$=\Sigma_{1}^{u}\,n+1=P(n+1,u)$