Teoria dos conjuntos

Os conjuntos são a base da forma de representação de enumerações de elementos em matemática discreta. Por definição um conjunto é:

uma estrutura que agrupa objetos e constitui uma base para construir estruturas mais complexas.

Em outras palavras, um conjunto é uma coleção de elementos, ou uma lista de elementos.

Segue uma definição mais formal:

Um conjunto é uma coleção de zero ou mais objetos distintos, chamados elementos do conjunto, os quais não possuem qualquer ordem associada.

O fato de não haver uma ordem associada não significa que os elementos não possam estar ordenados, num dado contexto, conforme algum critério. Apenas indica que, no geral, isso não é obrigatório.

Há três formas de representar conjuntos: notação por extensão e notação por compreensão.

Notação por extensão é quando todos os elementos do conjunto estão enumerados, representados entre chaves e separados por vírgula. Exemplo:

$\mbox{Vogais} = \{a, e, i, o, u\}$.

Entende-se que se um conjunto pode ser representado por extensão, então ele é finito. Caso contrário, é infinito.

Notação por compreensão: quando é usada uma representação por propriedades. Os exemplos usam uma pequena diferença de notação, mas representam a mesma coisa:

• $\mbox{Pares} = \{ n \mid n \mbox{ é um número par}\}$
• $\mbox{Pares} = \{ n : n \mbox{ é um número par}\}$

Este conjunto é interpretado como: o conjunto de todos os elementos $n$ tal que $n$ é um número par. A forma geral de representar um conjunto por propriedades é:

$X = \{x : p(x)\}$

Isso quer dizer que $x$ é um elemento de $X$ se a propriedade $p(x)$ for verdadeira.

A notação por propriedades é uma boa forma de representar conjuntos infinitos.

Há ainda uma outra forma aceitável de representar conjuntos usando uma representação semelhante à de por extensão. Exemplos:

• $\mbox{Digitos} = \{0, 1, 2, ..., 9\}$
• $\mbox{Pares} = \{0, 2, 4, 6, ...\}$

Embora haja elementos ausentes, substituídos por reticências ($...$) é completamente aceitável e entendível o que se quer informar com a descrição do conjunto.

A seguir, revemos conceitos de algumas relações entre e com conjuntos ou elementos.

Pertinência

Se um elemento $a$ pertence ao conjunto $A$ isso é representado como: $a \in A$. Caso contrário, se $a$ não pertence a $A$, então representa-se como: $a \not\in A$.

Exemplos: Pertence, não pertence:

• Quanto ao conjunto $\mbox{Vogais} = \{a, e, i, o, u\}$:
  • $a \in \mbox{Vogais}$
  • $h \not\in \mbox{Vogais}$
• Quanto ao conjunto $B = \{x : x \mbox{ é brasileiro}\}$:
  • $\mbox{Pele} \in B$
  • $\mbox{Bill Gates} \not\in B$

Conjuntos importantes

O conjunto vazio é um conjunto sem elementos, representado como $\{\}$ ou $\emptyset$. Exemplos:

• o conjunto de todos os brasileiros com mais de 300 anos;
• o conjunto dos números que são, simultaneamente, ímpares e pares.

O conjunto unitário é um conjunto constituído por um único elemento. Exemplos:

• o conjunto constituído pelo jogador de futebol Pelé;
• o conjunto de todos os números que são, simultaneamente, pares e primos, ou seja: $P = \{2\}$;
• um conjunto unitário cujo elemento é irrelevante: $1 = \{*\}$.

O conjunto universo, normalmente denotado por $U$, contém todos os conjuntos considerados em um dado contexto. Por isso, não é fixo (pois depende do contexto).

Outros conjuntos importantes:

• $N$: o conjunto dos números naturais (inteiros positivos e o zero)
• $Z$: o conjunto dos números inteiros (inteiros negativos, positivos e o zero)
• $Q$: o conjunto dos números racionais (os que podem ser representados na forma de fração)
• $I$: o conjunto dos números irracionais
• $R$: o conjunto dos números reais

Alfabetos, palavras e linguagens

Em computação, e mais especificamente em linguagens de programação, um conceito importante é o que define o conjunto de elementos ou termos-chave da linguagem.

Um alfabeto é:

um conjunto finito cujos elementos são denominados símbolos ou caracteres.

Uma palavra (cadeia de caracteres ou sentença) sobre um alfabeto é:

uma sequência finita de símbolos justapostos.

Uma linguagem [formal] é

um conjunto de palavras sobre um alfabeto.

Exemplos: alfabeto, palavra

• Os conjuntos $\emptyset$ e $\{a, b, c\}$ são alfabetos
• O conjunto $N$ não é um alfabeto
• $\epsilon$ é uma palavra vazia
• $\Sigma$ é geralmente usada para representar um alfabeto
• $\Sigma^*$ é o conjunto de todas as palavras possíveis sobre o alfabeto $\Sigma$
• $\epsilon$ é uma palavra do alfabeto $\emptyset$
• $\{a, b\}^* = \{\epsilon, a, b, aa, ab, ba, bb, aaa, ...\}$

Continência, subconjunto e igualdade de conjuntos

A continência permite introduzir os conceitos de subconjunto e igualdade de conjunto.

Se todos os elementos de um conjunto $A$ também são elementos de um conjunto $B$, então $A$ está contido em $B$, o que é representado por: $A \subseteq B$. Isso também é lido como $A$ é subconjunto de $B$.

Se $A \subseteq B$, mas há $b \in B$ tal que $b \not\in A$, então pode-se dizer que $A$ está contido propriamente em $B$, ou que $A$ é subconjunto próprio de $B$. Isso é denotado por: $A \subset B$.

A negação de subconjunto e subconjunto próprio é, respectivamente:

• $A \not\subseteq B$ e
• $A \not\subset B$

Exemplos: continência, subconjunto

• $\{a, b\} \subseteq \{b, a\}$
• $\{a, b\} \subset \{a, b, c\}$, e $\{a, b\} \subseteq \{a, b, c\}$

Se os elementos de $A$ também são elementos de $B$ e vice-versa, então $A = B$. Formalmente, uma condição para $A = B$ é que $A \subseteq B$ e $B \subseteq A$.

Exemplo:

• $\{1, 2, 3\} = \{3, 3, 3, 2, 2, 1\}$

É importante notar que pertinência ($\in$) é usado entre elementos e conjuntos, enquanto continência ($\subset$ e $\subseteq$) é usada entre conjuntos.

Por definição, um conjunto qualquer é subconjunto de si mesmo, e $\emptyset$ é subconjunto de qualquer conjunto.

Exemplo:

• Seja $A = \{1, 2\}$ então os subconjuntos de $A$ são: $\emptyset$, $\{1\}$, $\{2\}$ e $\{1, 2\}$.