15.1.14

Axiomas de Peano y consecuencias (3)

(Para ver todas las entradas de esta serie hágase clic en la etiqueta "Axiomas de Peano" en la columna derecha de este blog.)

Teorema 8: n.(m + k) = n.m + n.k.
(Es decir, vale la propiedad distributiva).
Demostración:
Fijamos n y m, y hacemos inducción en k. Para k = 0 vale por los axiomas 3 y 5.
Tenemos que probar que n.(m + k) = n.m + n.k implica n.(m + S(k)) = n.m + n.S(k). Veámoslo:
n.m + n.S(k) =
= n.m + (n.k + n)     (ax. 6)
= (n.m + n.k) + n     (teo. 4)
= n.(m + k) + n     (hipótesis)
= n.S(m + k)     (ax. 6)
= n.(m + S(k))    (ax. 4)

Teorema 9: (n.m).k = n.(m.k).
(Es decir, el producto es asociativo).
Demostración:
Fijamos n y m, y hacemos inducción en k. Para k = 0 vale por el axioma 5.
Tenemos que probar que si (n.m).k = n.(m.k). entonces (n.m).S(k) = n.(m.S(k)).
(n.m).S(k) =
= (n.m).k + n.m     (ax.6)
= n.(m.k) + n.m     (hipótesis)
= n.(m.k + m)     (teo. 8)
= n.(m.S(k))     (ax. 6).

10.1.14

Axiomas de Peano y consecuencias (2)

(Para ver todas las entradas de esta serie hágase clic en la etiqueta "Axiomas de Peano" en la columna derecha de este blog.)

Teorema 4: (n + m) + k = n + (m + k)
(Es decir, la suma es asociativa).
Demostración:
Fijamos n y m, y hacemos inducción en k.
Para k = 0 vale ya que:
(n + m) + 0 = n + m = n + (m + 0).
Tenemos que probar que (n + m) + k = n + (m + k) implica (n + m) + S(k) = n + (m + S(k)). Veamos que es así:
(n + m) + S(k) =
= S((n + m) + k)     (ax. 4)
= S(n + (m + k))     (hipótesis)
= n + S(m + k)     (ax. 4)
= n + (m + S(k))    (ax. 4).

Teorema 5: 0.n = 0
(Recuérdese que el axioma 5 afirma que n.0 = 0).
Demostración:
Hacemos inducción en n. Para n = 0 vale por el axioma 5. Tenemos que probar que 0.n = 0 implica 0.S(n) = 0. Veámoslo: 0.S(n) = 0.n + 0 = 0 + 0 = 0.

Teorema 6: S(n).m = n.m + m
Demostración:
Fijamos n y hacemos inducción en m. Para m = 0 vale porque: S(n).0 = 0 = 0 + 0 = n.0 + 0.
Tenemos que probar que S(n).m = n.m + m implica S(n).S(m) = n.S(m) + S(m). Veámoslo:
S(n).S(m) =
= S(n).m + S(n)     (por el ax. 6)
= (n.m + m) + S(n)     (hipótesis)
= n.m + (m + S(m))     (teo. 4)
= n.m + (S(m) + n)     (teo. 2)
= n.m + (n + S(m))     (teo. 3)
= (n.m + n) + S(m)     (teo. 4)
= n.S(m) + S(m)     (ax. 6)

Teorema 7: n.m = m.n (el producto es conmutativo).
Demostración:
Fijamos n y hacemos inducción en m. Para m = 0 vale porque n.0 = 0 = 0.n.
Tenemos que probar que n.m = m.n implica n.S(m) = S(m).n. Veámoslo:
n.S(m) =
= n.m + n     (ax. 6)
= m.n + n     (hipótesis)
= S(m).n     (teo. 6).

6.1.14

Axiomas de Peano y consecuencias (1)

(Para ver todas las entradas de esta serie hágase clic en la etiqueta "Axiomas de Peano" en la columna derecha de este blog.)

La intención de esta serie de entradas es simplemente explorar cómo, a partir de los Axiomas de Peano, pueden probarse las propiedades básicas de los números naturales.

Los axiomas de Peano
Estos axiomas se refieren a ciertos objetos a los que llamaremos números naturales y tienen como elementos primitivos al número 0, que es un número natural, a la función sucesor, que indicamos con la letra S, y a las operaciones de suma y producto. Los axiomas son:

Axioma 0: El sucesor de un número natural es siempre un número natural, la suma y el producto de dos números naturales es siempre un número natural.
Axioma 1: Para todo n, S(n) es distinto de 0.
Axioma 2: Si S(n) = S(m) entonces n = m.
Axioma 3: n + 0 = n.
Axioma 4: n + S(m) = S(n + m).
Axioma 5: n.0 = 0.
Axioma 6: n.S(m) = n.m + n.
Axioma 7 (Esquema de inducción): Para cada fórmula P(n), si puede probarse que vale P(0) y también que vale "P(n) implica P(S(n))" entonces P(n) vale para todo n.

Teoremas:
Estos son algunos teoremas que se deducen de los axiomas de Peano.

Teorema 1: 0 + n = n.
Demostración:   
Aplicamos el esquema de inducción.
Para n = 0 la afirmación vale por el axioma 3.
Tenemos que probar que "0 + n = n implica 0 + S(n) = S(n)". Veamos que es así:
Si 0 + n = n entonces 0 + S(n) = S(0 + n) = S(n).

Teorema 2: n + S(m) = m + S(n).
Demostración:  
Hacemos inducción en m.
Para m = 0 la afirmación vale porque:
n + S(0) = S(n + 0) = S(n) = 0 + S(n), esto último por el teorema 1.
Veamos que n + S(m) = m + S(n) implica n + S(S(m)) = S(m) + S(n).
S(m) + S(n) =
= S(m + S(n))     (ax. 4)
= S(n + S(m))     (hipótesis)
= n + S(S(m))     (ax. 4).

Teorema 3: n + m = m + n
(Es decir, la suma es conmutativa).
Demostración:
Fijamos n y hacemos inducción en m.
Para m = 0 vale ya que n + 0 = n = 0 + n, por axioma 3 y teorema 1.
Tenemos que probar que n + m = m + n implica n + S(m) = S(m) + n, veamos que es así:
n + S(m) =
= S(n + m)     (ax. 4)
= S(m + n)     (hipótesis)
= m + S(n)     (ax. 4)
= S(m) + n     (teo. 2).

24.12.13

Felicidades


Felices Fiestas para todos, el Topo Lógico volverá a sus publicaciones habituales el próximo 6 de enero de 2014.

Hasta entonces.

13.12.13

Crucigrama numérico

Espero que en éste no haya errores...


Hay que escribir una cifra en cada casilla, no deben quedar casillas vacías, ningún número comienza con cero.

Horizontales:
1) Múltiplo de 106.
4) El producto de sus cifras es 51.
6) El producto de sus cifras es igual al producto de las cifras de 2 vertical.
10) Múltiplo de 304.

Verticales:
1) Número primo, dos de cuyas cifras son pares e iguales.
2) Cuatro cifras diferentes.
3) Número par formado por cuatro cifras consecutivas, todas distintas de cero, y ordenadas en forma decreciente.
5) Tres cifras diferentes, pero con la misma paridad, que suman 12.

Actualización: Claudio Meller y Mariana Belén encontraron "la clave" para resolverlo.
Actualización: Pablo Rowies encontró que el problema tenía 9 soluciones (!). Lo he corregido para que la solución sea única (las correcciones están en azul). Gracias, Pablo.

11.12.13

Problemita de lógica (4)

En los comentarios al problema anterior Marcos Donnantuoni se pregunta si la solución de aquél problema es única. Esa pregunta, a su vez, me inspira este nuevo problema.

Para cada afirmación indicar si es verdadera o falsa:
1) La siguiente afirmación es falsa.
2) El problema tiene solución única.


Hoy

Hoy, 11.12.13, es uno de esos días.

10.12.13

Problemita de lógica (3)


1) En esta lista hay más afirmaciones verdaderas que falsas.
2) En esta lista hay más afirmaciones verdaderas que falsas.
3) En esta lista hay tantas afirmaciones verdaderas como falsas.
4) En esta lista hay más afirmaciones falsas que verdaderas.

¿Cuáles de estas afirmaciones son verdaderas y cuáles son falsas?

8.12.13

Problemita de lógica (2)

Cada casilla debe quedar pintada de blanco o de negro. Las casillas blancas contienen siempre afirmaciones verdaderas, las casillas negras contienen siempre afirmaciones falsas. Ninguna fila ni ninguna columna está formada por casillas que sean todas del mismo color. 

Actualización: ¡Cuidado! Había un error en el enunciado (en la casilla que ahora está de otro color). Por las dudas una aclaración, en la tercera casilla de la primera fila, la frase "la casilla aquí abajo" se refiere a la casilla inmediatamente inferior y no a la última de la columna.


Otra actualización: Pablo Rowies (quien me había advertido del error que había antes) y Laura Spivak lo han resuelto correctamente.

6.12.13

Problemita de Lógica (1)



1) En esta lista hay más afirmaciones verdaderas que falsas.
2) En esta lista hay tantas afirmaciones verdaderas como falsas.
3) En esta lista hay más afirmaciones falsas que verdaderas.

¿Cuáles de estas afirmaciones son verdaderas y cuáles son falsas?

2.12.13

Galileo y el infinito

Galileo
En su obra Diálogo sobre dos nuevas ciencias (1638) Galileo Galilei afirma que es absurdo decir que una cantidad infinita es mayor que una cantidad finita. Para entender su razonamiento, imaginemos unos escribas que, generación tras generación, se dedican a anotar los sucesivos números naturales. La pregunta es, a medida que estas personas van anotando números, ¿podemos decir que se acercan cada vez más a completar la escritura de todos los números naturales?

Una primera mirada podría decirnos que sí; después de todo, a medida que pase el tiempo los escribas irán avanzando cada vez más en la escritura. Pero un segundo razonamiento nos diría que no, que en realidad no se acercan, porque no importa cuántos números escriban, la colección de todos los que quedan por anotar es siempre infinita en acto. Para decirlo más dramáticamente, la colección de los números no anotados nunca dejará de ser infinita en acto por más que los escribas avancen en la escritura de los números. Por lo tanto, siempre están a "infinita distancia" de completar la tarea, tanto si acaban de anotar el número cien como si han alcanzado el billón.

Pero Galileo va más allá todavía, y afirma que los escribas no solamente no se acercan al infinito en acto, sino que en cierto modo se alejan de él. Su razonamiento es como sigue: entre el número 1 y el número 100 hay 10 cuadrados, es decir, entre los cien primeros números, un 10% son cuadrados. Por otra parte, entre los mil primeros números, el 3,16% son cuadrados; entre los diez mil primeros, el 1% son cuadrados, y entre los cien mil primeros, el 0,316%. Es decir, a medida que los escribas van anotando los números, el porcentaje de cuadrados va disminuyendo y en consecuencia se aleja cada vez más del 100%. Sin embargo, en el infinito en acto hay la misma cantidad de cuadrados que de naturales, por lo que —siempre hablando de lo que sucedería en el infinito en acto— el 100% de los números son cuadrados. De modo que los escribas, a medida que avanzan en su tarea, se alejan de las propiedades del infinito en acto, en lugar de acercarse a ellas.

(Este fragmento formaba parte de un libro que escribí para la editorial RBA de España, pero tuve que suprimirlo porque el libro excedía la cantidad prescripta de caracteres. En el texto puede rastrearse el origen del Problemita numérico de verano publicado en este blog en enero.)

15.11.13

El ABC de la creación (3): imposibilidades

Pares y nones
Las reglas del juego y los primeros desafíos pueden verse en este enlace, otros desafíos pueden verse en este otro enlace.

De los dos últimos desafíos planteados en la entrada original, uno de ellos pedía pasar de la cinta vacía a una que contuviera solamente la letra A, y el otro desafío, pasar de la letra A a la letra B. En los comentarios a esa misma entrada Marcos Donnantuoni conjeturó que estos objetivos son imposibles de alcanzar; mi intención aquí es demostrar que, en efecto, son imposibles.

La demostración de ambas imposibilidades pasa por un argumento de paridad. Recordemos que la primera regla dice que donde haya dos casillas vacías es posible "crear" dos letras iguales; la segunda regla enuncia la operación inversa, dos letras iguales y consecutivas pueden ser borradas. La tercera regla dice que dos letras diferentes consecutivas (AB, por ejemplo) pueden ser cambiadas por la letra restante (en el ejemplo, una C).

Pensemos ahora en las cantidades de letras que haya en la configuración inicial, y específicamente fijémonos en sus paridades. Las dos primeras reglas no alteran la paridad de esas cantidades, ya le suman o le restan un 2 a una de ellas. La tercera regla, en cambio, cambia las tres paridades a la vez, ya que le suma un 1 a una cantidad y le resta 1 a las otras dos. Es decir, al aplicar cualquiera de las reglas, o bien las tres paridades no cambian, o bien cambian todas a la vez.

Esto significa que, si al comenzar, las cantidades de dos de las letras tenían la misma paridad (ambas cantidades eran pares o ambas eran impares) entonces a lo largo de todo el proceso esas cantidades seguirán teniendo la misma paridad (porque, en caso de cambiar, ambas paridades cambiarán al mismo tiempo); y si esas dos cantidades, al comenzar, tenían diferente paridad entonces la paridad seguirá siendo siempre diferente (por la misma razón). Podemos decir, en resumen, que las paridades relativas de las cantidades de letras no cambiarán nunca.

Ahora bien, si quisiéramos pasar de la cinta vacía a la letra A entonces al comenzar las cantidades de A y de B tendrían la misma paridad (ambas cantidades serían pares, ya que valen cero), mientras que al terminar habría una cantidad impar de A (una letra) y una cantidad par de B (cero). La paridad relativa de A y B habría cambiado, lo cual es imposible. Luego, no puede pasarse de la cinta vacía a una sola A. Lo mismo sucede si queremos pasar de A a B, porque al comenzar A y C tendrían diferente paridad (uno y cero son las cantidades iniciales de esas letras), pero al terminar tendrían la misma (cero y cero, ambas pares).

Una pregunta que queda pendiente es si vale la afirmación recíproca; es decir, si tenemos dos configuraciones de letras en las cuales las paridades relativas de A, B y C son las mismas (es decir, dos paridades que sean iguales/diferentes en una configuración son también iguales/diferentes en la otra configuración) entonces ¿es siempre posible pasar de una configuración a la otra? Creo que la respuesta es que sí, aunque no he podido encontrar una demostración elegante de ese hecho.