Saltar al contenido principal
Library homepage
 
LibreTexts Español

4.7: Reducción

  • Page ID
    103717
  • \( \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

    Demostramos\(\Pow{\PosInt}\) ser incontables por un argumento de diagonalización. Ya teníamos una prueba de que\(\Bin^\omega\), el conjunto de todas las secuencias infinitas de\(0\)\(1\) s y s, es incontable. Aquí hay otra forma en la que podemos demostrar que\(\Pow{\PosInt}\) es incontable: Mostrar que si\(\Pow{\PosInt}\) es contable entonces también\(\Bin^\omega\) es contable. Ya que sabemos que no\(\Bin^\omega\) es contable, tampoco\(\Pow{\PosInt}\) puede serlo. Esto se llama reducir un problema a otro, en este caso, reducimos el problema de enumerar\(\Bin^\omega\) al problema de enumerar\(\Pow{\PosInt}\). Una solución a lo último, una enumeración de\(\Pow{\PosInt}\), daría una solución a la anterior, una enumeración de\(\Bin^\omega\).

    ¿Cómo reducimos el problema de enumerar un conjunto\(B\) al de enumerar un conjunto\(A\)? Proporcionamos una manera de convertir una enumeración de\(A\) en una enumeración de\(B\). La forma más fácil de hacerlo es definir una función suryectiva\(f\colon A \to B\). Si\(x_1\),\(x_2\),... enumera\(A\), entonces\(f(x_1)\),\(f(x_2)\),... enumeraría\(B\). En nuestro caso, estamos buscando una función suryectiva\(f\colon \Pow{\PosInt} \to \Bin^\omega\).

    Problema\(\PageIndex{1}\)

    Demostrar que si hay una función inyectora\(g\colon B \to A\), y\(B\) es incontable, entonces también lo es\(A\). Haz esto mostrando cómo puedes usar\(g\) para convertir una enumeración de\(A\) en una de\(B\).

    Prueba de Teorema 4.6.2 por reducción.

    Supongamos que\(\Pow{\PosInt}\) fueran contables, y así que hay una enumeración de la misma,\(Z_{1}\),\(Z_{2}\),\(Z_{3}\),...

    Definir la función\(f \colon \Pow{\PosInt} \to \Bin^\omega\) dejando\(f(Z)\) ser la secuencia\(s_{k}\) tal que\(s_{k}(n) = 1\) iff\(n \in Z\), y de\(s_k(n) = 0\) otra manera. Esto define claramente una función, ya que cada vez que\(Z \subseteq \PosInt\)\(n \in \PosInt\) cualquiera es un elemento de\(Z\) o no lo es. Por ejemplo, el conjunto\(2\PosInt = \{2, 4, 6, \dots\}\) de números pares positivos se mapea a la secuencia\(010101\dots\), el conjunto vacío obtiene mapeado a\(0000\dots\) y el conjunto\(\PosInt\) en sí mismo a\(1111\dots\).

    También es suryectiva: Cada secuencia de\(0\) s y\(1\) s corresponde a algún conjunto de enteros positivos, es decir, el que tiene como miembros esos enteros correspondientes a los lugares donde la secuencia tiene\(1\) s. Más precisamente, supongamos \(s \in \Bin^\omega\). Definir\(Z \subseteq \PosInt\) por:\[Z = \Setabs{n \in \PosInt}{s(n) = 1}\nonumber\] Entonces\(f(Z) = s\), como se puede verificar consultando la definición de\(f\).

    Ahora considera la lista\[f(Z_1), f(Z_2), f(Z_3), \dots\nonumber\] Ya que\(f\) es suryectiva, cada miembro de\(\Bin^\omega\) debe aparecer como un valor de\(f\) para algún argumento, y así debe aparecer en la lista. Por lo tanto, esta lista debe enumerar todos\(\Bin^\omega\).

    Entonces, si\(\Pow{\PosInt}\) fueran contables,\(\Bin^\omega\) serían contables. Pero\(\Bin^\omega\) es incontable (Teorema 4.6.1). De ahí\(\Pow{\PosInt}\) que sea incontable. ◻

    Es fácil confundirse sobre la dirección en la que va la reducción. Por ejemplo, una función suryectiva\(g \colon \Bin^\omega \to B\) no establece que\(B\) sea incontable. (Considera\(g \colon \Bin^\omega \to \Bin\) definida por\(g(s) = s(1)\), la función que mapea una secuencia de\(0\)'s y\(1\)'s a su primer elemento. Es suryectiva, porque algunas secuencias empiezan con\(0\) y algunas empiezan con\(1\). Pero\(\Bin\) es finito.) Obsérvese también que la función\(f\) debe ser suryectiva, o de lo contrario el argumento no pasa por:\(f(x_1)\)\(f(x_2)\),,... entonces no se garantizaría que incluyera todos los elementos de\(B\). Por ejemplo,\[h(n) = \underbrace{000\dots0}_{\text{$n$ $0$'s}}\nonumber\] define una función\(h\colon \PosInt \to \Bin^\omega\), pero\(\PosInt\) es contable.

    Problema\(\PageIndex{2}\)

    Mostrar que el conjunto de todos los conjuntos de pares de enteros positivos es incontable por un argumento de reducción.

    Problema\(\PageIndex{3}\)

    Demostrar que\(\Nat^\omega\), el conjunto de secuencias infinitas de números naturales, es incontable por un argumento de reducción.

    Problema\(\PageIndex{4}\)

    Dejar\(P\) ser el conjunto de funciones desde el conjunto de enteros positivos hasta el conjunto\(\{0\}\), y dejar\(Q\) ser el conjunto de funciones parciales desde el conjunto de enteros positivos hasta el conjunto\(\{0\}\). Demostrar que\(P\) es contable y no lo\(Q\) es. (Pista: reducir el problema de enumerar\(\Bin^\omega\) a enumerar\(Q\)).

    Problema\(\PageIndex{5}\)

    \(S\)Sea el conjunto de todas las funciones suryectivas desde el conjunto de enteros positivos hasta el conjunto {0,1}, es decir,\(S\) consiste en todas las suryectivas\(f\colon \PosInt \to \Bin\). Demostrar que\(S\) es incontable.

    Problema\(\PageIndex{6}\)

    Demostrar que el conjunto\(\Real\) de todos los números reales es incontable.


    This page titled 4.7: Reducción is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. (Open Logic Project) .