Matemática => Esquemas de demostración - Inducción => Mensaje iniciado por: FMCh en 14/11/2017, 11:26:27 pm



Título: Sobre Inducción
Publicado por: FMCh en 14/11/2017, 11:26:27 pm
Buen día.

Estaba haciendo un teorema sobre este tema y aparece está parte en el teorema, ¿cómo la podría demostrar?
sean [texx]n,k\in{\mathbb{Z}^+}[/texx]
Sea [texx]S\subseteq{ \left\{1,2,...,n \right\}}[/texx] un subonjunto no vacío. Entonces, existe una función boyectiva [texx]g: {\left\{1,2,...,n \right\}}\longrightarrow{\left\{1,2,...,n \right\}}[/texx] tal que  [texx] g(S)={\left\{1,2,...,r \right\}}[/texx] para algún [texx] r\in{\mathbb{N}}[/texx] tal que [texx]r\leq{n}[/texx]. Si [texx] S [/texx] es subconjunto propio de [texx] {\left\{1,2,...,n \right\}}[/texx] entonces [texx] r<n[/texx].

¿Se podría aplicar los Axiomas de Peano? ¿Si es así cómo podría aplicarlos?

Les agradezco sus colaboraciones.

Saludos,


Título: Re: Sobre Inducción
Publicado por: Masacroso en 14/11/2017, 11:44:43 pm
La función identidad demuestra el teorema. Por inducción también se puede demostrar empezando con el caso base [texx]n=1[/texx].


Título: Re: Sobre Inducción
Publicado por: feriva en 15/11/2017, 05:56:33 am

Hola. Un apunte:

El subconjunto tiene al menos un elemento, pero no tiene por qué ser el 1 en particular; es decir, el caso base en este caso es “un elemento”, ya que S no es vacío.

Saludos.


Título: Re: Sobre Inducción
Publicado por: FMCh en 16/11/2017, 12:31:48 am
Hola.
Gracias por las respuestas.

Sin embargo, quiero saber si me podrían dar una base para demostrarla por inducción.

Saludos,


Título: Re: Sobre Inducción
Publicado por: Masacroso en 16/11/2017, 02:40:58 am
Hola.
Gracias por las respuestas.

Sin embargo, quiero saber si me podrían dar una base para demostrarla por inducción.

Saludos,

Caso base: para conjuntos de cardinalidad uno [texx]\{x\}[/texx] y [texx]\{y\}[/texx] la función definida por [texx]f:\{x\}\to\{y\},\, x\mapsto y[/texx] es biyectiva.


Título: Re: Sobre Inducción
Publicado por: FMCh en 16/11/2017, 12:50:29 pm
Hola. ¿Luego supongo para r  y pruebo para r+1? ¿Sería de esa forma? ¿O debo tomar el n?

Saludos,


Título: Re: Sobre Inducción
Publicado por: Masacroso en 16/11/2017, 01:00:21 pm
Hola. ¿Luego supongo para r  y pruebo para r+1? ¿Sería de esa forma? ¿O debo tomar el n?

Saludos,

¿Qué r? Una demostración de inducción se puede realizar sobre cualquier variable cuyo dominio sea equivalente al de los números naturales. La letra que uses para designarla es irrelevante.

En este caso estamos haciendo inducción sobre la cardinalidad de conjuntos finitos, es decir, conjuntos cuya cardinalidad es un número natural.


Título: Re: Sobre Inducción
Publicado por: FMCh en 16/11/2017, 01:10:50 pm
Hola me refiero al al conjunto {1,2,...,r} al que está contenido S. Sin embargo, r+1 no estaría en dicho conjunto.


Título: Re: Sobre Inducción
Publicado por: feriva en 16/11/2017, 04:47:36 pm
Hola me refiero al al conjunto {1,2,...,r} al que está contenido S. Sin embargo, r+1 no estaría en dicho conjunto.

Hola.

Ese conjunto (según entiendo yo y si no estoy equivocado) es el que biyecta con S, no tiene por qué estar en S; pueden no estar ninguno de sus elementos. El conjunto S podría ser {1,7,n} y entonces “r=3”; así, el conjunto “S” del ejemplo biyecta con el conjunto {1,2,3}; y “n” tendría que ser al menos 4 si S fuera subconjunto propio, porque no está estrictamente contenido.

Tienes que sí, “r” es un elemento del conjunto principal, pero lo importante es que “r” marca el cardinal de S. Y “n” es mayor o igual que “r” en principio; pero si es subconjunto propio es menor que n; entonces en ese caso, como mucho, “r” podría valer “n-1”.

Creo que es así como se interpreta el problema.

Saludos.


Título: Re: Sobre Inducción
Publicado por: Luis Fuentes en 16/11/2017, 06:54:30 pm
Hola

 La prueba por inducción que sugiere Masacroso puede hacerse por inducción en [texx]n[/texx] (ojo, no en el número de elementos de [texx]S[/texx], sino en el número de elementos del conjunto grande.

 Es decir la propiedad sobre la cuál aplicaremos inducción es:

P(n):si [texx]S\subseteq{ \left\{1,2,...,n \right\}}[/texx] es un subonjunto no vacío, entonces, existe una función biyectiva [texx]g: {\left\{1,2,...,n \right\}}\longrightarrow{\left\{1,2,...,n \right\}}[/texx] tal que  [texx] g(S)={\left\{1,2,...,r \right\}}[/texx] para algún [texx] r\in{\mathbb{N}}[/texx] tal que [texx]r\leq{n}[/texx]. Si [texx] S [/texx] es subconjunto propio de [texx] {\left\{1,2,...,n \right\}}[/texx] entonces [texx] r<n[/texx].

 Para [texx]n=1[/texx] es trivial.  El único subconjunto no vacío de  [texx]\{1\}[/texx] es [texx]\{1\}[/texx] y la aplicación indicada es la identidad.

 Para el paso inductivo. Suponemos cierto [texx]P(n)[/texx] y lo probamos para [texx]P(n+1)[/texx].

 Sea [texx]S\subseteq{ \left\{1,2,...,n,n+1 \right\}}[/texx] no vacío. Distinguimos dos casos:

- Si [texx]n+1\not\in S[/texx] entonces [texx]S\subseteq{ \left\{1,2,...,n \right\}}[/texx]. Por hipótesis de inducción existe una función biyectiva [texx]g: {\left\{1,2,...,n \right\}}\longrightarrow{\left\{1,2,...,n \right\}}[/texx] tal que  [texx] g(S)={\left\{1,2,...,r \right\}}[/texx] para algún [texx] r\in{\mathbb{N}}[/texx] tal que [texx]r\leq{n}[/texx].

 Definimos:

 [texx]g': {\left\{1,2,...,n,n+1 \right\}}\longrightarrow{\left\{1,2,...,n,n+1 \right\}}[/texx]

como [texx]g'(x)=\begin{cases} g(x) & \text{si}& 1\leq x\leq n\\n+1 & \text{si}& x=n+1\end{cases}[/texx]

 Es fácil ver que es biyectiva y cumple  [texx] g'(S)={\left\{1,2,...,r \right\}}[/texx].

 Además como [texx]n+1\not\in S[/texx], [texx]S[/texx] es un subconjunto propio y [texx] r<n+1[/texx]

- Si [texx]n+1\in S[/texx] entonces [texx]S-\{n+1\}\subseteq{ \left\{1,2,...,n \right\}}[/texx]. Por hipótesis de inducción existe una función biyectiva [texx]g: {\left\{1,2,...,n \right\}}\longrightarrow{\left\{1,2,...,n \right\}}[/texx] tal que  [texx] g(S-\{n+1\})={\left\{1,2,...,r \right\}}[/texx] para algún [texx] r\in{\mathbb{N}}[/texx] tal que [texx]r\leq{n}[/texx].

 Si [texx]r<n[/texx], definimos:

 [texx]g': {\left\{1,2,...,n,n+1 \right\}}\longrightarrow{\left\{1,2,...,n,n+1 \right\}}[/texx]

como [texx]g'(x)=\begin{cases} g(x) & \text{si}& x\neq n+1,g^{-1}(r+1)\\r+1 & \text{si}& x=n+1\\n+1&\text{si}&x=g^{-1}(r+1)\end{cases}[/texx]

 Se puede ver que es biyectiva y cumple [texx] g'(S)={\left\{1,2,...,r+1 \right\}}[/texx]. Además [texx]r+1<n+1[/texx] y dado que [texx]S-\{n+1\}[/texx] es propio en [texx]\{1,2,\ldots,n\}[/texx] entonces [texx]S[/texx] es propio en [texx]\{1,2,\ldots,n,n+1\}[/texx].

 Si [texx]r=n[/texx] entonces [texx]S-\{n+1\}=\{1,2,3,\ldots,n\}[/texx] y por tanto [texx]S=\{1,2,\ldots,n,n+1\}[/texx] y el resultado es trivial.

Saludos.


Título: Re: Sobre Inducción
Publicado por: FMCh en 18/11/2017, 06:15:21 pm
Hola Luis,

Le agradezco su respuesta.
Queda claro.

Saludos,