Conjuntos Enumeráveis e Não Enumeráveis

Autor

Márcio Nicolau

Data de Publicação

11 de agosto de 2025

Objetivos da Aula

  • Compreender o conceito de conjuntos enumeráveis e não-enumeráveis
  • Diferenciar entre conjuntos contáveis e não-contáveis
  • Aplicar o conceito de enumeração em problemas computacionais

Conteúdo

NotaDefinições essenciais
  • Enumerável (contável): existe bijeção com \(\mathbb{N}\), ou enumeração total (e: \(\mathbb{N} \to A\)).
  • Não-enumerável: não existe tal bijeção; cardinalidade estritamente maior que \(|\mathbb{N}|\).
  • Cardinalidades:
    • \(|\mathbb{N}| = \aleph_0\) (contável).
    • \(|(0,1)| = |\mathbb{R}| = \mathfrak{c}\) (contínuo), não-enumerável (prova por diagonalização de Cantor; ver Sipser (2012)).
  • Fatos úteis:
    • União contável de conjuntos enumeráveis é enumerável.
    • Produto cartesiano \(\mathbb{N} \times \mathbb{N}\) é enumerável (enumeração por diagonais).

1. Conjuntos Enumeráveis

  • Definição formal de conjunto enumerável
  • Exemplos de conjuntos enumeráveis:
    • Números naturais \(\mathbb{N}\)
    • Números inteiros \(\mathbb{Z}\)
    • Números racionais \(\mathbb{Q}\)
  • Técnicas de enumeração

2. Conjuntos Não-Enumeráveis

  • O conceito de não-enumerabilidade
  • O conjunto dos números reais \(\mathbb{R}\)
  • O conjunto das funções f: \(\mathbb{N} \to \{0,1\}\)

Prova por Diagonalização de Cantor (esboço)

  • Suponha, para fins de contradição, que as sequências infinitas \(x: \mathbb{N} \to \{0,1\}\) possam ser enumeradas: \(x_1, x_2, x_3, \dots\).
  • Construa a sequência \(y\) tal que \(y(i) = 1 - x_i(i)\) (inverte o i-ésimo bit da i-ésima sequência).
  • Então \(y\) difere de cada \(x_i\) no i-ésimo bit, logo \(y\) não aparece na enumeração — contradição. Portanto, o conjunto é não-enumerável (ver Sipser (2012)).

3. Cardinalidade e Comparação de Conjuntos

  • Noção de cardinalidade
  • Conjuntos equipotentes
  • O conceito de contagem em conjuntos infinitos

Diagrama: Enumeração por Diagonais em \(\mathbb{N} \times \mathbb{N}\)

graph TD
    subgraph Diagonais
    D2["s=2: (1,1)"]
    D3["s=3: (1,2),(2,1)"]
    D4["s=4: (1,3),(2,2),(3,1)"]
    D5["s=5: (1,4),(2,3),(3,2),(4,1)"]
    end

    start((Início)) --> D2 --> D3 --> D4 --> D5

    note["Ordem por soma s=n+m crescente; percorre cada diagonal listando pares (n,m)."]
    D4 -.-> note
Figura 1: Enumeração por Diagonais em \(\mathbb{N} \times \mathbb{N}\)

Prova: Produto de Enumeráveis é Enumerável (esboço)

Sejam \(A = \{a_i\}_{i\in\mathbb{N}}\) e \(B = \{b_j\}_{j\in\mathbb{N}}\) enumerações. Para enumerar \(A\times B\):

  • Considere o reticulado de índices \((i,j)\in\mathbb{N}\times\mathbb{N}\) e percorra por diagonais de soma \(s=i+j\) crescente (ver Seção 2.3.1).
  • Liste os pares \((a_i, b_j)\) na mesma ordem dos índices.

Alternativamente, use a função de pareamento de Cantor \(\pi(i,j) = \tfrac{1}{2}(i+j)(i+j+1) + j\), que é uma bijeção \(\mathbb{N}\times\mathbb{N} \to \mathbb{N}\). Assim, \(k=\pi(i,j)\) fornece uma enumeração explícita.

Exemplo: Enumerando os Números Racionais

Código Python 
from math import gcd

def racionais_positivos_unicos():
    """Gera racionais positivos em termos reduzidos (n/d) sem duplicatas,
    percorrendo diagonais de n+d = s (s = 2,3,...) em ordem crescente."""
    s = 2
    while True:
        for n in range(1, s):
            d = s - n
            if gcd(n, d) == 1:
                yield (n, d)
        s += 1

print("Primeiros 20 racionais positivos em termos reduzidos (n/d):")
gen = racionais_positivos_unicos()
for i in range(20):
    n, d = next(gen)
    print(f"{n}/{d}", end="\n" if i % 5 == 4 else " ")
Primeiros 20 racionais positivos em termos reduzidos (n/d):
1/1 1/2 2/1 1/3 3/1
1/4 2/3 3/2 4/1 1/5
5/1 1/6 2/5 3/4 4/3
5/2 6/1 1/7 3/5 5/3
Figura 2

Diagrama: Relação entre Conjuntos Numéricos

graph TD
    N[Naturais ℕ] --> Z[Inteiros ℤ]
    Z --> Q[Racionais ℚ]
    Q --> R[Reais ℝ]
    R --> C[Complexos ℂ]
    
    style N fill:#f9f,stroke:#333,stroke-width:2px
    style Z fill:#bbf,stroke:#333,stroke-width:2px
    style Q fill:#9f9,stroke:#333,stroke-width:2px
    style R fill:#f99,stroke:#333,stroke-width:2px
    style C fill:#ff9,stroke:#333,stroke-width:2px
    
    classDef enumeravel fill:#9f9,stroke:#333,stroke-width:2px
    class N,Z,Q enumeravel
    
    classDef nao_enumeravel fill:#f99,stroke:#333,stroke-width:2px
    class R,C nao_enumeravel
Figura 3: Relação entre Conjuntos Numéricos
NotaAtividade Prática
  1. Implemente uma função em Python que gere os números inteiros na seguinte ordem: \(0, 1, -1, 2, -2, 3, -3, \ldots\)
  2. Explique por que o conjunto dos números reais entre 0 e 1 é não-enumerável (veja Seção 2.2.1).
  3. Demonstre que o conjunto dos números algébricos é enumerável.
def inteiros_zigzag():
    """Gera 0, 1, -1, 2, -2, 3, -3, ..."""
    yield 0
    k = 1
    while True:
        yield k
        yield -k
        k += 1

Exercícios para Casa

  1. Mostre que a união de uma quantidade enumerável de conjuntos enumeráveis é enumerável.
  2. O produto cartesiano \(\mathbb{N} \times \mathbb{N}\) é enumerável? Justifique sua resposta (veja Seção 2.3.1 e Seção 2.3.2).
  3. O conjunto das sequências finitas de números naturais é enumerável? E o conjunto das sequências infinitas?
  1. União contável de enumeráveis: interlace/pareamento de enumerações (por diagonais) produz uma enumeração única.
  2. \(\mathbb{N}\times\mathbb{N}\) é enumerável: ordenar por diagonais de \(n{+}m\) e listar pares \((n,m)\) nessa ordem (cf. Seção 2.3.1, Seção 2.3.2).
  3. Sequências finitas de naturais: enumerável (união, sobre o comprimento, de \(\mathbb{N}^k\), cada \(\mathbb{N}^k\) é enumerável). Sequências infinitas de naturais: não-enumerável; há uma injeção de \(\{0,1\}^{\mathbb{N}}\) em \(\mathbb{N}^{\mathbb{N}}\) e \(\{0,1\}^{\mathbb{N}}\) é não-enumerável por diagonalização.

Referências Bibliográficas

SIPSER, Michael. Introdução à Teoria da Computação. 3. ed. São Paulo, Brasil: Cengage Learning, 2012.