Se nos pide demostrar que siendo A un conjunto de conjuntos, el conjunto { x ∈ A | x ∉ x } ∉ A. Es interesante y por eso lo blogueo porque es una aplicación de la paradoja de Russell.

Demostración

Llamemos B al conjunto { x ∈ A | x ∉ x }. Supongamos que B ∈ A y consideremos a B con respecto a si mismo desde la relación ∈, o bien B ∈ B o bien B∉ B.

Supongamos que B ∈ B entonces por la propia definición de B, B ∉ B, lo cual es una contradicción. Ahora si B ∉ B también por la definición de B sigue que B ∈ B, lo cual también es una contradicción.

Dado que nuestra premisa original nos lleva siempre a una contradicción, debe ser falsa, por consiguiente B ∉ A.

Es interesante también como este ejercicio sirve de introducción a los tipos y clases de Haskell.

Esta demostración maravillosa que esta en el ejercicio 3.7.9 del libro How to Prove It: A Structured Approach, que la transcribo directamente porque es fantástica.

Teorema: Existen 2 números Irracionales a,b tales que a^b es racional.

Demostración: O ${\left(\sqrt{2}\right)}^{\sqrt{2}}$es racional o es irracional.

Caso 1: Si es racional, ya se probo lo que queríamos probar porque $\sqrt{2}$es irracional y tomamos a=b=$\sqrt{2}$ .

Caso 2: Si es irracional entonces sea a = ${\left(\sqrt{2}\right)}^{\sqrt{2}}$y b = $\sqrt{2}$. Entonces podemos formar el numero ${\left({\left(\sqrt{2}\right)}^{\sqrt{2}}\right)}^{\sqrt{2}}$ = ${\left(\sqrt{2}\right)}^{\sqrt{2}.\sqrt{2}}$= ${\left(\sqrt{2}\right)}^2=2$. Como $\sqrt{2}$es irracional, ${\left(\sqrt{2}\right)}^{\sqrt{2}}$es irracional por asumción de caso y 2 es racional, el Teorema queda demostrado.

Lo maravilloso es que llegamos a una demostración rigurosa del teorema sin necesidad de saber si  ${\left(\sqrt{2}\right)}^{\sqrt{2}}$es irracional o no. Simplemente por exhaustación de casos el teorema queda demostrado.
Nota: es irracional, lo que igual no quita lo maravilloso de la demostración y lo impecable de su lógica.

Se nos pide demostrar si hay o no hay triplos de primos de la forma ( p , p+2, p+4 ) que no sean ( 3, 5, 7 ). Este ejercicio me gusto porque estuve unos 15 minutos pensando antes de poder resolverlo. Bueno, despues de mirar un poco la Criba de Eratosthenes y pensar en la aritmetica mod( 3 ) finalmente encontre la forma:

Demostración

Sabemos que p es primo por lo tanto no es multiplo de 3, o sea que es o de la forma 3k + 1 o 3k + 2 con k ∈ Z. Supongamos que es de la forma 3k + 1, entonces p + 2 = 3k + 1 + 2 = 3 ( k + 1 ) entonces p + 2 es multiplo de 3 y no es primo. Ahora si es de la forma 3k + 2 entonces p + 4 = 3k + 2 + 4 = 3 ( k + 2) por lo que p + 4 es multiplo de 3 y no es primo. De lo que sigue que no existen triplos de primos de la forma ( p, p+2, p+4 ) salvo ( 3, 5, 7 ).

De manera similar puede resolverse el ejercicio 3.43, que es demostrar que siendo p primo, no existen primos de la forma ( p² + 2 ) ≠ 11 o lo que es lo mismo con p ≠ 3 .

Demostración

Si p es primo ≠ 3 , entonces necesariamente no es multiplo de 3, o sea que es de la forma 3k + 1 o 3k + 2 con k ∈ Z. Supongamos que es de la forma 3k + 1, entonces p² + 2 = ( 9k² + 6k + 1) + 2 = 3 ( 3k² + 2k + 1 ) , porque lo que es multiplo de 3 y no es primo. Supongamos entonces que es de la forma 3k + 2, entonces p² + 2 = ( 9k² + 12k + 4) + 2 = 3 ( 3k² + 4k + 2 ), multiplo de 3 y no primo. Por exhaustación de casos, la proposición queda demostarda.

Bueno termine con el cápitulo 3, si alguién tiene la solución del ejercicio 3.34 me haría un favor enorme si me lo mandan porque estuve un buen rato y no lo pude resolver. Mierda, me gustaría poder dedicarle más tiempo, pero si me cuelgo no avanzo más y quiero seguir aprendiendo Haskell.

Resolución del ejercicio 3.41 de The Haskell Road To Logic, Math and Programming. Demostrar que 2^{n - 1} ( 2ⁿ- 1 ) es un numéro perfecto ( la suma de todos sus divisores propios es igual al mismo número ) si ( 2ⁿ- 1 ) es primo ( un primo de mersenne en realidad ). Como es primo se puede descomponer en los siguientes divisores propios:

2^{n - 1} ( 2ⁿ- 1 ) = 1 + 2 + 2² + …. + 2^{n - 1} + ( 2ⁿ- 1 ) + 2.( 2ⁿ-1 ) + 2².( 2ⁿ-1 ) + …. + 2^{n - 2}.( 2ⁿ-1 )

= 1 + 2 + 2² + …. + 2^{n - 1} + ( 2ⁿ- 1 ) + ( 2^{n + 1} -2 ) + ( 2^{n + 2} - 2² ) + …. + ( 2^{2n - 2} - 2^{n - 2})
Realizando las multiplicaciones de los terminos del final.

= 2^{n - 1} + 2ⁿ + 2^{n + 1} +  2^{n + 2} + …. + 2^{2n - 2}
Simplificando terminos equivalentes pero negativos.

= 2^{n - 1} ( 1 + 2 + 2² + …. + 2^{n - 1} )
Por propiedades de la exponenciación.

= 2^{n - 1}( 2  - 1 + 2 + 2² + …. + 2^{n - 1} )
Porque 2 - 1 = 1

Y es exactamente acá donde la cosa se pone interesante.  Ya logre 2^{n - 1} y el - 1 en el segundo termino. Pero me queda demostrar que ( 2 +2 + 2² + …. + 2^{n - 1} ) = 2ⁿ .

En principio no parece demasiado complicado.. digamos:

2 + 2 = 4 = 2²

2² + 2² = 8 = 2³

2³ + 2³ = 16 = 2⁴

…….

2^{n - 1} + 2^{n - 1} = 2ⁿ

Que se puede probar fácilmente por inducción completa.

2ⁿ = 2^{n - 1} + 2^{n - 1}
1) Demostrarlo para n = 1, es trivial: 2 = 1 +1.

2) 2ⁿ = 2^{n - 1} + 2^{n - 1} => 2^{n + 1} = 2ⁿ + 2ⁿ
2ⁿ + 2ⁿ = 2.(2^{n - 1} + 2^{n - 1}) = 2.2ⁿ (Por hipotesis) =  2^{n + 1}

Ahora, en el texto todavía no vimos inducción y hay un capitulo entero dedicado al tema. El tema es como probar esto sin usar inducción completa. Ni la más puta idea.

DUH! Agregado ( 1 mes después releyendo mi post y sorprendiéndome por mi absoluta falta de lucidez al momento de escribirlo )

2^{n - 1} + 2^{n - 1} = 2. (2^{n - 1}) = 2ⁿ

En el ejercicio 3.21.12 del libro Algebra I de Armando Rojo, se nos pide demostrar por inducción completa que:

3 / 8ⁿ - 5ⁿ o lo que es lo mismo 8ⁿ - 5ⁿ = 3k; k ∈ Z .

Lo interesante es que cuando curse Algebra y Matematica Discreta había un ejercicio bastante similar ( Demostrar que 5 / 7ⁿ - 2ⁿ).  Se me ocurrio entonces que la demostración podía generalizarse.

Demostración Inicial: 3 / 8ⁿ - 5ⁿ

1) Primer paso demostrar para n=1

3 / 8 -5 => 3 / 3
Lo cual es evidentemente cierto.

2) Paso Inductivo:
8ⁿ - 5ⁿ = 3k; k ∈ Z => 8ⁿ⁺¹ - 5ⁿ⁺¹ = 3w; w ∈ Z

Demostración:

3 / 8ⁿ⁺¹ - 5ⁿ⁺¹ => 8ⁿ⁺¹ - 5ⁿ⁺¹ = 3k; k ∈ Z

8ⁿ⁺¹ - 5ⁿ⁺¹ = 8 . 8ⁿ - 5 . 5ⁿ
Por Propiedades de la exponenciación.

= ( 3 + 5 ). 8ⁿ - 5 . 5ⁿ    
Porque 8 = 3 + 5.

= 3 .8ⁿ + 5. 8ⁿ + - 5 . 5ⁿ
Por distributividad.

= 3 .8ⁿ + 5. ( 8ⁿ - 5ⁿ )
Por dirtributividad.

= 3 .8ⁿ + 5. ( 3.k )
Por hipotesis.

= 3 ( 8ⁿ + 5k )    
Por Distributividad:

Como ( 8ⁿ + 5k ) ∈ Z ; queda demostrada la proposición inicial.

Demostración generalizada: Sean a,b,c ∈ Z; a = b -c se cumple que a / bⁿ - cⁿ

1) Primer paso demostrar para n=1

b¹ - c¹ = a         (Por Definicion de a,b,c)

2) Paso Inductivo:
bⁿ - cⁿ = ak; k ∈ Z => bⁿ⁺¹ - cⁿ⁺¹ = aw; w ∈ Z

Demostración:

a / bⁿ⁺¹ - cⁿ⁺¹ => bⁿ⁺¹ - cⁿ⁺¹ = ak; k ∈ Z

bⁿ⁺¹ - cⁿ⁺¹ = b . bⁿ - c . cⁿ
Por Propiedades de la exponenciación.

= ( a + c ). bⁿ - c . cⁿ
Porque a = b - c => b = a + c

=  a. bⁿ + c .bⁿ - c . cⁿ
Por distributividad.

= a .bⁿ + c. ( bⁿ - cⁿ )
Por dirtributividad

= a .bⁿ + c. ( a.k )
Por hipotesis.

= a ( bⁿ + ck )
Por Distributividad.

Como ( bⁿ + ck ) ∈ Z queda demostrada la proposición.

Referencias

Algebra I; Rojo, Armando; 21ª ed, Magister Eos; 2006

Hace unos días me encontre en el medio de una demostración sobre propiedades de los limites con la siguiente formula:

1 - qⁿ = ( 1 - q ) ( 1 + q¹ + q² + …. + q^n-1)

Lo interesante es que lo daba como un hecho ya establecido. Como nunca me habia encontrado con esa formula, decidi investigarla un poco. En principio, parece bastante lógico, ya que si multiplicamos en el segundo termino 1 por la seguna secuencia nos queda una serie de terminos positivos  1 + q + q² + …. + q^n-1   y al multiplicar el -q por la segunda secuencia nos queda  -q  - q² - q³  …. - qⁿ . Con lo cual salvo el primer 1 y el ultimo - qⁿ todo el resto de los terminos se anulan entre si. Ej:

( 1 - q ) ( 1 + q + q² + …. + q^n-1) = ( 1 + q¹ + q² + …. + q^n-1) + ( - q¹  - q² … - q^n-1 -  qⁿ) = 1 + q¹ - q¹ + q² - q² + …. + q^n-1 - q^n-1 -  qⁿ  =  1 - qⁿ

Esa es una buena explicación, pero sin embargo la propiedad ( así como estaba formulada ) no se cumple para n=1:

( 1 - q ) .(1 + q^n-1) = ( 1 - q ) ( 2 ) =  2 -2q ≠ ( 1 - q¹)

Entonces habría que reformular la propiedad:

∀n ϵ N, n > 2:  1 - qⁿ = ( 1 - q ) ( 1 + q + q² + …. + q^n-1 )

Y la demostración por Inducción Completa sería:

1) Primer paso, probarlo para n = 2.

1 - q² = ( 1 - q ) ( 1  + q^n-1 )  = ( 1 + q) + ( - q - q² ) = ( 1 - q² )

2) Paso inductivo:.

1 - qⁿ⁺¹ = ( 1 - q ) ( 1 + q¹ + q² + …. + q^n-1 + qⁿ)

Por multiplicación entre polinomios queda:

= ( 1 + q¹ + q² + …. + q^n-1 + qⁿ ) + ( - q¹  - q² … - q^n-1 -  qⁿ -  qⁿ⁺¹)

Por conmutatividad de + en R:
= ( 1 + q¹ + q² + …. + q^n-1 ) + ( - q¹  - q² … - q^n-1 -  qⁿ ) + qⁿ -  qⁿ⁺¹   

Por hipotesis queda:

= (1 - qⁿ) + qⁿ -  qⁿ⁺¹

Simplicando las sumas y restas queda:

= 1 -  qⁿ⁺¹

Con lo cual queda demostrada la propiedad.  

Nota: Es interesante pensar que teniendo en cuenta que  ∀ q ∈ R: q⁰= 1 , si se reformula la propiedad de la siguiente forma :

1 - qⁿ = ( q⁰ + q¹ + q² + …. + q^n-1 )

Si se cumple para n = 1 .

Del Algebra Booleana

Definiciones

∧ Conjunción, y
∨ Disyunción, o
¬ Negación, no

Equivalencias Basicas

Doble negación
p  ≡ ¬(¬p)

Idempotencia
p∧p ≡ p
p∨p ≡ p

De morgan
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

Conmutativa
(p ∧ q) ≡ (q ∧ p)
(p ∨ q) ≡ (q ∨ p)

Asociativa
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

Distributiva
p ∧ (q ∨ r) ≡ (p ∨ q) ∧ (p ∨ r)
p ∨ (q ∧ r) ≡ (p ∧ q) ∨ (p ∧ r)

Absorción
p ∧ (p ∨ q) ≡ p
p ∨ (p ∧ q) ≡ p

Tautologia y Contradicción

T Tautologia, Verdad
⊥ Falacia, Contradicción, Falsedad

¬⊥ ≡ T
¬T ≡ ⊥

Dominancia
T ∨ p ≡ T
⊥ ∧ p ≡ ⊥

Identidad
T ∧ p ≡ p
⊥ ∨ p ≡ p

Ley del medio excluido
p ∨ ¬p ≡ T

Contradicción
p ∧ ¬p ≡ ⊥

Implicación, Doble Implicación, Disyunción exclusiva

Definiciones

=> Implicación, Si… Entonces
<=> Doble Implicación, Equivalencia, Si y solo si, iff
⊻ Disyunción exclusiva, xor

Equivalencias

Equiv:
p => q  ≡  q ∨ ¬p  ≡  ¬q => ¬p
p <=> q  ≡ (p => q) ∧ (q => p)  ≡ (p ∧ q) ∨ (¬p ∧ ¬q)  ≡ ¬ (p ⊻ q) ≡  ¬p <=> ¬q
p ⊻ q ≡ (p ∧ ¬q) ∨ (¬p ∧ q)  ≡  ¬( p <=> q)  ≡ ¬p ⊻ ¬q

Condición Necesaria y Suficiente

p => q
p es el antecedente.  Condición suficiente para q.
q es el consecuente. Condición necesaria para p.

Quantificadores

Definiciones

∃ Existe
∀ Para todo
En adelante voy a usar: Φ, Ψ (Phi, Psi) para representar Formulas.
Una estructura (o contexto) para una formula es:
1) Una especificación de un dominio para todos los cuantificadores. (ej: ∀x se especifica que x ∈ R)
2) Un significado para cualquier símbolo no especificado. (ej: xRy se especifica como x < y)

Φ Es valida si es Verdadera para cualquier estructura.
Φ ≡ Ψ <=> si se obtiene el mismo conjunto de valores de verdad en cualquier estructura. (Equivalencia entre formulas)

Equivalencias

∀x∀yΦ(x) ≡ ∀y∀xΦ(x)
∃x∃yΦ(x) ≡ ∃y∃xΦ(x)

¬∀xΦ(x)  ≡ ∃x¬Φ(x)
¬∃xΦ(x)  ≡ ∀x¬Φ(x)
¬∀x¬Φ(x)  ≡ ∃xΦ(x)
¬∃x¬Φ(x)  ≡ ∀xΦ(x)

∀x(Φ(x) ∧ Ψ(x)) ≡ (∀xΦ(x) ∧ ∀xΨ(x))
∃x(Φ(x) ∨ Ψ(x)) ≡ (∃xΦ(x) ∨ ∃xΨ(x))

∀x(Φ(x) ∨ Ψ(x)) ≢ (∀xΦ(x) ∨ ∀xΨ(x))
∃x(Φ(x) ∧ Ψ(x)) ≢ (∃xΦ(x) ∧ ∃xΨ(x))

Equivalencias con respecto al contexto.

∀x∈AΦ(x) ≡ ∀x(x∈A => Φ(x))
∃x∈AΦ(x) ≡ ∃x(x∈A ∧ Φ(x))

Referencias

Capitulo 1,2,3 de The Haskell Road To Logic, Math and Programming; Doets, Van Eijck; King´s College London Publications; 2004

Capitulo 1,2,3 de How to Prove It: A Structured Approach; Velleman, Daniel; Cambridge University Press; 2006

En el ejemplo del capitulo 2.8 de The Haskell Road To Logic, Math and Programming, la formula:

∀x ∈ {1,2,3} ∃y ∈ {1,4,9} x = y²

Se codifica como:

every, some :: [a] -> (a -> Bool) -> Bool
every xs p = all p xs
some xs p = any p xs
every [1,4,9] (\x -> some [1,2,3] (\y -> x = y^2))

Después en el Ej 2.51 se propone definir una función unique :: (a -> Bool) -> [a] -> Bool
que retorne True para unique p xs solo cuando haya un solo elemento de xs que cumpla con p.

La forma obvia de resolverlo es:

unique :: (a -> Bool) -> [a] -> Bool
unique p [] = False
unique p xs = length(filter p xs) == 1

Que se puede testear con:

unique (\x -> x>4) [1,2,3,4,5]
True
unique (\x -> x>4) [1,2,3,4,5,6]
False

Sin embargo es interesante pensarlo en la formula de Russell para Unicidad: ∃x ( Φ(x) ∧ ∀y ( Φ(y) => x=y ) ) . Que se puede hacer como:

unique1 :: (Eq a) => (a -> Bool) -> [a] -> Bool
unique1 p xs = some xs (\x -> p x && every xs (\y -> p y ==> x == y))
unique1 (\x -> x>4) [1,2,3,4,5]
True
unique1 (\x -> x>4) [1,2,3,4,5,6]
False

Lo interesante es que usando expresiones lambda llegamos a una formula que expresa prácticamente idéntica la original.

Demostrar que si a es par <=> a² es par

Como es doble implicación tengo que demostrar: 1) a es par => a² es par ∧  2) a² es par => a es par

1) a es par => a² es par

a es par => a = 2k; k ∈ Z => a² = ( 2k )² => a² = 4k² => a² = 2( 2k² )
Como ( 2k² ) ∈ Z => a² es par.

2) a² es par => a es par

Para esta parte de la demostración se usa el contrareciproco. ( p => q ≡ ¬q => ¬p )

a² es par => a es par ≡ a es impar => a² es impar

a es impar => a = 2k +1; k ∈ Z => a² = ( 2k+ 1 )² => a² = 4k² + 4k + 1 => a² = 2( 2k² + 2k ) + 1
Como ( 2k² + 2k ) ∈ Z => a² es impar y la proposición queda demostrada.

Demostrar que el producto de 2 números consecutivos es par.

El producto de dos números consecutivos puede escribirse como a.( a+1 ). La demostración es por exhaustación de casos.

1) Supongamos que a es par

a es par => a = 2k; k ∈ Z => a. ( a + 1) = 2k . ( 2k + 1)
Como k . ( 2k  + 1 ) ∈ Z => a. ( a + 1)  es par.

2) Supongamos que a es impar

a es impar => a = 2k + 1; k ∈ Z => a. ( a + 1) => 2k + 1. ( 2k + 1 + 1) = 2k +1 . ( 2k + 2 ) = ( 2k + 1) . 2 (k + 1) = 2 ( 2k + 1) . (k + 1)
Como ( 2k + 1) . (k + 1) ∈ Z => a. ( a + 1)  es par.

Demostrar que si p es primo y p / a.b => p/a ∨ p/b

Es una implicación que tiene una disyunción en la conclusión.

Supongamos que p/a, entonces listo no queda nada que demostrar.

Ahora si ¬(p/a) => p y a son coprimos o sea que ( p ; a ) = 1 => ∃ n; s ∈ Z / p.n + a.s = 1

Como p/a.b => a.b = pk; k ∈ Z
Tomamos:
p.n + a.s = 1

Multiplicamos ambos terminos por b:
b.p.n + a.b.s = b

Sustituimos a.b por p.k:
b.p.n + p.k.b.s = b

Despejamos p:
p (bn + kbs) = b

Como (bn + kbs) ∈ Z, queda demostrado que p/b y por exhaustación de casos queda demostrado que si p es primo y p / a.b => p/a ∨ p/b .

Referencias

Apuntes de Clase de Algebra y Matemática Discreta cursada con Marcela Wilder en ella Universidad de Palermo, el segundo cuatrimestre de 2007