You are currently browsing the category archive for the ‘math.IC’ category.

   En lógica proposicional clásica podemos probar que la siguiente proposición es válida:

\displaystyle  (A \iff B) \lor (A \iff C) \lor (B \iff C),

donde {A}, {B} y {C} representan proposiciones, cada una de la cuales puede ser verdadera o falsa. El punto de la cuestión es que, no importa qué son esas proposiciones o cuáles de ellas (si las hay) son ciertas: la proposición mostrada es verdadera sin importar qué.

   Podemos probar esta proposición mediante una tabla de verdad. Sin embargo, de hecho no es necesario usarla. La proposición {(A\iff B)\lor(A\iff C)\lor(B\iff C)} es verdadera si, y sólo si, al menos uno de los disyuntos {A\iff B}, {A\iff C} y {B\iff C} es verdadero. Así, sabemos que la proposición {A\iff B} es verdadera exactamente cuando {A} y {B} tienen el mismo valor de verdad: ambos son verdaderos o ambos son falsos. Análogamente, la proposición {A\iff C} es verdadera exactamente cuando {A} y {C} tienen el mismo valor de verdad, y {B\iff C} es verdadera exactamente cuando {B} y {C} tienen el mismo valor de verdad.

   Ya que sólo hay dos valores de verdad en la lógica proposicional clásica, no importa como asignemos los valores de verdad a las proposiciones {A}, {B} y {C}, dos de las cuales tiene el mismo valor de verdad. Esto quiere decir que bajo cualquier asignación de valores de verdad a {A}, {B}, y {C}, al menos uno de los tres disyuntos tiene que ser verdadero, y, por lo tanto, toda la proposición también debe ser verdadera.

   Suele suceder que uno puede saber como probar por contradicción una afirmación, pero a la vez no estar seguro de cómo abordarlo. Es usual que escribamos una prueba en la forma «{P\text{ implica }Q}», luego si podemos probar que «{P\text{ y no }Q}» es falso, tenemos que «{P\text{ implica }Q}» debe ser verdadero.

Ejercicio 1. Sea {c} un entero positivo que no es primo. Mostrar que hay algún entero positivo {b} tal que {b\mid c} y {b\leq\sqrt{c}}.

   En este caso, escribimos: si {c} es un entero positivo compuesto, entonces {b|c} y {b\leq\sqrt{c}} para algún entero positivo {b}.

   Uno podría suponer que mientras que se asuma que {b|c} o {b>\sqrt{c}}, esto todavía esa válido como «{\text{no }Q}»; es decir, ¿no tenemos que asumir el recíproco de ambas partes de {Q}?

   Además, cuando {b>\sqrt{c}} y {b|c}, tenemos {br=c} para algún entero {r}, para el cual {r<\sqrt{c}}.

   Cuando negamos una afirmación con cuantificadores, necesitamos dar la vuelta a los cuantificadores. Por ejemplo, lo opuesto de «todo gato es blanco» no es «todo gato no es blanco», sino «hay algún gato que no es blanco».

   En este caso, la negación correcta de «hay algún {b} tal que {b|c} y {b\le\sqrt{c}}», si deseamos mantener la condición que {b} es un divisor, es «para todo {b} tal que {b|c}, {b>\sqrt{c}}». Esta es la afirmación desde la cual podemos probar una contradicción: para todo {b} que satisface esta condición, {\frac{c}{b}} también debe satisfacer esta condición; lo que da la contradicción {c>c}. (Y se quiere la condición que {b>1} o de lo contrario el problema es trivial.)

Ariana y David ganan dos monedas de un nuevo sol cada día y gastan dos de ellas.

   Ariana organiza sus ahorros del siguiente modo: el día {n} gana dos monedas {r_n} y {s_n}. Alquila un almacén, deposita allí la moneda {r_n} en una pila de monedas de los días anteriores, y gasta {s_n}. De este modo, el primer día ahorrado {\{r_1\}}, el segundo {\{r_1,r_2\}}, el tercero {\{r_1,r_2,r_3\}}, etc. (Así,la moneda situada arriba de la pila es la escrita a la derecha.)

   David se organiza de otra manera, y hace circular todas sus monedas: el día {n} coloca bajo la pila de monedas ahorradas las monedas {r_n} y {s_n} que acaba de ganar; coge la moneda que se encuentra encima de la pila y la gasta. Así, el primer día su pila tiene la moneda {\{s_1\}} (ha colocado {r_1} y {s_1} y gastado la moneda {r_1}), el segundo día sus monedas son {\{r_2,s_2\}} (ha añadido {r_2} y {s_2} debajo de la pila, quedando {\{s_1,r_2,s_2\}}, y ha gastado la moneda de encima {s_1}), el tercer día su montón se transforma en {\{s_2,r_3,s_3\}}, el cuarto en {\{r_3,s_3,r_4,s_4\}}, el quinto en {\{s_3,r_4,s_4,r_5,s_5\}}, etc.

   Así expuesto, ambos ahorran y gastan la misma cantidad de dinero. Veremos que sorprendentemente Ariana será infinitamente rica y David estará en la más absoluta ruina.

   En efecto, Ariana tendrá ahorradas las monedas

\displaystyle  \{r_1,r_2,r_3,r_4,r_5,r_6,r_7,\dotsc,r_n,r_{n+1},\dotsc\}.

Sin embargo, David no tendrá nada: la moneda {r_n} —colocada el día {n}–– se gastará el día {2n-1}, y la moneda {s_n} ––también colocada el día {n}–– se invertirá el día {2n}. Así, toda moneda termina siendo desembolsada por David, con lo cual, “al final de los tiempos”… no le quedará nada.

¿Parece absurdo, no: ganando y gastando ambos lo mismo, Ariana es rica y David, pobre? Esta es una de las muchas paradojas que minan nuestro razonamiento intuitivo acerca del infinito; la misma que involucra la noción de cardinal. El cardinal de un conjunto finito es el número de elementos que posee. Definimos {card(A)} como el cardinal del conjunto {A}.

   Diremos que {A_n} es el conjunto de las monedas conservadas por Ariana en el instante {n},

\displaystyle  A_n = \{r_1,r_2,r_3,r_4,r_5,r_6,r_7,\dotsc,r_n\},

y {A} es el conjunto con las monedas que posee Ariana al final de los tiempos. El cardinal de {A_n}, es {card(A_n)=n}, que tiende a infinito cuando {n} tiende al infinito, de modo que {card(A)=\infty}, y, así, Ariana termina siendo infinitamente rica.

   Similarmente, sea {D_n} el conjunto de las monedas ahorradas por David en el instante {n} y {D} el número de ellas que conserva al final de los tiempos. Como dijimos, David gasta todas sus monedas, ya que invierte la moneda {r_n} el día {2n-1}, y la moneda {s_n} el día {2n}. Así, {card(D)=0}, ya que {D} es el conjunto vacío. ¡David está en la ruina!

   Comprobemos el resultado. Al cabo de {2n} días:

\displaystyle  A_{2n}=\{r_1,r_2,r_3\dotsc,r_{2n-1},r_{2n}\},

y {card(A_{2n})=2n}, que tiende a infinito cuando {n\rightarrow\infty}, de modo que {card(A)=\infty}. En el caso de Ariana, confirmamos que obtiene una fortuna infinita. Al cabo de esos mismos {2n} días, David tiene guardado

\displaystyle  D_{2n}=\{r_{2n},s_{2n},r_{2n-1},r_{2n-1},\dotsc,r_{n+2},s_{n+2},r_{n+1},s_{n+1}\},

es decir, {card(D_{2n})=2n}, que tiende a infinito cuando {n\rightarrow\infty}, así

\displaystyle  card(D)=\lim card(D_{2n})=\lim(2n)=\infty.

¿No habíamos dicho antes que {D} era el conjunto vacío?

   El problema en este razonamiento se produce al pensar que los límites se pueden intercambiar con el cardinal. Si fuera

\displaystyle  \lim card(D_{2n})=card(\lim D_{2n}),

se obtendría

\displaystyle  \infty=\lim card(D_{2n})=card(\lim D_{2n})=card(D)=0.

   Vemos que debemos ser cuidadosos con los razonamientos sobre sucesiones infinitas. En una próxima entrega podríamos revisar con algo más de detalle este tipo de argumentos… mientras, ¡mucho cuidado con el infinito!

Una de las consecuencias “curiosas” de los conjunto ordenados es el principio del palomar. Tiempo atrás, vi dos ejercicios que me parecieron interesante al resolverlos. Veremos algunas perspectivas de este principio al momento de resolver los ejercicios; por ejemplo, la interpretación desde la teoría de cardinales.

Proposición 1 (Principio del palomar). Si {n} palomas se distribuyen en {m} palomares y {n > m}, entonces al menos habrá un palomar con más de una paloma.

Ejercicio 1. Dados los primeros {20} enteros positivos, demostrar que en todo subconjunto de {12} de ellos siempre hay dos números cuya suma da como resultado un elemento del propio subconjunto.

Ejercicio 2. En una reunión, al menos dos de los participantes conocen al mismo número de invitados.

— 1. Interpretación en la teoría de conjuntos —

Analizando el escenario de las palomas, vemos que si {A} es el conjunto de todas las palomas y {B} es el conjunto de los palomares, entonces es fácil apreciar que deben haber dos palomas “asignadas” a un mismo palomar. Esto, desde la perspectiva de la teoría de conjuntos, quiere decir que dicha “asignación” no puede ser inyectiva. De esta manera, podemos dar un enunciado equivalente a la Proposición 1.

Proposición 2. Sean {A} y {B} conjuntos finitos. Sean {\alpha} y {\beta} sus cardinales respectivos, i.e., {\alpha=card(A)} y {\beta=card(B)}, tales que {\alpha<\beta}. Entonces no existe ninguna función inyectiva de {A} a {B}.

Cuando se busca probar la existencia de cierto número es común recurrir a una demostración por contradicción. Usualmente se procede asumiendo que no existe un objeto tal que… No obstante, a veces un puede tener cierta satisfacción encontrado un procedimiento en el cual se halle dicho objeto. Aunque, este camino podría ser más tortuoso de lo que uno podría esperar. Ahora, pretendemos demostrar la siguiente proposición:

Proposición 1. Sea {x} un número real. Demostrar que existe un único entero {N} tal que {N \le x < N + 1}.

Asumamos que tenemos construido el conjunto de los números racionales, las leyes usuales del álgebra y orden y el valor absoluto. Además, tenemos definido la parte entera para los racionales:

Lema 2. Sea {x} un número racional. Entonces existe un único entero {N} tal que {N \le x < N + 1}.

Por otro lado, se define un real como el límite formal de alguna sucesión de Cauchy de números racionales.

Definición 3. Un número real es un objeto de la forma {\text{LIM}_{n \rightarrow \infty} a_n}, donde {(a_n)_{n=1}^\infty} es una sucesión de Cauchy de números racionales.

Definición 4. Una sucesión de racionales {(a_n)_{n=1}^\infty} es de Cauchy si para cualquier número racional {\epsilon > 0} existe un entero {N \ge 1} tal que {|a_j - a_k| \le \epsilon} para cualquier {j, k \ge N}.

Con estos hechos en mente, podemos iniciar la búsqueda de dicha parte entera {N}.

Sea {x} un número real. Se tiene que {x = \text{LIM}_{n \rightarrow \infty} a_n} para alguna sucesión de Cauchy {(a_n)_{n=1}^\infty}. Como {a_1, a_2, \dotso} son números racionales, sabemos que existe un entero {N_n} tal que {N_n \le a_n < N_n + 1} para el número racional {a_n} de la sucesión. En este punto, es claro que lo ideal sería demostrar que {(N_n)_{n=1}^\infty} es una sucesión de Cauchy, ya que así, dicha sucesión haría referencia al entero que buscamos.

Veamos con lo que contamos. Tenemos la sucesión de racionales {a_1, a_2, \dotso} que es de Cauchy y tenemos la sucesión de enteros {N_1, N_2, \dotso} que “no sabemos” si es de Cauchy, pero que representan respectivamente la parte entera de los racionales de la primera sucesión. Así, tenemos

\displaystyle   |a_j - a_k| \le \epsilon \ \ \ \ \ (1)

para todo {j, k \ge L} para enteros {j, k, L} y cierto {L \ge 1}; también tenemos

\displaystyle   N_i \le a_i < N_i + 1 \ \ \ \ \ (2)

para todo entero {i \ge 1}. Por comodidad, vamos a continuar el razonamiento sin hacer referencia a {L}, ya que siempre podemos fijar {j, k \ge L} y continuar, añadiendo (1) a la línea de razonamiento.

De (2) podemos obtener

\displaystyle  \begin{array}{rcccl} N_j & \le & a_j & < & N_j + 1 \\ 0 & \le & a_j - N_j & < & 1, \end{array}

similarmente

\displaystyle  0 \le a_k - N_k < 1

y

\displaystyle  -1 < N_k - a_k \le 0;

así

\displaystyle  |(a_j - N_j) - (a_k - N_k)| < 1

que es lo mismo que {|(a_j - a_k) - (N_j - N_k)| < 1}. Usando la desigualdad triangular y (1), obtenemos {|N_j - N_k| < 1 + \epsilon}, i.e., {|N_j - N_k| \le 1}. De manera que, {N_j = N_k} o uno es el sucesor (o predecesor) del otro.

En este punto, nos detenemos para meditar un poco. ¿Qué quiere decir {|N_j - N_k| \le 1}? Imaginemos que formamos una sucesión de unos y ceros a partir de la diferencia {|N_j - N_k|} ¿Esta los valores de esta sucesión serán alternativamente uno o cero? ¿Puede ser siempre cero o uno? Definitivamente, que la diferencia {|N_j - N_k|} sea siempre cero es lo deseado. No obstante, no olvidemos que esta sucesión podría ser siempre igual a uno. ¿Seguiría siendo la sucesión {(N_n)_{n=1}^\infty} equivalente al entero buscado? ¿Y si esta sucesión de las diferencias {|N_j - N_k|} fuera algo como {0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0,\dotso}? Es en este tipo de situaciones en las que la mecánica del razonamiento no basta para llegar a la respuesta deseada. Reflexionando acerca de la desigualdad obtenida, podemos intuir cierto comportamiento deseado (para obtener el entero {N}). Primero, si en efecto {N_j - N_k = 0}, entonces no hay nada más que hacer, esto sería cierto porque {(N_j = N_k) \le a_j, a_k < (N_j = N_k) + 1}, y, por lo tanto, la sucesión {(N_n)_{n=1}^\infty} sería de Cauchy y equivalente a un entero, ciertamente, el buscado. Segundo, de ser {|N_j - N_k| = 1}, uno de ellos es el sucesor del otro. Supongamos {N_k = N_j + 1}, para que {|a_j - a_k|} sea menor que cualquier {\epsilon} se necesita que {a_k = N_k}, ya que se cumple {a_j < (N_j + 1 = N_k)}, i.e., como {a_k} no puede ser menor que {N_k}, sólo queda que {a_j} se acerque {a_k}, pero sin igualarlo, ya que {a_j < N_k}. Tercero, si la sucesión fuera algo similar a {0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0,\dotso}, entonces, de manera similar al caso anterior, {a_j} sería igual a {N_j} y {a_k} estaría alternativamente entre {a_j - \epsilon} y {a_j + \epsilon}.

Como comenté al inicio, el camino hacia la “construcción” puede ser algo complicado, para poder continuar con la demostración tendríamos que hacer una demostración por casos: cuando {x} es entero y cuando no lo es. (Notar que la demostración de la proposición sería más simple si tomáramos tres casos basados en el orden de los reales (cuando es positivo, cero y negativo), que es el procedimiento usual que se plantearía uno al intentar llegar a la demostración.) Ahora, por lo dicho anteriormente, podemos intuir que hay cierta dualidad entre ser o no entero, palpable en los dos últimos casos.

Veamos otro enfoque. Deseamos obtener una sucesión {(N_n)_{n=1}^\infty} que sea equivalente a cero, y de hecho sería una sucesión de Cauchy , por lo que lo ideal sería obtener algo similar a {N_j = N_k} o {|N_j - N_k| = 0} para todo {j, k \ge L}. Para ello, si pudiéramos formular un {\epsilon > 0} en relación con {a_j, a_k, N_j, N_k} de manera que {(N_n)_{n=1}^\infty} sea una sucesión de Cauchy, entonces tendríamos hecha la demostración. Supongamos que existe un {\epsilon} tal que

\displaystyle   \begin{array}{rcl} \epsilon < a_j - N_j + \epsilon < 1 \\ \epsilon < a_k - N_k + \epsilon < 1 \end{array} \ \ \ \ \ (3)

así, con (1)

\displaystyle  \begin{array}{rcl} -1 < & N_j - a_j - \epsilon & < -\epsilon \\ \epsilon < & a_k - N_k + \epsilon & < 1 \\ -\epsilon < & a_j - a_k & < \epsilon \end{array}

de modo que

\displaystyle  |N_j - N_k| < 1

y, por lo tanto, {N_j = N_k}. Así, {(N_n)_{n=1}^\infty} es una sucesión de Cauchy equivalente a un entero. ¡No nos alegremos tan rápido! Esto sólo es cierto si dicho {\epsilon} fuera posible, pero sólo hemos supuesto la existencia de un {\epsilon} que cumple las condiciones que nos favorecen.

Para hacernos una idea de cómo podría hallarse usemos las diferencias {d_j := a_j - N_j} y {d_k := a_k - N_k}. Ambas se encuentran entre {0} y {1}. Nuestro {\epsilon} debe ser la mínima distancia entre “{0} y el menor de entre {d_j} y {d_k}” o “{1} y el mayor de entre {d_j} y {d_k}”. Para ello hay una manera sencilla de obtener el mayor y menor de entre dos números {A} y {B}: sea su suma {S := A + B} y su distancia {D := |A - B|}, entonces el menor {m} es {n := (S - D) / 2} y el mayor {M} es {M := (S + D) / 2}. Esto se prueba fácilmente mediante la tricotomía. Ahora, primero necesitamos obtener las distancias que mencionamos al inicio, {d_j} y {d_k}. Es simple, si establecemos {S_d := d_j + d_k} y {D_d := |d_j - d_k|}, el menor es {m_d = (S_d - d_k) / 2} y el mayor {M_d = (S_d + D_d) / 2}. Luego, necesitamos obtener la menor distancia de entre “{0} y el menor” y “{1} y el mayor”. El procedimiento es el mismo, buscamos el menor de entre “{0} y {m_d}” y “{M_d} y {1}”. Si establecemos {D_0 := m_d - 0 = m_d} y {D_1 := 1 - M_d} y buscamos el menor de entre {D_0} y {D_1}, aplicando la fórmula obtenemos la menor distancia mediante {D_m := ((D_0 + D_1) - |D_0 - D_1|) / 2}. Así, mientras nuestro {e} sea menor que {D_m}, las relaciones en (3) se cumplirán.

Por lo tanto, hemos demostrado que podemos hallar un {\epsilon} a partir del cual la parte entera de cada racional de la sucesión es el mismo entero. No obstante, he dejado algunas sutilezas para lector; por ejemplo, si nota la relación {0 < \epsilon < D_m} verá que hay una dicotomía entre si la sucesión de Cauchy {(a_n)_{n=1}^\infty} no representa ya un entero, además, verificar que {M_d + \epsilon < 1}, aunque esto es fácil. Finalmente, recordar que desde un punto de vista del intuicionismo no puede haber una construcción de una función {f \colon \mathbf R \rightarrow \mathbf N} a menos que sea constante, pero esto es otro tema que podríamos ver luego.