4.2: Enumeraciones y conjuntos contables

Última actualización
Guardar como PDF

Page ID: 103735

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Template:MathJaxZach

Ya hemos dado ejemplos de conjuntos al enumerar sus elementos. Discutamos en términos más generales cómo y cuándo podemos enumerar los elementos de un conjunto, aunque ese conjunto sea infinito.

Definición$\PageIndex{1}$: Enumeration, informally

Informalmente, una enumeración de un conjunto$A$ es una lista (posiblemente infinita) de elementos de$A$ tal manera que cada elemento de$A$ aparece en la lista en alguna posición finita. Si$A$ tiene una enumeración, entonces$A$ se dice que es contable.

Un par de puntos sobre las enumeraciones:

Contamos como enumeraciones solo listas que tienen un comienzo y en las que cada elemento que no sea el primero tiene un solo elemento inmediatamente anterior al mismo. Es decir, sólo hay finitamente muchos elementos entre el primer elemento de la lista y cualquier otro elemento. En particular, esto significa que cada elemento de una enumeración tiene una posición finita: el primer elemento tiene posición$1$, la segunda posición$2$, etc.
Podemos tener diferentes enumeraciones del mismo conjunto$A$ que difieren por el orden en que aparecen los elementos:$4$,,$1$,$25$,$16$,$9$ enumera los (conjunto de los) primeros cinco números cuadrados igual de bien como$1$,,$4$,$9$$16$,$25$ lo hace.
Las enumeraciones redundantes siguen siendo enumeraciones:$1$$1$$2$,$2$,,$3$,$3$,,... enumera el mismo conjunto que$1$,$2$,$3$,... hace.
El orden y la redundancia sí importan cuando especificamos una enumeración: podemos enumerar los enteros positivos comenzando con$1$,$2$,$3$,$1$,..., pero el patrón es más fácil de ver cuando se enumera de manera estándar como $1$,$2$,$3$,$4$,...
Las enumeraciones deben tener un comienzo:...$3$$2$,, no$1$ es una enumeración de los enteros positivos porque no tiene primer elemento. Para ver cómo se desprende esto de la definición informal, pregúntese, “¿en qué posición de la lista aparece el número 76?”
El siguiente no es una enumeración de los enteros positivos:$1$,$3$,$5$,...,$2$,$4$$6$,... El problema es que los números pares ocurren en lugares$\infty + 1$, $\infty + 2$$\infty + 3$, más que en posiciones finitas.
El conjunto vacío es enumerable: ¡está enumerado por la lista vacía!

Proposición$\PageIndex{1}$

Si$A$ tiene una enumeración, tiene una enumeración sin repeticiones.

Prueba. Supongamos que$A$ tiene una enumeración$x_1$$x_2$,,... en la que cada uno$x_i$ es un elemento de$A$. Podemos eliminar repeticiones de una enumeración eliminando elementos repetidos. Por ejemplo, podemos convertir la enumeración en una nueva en la que enumeremos$x_i$ si es un elemento de$A$ que no está entre$x_1$,...,$x_{i-1}$ o eliminar$x_i$ de la lista si ya aparece entre $x_1$,...,$x_{i-1}$. ◻

El último argumento muestra que para poder manejar bien las enumeraciones y conjuntos contables y para probar cosas sobre ellos, necesitamos una definición más precisa. Lo proporciona lo siguiente.

Definición$\PageIndex{2}$: Enumeration, formally

Una enumeración de un conjunto$A \neq \emptyset$ es cualquier función suryectiva$f \colon \PosInt \to A$.

Vamos a convencernos de que la definición formal y la definición informal usando una lista posiblemente infinita son equivalentes. Primero, cualquier función suryectiva de$\PosInt$ a un conjunto$A$ enumera$A$. Tal función determina una enumeración como se definió informalmente anteriormente: la lista$f(1)$,$f(2)$,$f(3)$,... Ya que$f$ es suryectiva,$A$ se garantiza que cada elemento de sea el valor de$f(n)$ para algunos$n \in \PosInt$. De ahí que cada elemento de$A$ aparezca en alguna posición finita de la lista. Dado que la función puede no ser inyectiva, la lista puede ser redundante, pero eso es aceptable (como se señaló anteriormente).

Por otro lado, dada una lista que enumera todos los elementos de$A$, podemos definir una función suryectiva$f\colon \PosInt \to A$ dejando$f(n)$ ser el elemento$n$ th de la lista, o el elemento final de la lista si no hay$n$ th elemento. El único caso en el que esto no produce una función suryectiva es cuando$A$ está vacía, y por lo tanto la lista está vacía. Entonces, cada lista no vacía determina una función suryectiva$f\colon \PosInt \to A$.

Definición$\PageIndex{3}$

Un conjunto$A$ es contable si está vacío o tiene una enumeración.

Ejemplo$\PageIndex{1}$

Una función que enumera los enteros positivos ($\PosInt$) es simplemente la función de identidad dada por$f(n) = n$. Una función que enumera los números naturales$\Nat$ es la función$g(n) = n - 1$.

Ejemplo$\PageIndex{2}$

Las funciones$f\colon \PosInt \to \PosInt$ y$g \colon \PosInt \to \PosInt$ dadas por\[\begin{aligned} f(n) & = 2n \text{ and}\\ g(n) & = 2n+1\end{aligned}\] enumeran los enteros positivos pares y los enteros positivos impares, respectivamente. Sin embargo, ninguna función es una enumeración de$\PosInt$, ya que ninguna es suryectiva.

Problema$\PageIndex{1}$

Definir una enumeración de los cuadrados positivos$1$,$4$,$9$,$16$,...

Ejemplo$\PageIndex{3}$

La función$f(n) = (-1)^{n} \lceil \frac{(n-1)}{2}\rceil$ (donde$\lceil x \rceil$ denota la función de techo, que$x$ redondea al entero más cercano) enumera el conjunto de enteros$\Int$. Observe cómo$f$ genera los valores de$\Int$ “saltando” de un lado a otro entre enteros positivos y negativos: También\[\begin{array}{c c c c c c c c} f(1) & f(2) & f(3) & f(4) & f(5) & f(6) & f(7) & \dots \\ \\ - \lceil \tfrac{0}{2} \rceil & \lceil \tfrac{1}{2}\rceil & - \lceil \tfrac{2}{2} \rceil & \lceil \tfrac{3}{2} \rceil & - \lceil \tfrac{4}{2} \rceil & \lceil \tfrac{5}{2} \rceil & - \lceil \tfrac{6}{2} \rceil & \dots \\ \\ 0 & 1 & -1 & 2 & -2 & 3 & \dots \end{array}\nonumber\] puede pensar en lo$f$ definido por los casos de la siguiente manera:\[f(n) = \begin{cases} 0 & \text{if $n = 1$}\\ n/2 & \text{if $n$ is even}\\ -(n-1)/2 & \text{if $n$ is odd and $>1$} \end{cases}\nonumber\]

Problema$\PageIndex{2}$

Demuestre que si$A$ y$B$ son contables, así es$A \cup B$. Para ello, supongamos que existen funciones suryectivas$f\colon \PosInt \to A$ y$g\colon \PosInt \to B$, y definir una función suryectiva$h\colon \PosInt \to A \cup B$ y demostrar que es suryectiva. También considere los casos donde$A$ o$B = \emptyset$.

Problema$\PageIndex{3}$

Demostrar que si$B \subseteq A$ y$A$ es contable, así es$B$. Para ello, supongamos que existe una función suryectiva$f\colon \PosInt \to A$. Definir una función suryectiva$g\colon \PosInt \to B$ y demostrar que es suryectiva. ¿Qué pasa si$B = \emptyset$?

Problema$\PageIndex{4}$

Mostrar por inducción sobre$n$ eso si$A_1$,$A_2$,...,$A_n$ son todos contables, así es$A_1 \cup \dots \cup A_n$. Se puede asumir el hecho de que si dos conjuntos$A$ y$B$ son contables, así es$A \cup B$.

Aunque quizás sea más natural a la hora de enumerar los elementos de un conjunto para comenzar a contar desde el elemento$1$ st, a los matemáticos les gusta usar los números naturales$\Nat$ para contar cosas. Hablan de los elementos$0$ th,$1$ st,$2$ nd, y así sucesivamente, de una lista. Correspondientemente, podemos definir una enumeración como una función suryectiva de$\Nat$ a$A$. Por supuesto, las dos definiciones son equivalentes.

Proposición$\PageIndex{2}$

Hay una sobrejección$f\colon \PosInt \to A$ si hay una sobrejección$g\colon \Nat \to A$.

Prueba. Ante una sobrejección$f\colon \PosInt \to A$, podemos definir$g(n) = f(n+1)$ para todos$n \in \Nat$. Es fácil ver que$g\colon \Nat \to A$ es suryectiva. Por el contrario, dada una sobreyección$g\colon \Nat \to A$, definir$f(n) = g(n+1)$. ◻

Esto nos da el siguiente resultado:

Corolario$\PageIndex{1}$

Un conjunto$A$ es contable si está vacío o hay una función suryectiva$f\colon \Nat \to A$.

Discutimos anteriormente que una lista de elementos de un conjunto se$A$ puede convertir en una lista sin repeticiones. Esto también es cierto para las enumeraciones, pero un poco más difícil de formular y probar rigurosamente. Cualquier función$f\colon \PosInt \to A$ debe ser definida para todos$n \in \PosInt$. Si solo hay finitamente muchos elementos en$A$ entonces claramente no podemos tener una función definida en los infinitamente muchos elementos de$\PosInt$ eso toma como valores todos los elementos de$A$ pero nunca toma el mismo valor dos veces. En ese caso, es decir, en el caso de que la lista sin repeticiones sea finita, debemos elegir un dominio diferente para$f$, uno con solo finitamente muchos elementos. No tener repeticiones significa que$f$ debe ser inyectivo. Como también es suryectiva, estamos buscando una biyección entre algún conjunto finito$\{1, \dots, n\}$ o$\PosInt$ y$A$.

Proposición$\PageIndex{3}$

Si$f\colon \PosInt \to A$ es suryectiva (es decir, una enumeración de$A$), hay una biyección$g\colon Z \to A$ donde$Z$ está$\PosInt$ o$\{1, \dots, n\}$ para algunos$n \in \PosInt$.

Prueba. Definimos la función$g$ recursivamente: Let$g(1) = f(1)$. Si ya se$g(i)$ ha definido, que$g(i+1)$ sea el primer valor de$f(1)$$f(2)$,,... no ya entre$g(1)$,...$g(i)$,, si hay uno. Si$A$ tiene solo$n$ elementos, entonces$g(1)$,...,$g(n)$ están todos definidos, y así hemos definido una función$g\colon \{1, \dots, n\} \to A$. Si$A$ tiene infinitamente muchos elementos, entonces para cualquiera debe$i$ haber un elemento de$A$ en la enumeración$f(1)$,$f(2)$,..., que no está ya entre$g(1)$,...,$g(i)$. En este caso hemos definido una función$g\colon \PosInt \to A$.

La función$g$ es suryectiva, ya que cualquier elemento de$A$ se encuentra entre$f(1)$$f(2)$,,... (ya que$f$ es suryectiva) y así eventualmente será un valor de$g(i)$ para algunos$i$. También es inyectivo, ya que si hubiera$j < i$ tal que$g(j) = g(i)$, entonces ya$g(i)$ estaría entre$g(1)$,...,$g(i-1)$, contrario a como definimos$g$. ◻

Corolario$\PageIndex{2}$

Un conjunto$A$ es contable si está vacío o hay una biyección$f\colon N \to A$ donde cualquiera$N = \Nat$ o$N = \{0, \dots, n\}$ para algunos$n \in \Nat$.

Prueba. $A$es contable iff$A$ está vacío o hay una suryectiva$f\colon \PosInt \to A$. Por Proposición$\PageIndex{3}$, esta última sostiene si hay una función biyectiva$f\colon Z \to A$ donde$Z = \PosInt$ o$Z = \{1, \dots, n\}$ para algunos$n \in \PosInt$. Por el mismo argumento que en la prueba de Proposición$\PageIndex{2}$, ese a su vez es el caso si hay una biyección$g\colon N \to A$ donde cualquiera$N = \Nat$ o$N = \{0, \dots, n-1\}$. ◻

Problema$\PageIndex{5}$

Según Definición$\PageIndex{3}$, un conjunto$A$ es enumerable iff$A = \emptyset$ o hay una suryectiva$f\colon \PosInt \to A$. También es posible definir “conjunto contable” precisamente por: un conjunto es enumerable si hay una función de inyección$g\colon A \to \PosInt$. Demostrar que las definiciones son equivalentes, es decir, mostrar que existe una función$g\colon A \to \PosInt$ de inyección si bien$A = \emptyset$ o hay una suryectiva$f\colon \PosInt \to A$.