Principio de inducción completa

Principio de inducción completa:

Surge del principio de buena ordenación visto en Cardinales y Ordinales

Sea P(n): \mathbb{N} \to  \mathbb{N} que depende de $ n > o \in \mathbb{N} $ queremos poder demostrar que P(n) se cumple para todo n > 0.

1- Si la expresión P(0) se verifica.

2- Si para todo k \in \mathbb{N} se cumple P(k-1) entonces se verifica P(k)

Ejemplo:

Sea P(n) : la suman de los primero n números naturales, o sea P(n) =  \displaystyle\sum_{i=0}^n i = 1+2+3+4+5+ \cdot\ldots\cdot + n = \frac{n(n+1)}{2}

1- P(0) =  \frac{0(0+1)}{2} = 0 \checkmark

2- P(k-1) = \frac{(k-1)(k-1+1)}{2}= \frac{k(k-1)}{2} =  \displaystyle\sum_{i=0}^{k-1} i =   1+2+3+4+5+ \cdot\ldots\cdot + (k-1) =  \frac{k(k-1)}{2} .

Sumando k en ambos miembros obtenemos:

1+2+3+4+5+ \cdot\ldots\cdot + (k-1)  + k =  \frac{k(k-1)}{2}+k =  \frac{k(k-1)+2k}{2} =  \frac{k ^ 2- k+2k}{2} =   \frac{((k+ 2)- 1)k)}{2} = \frac{k(k+1)}{2}   \checkmark

Porque \displaystyle\sum_{i=0}^n i = 1+2+3+4+5+ \cdot\ldots\cdot + n = \frac{n(n+1)}{2} ?

Sea S1 = 1+2+3+ \cdot \ldots \cdot +(n-1)+n la suma de los primero n números naturales. Reordenamos la suma tal que S2 = n+(n-1)+ \cdot \ldots \cdot +3+2+1. Al realizar la operación S1+S2 obtenemos:

1+2+3+ \cdot \ldots \cdot +(n-1)+n \\ + \\ n+(n-1)+ \cdot \ldots \cdot 3+2+1 \\ \underbrace{ (n+1)+ (n+1)+ \cdot \ldots \cdot + (n+1) }_{\text{n veces}} \\ S1+S2 = 2 S = n(n+1) \Rightarrow S  = \frac{n(n+1)}{2}  \checkmark

Teoría de conjuntos 8 – Cardinales y ordinales.

Si tenemos un conjunto finito , ¿cómo haríamos para contar la cantidad de elementos que tiene el conjunto?

Una forma sería contar uno por uno los elementos hasta completar la totalidad de los mismos. La otra forma sería , dado un conjunto que sabemos la cantidad de elemento que tiene relacionar el primer elemento de un conjunto con el primero del otros, el segundo con el segundo, hasta el n-esimo.

Por ejemplo si tenemos una sala de teatro donde se venden entradas sin numerar, y no sabemos la cantidad de butacas disponibles, cada espectador que llega se sienta en alguna silla libre, el el momento que se ocupe la última silla sabremos que la sala está llena.

De esa forma sabremos que la cantidad de espectadores es igual a la cantidad de butacas.

Definiendo como A al conjunto de las butacas y B a las de los espectadores existirá una relación uno a uno entre cada elemento de A con los de B y de B con los de A. Es decir tendremos una relación biunívoca entre A y B. Cuando ocurre esa relación se dice que los conjuntos A y B con coordinables o tienen una relación de coordinabilidad. Es símbolos se expresa como A \sim B.

Esta relación divide a los conjuntos en clases que son coordinables entre si. Esto permite definir una abstracción , el número cardinal.

Se puede demostrar que la relación de coordinabilidad es una relación de equivalencia.

Sea a \quad y b dos números cardinales , se dice que b sigue a a ( a \leq b \lor b \leq a ) si siendo A y B dos conjuntos con cardinalidades a y b respectivamente , se dice que A es coordinable con una parte de B

Esta definición no depende de los representantes elegidos en las clases a y b.

Dos conjuntos tiene el mismo cardinal si pertenecen a la misma clase, o sea son coordinables entre si.

El cardinal del conjunto A se denota como |A|

Si el conjunto es finito y ordenado establecemos implícitamente una ordenación entre sus elementos, y el último n se llama ordinal del conjunto.

Cualquiera sea la forma de contar los elementos de un conjunto finito llegaremos al mismo ordinal n (teorema de la invariancia del ordinal de un conjunto finito).

Construcción de ordinales

En el post sobre Relacion de orden se analizó detalles de los conjuntos ordenados y bien ordenados, en este apartado se describirá más detalles sobre los conjuntos bien ordenados.

Conjunto bien ordenado:

Sea (A,\leq) un conjunto ordenado. Si \exists a \in A / \forall x \in A a \leq x , dicho elemento es el único que goza de tal propiedad, pues si \forall x \in A x \leq a'  \to a'=a

Definición: Sea (A,\leq) un conjunto ordenado se dice que el elemento a \in A es el primer elemento de (A,\leq) o el menor. Si para todo x \in A se verifica a \leq x  x \leq a.

Principio del buen orden: Se dice que un conjunto ordenado (A,\leq) está bien ordenado de (A,\leq) si todo subconjunto no vacío tiene primer elemento. Se dice que la relación de orden es un buen orden en A o que bien ordena a A . En el conjunto de los números naturales \mathbb{N} ese elemento es el 1.

Principio de inducción: Sea (A,\leq ) un conjunto bien ordenado, y sea B \subset A tal que:

  • El primer elemento de A es un elemento de B.
  • Para todo x \in A \quad  \forall y ( y < x \to y \in B) \Rightarrow x \in B \Rightarrow B = A

El principio del buen orden implica el principio de inducción y el principio de inducción implica el principio del buen orden

Demostración: Supongamos que se verifica el principio de buena ordenación. Tomemos un subconjunto de los naturales no vacío, \displaystyle A\neq \varnothing , de modo que dicho subconjunto cumpla dos condiciones:

Teoría de conjuntos 7 – Relación de orden

En este apartado vamos a estudiar la estructuras definidas por una relación de orden entre conjuntos.

Definición: Sea A un conjunto y R una relación en A , se dice que R es una “relación de orden” en A (o un orden en A ) si es reflexiva , anti simétrica y transitiva.

  • Una relación es reflexiva cuando \forall x \in A \quad xRx
  • Es anti simétrica cuando \forall x,y \in A \quad  xRy \land yRx
  • Sea cual fuere x , y \quad xRy \lor yRx, es decir no se excluye que dos elementos sean incomparables.

Un ejemplo evidente de conjunto provisto por tal estructura es el conjunto de los números enteros (o el de los reales), reemplazando el símbolo R por $latex \l

Definición:

Se llama conjunto de orden a un par (A,R), donde A es un conjunto y R una relación de orden en A. Al conjunto ordenado (A,R) se los denomina conjunto A ordenado por R. Al conjunto A se los llama conjunto subyacente del conjunto ordenado (A,R). También se los denomina conjunto parcialmente ordenado.

Se suele utilizar los símbolos \leq , \geq para definir una relación de orden, donde dependiendo de como donde se aplica definen:

  • \leq x es anterior que y o x es inferior a y, o x sigue a y.
  • \geq x es posterior a x , x es superior a y, y es predecesor de x.

Propiedades:

  • \forall x \in A \quad x \leq x
  • x \leq y y y \leq z \Rightarrow x \leq z

Ejemplos:

1- (\mathbb{N}, \leq), (\mathbb{R}, \leq) ,  (\mathbb{Z}, \leq) son relaciones de orden.

2- Sea \mathbb{E} un conjunto \mathcal{P}(E) definida como A \leq B \iff A \subset B es una relación de orden:

a) \forall A \in  \mathcal{P}(E)  A \subseteq A

b) Si A \subset B y B \subset A \to A = B

c) Si A \subset B y B \subset C \to A \subset C

3- Sea x \in \mathbb{N} definimos la relación x , y \in \mathbb{N} \to  x | y  ¿es de orden?. Donde x| y  es ” x divide a y “.

a) \forall x \in \mathbb{N} x|y  \to Reflexiva.

b) \forall x,y \in \mathbb{N} \quad  x|y \land y|x \to x=y \to Antisimétrica

c) \forall x,y,z \in \mathbb{N} \quad x|y \land y|z \to x|z \to Transitiva

Conjunto totalmente ordenado

En una relación de orden puede suceder que \forall x,y \in A \quad x \not \leq y \land  y \not \leq x .

Ejemplo: Sea x,y \in \mathbb{N} con R =  x|y, si x = 2 e y=3  \Rightarrow x \not \leq y \land y \not \leq x.

Definición:

Se dice que una relación de orden (A,\leq) es de orden total o que está totalmente ordenado por la relación \leq si \forall x,y \in A se cumple que x \leq y o b \leq a.

Ejemplo: la relación \leq usual entre números naturales es una relación de orden total.

Orden total equivale a orden lineal

Un subconjunto ordenado de (A,\leq) se llama subconjunto totalmente ordenado de A o cadena de A

Elementos maximales y minimales

Definición: Sea (A, \leq) un conjunto ordenado , un elemento de a \in A se llama maximal de A si para todo x \in A \quad x \leq a. Si a \geq a \to x = a. Analogamente , un minimal de A es aquel que para todo x \in A \quad x \geq a si x \leq a \to x=a

“Un conjunto ordenado de (A,\leq) puede tener elementos maximales o minimales pero si los tienen son únicos”

Ejemplos:

Sea E un conjunto y (\mathcal{P}(E),\subset) el conjunto de partes ordenados por inclusión. Entonces \emptyset es el minimal y E el maximal. En el conjunto de partes no vacías de E los elementos unitarios también son minimales (cuando son ordenados por inclusión).

Este ejemplo es muy interesante porque es anti intuitivo. Sea (\mathbb{N},\leq) el conjunto ordenado por la relación x \leq y \iff x|y el minimal es 1 porque si x \not \leq 1 \to x=1 y el maximal es 0 porque si 0|x \to x = 0

Cotas superiores e inferiores:

Definición: Sea (A,\leq) un conjunto ordenado y x \subset A, un elemento k \in A es una cota superior de X si para todo x \in X se tiene que x \leq k y es cota inferior de X si para todo x \in X \quad x \geq k.

El elemento k es cota inferior (superior) del subconjunto ordenado (X,\leq) de (A,\leq). Si el conjunto de cotas superiores no es vacío se dice que X está acotado superiormente (inferiormente). Si X está acotado superior e inferiormente se dice que X es un conjunto acotado.

Ejemplos:

Sea (\mathbb{N},\leq) está acotado inferiormente por el 0 pero no tiene cota superior.

El intervalo cerrado [a,b] tienen cota inferior a y cota superior b , por lo tanto es un conjunto acotado.

Sea E un conjunto y (\mathcal{P}(E),\leq) un conjunto de partes ordenado por inclusión , tiene cota inferior ( \bigcap_{i \in I} E_i ) y cota superior (\bigcup_{i \in I} E_i)

Conjunto bien ordenado:

Sea (A,\leq) un conjunto ordenado. Si \exists a \in A / \forall x \in A a \leq x , dicho elemento es el único que goza de tal propiedad, pues si \forall x \in A x \leq a'  \to a'=a

Definición: Sea (A,\leq) un conjunto ordenado se dice que el elemento a \in A es el primer elemento de (A,\leq) o el menor. Si para todo x \in A se verifica a \leq x  x \leq a.

Definición: Se dice que un conjunto ordenado (A,\leq) está bien ordenado de (A,\leq) si todo subconjunto no vacío tiene primer elemento. Se dice que la relación de orden es un buen orden en A o que bien ordena a A .

Ejemplos:

1- \mathbb{N} está bien ordenado con el orden usual.

2- \mathbb{Q} con el orden usual no está bien ordenado. En efecto en todo intervalo abierto racional \{ x: x \in Q , \frac{a}{b} < x < \frac{c}{d} \} con \frac{a}{b} \not = \frac{c}{d} carece de primer elemento , pues \forall \frac{p}{q} \in (\frac{a}{b},\frac{c}{d}) se verifica que \frac{a}{b} < \frac{a+p}{b+q} < \frac{c}{d} con p,q \in \mathbb{N}

Un conjunto bien ordenado está totalmente ordenado.

Bibliografía:

  • “Las grandes corrientes del pensamiento matemático” – Francois Le Lionnais
  • “Introducción a la teoría de conjuntos ” – Lia Oubiña

Teoría de conjuntos 6 – Relación de equivalencia

Existen varios tipos de relaciones entre conjuntos, en Aplicaciones y Funciones vimos los aspectos generales de la relaciones entre conjuntos.

En este post vamos a ver una relación muy importante y que se usa tanto en teoría de conjuntos, álgebra o matemática discreta es la relación de equivalencia.

Definición:

Sea la relación R una relación entre los conjuntos A y B , se dice que es de equivalencia cuando cumple las siguientes propiedades:

  1. Reflexividad:
  2. Simetria
  3. Transitividad

Una relación es reflexiva cuando \forall x \quad xRx

Es simétrica cuando \forall x,y \quad xRy \Rightarrow yRx

Y es transitiva cuando \forall x,y,z \quad xRy \land yRz \Rightarrow xRz

Cuando aRb es una relación de equivalencia entre a y b la denotamos como a \sim b

Ejemplo:

Sea A un conjunto y R= \{ x,y  \in A / x = y \} es una relación de equivalencia. En efecto.

  1. Para todo x \in A  , se cumple que x\sim x \to Reflexiva
  2. Si x\sim x implica y\sim x \to Simétrica
  3. Si x\sim y e y\sim z \to  x\sim z \to Transitiva

Ejemplo 2:

Si E es el conjunto de rectas del plano, la relación a\sim b  \iff a \| b es una relación de equivalencia en E . En efecto

  1. Toda recta el paralela a si misma.
  2. Si a \| b \to b \| a
  3. Si a \| b  \land   b \| c   \to a \| c

En cambio la relación a \perp  b  NO es una relación de equivalencia por que a \not \perp a y por lo tanto no es una relación reflexiva. Con esto ya alcanza para decir que no es una relación de equivalencia, pero es interesante verificar las otras propiedades.

Si a \perp b  \to  b \perp a se cumple la propiedad de simetría

Si a \perp b \land    b \perp c   \to  a  \not \perp c sino que a \quad y \quad c son paralelas, entonces no se cumple la propiedad transitiva.

Ejemplo 3:

Sea los vectores \mathbf{v} , \mathbf{u}  \in \mathbb{R}^n la relación \mathbf{v} \| \mathbf{u} es una relación de equivalencia. En efecto:

  1. Todo vector es paralelo a si mismo.
  2. Si \mathbf{v} \| \mathbf{u} \to \mathbf{u} \| \mathbf{v}
  3. Si \mathbf{v}  \| \mathbf{u}   \land \mathbf{u}   \|          \mathbf{w} \to \mathbf{v} \| \mathbf{w}

Ejemplo 4:

Se dice que el conjunto A es coordinable con el conjunto B si existe una biyección entre A y B .

Sea E un conjunto , la relación X \sim Y si y solo si X es coordinable con Y , es una relación de equivalencia en \mathcal{P}(E) . En efecto:

  1. Para todo X \subset E \ la función idéntica* de X es una biyección de X  \to Reflexiva.
  2. Si X es coordinable con Y , existe una biyección f de X en Y y por lo tanto existe la función inversa f ^{-1} que es una biyección de Y en X \to Simétrica.
  3. Si X es coordinable con Y y Y es coordinable con Z , existen biyecciones f y g de X en Y y de Y en Z respectivamente la composición gof es una biyección de X en Z \to Transitiva.

* Se A un conjunto , se llama “diagonal de A \times A ” y se denota como \Delta A , al conjunto

\Delta A  = \{ (x,x): x \in A \}

La correspondencia \Delta A \to A se llama “función idéntica de A” y para todo x \in A \quad I_d(x) = x

Ejemplo 4:

Sea a,b \in \mathbb{N} \land a < b si \forall  a | b  se dice que b divide a a o b es múltiplo de a . En ese caso el conjunto de los números a_{i} forman una clase de equivalencia : “Divisores de b

Se dice que a es congruente con b módulo m cuando el resto de a/m es b donde a = mk + b  con k,m,b  \in \mathbb{N} . Si b = 0 a es divisible por b , es decir a | b módulo m .

Sea a el representante de la clase “divisible por b ” se denota por [a] .

La relación de congruencia se denota con el símbolo \equiv y es una relación de equivalencia.

En efecto:

  • Para todo número entero a a-a=0 y como 0 es múltiplo de m resulta a \equiv a \pmod{m}  \to Reflexiva.
  • Si a \equiv  b   \pmod{m} se tiene a-b es múltiplo de m es decir existe un entero k tal que a-b = mk pero entonces b-a = (-k)m de donde b-a es múltiplo de m , por lo tanto a \equiv b  \pmod{m}  \to Simétrica.
  • Si a \equiv  b  \pmod{m} y b \equiv c  \pmod{m} se tiene que a-b y b-c son múltiplos de m . Es decir existen dos números enteros k \land k' tales que a-b = mk y b-c=mk' , sumando miembro a miembro las anteriores igualdades tenemos a-c = (k+k')m o sea a-c es múltiplo de m y por lo tanto a \equiv c  \pmod{m} \to Transitiva.

Ejemplo 5:

Sean p, q, r , s enteros, con q \land  s  \neq 0. Definimos p/q \sim r/s  si ps=qr. Claramente \sim es refleja y simétrica. Para mostrar que también es transitiva, supongamos que p/q \sim r/s \land  r/s \sim t/u , con q, s, u todos distintos de cero. Entonces ps=qr \land  ru=st

Por lo tanto, psu=qru=qst .

Como s \neq 0 \quad pu=qt . Así, p/q \sim t/u.

Relación de equivalencia y conjunto cociente:

Definición: Sea E un conjunto y R una relación de equivalencia en E se llama clase de equivalencia módulo R (o según R) a la imagen de R por \{x\}, donde \{x\} es un elemento de la relación de equivalencia y se denomina “representante de la clase” .

Es decir R(x)= \{ y / y \in E   \land x \sim y\}

Definición: Sea E un conjunto y R una relación de equivalencia en E por R. Se llama conjunto cociente de E por R al conjunto de las clases de equivalencia módulo R en E. Al conjunto cociente se denota como E/R.

Lema: Si R es una relación de equivalencia en un conjunto E, entonces para todo para (x,y) perteneciente a E \times E se tiene que x \sim y  \iff R(x) = R(y) .

Teorema: Sea E un conjunto y R una relación de equivalencia en E . El conjunto cociente de E es una partición de E

Demostración: \forall x \in E \quad x \in R(x) , los elementos de E/R son subconjuntos no vacíos de E y sea R(x) y R(y) dos elementos de E/R y sea z  \in R(x) \cap R(y) \Rightarrow  x \sim y \quad y \sim z   \Rightarrow  x \sim y entonces por el lema anterior R(x) =  R(y) . Propiedad simétrica y transitiva.

Por lo tanto los elementos de E/R son dos a dos disjuntos \Box .

Teoría de conjuntos 5 – Recubrimiento y partición

En este curso de teoría de conjuntos hemos visto las operaciones entre conjuntos, las relaciones , aplicaciones y funciones entre conjuntos. En este capitulo estudiaremos los conceptos de cubrimiento (o recubrimiento) y partición de un conjunto.

Definición: Sea A un conjunto y C una colección finita de conjuntos. Se dice cubrimiento de A por C cuando la unión de los conjuntos de la colección C incluye a todos los elementos de A

A \subset \bigcup_{i \in I} C_{i}

Si A = \bigcup_{ i \in I} C_{i} se dice que \forall i C_{i} es una partición de A

Cabe destacar que \forall i,j \in I \wedge i \not = j C_{i} \cap C_{j}=\emptyset , es decir son conjuntos disjuntos dos a dos.

Ejemplo:

Sea A = {a,b,c} determinar las particiones de A.

\mathcal{P} = {{a},{b},{c}},{{a,b}, {c}},{{a,c},{b}},{{b,c},{a}},{{a,b,c}}

De esta forma se puede pensar al conjunto de particiones como porciones de una pizza que unidas forman la pizza completa pero que cada porción no comparte contenido de la pizza con las otras porciones. Lo mismo pasa si las agrupamos de subconjuntos de mas de un elemento, cada subconjunto será formado por partes de pizza que no estarán en los otros subconjuntos de la misma partición.

Las particiones de una pizza

Los conjuntos se puede agrupar por elementos que tienen una característica en común , por ejemplo en la foto de la pizza podemos ver porciones con queso rallado, longaniza, jamón y choclo. Empezando por la partes con longaniza y recorriendo en sentido de las agujas del reloj tenemos: Conjunto Longaniza : {1,2}, conjunto choclo: {3,4}, conjunto queso rallado: {5,6} y conjunto jamón: {7,8}.

Formalmente , la relación entre elementos de subconjuntos con elementos comunes que dice que forman una Relación de equivalencia, cada uno de los subconjuntos mencionados se denominan clases, y un elemento en particular, representante de la clase al que pertenece.

En símbolos: Sea a,b \in \mathbb{S} [a] = [b]

Ejemplo 2:

En este ejemplo si agrupamos por clases según el color, cada clase tiene un solo elemento.

Ejemplo 3:

En este caso nombrando cada clase por su color.

Verde= {A8}, Violeta= {A7,A4}, Marrón= {A5}, Rosa= {A6,A2}, Celeste={A9}, Amarillo={A1,A3}.

Denominando C al conjunto total tenemos

C= {Verde \cup Violeta  \cup  Marron \cup  Rosa \cup  Celeste \cup  Amarillo }

Ejemplo 3:

La totalidad de los triangulo del plano se pueden partir en clases según diferentes criterios. Por ejemplo, el conjunto se triángulos que tiene igual área. Sea a,b \in \mathbb{T} a pertenece a la misma clase que b si el área de a es igual al área de b

Se representa como [a] como la clase que agrupa elementos con la misma característica de a . Entonces a es el representante de la clase.

En símbolos: Sea a,b \in \mathbb{T}  \land [a]=[b] \iff a \in Clase(A) \land b \in Clase(A) Si A_{i} y A_{j} son partes de \mathbb{T} \Rightarrow A_{i} = A_{j} \lor A_{i} \cap A_{j} = \emptyset

Cuantos elementos puede tener un partición de un conjunto de n elementos?

La cantidad de particiones posibles para un conjunto finito solo depende de su cardinal n y se denominan números de Bell. Los primeros números de Bell son B0 = 1, B1 = 1, B2 = 2, B3 = 5, B4 = 15, B5 = 52, B6 = 203, …

Para más detalles sobre los números de Bell ver https://oeis.org/A000110 (en inglés)

Ejercicio:

Sea A = { x:x  \in \mathbb{N} / 0 < x \leq 10 }
Hallar una colección de conjuntos de A tal que cada subconjunto A_{i} de A están formados por elemento x \in \mathbb{N} tal que su suma es i.

Es decir, la colección mencionada es \mathcal{C} = { x: x \in A_{i} \land \sum_{i \in \mathbb{I}} A_{i} = i  \forall A_{i} \in A}

Esa colección de conjuntos es partición o un cubrimiento de A?.