3 Producto cartesiano, grafos y funciones

3.1 Pares ordenados, productos cartesianos y grafos

Definition 3.1 (Par ordenado).

Se define el par ordenado $(x,y)$ como el conjunto

(x,y)=\left\{\left\{x\right\},\left\{x,y\right\}\right\}

Por otra parte, a partir de los pares ordenados podemos definir las $n$ -tuplas. Por ejemplo, las ternas se pueden definir del siguiente modo:

(x,y,z)=(x,(y,z))

Definition 3.2 (Producto cartesiano).

Dados $A$ y $B$ dos conjuntos, se define el producto cartesiano $A\times B$ como el conjunto de todos los pares ordenados $(a,b)$ tal que $a\in A$ y $b\in B$ . Es decir,

A\times B=\left\{(a,b)\mid a\in A\wedge b\in B\right\}.

Definition 3.3.

Un grafo $G\subset A\times B$ es un subconjunto de un producto cartesiano.

Si $A$ es un conjunto, una relación (binaria) en $A$ es un subconjunto $R\subset A\times A$ .

Si $G\subset A\times B$ , se denomina dominio de $G$ al conjunto

dom(G)=\left\{x\in A\mid\exists y\in B..(x,y)\in G\right\}

y rango de $G$ al conjunto

ran(G)=\left\{y\in B\mid\exists x\in A..(x,y)\in G\right\}

Por ejemplo, si $A$ es un conjunto, el grafo identidad de $A$ es $Id_{A}=\left\{(x,y)\in A\times A\mid x=y\right\}$ .

Si $G\subset A\times B$ es un grafo, se denomina grafo inverso de $G$ al grafo $G^{-1}=\left\{(y,x)\in B\times A\mid(x,y)\in G\right\}$ . Si $G\subset A\times B$ y $H\subset B\times C$ , se denomina grafo composición de $H$ y $G$ en ese orden, y se denota por $H\circ G$ al grafo $H\circ G=\left\{(x,z)\in A\times C\mid\exists y\in B..(x,y)\in G\wedge(y,z)\in H\right\}$ .

Example 3.4.

Ejercicio: comprobar que si $G\subset A\times B$ y $H\subset B\times C$ , entonces

1.

$G\circ Id_{A}=G$
2.

$Id_{H}\circ G=G$
3.

$(G^{-1})^{-1}=G$
4.

$(H\circ G)^{-1}=G^{-1}\circ H^{-1}$ .

$\subset)$

Sea $(z,x)\in(H\circ G)^{-1}$ , tenemos que ver que $(z,x)\in G^{-1}\circ H^{-1}$ . Como $(z,x)\in(H\circ G)^{-1}$ , $(x,z)\in H\circ G$ , por lo que $\exists y\in B$ tal que $(x,y)\in G\wedge(y,z)\in H\Rightarrow\exists y\in B$ tal que $(y,x)\in G^{-1}\wedge(z,y)\in H^{-1}\Rightarrow(z,x)\in G^{-1}\circ H^{-1}$ .

$\supset)$

Análogo.

Definition 3.5.

Una función de un conjunto $A$ en un conjunto $B$ es un conjunto de pares ordenados $f\subset A\times B$ tal que si $(a,b)\in f$ y $(a,c)\in f$ , necesariamente $b=c$ .

Si $\forall a\in A$ existe $b\in B$ tal que $(a,b)\in f$ , diremos que $f$ es una función de $A$ en $B$ y escribiremos $f\colon A\to B$ . Finalmente, si $f$ es una función y $(a,b)\in f$ , es habitual indicar este hecho escribiendo $f(a)=b$ , y afirmando que $b$ es la imagen de $a$ mediante la función $f$ .

Example 3.6.

Algunos ejemplos de funciones son los siguientes:

1.

Si $A$ es un conjunto $Id_{A}$ es una función, por lo que podemos escribir $Id_{A}\colon A\to A$ .
2.

Si $A$ es un subconjunto de $X$ , $\aleph_{A}=\left\{(x,y)\in X\times\left\{0,1\right\}\mid(x\in A\to y=1)\wedge(% x\notin A\to y=0)\right\}$ es una función a la que se denomina función característica de $A$ .
3.

Si $A$ y $B$ son conjuntos, el grafo $p_{1}=\left\{((x,y),z)\in(A\times B)\times A\mid z=x\right\}$ es una función a la que se denomina proyección de $A\times B$ sobre $A$ .
4.

Una sucesión de números reales es una función $x\colon\mathbb{N}\to\mathbb{R}$ , de manera que a cada número natural $n\in\mathbb{N}$ se le asocia un único número real $x(n)$ . En general a $x(n)$ se le llama término $n$ -ésimo de la sucesión y, tradicionalmente, se le representa por $x_{n}$ . De la misma manera, la notación para representar la sucesión es $(x_{n})^{\infty}_{n=1}$ , $(x_{n})$ , $\left\{x_{n}\right\}_{n\in\mathbb{N}}$ o, incluso, $\left\{x_{n}\right\}$ .

3.2 Tipos de funciones

Se dice que una función $f\colon A\to B$ es inyectiva si se satisface la siguiente propiedad:

(\forall x\forall x^{\prime}\forall y\;((x,y)\in f\wedge(x^{\prime},y)\in f)% \Rightarrow x=x^{\prime})

Se dice que una función $f\colon A\to B$ es sobreyectiva si $ran(f)=B$ . Finalmente, se dice que $f\colon A\to B$ es biyectiva si es inyectiva y sobreyectiva. Siendo $f\colon A\to B$ y $g\colon B\to C$ no es difícil comprobar las siguientes afirmaciones:

1.

$f\colon A\to B$ es biyectiva si y solo si $f^{-1}\subset B\times A$ es una función y $dom(f^{-1})=B$ . Además, en ese caso $f^{-1}\colon B\to A$ es también una función biyectiva.

Proof 3.7.

$\Rightarrow)$

Supongamos que $f\subset A\times B$ es función y es biyectiva. Veamos que $f^{-1}\subset B\times A$ es función.

Si $(x,y)\in f^{-1}$ y $(x,z)\in f^{-1}$ , entonces $(y,x)\in f$ y $(z,x)\in f$ . Como además se tiene que $f$ es inyectiva, $y=z$ , con lo que $f^{-1}$ es función.

Por otra parte, como $f$ es sobreyectiva $\forall y\in B$ existe $x\in A$ tal que $(x,y)\in f\Rightarrow(y,x)\in f^{-1}\Rightarrow y\in dom(f^{-1})$ . (Hemos visto que $B\subset dom(f^{-1})$ , pero también hay que ver que $B\supset dom(f^{-1})$ ).
2.

Si $f$ y $g$ son funciones, entonces $g\circ f$ también es una función denominada función compuesta de $f$ y $g$ . De hecho, si $x\in A$ , tendremos que $(x,f(x))\in f$ , y como $f(x)\in dom(g)$ , resultará que $(f(x),g(f(x)))\in g$ . Pero entonces $(x,g(f(x)))\in g\circ f$ , es decir, $(g\circ f)(x)=g(f(x))$ .
3.

Si $f$ y $g$ son inyectivas, entonces $g\circ f$ es inyectiva.
4.

Si $g\circ f$ es inyectiva entonces $f$ es inyectiva.

Proof 3.8.

Suponer que $f(x_{1})=f(x_{2})$ . Entonces $g(f(x_{1}))=g(f(x_{2}))$ , que es lo mismo que $(g\circ f)(x_{1})=(g\circ f)(x_{2})$ . Como $g\circ f$ es inyectiva, $x_{1}=x_{2}$ .
5.

Si $f$ y $g$ son sobreyectivas, entonces $g\circ f$ es sobreyectiva.
6.

Si $g\circ f$ es sobreyectiva entonces $g$ es sobreyectiva.
7.

Si $f$ y $g$ son biyectivas, entonces $g\circ f$ es biyectiva y $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$ .
8.

Si $C=A$ , $g\circ f=Id_{A}$ y $f\circ g=Id_{B}$ , entonces $f$ y $g$ son biyectivas y $g=f^{-1}$ .

3.3 Familias subindicadas

Definition 3.9.

Dados dos conjuntos $X$ e $I$ , llamaremos familia de elementos de $X$ cuyos índices recorren $I$ a cualquier función cuyo dominio sea $I$ y cuyo rango esté contenido en $X$ . El conjunto $I$ es el conjunto de índices de la familia. Si

\displaystyle x\colon I

\displaystyle{}\longrightarrow X

\displaystyle i

\displaystyle{}\longmapsto x(i)

es usual denotar al elemento $x(i)$ por $x_{i}$ y a la familia por $\left\{x_{i}\right\}_{i\in I}$ .

Por ejemplo, para referirnos a una familia de subconjuntos de un conjunto $X$ , en lugar de

\displaystyle A\colon I

\displaystyle{}\longrightarrow P(X)

\displaystyle i

\displaystyle{}\longmapsto A(i)

escribiremos $\left\{A_{i}\right\}_{i\in I}$ . Por otra parte, dada una familia $\left\{A_{i}\right\}_{i\in I}$ de subconjuntos de un conjunto $X$ , se denomina unión de los elementos de dicha familia al conjunto

\bigcup_{i\in I}A_{i}=\left\{x\in X\mid\exists i\in I..x\in A_{i}\right\}

y se denomina intersección de los elementos de dicha familia al conjunto

\bigcap_{i\in I}A_{i}=\left\{x\in X\mid\forall i\in I..x\in A_{i}\right\}

1.

$A-\cap_{i\in I}A_{i}=\cup_{i\in I}(A-A_{i})$

Proof 3.10.

$\Rightarrow)$

Si $x\in A-\cup_{i\in I}A_{i}\Rightarrow x\in A\wedge x\notin\cup_{i\in I}A_{i}% \Rightarrow x\in A\wedge\forall i\in I\;x\notin A_{i}\Rightarrow\forall i\in I% \;x\in(A-A_{i})\Rightarrow\forall i\in I\;x\in\cap_{i\in I}(A-A_{i})$ .

$\Leftarrow)$

Sin hacer.
2.

$A-\cup_{i\in I}A_{i}=\cap_{i\in I}(A-A_{i})$

3.4 Imágenes directas y recíprocas

Dada una función $f\colon A\to B$ y un subconjunto $C\subset A$ , se denomina imagen directa de $C$ mediante $f$ al conjunto

f(C)=\left\{y\in B\mid\exists x\in C..y=f(x)\right\}

De manera análoga, si $D\subset B$ , se denomina imagen recíproca de $D$ mediante $f$ al conjunto

f^{-1}(D)=\left\{x\in A\mid f(x)\in D\right\}

Si $f\colon X\to Y$ es una función, $A$ , $A^{\prime}\subset X$ , $B$ , $B^{\prime}\subset Y$ , $\left\{A_{i}\right\}_{i\in I}$ es una familia de subconjuntos de $X$ , y $\left\{B_{i}\right\}_{i\in I}$ es una familia de subconjuntos de $Y$ , se verifica que:

1.

$A\subset A^{\prime}\Rightarrow f(A)\subset f(A^{\prime})$
2.

$B\subset B^{\prime}\Rightarrow f^{-1}(B)\subset f^{-1}(B^{\prime})$
3.

$f(A\cup A^{\prime})=f(A)\cup f(A^{\prime})$
4.

$f^{-1}(B\cup B^{\prime})=f^{-1}(B)\cup f^{-1}(B^{\prime})$
5.

$f(\cup_{i\in I}A_{i})=\cup_{i\in I}f(A_{i})$
6.

$f^{-1}(\cup_{i\in I}B_{i})=\cup_{i\in I}f^{-1}(B_{i})$
7.

$f(A\cap A^{\prime})\subset f(A)\cap f(A^{\prime})$
8.

$f(\cap_{i\in I}A_{i})\subset\cap_{i\in I}f(A_{i})$
9.

$f^{-1}(\cap_{i\in I}B_{i})=\cap_{i\in I}f^{-1}(B_{i})$
10.

$A\subset f^{-1}(f(A))$
11.

$f(f^{-1}(B))\subset B$
12.

Si $f$ es inyectiva entonces $A=f^{-1}(f(A))$ y $f(A\cap A^{\prime})=f(A)\cap f(A^{\prime})$