1 Conjuntos ‣ Part I Conjuntos, relaciones y funciones ‣ Lógica

Definition 1.1.

Un conjunto es una coleccion de objetos, que se denominan elementos de ese conjunto.

Si $A$ es un conjunto y $b$ es un elemento de $A$ decimos que $b$ pertenece a $A$ . Notacion: $b\in A$ .

En caso contrario, decimos que $b$ no pertenece a $A$ . Notacion: $b\notin A$ .

Example 1.2.

$A=\left\{1,3,5,7\right\}$

Definition 1.3 (Subconjunto).

Sean $A$ y $B$ dos conjuntos. Se dice que $A$ es un subconjunto de $B$ si todo elemento de $A$ es tambien elemento de $B$ .

Tambien se dice que $A$ esta contenido en $B$ . Notacion: $A\subseteq B$ .

En caso contrario diremos que $A$ no esta contenido en B.

Notacion: $A\not\subseteq B$ .

Definition 1.4.

Sean $A$ y $B$ dos conjuntos. Decimos que $A$ y $B$ son iguales si tienen los mismos elementos. Esto es lo mismo que decir que $A\subseteq B$ y $B\subseteq A$ .

Notacion: $A=B$ .

En caso contrario, diremos que $A$ y $B$ son distintos.

Notacion: $A\neq B$ .

Remark 1.5.

En un conjunto no se tienen en cuenta elementos repetidos.

Tampoco se tiene en cuenta el orden.

Definition 1.6 (Contenido estricto).

Decimos que A esta estrictamente contenido en $B$ si $A\subseteq B$ y $A\neq B$ . Notacion: $A\subset B$ .

Example 1.7.

A=\left\{x\mid x\text{ es un numero primo menor que 15}\right\}

A=\left\{2,3,5,7,11,13\right\}

B=\left\{x\mid x\text{ es un numero primo mayor que 15}\right\}

B=\left\{17,19,23,29,31,37,41,43,\ldots\right\}

Definition 1.8 (Conjuntos numericos, informal).

•

Numeros naturales:
$\mathbb{N}\coloneqq\left\{1,2,3,4,5,\ldots\right\}$ . No tiene solucion $2-x=5$ .
•

Numeros enteros:
$\mathbb{Z}\coloneqq\left\{\ldots,-2,-1,0,1,2,\ldots\right\}$ . No tiene solucion $2x=5$ .
•

Numeros racionales:
$\mathbb{Q}\coloneqq\left\{\frac{a}{b}\mid a,b\in\mathbb{Z},b\neq 0\right\}$ . Tienen expresion decimal periodica. No tiene solucion $x^{2}=2$ .
•

Numeros reales:
$\mathbb{R}$ . Tienen expresion decimal arbitraria, periodica o no periodica. No tiene solucion $x^{2}=-1$ .
•

Numeros complejos:
$i\coloneqq\sqrt{-1}$ la unidad imaginaria.

$\mathbb{C}\coloneqq\left\{a+bi\mid a,b\in\mathbb{R}\right\}$

Definition 1.9.

Se define el conjunto vacio como un conjunto sin elementos.

Notacion: $\varnothing$

Proposition 1.10.

Sea $A$ un conjunto cualquiera. Se cumple que $\varnothing\subseteq A$ .

Proof 1.11.

Lo demostraremos por reduccion al absurdo.

Supongamos que $\varnothing\not\subseteq A$ . Entonces, existe un elemento $x$ tal que $x\in\varnothing$ y $x\notin A$ .

Esto es una contradiccion, ya que el conjunto $\varnothing$ no tiene elementos.

Luego es falso que $\varnothing\not\subseteq A$ y por tanto $\varnothing\subseteq A$ .

Definition 1.12 (Operaciones con conjuntos).

Sean $A$ y $B$ dos conjuntos. Se definen:

•

Interseccion de $A$ y $B$ :
$A\cap B\coloneqq\left\{x\mid x\in A\text{ y }x\in B\right\}$
•

Union de $A$ y $B$ :
$A\cup B\coloneqq\left\{x\mid x\in A\text{ o }x\in B\right\}$
•

Diferencia entre $A$ y $B$ (o $A$ menos $B$ ):

$A\setminus B\coloneqq\left\{x\mid x\in A\text{ y }x\notin B\right\}$

Definition 1.13.

Decimos que un conjunto $A$ es finito si tiene tantos elementos como un numero natural o bien si no tiene elementos ( $\varnothing$ ).

En caso contrario decimos que $A$ es infinito.

Definition 1.14.

Si $A$ es un conjunto finito, se define el cardinal de $A$ como su numero de elementos. El cardinal de $\varnothing$ es 0. Si $A$ es un conjunto infinito tiene cardinal infinito.

Notacion: $|A|$

Definition 1.15 (Partes de un conjunto).

Sea $A$ un conjunto. Se define el conjunto de las partes de $A$ como el conjunto formado por todos los subconjuntos de $A$ . Simbolicamente:

\mathcal{{P}}(A)=\left\{B\mid B\subseteq A\right\}

Example 1.16.

Sean $A=\left\{1,2\right\}$ , $B=\left\{1,2,3\right\}$ , $C=\left\{1,2,3,4\right\}$ . Escribir los conjuntos $\mathcal{{P}}(A),\mathcal{{P}}(B),\mathcal{{P}}(C),\mathcal{{P}}(\mathcal{{P}}% (A))$ .

•

Subconjuntos de $A$ : $\left\{1\right\},\left\{2\right\},\left\{1,2\right\},\varnothing$ .

Luego $\mathcal{{P}}(A)=\left\{\varnothing,\left\{1\right\},\left\{2\right\},\left\{1% ,2\right\}\right\}$
•

Subconjuntos de $B$ : $\left\{1\right\},\left\{2\right\},\left\{3\right\},\left\{1,2\right\},\left\{1% ,3\right\},\left\{2,3\right\},\left\{1,2,3\right\},\varnothing$ .

Luego $\mathcal{{P}}(B)=\left\{\varnothing,\left\{1\right\},\left\{2\right\},\left\{3% \right\},\left\{1,2\right\},\left\{1,3\right\},\left\{2,3\right\},\left\{1,2,3% \right\}\right\}$

Theorem 1.17.

Sea $A$ un conjunto finito. Entonces se cumple que

|\mathcal{{P}}(A)|=2^{|A|}

Proof 1.18.

Considero el conjunto $A$ formado por $n$ elementos donde $n\in\mathbb{N}$ .

Sin perdida de generalidad, supongo que $A=\left\{1,2,3,\ldots,n\right\}$ . Para contar subconjuntos de $A$ , planteo el cuestionario

1.

¿Está 1 en el subconjunto?
2.

¿Está 2 en el subconjunto?
n.

¿Está $n$ en el subconjunto?

Hay el mismo numero de subconjuntos de $A$ que de respuestas al cuestionario. Como el cuestionario tiene $n$ preguntas y cada una 2 respuestas posibles, hay $2^{n}$ respuestas diferentes al cuestionario y, por tanto, $2^{n}$ subconjuntos de $A$ .

Falta probarlo para $A=\varnothing$ . Se cumple que $\varnothing\subseteq\varnothing$ y es el unico posible.

Luego $\mathcal{{P}}(\varnothing)=\left\{\varnothing\right\}$

Tenemos que $|A|=0$ y $|\mathcal{{P}}(A)|=1$ . Ademas, $2^{|A|}=2^{0}=1=|\mathcal{{P}}(A)|$

Proof 1.19.

Tambien lo demostraremos por induccion sobre $n$ , el numero de elementos de $A$ .

El caso $n=0$ esta hecho en la demostracion anterior.

En el caso base, $n=1$ , $A=\left\{1\right\}$ y $\mathcal{{P}}(A)=\left\{\varnothing,\left\{1\right\}\right\}$ . Luego $|A|=1$ y $|\mathcal{{P}}(A)|=2=2^{1}=2^{|A|}$ . Se cumple para $n=1$ .

Hipotesis de induccion: Supongamos que el resultado es cierto para $n$ ( $A=\left\{1,2,3,\ldots,n\right\}$ y $|\mathcal{{P}}(A)|=2^{n}$ )

Tengo que demostrar, a partir de esto, la tesis de induccion:

Si $B=\left\{1,2,3,\ldots,n,n+1\right\}$ entonces $|\mathcal{{P}}(A)|=2^{n+1}$ .

Hay 2 tipos de subconjuntos de $B$ .

Tipo 1: Los que no tienen a $n+1$ como elemento. Por hipotesis de induccion hay $2^{n}$ subconjuntos de $B$ de este tipo (son los mismos que los de $A$ ).
Tipo 2: Los que si tienen a $n+1$ como elemento. Cada uno de estos se obtiene añadiendo el elemento $n+1$ a un subconjunto de Tipo 1. Por tanto, hay tantos como habia de Tipo 1: $2^{n}$ .

En total, $B$ tiene:

\underbrace{2^{n}}_{\text{Tipo 1}}+\underbrace{2^{n}}_{\text{Tipo 2}}=2\cdot 2% ^{n}=2^{n+1}=|\mathcal{{P}}(B)|

Asi, queda demostrada la tesis de induccion.

Definition 1.20 (Par ordenado).

Dados dos conjuntos $A$ y $B$ y dos elementos $a\in A$ y $b\in B$ , se define el par ordenado formado por $a$ y $b$ como la expresion simbolica

(a,b)

donde $a$ es el primer elemento del par y $b$ es el segundo elemento del par.

Definition 1.21 (Producto cartesiano).

Sean $A$ y $B$ dos conjuntos no vacios. Se define el producto cartesiano de $A$ por $B$ como el conjunto formado por todos los pares ordenados de la forma $(a,b)$ donde $a\in A$ y $b\in B$ . Simbolicamente:

A\times B\coloneqq\left\{(a,b)\mid a\in A,b\in B\right\}

Example 1.22.

$A=\left\{1,2,3\right\}$ , $B=\left\{2,4\right\}$

A\times B=\left\{(1,2),(1,4),(2,2),(2,4),(3,2),(3,4)\right\}

B\times A=\left\{(2,1),(2,2),(2,3),(4,1),(4,2),(4,3)\right\}

El producto cartesiano no es conmutativo.

Proposition 1.23.

Sean $A$ y $B$ dos conjuntos finitos y no vacios. Se cumple que

|A\times B|=|A|\cdot|B|

Proof 1.24.

Para formar todos los pares ordenados posibles, tenemos $|A|$ opciones en la primera coordenada y $|B|$ en la segunda.

Por tanto, hay en total $|A|\cdot|B|$ pares ordenados.

Así, $|A\times B|=|A|\cdot|B|$

Remark 1.25.

Si $A$ o $B$ es infinito $\Rightarrow$ $|A\times B|=\infty$

Definition 1.26 (n-tupla ordenada).

Sea $n\in\mathbb{N}$ , $n\geq 2$ . Sean $A_{1},A_{2},\ldots,A_{n}$ conjuntos y $a_{1}\in A_{1}$ , $a_{2}\in A_{2}$ , $\ldots$ , $a_{n}\in A_{n}$ elementos de sus conjuntos. Se define la n-tupla ordenada formada por esos elementos como la expresion simbolica

(a_{1},a_{2},\ldots,a_{n})

Definition 1.27.

Sea $n\in\mathbb{N}$ , $n\geq 2$ . Sean $A_{1},A_{2},\ldots,A_{n}$ conjuntos no vacios. Se define el producto cartesiano de esos conjuntos como

A_{1}\times A_{2}\times\dots\times A_{n}\coloneqq\left\{(a_{1},a_{2},\dots,a_{% n})\mid a_{1}\in A_{1},a_{2}\in A_{2},\ldots,a_{n}\in A_{n}\right\}