Foros de matemática
22/11/2017, 04:21:46 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Sobre Inducción  (Leído 166 veces)
0 Usuarios y 1 Visitante están viendo este tema.
FMCh
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 67


Ver Perfil
« : 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,
En línea
Masacroso
Pleno*
*****

Karma: +0/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 378


Ver Perfil
« Respuesta #1 : 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].
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6.655



Ver Perfil
« Respuesta #2 : 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.
En línea

FMCh
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 67


Ver Perfil
« Respuesta #3 : 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,
En línea
Masacroso
Pleno*
*****

Karma: +0/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 378


Ver Perfil
« Respuesta #4 : 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.
En línea
FMCh
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 67


Ver Perfil
« Respuesta #5 : 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,
En línea
Masacroso
Pleno*
*****

Karma: +0/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 378


Ver Perfil
« Respuesta #6 : 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.
En línea
FMCh
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 67


Ver Perfil
« Respuesta #7 : 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.
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6.655



Ver Perfil
« Respuesta #8 : 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.
En línea

Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 40.308


Ver Perfil
« Respuesta #9 : 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.
En línea
FMCh
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 67


Ver Perfil
« Respuesta #10 : 18/11/2017, 06:15:21 pm »

Hola Luis,

Le agradezco su respuesta.
Queda claro.

Saludos,
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.1 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!