CB 22

III REPEM Memorias Santa Rosa, La Pampa, Argentina, Agosto 2010

538

CB 22

DE LA INDUCCIN COMPLETA A LA INDUCCIN ESTRUCTURAL

Jos L. AGUADO Facultad de Ciencias Exactas - Universidad Nacional del Centro de la Provincia de Buenos

Aires - Argentina [email protected]

Nivel Educativo: Educacin Superior. Palabras Clave: induccin, recurrencia, induccin estructural, conjuntos inductivos. RESUMEN El mtodo de induccin matemtica se ensea a los alumnos, principalmente de matemticas y computacin, desde su primer ao de carrera universitaria. Si el alumno de matemtica o informtica percibe que la construccin de un conjunto por induccin permite definir funciones recursivamente, le parecer natural usar el Mtodo de Induccin Estructural para demostrar propiedades en teora de lenguajes o teora de grafos. Es deseable, entonces, conocer los fundamentos sobre los cuales se basa la induccin sobre los naturales de modo de poder comprender cmo funciona en el marco de otros conjuntos. En este trabajo exponemos algunos fundamentos que responden a preguntas como las siguientes: De dnde viene este principio? Por qu funciona? 1. INTRODUCCIN Induccin: (Fil.) Extraer, a partir de determinadas observaciones o experiencias particulares, el principio general que en ellas est implcito.- (Biblioteca de Consulta Microsoft Encarta 2005. 1993-2004 Microsoft Corporation. Reservados todos los derechos). En 1922 apareci el Crculo de Viena que propuso un modelo en el que la ciencia acta mediante generalizaciones (proceso de induccin) a partir de los datos. La visin de la ciencia del Crculo de Viena es llamada tambin Concepcin Heredada. La idea es que la ciencia debe utilizar las teoras como instrumentos para predecir fenmenos observables y debe renunciar a buscar explicaciones (que es la funcin de la metafsica). Los integrantes del Crculo defendieron un criterio verificacionista que agrupaba los enunciados en dos clases: 1) Los enunciados con sentido, que son afirmaciones que pueden comprobarse empricamente si son verdaderas o falsas. 2) Los enunciados sin sentido, cuya verdad o falsedad no puede comprobarse y se deben descartar.


539

Posteriormente, lleg Karl Popper con el falsacionismo. A diferencia del Crculo de Viena, para Popper la ciencia no es capaz de verificar si una hiptesis es cierta, pero s puede demostrar si sta es falsa. Segn este punto de vista, la induccin no sirve: por mucho que se experimente nunca se podrn examinar todos los casos posibles. Pero basta con un solo contraejemplo para refutar y destruir una teora. Muchas ciencias utilizan como metodologa la induccin emprica, afirmando la validez de una ley cuando se verifica en un gran nmero de casos particulares, seleccionados adecuadamente. Nadie, por ejemplo, ha verificado que todos los cuerpos que se hallan en la tierra librados a su propio peso caen en el vaco segn la vertical del lugar; sin embargo nadie duda de la certeza de semejante ley. La certeza de un teorema matemtico se establece de manera totalmente diferente. Un mtodo de demostracin matemtica que se usa en una infinidad de casos es el Principio de Induccin Matemtica o Principio de Induccin Completa. El principio de induccin sobre los naturales nos permite deducir que una propiedad es satisfecha por cada uno de sus elementos. Segn nuestra experiencia, a los alumnos les resulta difcil entender cundo se puede aplicar este mtodo de demostracin y cundo no. Posiblemente a muchos no les queda claro como mtodo en s mismo. Las razones para que esto suceda pueden ser varias, pero las ms clsicas son:

1) En los cursos de lgebra se ensea en forma exclusiva a partir de ejercicios de demostracin de frmulas cerradas para sumas de trminos de una sucesin. El estudiante asocia sumatoria con induccin completa y hasta ah no est mal, pero muchas veces supone que sumatoria es una unidad del programa de estudios y que induccin no lo es.

2) En los cursos de Clculo, la inmadurez del alumno en lo tocante a tcnicas de acotacin complica de manera dramtica la comprensin del mtodo. En nuestra opinin, un primer curso de Clculo es el peor contexto para aprender el mtodo de induccin.

Por otro lado, en Ciencias de la Computacin el mecanismo inductivo se utiliza ampliamente sobre conjuntos de diversa naturaleza y no solamente sobre los nmeros naturales. Para poder extrapolar el procedimiento inductivo efectuado en N, es conveniente definir a los nmeros naturales de manera abstracta, es decir formular un conjunto de axiomas que establecen las propiedades mnimas que un conjunto debe obedecer para poder llamarse el conjunto de los nmeros naturales. La construccin de los nmeros naturales a partir de los axiomas de Peano contiene al Mtodo de Induccin Completa. Luego es posible generalizar a la Induccin Estructural, tal como se implementa en Lgica Computacional. Los profesores de un primer ao de matemtica en carreras cientficas no necesitan ser especialistas en Lgica o Teora de la Computacin. As, no necesitan estudiar en profundidad textos como [1] o [3]. Nuestro objetivo es describir someramente algunos aspectos fundacionales de los procesos inductivos y recurrentes en matemtica, a fin de ofrecer a los docentes que se deben encargar de ensear los rudimentos del tema, un punto de partida para disear actividades didcticas en induccin y recurrencia. Para echar de ver la formacin que en el tema se espera de alumnos de informtica (y matemtica!) en aos ms avanzados, hemos extrado los


540

problemas 5.2 y 5.3 que siguen del estupendo libro Concrete Mathematics ([6]). Los autores explican que concrete se adopt como una mezcla de continuous y discrete mathematics. 2. EL CONJUNTO DE LOS NMEROS NATURALES El conjunto de los nmeros naturales N, como subconjunto de R, est definido por:

{ } ,3,2,1 =N donde 2=1+1,3=1+1+1=2+1, etc. Observando la definicin del conjunto anterior cabe preguntarse si esta definicin es por extensin o por comprensin. Como sabemos, todo conjunto tiene una definicin por comprensin: la tautolgica. Pero si ponemos { } NRN = :nn no ganamos nada. Algunos autores consideran que la notacin { } ,3,2,1 es por extensin, aunque podra objetarse que no estn listados todos los naturales. Pero la ley de generacin de los elementos de N es clara, ya que cada uno de ellos se obtiene sumando el 1 una cierta cantidad de veces y por la forma de generar los elementos de este conjunto, siempre se est en condiciones de probar, luego de un nmero finito de etapas, que el nmero 5002 digamos, pertenece al conjunto N. Precisamente, los nmeros naturales son la versin matemtica del concepto "nmero finito de veces" (sea lo que sea que esto signifique para filsofos, fillogos, epistemlogos o matemticos). Son usados para dos propsitos fundamentalmente: para describir la posicin de un elemento en una sucesin ("el 9 mandamiento") lo que lleva al concepto de ordinal, y para especificar el tamao de un conjunto finito ("9 vidas"), lo que lleva al concepto de cardinal. En el mundo de lo finito, estos dos conceptos son coincidentes: los ordinales finitos son iguales a los cardinales finitos. Cuando nos movemos ms all de lo finito, ambos conceptos no coinciden. Una suma de dos nmeros que son sumas de 1's es de nuevo una suma de 1's por la propiedad asociativa de la suma de nmeros reales:

( ) ( )vecesmvecesn

mn 111111 +++++++=+

Por lo tanto en N se verifica la ley de cierre para la suma y se deduce que la operacin suma de naturales cumple las propiedades de asociatividad y conmutatividad. De la misma manera, usando la propiedad distributiva de los nmeros reales se ve que el producto de naturales es un natural. Tambin para el producto de naturales vale la asociatividad, conmutatividad y existencia de neutro. Finalmente tambin vale la propiedad distributiva en N. Es usual definir { } ,,,= 2100N que es el conjunto de nmeros naturales con el agregado del 0. Los elementos de 0N se llaman nmeros enteros no negativos. Observar que en 0N , valen todos los axiomas para la suma y el producto que valen en N, y tambin el axioma de existencia de neutro para la suma. El siguiente principio es vlido en N, con el orden usual heredado del orden en los nmeros reales. Principio de Buena Ordenacin (PBO) Cualquier subconjunto de N no vaco, tiene un elemento mnimo (llamado tambin primer elemento). Usando el PBO se puede demostrar el:


541

Teorema 2.1 Entre 0 y 1 no hay ningn nmero natural. Demostracin. Supongamos que existe un nmero Nx tal que 10


542

642

321

Como los nmeros de la fila superior son siempre los mismos, podemos escribir sencillamente 2, 4, 6, 8, 10,omitiendo la fila superior. Es convencin universal usar la notacin ms prctica siguiente: ( )nfan = , es decir ( ) ( ),2, 21 fanfa == con lo cual las sucesiones se describen ,, 21 aa . Lo llamaremos el recorrido sugerido de la sucesin. Tambin se dice que

na est indexada por los nmeros naturales. Con estas convenciones la manera usual es definir las sucesiones dando la ley del trmino general poniendo na = definicin en funcin de n, que como veremos pueden ser definiciones de forma muy diversa, incluyendo definiciones por recurrencia. Ejemplos 3.3 1) Sean a y k nmeros reales que se eligen de manera arbitraria y ( )knaan n 1: += . El recorrido sugerido es l,2,, kakaa ++ . Esta sucesin se llama la progresin aritmtica de razn k. 2) 1: = nn qaNn donde q es un nmero real no nulo fijo. El recorrido sugerido es

,,,,1 32 qqq Observar que si 1=q , obtenemos una sucesin constante. En realidad si 0=q , el nico valor de la sucesin que no est definido es 1a . Esta sucesin se llama la progresin geomtrica de razn q. Observacin 3.4 Los puntos suspensivos "", llamados el etctera matemtico, se colocan cuando se sabe en cada caso, qu los sustituye si se desea continuar y, generalmente a travs de la informacin que se obtiene por conocer los elementos anteriores. Por ejemplo { } { } ,4,3,2,1,3,2,1 = . Mientras est clara la ley de generacin se considera lcito el uso de "" para sugerir los restantes elementos del conjunto. El recorrido sugerido ,,, 321 aaa no contiene toda la informacin sobre la sucesin en tanto no se conozca la funcin f o su ley de generacin. La mayora de los test de CI incluyen preguntas de este tipo: "Escriba el nmero que sigue en 1, 10, 19,". En este caso, la respuesta es, fcilmente, 28, desde que 1, 10, 19, son los 3 primeros trminos del recorrido sugerido de una progresin aritmtica de razn 9, definida por y 9:1y 1 11 +== + nn aana . Pero tambin, la respuesta podra ser 100, puesto que para la sucesin definida por 32 4243516 n-nn-bn += se tiene que 10019101 4321 ==== ,b,b,bb , como puede comprobarse. Adems se ve que 37=5a y que 59=5b . Es decir, ambas sucesiones son distintas. Convencin 3.5 En muchos casos es til comenzar las sucesiones desde 0a en lugar de 1a , esto significa que tratamos con funciones Af 0: N . Por ejemplo en 7), la progresin geomtrica 1nq comenzando desde 1=n , tiene el mismo recorrido que la progresin geomtrica q comenzando desde n=0.


543

En general, es fcil ver que dada una sucesin ,,, 321 aaa que comienza con 1=n , es posible definir una sucesin ,,, 210 bbb por 10 : += nn abn N y, recprocamente, dada la sucesin ,,, 210 bbb se obtiene ,,, 321 aaa definiendo 1: = nn ban N . Ambas sucesiones toman exactamente los mismos valores del conjunto A. La eleccin puede residir en la comodidad de definicin. 4 PRINCIPIO DE INDUCCIN MATEMTICA El principio de induccin matemtica (o induccin completa) establece lo siguiente: Principio de Induccin Completa (PIC) Sea 21 ,,P,,PP n una sucesin de proposiciones matemticas y sea que:

i) La proposicin 1P es verdadera ii) Para cada k se verifica que si kP es verdadera entonces 1+kP es verdadera.

Entonces nP es verdadera para todo n. Este principio se acepta sin demostracin cuando se considera N como un concepto primitivo. Puede justificarse usando la axiomtica de Peano, ya que si consideramos el subconjunto de naturales K para los cuales nP es verdadera, entonces K1 por i) y por ii) si Kn entonces

Kn +1 ; luego por el Axioma III de Peano, debe ser K=N. La proposicin kP de ii) que se supone verdadera se llama la Hiptesis Inductiva (HI). Es claro que se puede tener adems una proposicin 0P . En ese caso, se demuestra tambin para el caso n=0 por separado o se usa sencillamente en el PIC la clusula i) La proposicin

0P es cierta. Teorema 4.1 El PIC puede demostrarse a partir del PBO. Demostracin. Sea S el conjunto de los naturales k tal que kP es falsa. Si S es no vaco, por el PBO, S tiene un elemento mnimo m. Claramente, m 1 , pues por la primera hiptesis de PIC

1P es verdadera. Por lo tanto es m > 1. Asimismo 1mP es verdadera (por definicin de m) y, por la segunda hiptesis de PIC, obtenemos que mP es verdadera. Esta contradiccin muestra que S es vaco y que, por lo tanto nP es verdadero para todos los naturales n. Teorema 4.2 El PBO puede demostrarse a partir del PIC. Demostracin. Supongamos que el PIC es vlido y sea S un subconjunto no vaco de N. Veamos que S tiene un menor elemento. Sea que S no tiene un menor elemento. Sea

SS c = N el complemento de S. Definimos { }cSyxyxT = ,cadapara:N . Entonces cS1 (pues si S1 , entonces 1 debe ser el menor elemento de S). Luego T1 . Supongamos ahora que Tk . Debido a la definicin de T, esto significa que k,,2,1 deben ser todos elementos de cS . Ahora, si Sk +1 , entonces debe ser el menor elemento de S lo que no es posible ya que S no tiene un elemento menor. Por lo tanto Tk +1 y por el PIC debe ser T = N. Esto significa que S es vaco lo que es una contradiccin. Por lo tanto, S debe tener un menor elemento.


544

Existe una formulacin equivalente del principio de induccin, que puede ser til en algunos casos. Principio de Induccin Fuerte (PIF) Sea 21 ,,P,,PP n una sucesin de proposiciones matemticas y sea que:

i) La proposicin 1P es verdadera ii) Para cada 1 k > se verifica que si jP es verdadera para todo kj < entonces kP es verdadera.

Entonces nP es verdadera para todo n. Veamos un ejemplo de aplicacin del PIF. Teorema 4.3 La proposicin nP : 2 n + puede ser factorizada como producto de nmeros primos es verdadera para todo n natural. Demostracin. El caso base ( 1=n ) es inmediato pues 2 es primo. Pasemos al caso inductivo. Supongamos que para un 1 k > se verifica que jP es verdadera para todo kj < . Veamos que kP es verdadera. Si k es primo concluimos de inmediato. Si k no es primo debe ser divisible por un nmero r con k r


545

Las definiciones por recurrencia se utilizan para definir sucesiones y se aplica un procedimiento copiado de los dos pasos del PIF. Supongamos que queremos definir una sucesin na por recurrencia. Entonces se siguen los siguientes dos pasos:

i) Se define 1a . ii) Si suponemos definidos naaa ,,, 21 entonces definimos 1+na . Si con conocer na alcanza para definir 1+na se adopta el esquema del PIC.

Entonces de nuevo, por el Axioma III de Peano, hemos definido na , para todo Nn . Ejemplos 5.1 1) ka ,1 son nmeros reales que se eligen de manera arbitraria, kaan n-n +=> 1:1 . El recorrido sugerido es ,2,, 111 kakaa ++ . Nuevamente obtenemos la progresin aritmtica de razn k pero ahora definida por recurrencia. 2) 11 :1,1 n-n naana =>= . El recorrido sugerido es

,, , , , , , , , , 362880036288040320504072012024621 Esta sucesin es n! (factorial de n). 3) 21, aa son nmeros reales que se eligen de manera arbitraria y 21:2 +=> nn-n aaan . Por ejemplo, con 121 == aa , el recorrido sugerido es 1,1 , 2, 3, 5, 8,. Esta sucesin se llama la sucesin de Fibonacci. Ejemplo 5.2 La recurrencia ayuda a resolver el Problema de las Torres de Hanoi. El bastante conocido juego de las torres de Hanoi es como sigue: Se tienen n discos de dimetros todos distintos con agujeros en sus centros y tres pilares denominados A, B y C respectivamente. Originalmente los n discos se hallan anillados en el pilar A, el de mayor dimetro est ms abajo de todos y de all, hacia arriba todos en orden decreciente de dimetros.

El juego consiste en pasar a la misma pila en C, usando el pilar B como auxiliar, con una regla: nunca debe quedar un disco encima de uno de dimetro menor. Evidentemente, si 1=n , pasamos el disco 1 directamente desde A hasta C. Si 2=n , pasamos el disco 1 desde A hasta B, el disco 2 desde A hasta C y luego el disco 1 desde B hasta C. Ahora queremos averiguar dos cosas: i) Un algoritmo para efectuar los pasos. ii) Calcular ( )np , el nmero de pasos necesarios para transportar n discos.

Vemos que si 21, n = un tal algoritmo existe y que ( ) ( ) 32y 11 == pp .


546

Ahora bien, supongamos que tenemos un algoritmo para transportar n discos de un pilar a otro, usando un tercero como auxiliar. Y queremos transportar 1+n desde A hasta C. Procedemos as: 1 Transportamos los n discos de ms arriba desde A hasta B, usando el pilar C como auxiliar. Hasta aqu hemos efectuado ( )np pasos. 2 Pasamos el disco n+1 desde A hasta C. Hasta aqu hemos efectuado ( )np +1 pasos. 3 Transportamos los n discos desde B hasta C, usando el pilar A como auxiliar. Y hemos efectuado en total ( )np +1+ ( )np =2p(n)+1 pasos. Luego tenemos el algoritmo buscado y el nmero de pasos requerido para este algoritmo verifica la relacin de recurrencia ( ) ( ) 1p(1)con 121 =+=+ npnp . Ahora se trata de hallar una expresin para ( )np Analizando los primeros trminos del recorrido de ( )np vemos que es 1, 3, 7, 15,, de donde conjeturamos que ( ) np n21=+ o sea ( ) 12 -np n= . Hasta ahora es una conjetura, pero podemos demostrar que ( ) 12 -np n= para todo natural n, usando induccin. Como p(1)=1 y 2-1=1, para n=1 la identidad es cierta. Supuesta verdadera para n dado, tenemos que ( ) ( ) 121122121 1 =+=+=+ +nn )-(npnp . Una leyenda asegura que en algn monasterio de Oriente, una congregacin de monjes tienen la misin de efectuar el pasaje de 64 discos de oro utilizando tres obeliscos de diamante. Comenzaron al formarse el Universo y cuando acaben ser el fin. Suponiendo que los monjes trabajan de manera continua y que tardan 1 segundo en efectuar un paso, el nmero de segundos que dure este Universo ser ( ) 70955161584467440731264 64 ==p segundos. Considerando que en un ao (no bisiesto) hay 360024365=31536000 segundos, deducimos que el Universo debe durar aproximadamente 8446744073709551615/315360002.678410 aos como mnimo. Ejemplo 5.3 Una variante ms sencilla del conocido problema de Josephus (ver [2] por ejemplo) es arreglar n personas en una ronda y eliminar cada segunda. Veamos cmo se puede trabajar con recurrencia en esta variante del problema. Con el objeto de hallar algn tipo de frmula recurrente, llamemos J(n) al nmero que ocupa el sobreviviente en una ronda de n personas. Aqu es til hacer una tabla, usando papel y lpiz, para los primeros 10 naturales.

n 1 2 3 4 5 6 7 8 9 10 J(n) 1 1 3 1 3 5 7 1 3 5

Lo primero que observamos de la tabla es que ( )nJ parece ser siempre impar. De hecho, luego de la primera vuelta sobre la ronda se eliminan todos los que ocupan lugares pares. Cuando kn 2= es par, despus de la primera vuelta sobre la ronda, se llega a una situacin similar a la original con la mitad de personas: 12531 k-, ,, , . Es decir que si para calcular ( ) kJ partimos de la sucesin 1, 2, 3,, k y la transformamos segn la funcin ( ) jjf 12 =

como una nueva numeracin de los integrantes, tendremos que ( ) ( ) 122 = kJkJ . Es decir ( ) ( ) 122 = nJnJ para todo n. Entonces ya podemos extender la tabla de arriba, por ejemplo ( ) ( ) ( ) ( ) 17120240y9152110220 ===== J J JJ , etc.

Cuando 12 += kn es impar, en la primera vuelta la persona 1 se elimina, y los restantes k que quedan son 3, 5, 7,, 2k+1. De nuevo, si partimos de la sucesin 1, 2, 3,, k para calcular J(k) y le aplicamos la funcin g(j)=2j+1, obtenemos una numeracin de los integrantes que


547

coincide con la que queda despus de la primera vuelta aplicada a la sucesin 1, 2, 3,, 2k+1. Entonces obtenemos ( ) ( ) nJ n J 1212 +=+ para todo n. As, la recurrencia completa para ( )nJ es: ( ) 11 =J ( ) ( ) 122 = nJnJ para todo n ( ) ( ) nJnJ 1212 +=+ para todo n

Usando estas frmulas de recurrencia, podemos calcular J(n) para cualquier valor de n. Sin embargo, si n es muy grande, digamos 1000=n , es posible que se requieran muchos pasos. ( ) ( ) ( )( ) === 112502150021000 JJJ

Buscar una forma cerrada para J(n) es el prximo objetivo. Extendamos la tabla anterior un poco ms.

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 J(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1

Esto es ms que interesante, parece que J vale 1 en las potencias de 2 y que entre cada dos potencias sucesivas aparece una sucesin de impares desde 1, de longitud el doble de la anterior. As que si para un n dado ponemos

nrn mm a excede no que 2 de potenciamayor la 2con 2 += entonces la solucin a nuestro sistema de recurrencias parece ser: ( ) mm rmrrJ 20y 0 para 122 entonces, usando HI para m-1 tenemos:

( ) 12112

2212

222 1 +=

+

=

+=+ rrrJrJ mm

Una comprobacin similar se puede hacer para el caso r impar. Ahora podemos calcular J(1000). Como 10242y 5122 109 == , ponemos

( ) ( ) 9771488248821000 9 =+=+= JJ

Cuando una sucesin est definida por recurrencia puede o no existir una frmula que exprese el trmino general, y an cuando exista puede ser muy difcil calcular esa expresin. Desde el punto de vista computacional, parecera mejor tener una frmula para calcular el trmino n- simo de una sucesin, ya que cuando la sucesin est dada por recurrencia, para calcular, digamos 100a , cualquier programa debe calcular s o s primero 99321 ,,,, aaaa . Las definiciones por recurrencia insumen mucha memoria y tiempo de mquina. Un caso donde, con toda seguridad, es preferible usar la frmula del trmino general y no la ley de recurrencia es el del Ejemplo 5.3. Sin embargo, las frmulas pueden involucrar el clculo de nmero muy grandes para terminar dando nmeros relativamente chicos en comparacin a los obtenidos en clculos intermedios. Un ejemplo tpico de esto son los coeficientes binomiales.


548

6. CONJUNTOS DEFINIDOS INDUCTIVAMENTE E INDUCCIN ESTRUCTURAL

La idea es la de construir un conjunto comenzando a partir de ciertos elementos bsicos utilizando reglas que nos permiten armar elementos compuestos a partir de otros dados. Definicin 6.1 (Definicin inductiva de un conjunto) Una definicin inductiva de un conjunto A consiste en una coleccin de esquemas de reglas (abreviado esquemas). Cada esquema es de uno de los dos tipos: bsico o inductivo. Los esquemas bsicos son aquellos que establecen incondicionalmente que ciertos elementos pertenecen al conjunto. Los esquemas inductivos son aquellos que establecen que un elemento, llamado conclusin del esquema, est en el conjunto si ciertos otros elementos llamados hiptesis del esquema estn en el conjunto. Los elementos de A son aquellos para los cuales puede mostrarse que pueden construirse a partir de un nmero finito de aplicaciones de esquemas. Ejemplo 6.2 Definimos inductivamente al conjunto N del siguiente modo: 1. La expresin uno pertenece a N. 2. Si n es una expresin en N, entonces suc(n) pertenece a N. El conjunto N cuenta con los siguientes elementos {uno, suc(uno), suc(suc(uno)), suc(suc(suc(uno))), . . .}. Ejemplo 6.3 Sea V un conjunto de nombres de variable, C un conjunto de constantes numricas y { })(, el conjunto de parntesis. Definimos inductivamente el conjunto ARIT de expresiones aritmticas del siguiente modo: 1. Cada constante numrica en C pertenecen a ARIT. 2. Cada variable en V pertenece a ARIT. 3. Si e pertenece a ARIT, entonces (e) pertenece a ARIT. 4. Si a y b pertenece a ARIT, entonces a + b pertenece a ARIT. 5. Si a y b pertenece a ARIT, entonces ab pertenece a ARIT. El Principio de Induccin Estructural permite demostrar propiedades P sobre conjuntos inductivos. En analoga con el PIC sobre N, establece que para probar que P es verdadera para todos los elementos de un conjunto inductivo debe probarse: 1) P vale para todos los casos base determinados por los esquemas de reglas bsicos, y 2) si una expresin e est construida en el conjunto inductivo utilizando un esquema de regla inductivo y elementos naaaa ,,,, 321 , entonces debe probarse que si P es verdadero para cada ia , entonces los es para e. Principio de Induccin Estructural Sea A un conjunto definido inductivamente y P una propiedad sobre los elementos de A. Supongamos que 1. Para cada esquema bsico en la definicin de A, si x es introducido en A por la misma, entonces P(x) es verdadera. 2. Para cada esquema inductivo en la definicin de A, si P es verdadera para cada hiptesis del esquema entonces P es verdadera para la conclusin del esquema. Entonces, P(x) es verdadera para todo x en A. Ejemplo 6.4 Sea P(x) la siguiente propiedad sobre los elementos de ARIT.


549

P(e) estipula que la expresin e en ARIT tiene el mismo nmero de parntesis que abren que los que cierran. Para probar esto debemos ver que: 1. P(n) es verdadera para toda constante numrica en n en C. 2. P(v) es verdadera para toda variable v en V. Aqu P(c) y P(x) son claramente verdaderas pues no tienen parntesis. 3. Si P(e) es verdadera, entonces P((e)) es verdadera. Supongamos que P(e) es verdadera. Entonces P((e)) es verdadera pues dado que e tiene el mismo nmero de parntesis que abren y que cierran, esta condicin se mantiene si se agrega un parntesis que abre y otro que cierra. 4. Si P(a) y P(b) son verdaderas, entonces P(a + b) es verdadera. 5. Si P(a) y P(b) son verdaderas, entonces P(ab) es verdadera. Estas afirmaciones son inmediatas porque no se agregan parntesis. Por lo tanto, apelamos al Principio de Induccin Estructural sobre ARIT para concluir que P(x) vale para toda expresin x en ARIT. 7. CONCLUSIONES La tendencia actual en la enseanza del lgebra en carreras cientficas obliga a prestar atencin a los procesos algortmicos y de automatizacin. Al fin y al cabo vivimos en la era de la informtica, es decir del tratamiento automtico de la informacin por medio de computadoras. Una pregunta central en informtica es:

Cules funciones son calculables por una computadora? Naturalmente esta pregunta precede a la invencin de las modernas computadoras y originalmente su formulacin fue: cules funciones son mecnicamente calculables? La palabra mecnicamente aqu debe interpretarse como sin pensar" o automticamente. En la actualidad, varias reas del lgebra hacen importantes aportes a la Lgica y Teora de la Computacin para contestar a esta pregunta. No vamos a formalizar aqu el concepto de una funcin calculable. Solamente vamos a justificar su relacin con los nmeros naturales. De hecho podemos codificar una gran familia de tipos de objetos discretos como un nmero natural, o una sucesin de nmeros naturales. Como un ejemplo, supongamos que se tiene una funcin de las palabras del alfabeto a los grafos. Podemos pensar en una palabra en el alfabeto como un nmero escrito en base 27 con

a = 1, b = 2 y as sucesivamente. Un grafo con n nodos pensarse como un

2n

-vector

booleano (i.e. de 0 y 1) donde cada coordenada se corresponde con una arista, y va 1 si y slo si la correspondiente arista est en el grafo. Por ejemplo si el grafo tiene 3 nodos, las posibles aristas son (1; 2); (1; 3) y (2; 3). Si el grfico slo contiene las aristas (1; 3) y (2; 3) lo codificamos como 011. Agregamos un 1 al principio y consideramos el resultado como un nmero escrito en notacin binaria (nuestro ejemplo corresponde a ( ( ) 111011 2 = ). Es fcil ver que esta asignacin es una funcin biyectiva entre el conjunto de todos los grafos finitos y N. As una funcin con dominio en el alfabeto y co-dominio en los grafos puede ser representada como una funcin de los nmeros naturales a los nmeros naturales Es decir una sucesin de nmeros naturales!


550

Como en el caso de la relacin entre el PBO en N y el principio de induccin, tambin aparece una relacin entre buenos rdenes definidos en conjuntos inductivos y la induccin estructural, que ya aqu se llama induccin transfinita. Para finalizar permtasenos enfatizar el beneficio pedaggico de introducir ejercitaciones sobre problemas que se resuelven con argumentos recurrentes. Por ejemplo los expuestos en los Ejemplo 5.2 y Ejemplo 5.3. En estos casos ayuda disponer de algn programa de matemtica simblica como MAXIMA (gratuito). BIBLIOGRAFA [1] Aczel, Peter. Handbook of Mathematical Logic, captulo An Introduction to Inductive Definitions, 739782. North-Holland Publishing Company, 1977. [2] Aguado, Jos L., Rbora, Laura, Velzquez, Mara. La Ronda de Josefo, RELME XV, Universidad de El Salvador, Buenos Aires, Argentina, 2001. [3] Barnes, D. W.; Mack, J. M. An Algebraic Introduction to Mathematical Logic. Springer Verlag. N. Y., 1975. [4] Birkhoff, G, Mac Lane, S. lgebra Moderna. Ed. Vicens-Vives Barcelona, 1963. [5] Busby, R. C., Kolman, B. Estructuras de Matemticas Discretas para la Computacin. Prentice-Hall Hispanoamericana, 1984. [6] Grahan, R.L., Knutn, D.E., Patashnik, O. Concrete Mathematics, Addison Wesley, Reading, Massachusetts, 1988. [7] Korfhage, Robert R. Discrete Computational Structures. Academic Press, INC, 1974.

Documents

CB 22