[MCTB019-17] §5 — Teoria intuitiva de conjuntos

A teoria dos conjuntos é uma linguagem adequada para descrever e explicar as estruturas matemáticas; de fato é o fundamento dominante de toda a matemática; a ideia é que tudo pode ser descrito em termos de conjuntos. É possível desenvolver a teoria de conjuntos de maneira axiomática em lógica de primeira ordem, como foi feito por Ernest Zermelo e Abraham Fraenkel. A teoria de conjuntos de Zermelo–Fraenkel (ZF) é um dos vários sistemas axiomáticos propostos no início do século 20 para formular uma teoria de conjuntos livre de paradoxos como o. Acrescentando aos axiomas de ZF o historicamente controverso axioma da escolha, a teoria é chamada de Teoria ZFC dos conjuntos e é o tratamento axiomático mais comum da teoria dos conjuntos na matemática.

5.1. Abordagem intuitiva

Conjunto é informalmente entendido como uma coleção de entidades, essas entidades são chamadas de elementos ou membros do conjunto e eles mesmos podem ser conjuntos. Um elemento ${x}$ pertence se ${x}$ é um elemento de ${A}$ o que é denotado por

$\displaystyle x\in A$

e escrevemos a negação como ${x\not\in A}$ .

Essa descrição de conjunto é circular pois usa o termo coleção que é sinônimo de conjunto. Não definimos conjunto e assumimos que todo têm alguma noção, mesmo que possivelmente errada, da concepção de conjuntos.

Convencionamos usar letras maiúsculas para conjuntos e minúsculas para elementos. Assim, um conjunto representado por uma letra minúscula deve ser entendido como um elemento de algum conjunto.

Igualdade de conjuntos

Dois conjuntos são iguais se, e somente se, têm os mesmos elementos.

Ou seja, a única propriedade distintiva de um conjunto é sua lista de membros. Essa sentença é um axioma da teoria axiomática de conjuntos (o Axioma da Extensionalidade).

Conjunto vazio

Há um (único) conjunto sem elementos, denotado por ${\emptyset}$ e chamado de conjunto vazio.

Especificação de conjuntos

Da igualdade de conjuntos podemos inferir que especificar todos os elementos de um conjunto é suficiente para defini-lo, podemos fazer isso de diversas formas.

Se um conjunto tem poucos elementos, podemos listá-los entre chaves “{ }” separados por vírgulas. Por exemplo, o conjunto dos algarismos primos é formado pelos números inteiros 2, 3, 5 e 7 e escrevemos ${\{2, 3, 5, 7\}}$ . O conjunto dos algarismos indo-arábicos é ${\{0,1,2,3,4,5,6,7,8,9\}}$ .

Quando os conjuntos têm muitos elementos não é viável escrever todos seus elementos e uma solução comum, mas que só usamos quando o contexto não dá margem a ambiguidade sobre seu significado, é o uso de reticências ( ${\dots}$ ). Por exemplo, o conjunto dos naturais menores que ${2.017}$ é descrito por ${\{0,1,\dots, 2.016\}}$ ; o conjunto das letras do alfabeto ${\{a,b,c,\dots,z\}}$ ; o conjunto dos naturais pares ${\{0, 2, 4, 6, \dots\}}$ . No geral é preciso muito cuidado e a recomendação é que essa solução deve ser evitada pois, por exemplo, o que é o conjunto ${\{3,5,7,\dots\}}$ ?

Exercício 20 Encontre duas respostas factíveis para a pergunta acima.

Além de listar os elementos de um conjunto explicitamente, também podemos definir conjunto por especificação (também chamado de compreensão), onde damos uma regra de como gerar todos os seus elementos. Podemos especificar um conjunto através de uma ou mais propriedade de seus elementos e, nesse caso, usamos a notação como

$\displaystyle A=\{ x : P(x) \}$

em que ${P}$ é um predicado (fórmula da lógica de 1ª ordem). Assim, ${a\in A}$ se, e só se, ${P(a)}$ é verdadeiro. Por exemplo, ${\{ x\in{\mathbb R} : x^2\leq 2\} = [-\sqrt{2},\sqrt{2}]}$ . Por exemplo, o conjunto dos números primos é

$\displaystyle \Big\{ x : x\in{\mathbb N} \land x>1 \land \forall y\in{\mathbb N},\forall z\in {\mathbb N} ( yz = x \rightarrow y = 1 \lor z = 1)\Big\}$

Observamos que ${\{2, 3, 5, 7\}}$ pode ser especificado como

$\displaystyle \{ x : x=2 \lor x=3\lor x=5 \lor x=7\}.$

Observamos também que os elementos de um conjunto podem, eles mesmos, serem conjuntos

$\displaystyle X=\Big\{\{a\},\{b\},\{c\} \Big\}$

Observamos, ainda, que

$\displaystyle \begin{array}{rcl} \{1,1,1\} &=& \{1\} \\ \{1,2,1,1\} &=& \{1,2\} \\ \{1,2,3\} &=& \{1,3,2\}\\ &=& \{2,3,1\}\\ &=& \{2,1,3\}\\ &=&\dots \end{array}$

são consequências do princípio de extensionalidade (igualdade de conjuntos).

Paradoxo de Russel

O que é o conjunto

$\displaystyle S=\{x : x\not\in x\}?$

Inclusão de conjuntos

O conjunto ${A}$ é subconjunto de um conjunto ${B}$ , fato denotado por ${ A\subseteq B}$ , se todo elemento de ${A}$ pertence a ${B}$ , ou seja,

$\displaystyle \forall x(x\in A \Rightarrow x\in B)$

isto é ${x\in A \rightarrow x\in B}$ é uma tautologia para todo ${x}$ .

Se ${A}$ não é subconjunto de ${B}$ denotamos ${ A\not\subseteq B}$ ,

$\displaystyle \begin{array}{rcl} A\not\subseteq B &\Leftrightarrow& \text{n\~ao}\left( \forall x (x\in A \Rightarrow x\in B)\right) \\ &\Leftrightarrow& \exists x, ~\text{n\~ao} (x\in A \Rightarrow x\in B) \\ &\Leftrightarrow& \exists x (x\in A \text{ e } x\not\in B) \end{array}$

Observemos que

$\displaystyle A = B \Leftrightarrow A\subseteq B \textrm{ e } B\subseteq A. \ \ \ \ \ (26)$

e, assim, ${ A \neq B \Leftrightarrow A\not\subseteq B \textrm{ ou } B\not\subseteq A.}$

Teorema 31 Para qualquer conjunto ${A}$ , ${\emptyset \subseteq A}$ .

Demonstração: A implicação ${x\in \emptyset \rightarrow x\in A}$ é tautologia para todo ${x}$ pois ${x\in\emptyset}$ é falso. $\Box$

Usaremos ${A \subsetneqq B}$ para expressar ${A \subset B}$ e ${ A \neq B}$ .

5.7. Provando proposições de conjuntos

Há essencialmente três coisas provamos sobre conjuntos:

Dados ${x}$ e ${S}$ , prove que ${x\in S}$ . Isto requer olhar a definição de ${S}$ para ver se ${x}$ satisfaz as propriedades que os elementos de ${S}$ satisfazem.
Dados ${A}$ e ${B}$ , prove que ${A\subseteq B}$ . Temos que mostrar que todo ${x}$ em ${A}$ também está em ${B}$ . Assim, uma demonstração considera um elemento arbitrário ${x}$ em ${A}$ e mostra que ele também deve ser um elemento de ${B}$ . Isto implicará usar as propriedades que definem ${A}$ para mostrar que ${x}$ satisfaz a definição de ${B}$ .
Dados ${A}$ e ${B}$ , prove que ${A=B}$ . Usualmente, fazemos isso mostrando ${A\subseteq B}$ 4 ${B\subseteq A}$ separadamente.

5.8. Operações sobre conjuntos

As operações sobre conjuntos definem novos conjuntos. A seguir descrevemos as operações mais usuais e suas propriedades.

União: ${ A \cup B}$ denota a união dos conjuntos ${A}$ e ${B}$ que é o conjunto dos elementos que pertencem a ${A}$ ou a ${ B}$

$\displaystyle A \cup B = \{ x : x\in A \text{ ou } x\in B \} \ \ \ \ \ (27)$

Intersecção: ${ A \cap B}$ denota a intersecção dos conjuntos ${A}$ e ${B}$ que é o conjunto dos elementos que pertencem a ${A}$ e a ${B}$

$\displaystyle A \cap B = \{ x : x\in A \text{ e } x\in B \} \ \ \ \ \ (28)$

${A}$ e ${B}$ são disjuntos se ${A\cap B=\emptyset}$ .

Exercício 21 Para quaisquer conjuntos ${A}$ e ${B}$

$\displaystyle A\cap B \subset A \subset A\cup B.$

Diferença: ${ A \setminus B}$ denota o conjunto dos elementos pertencem a ${A}$ e não a ${B}$

$\displaystyle A \setminus B = \{ x : x\in A \text{ e } x\not\in B \}. \ \ \ \ \ (29)$

Diferença simétrica: ${A \bigtriangleup B}$ denota o conjunto dos elementos que pertencem exclusivamente a ${A}$ ou a ${B}$ , não a ambos

$\displaystyle A \bigtriangleup B = \{ x : x\in A \cup B \text{ e } x\not\in A\cap B\}. \ \ \ \ \ (30)$

Propriedades das operações em conjuntos

Fica como exercício a verificação das seguintes propriedades.

Leis de identidade
$\displaystyle \begin{array}{rcl} A \cap (C\setminus A) &=& \emptyset \\ A \cup \emptyset &=& A\\ A \cap \emptyset &=& \emptyset \end{array}$
Leis de idempotência
$\displaystyle \begin{array}{rcl} A \cup A &=& A \\ A \cap A &=& A \end{array}$
Leis distributivas
$\displaystyle \begin{array}{rcl} A \cap (B \cup C) &=& (A \cap B) \cup (A \cap C)\\ A \cup (B \cap C) &=& (A \cup B) \cap (A \cup C) \end{array}$
Leis comutativas
$\displaystyle \begin{array}{rcl} A \cap B &=& B \cap A\\ A \cup B &=& B \cup A \end{array}$
Leis associativas
$\displaystyle \begin{array}{rcl} A \cap (B \cap C) &=& (A \cap B) \cap C\\ A \cup (B \cup C) &=& (A \cup B) \cup C \end{array}$
Leis de De Morgan
$\displaystyle \begin{array}{rcl} C\setminus ( A \cup B) &=& (C\setminus A) \cap (C\setminus B)\\ C\setminus ( A \cap B) &=& (C\setminus A) \cup (C\setminus B) \end{array}$
Leis de absorção
$\displaystyle \begin{array}{rcl} A \cup (A \cap B) &=& A \\ A \cap (A \cup B) &=& A \end{array}$

Demonstração: [Prova de uma das leis de De Morgan] Sejam ${A}$ , ${B}$ e ${C}$ conjuntos e vamos provar que ${C\setminus( A \cup B) = (C\setminus A) \cap (C\setminus B)}$ . Para provar essa igualdade, precisamos provar que ${(i)}$ ${C\setminus( A \cup B) \subseteq (C\setminus A) \cap (C\setminus B)}$ e que ${(ii)}$ ${(C\setminus A) \cap (C\setminus B) \subseteq C\setminus( A \cup B)}$ .

Para provar ${(i)}$ , seja ${x\in C\setminus( A \cup B)}$

$\displaystyle \begin{array}{rcl} x\in C\setminus( A \cup B) \Rightarrow& x\in C \text{ e } x\not\in { A \cup B} & \text{ por defini\c{c}\~ao} \\ \Rightarrow& x\in C \text{ e } \text{n\~ao}(x\in { A \cup B}) & \text{ por defini\c{c}\~ao de }\notin \\ \Rightarrow& x\in C \text{ e } \text{n\~ao}(x\in A \text{ ou }x\in B) & \text{ por defini\c{c}\~ao de }\cup \\ \Rightarrow& x\in C \text{ e } \text{n\~ao}(x\in A) \text{ e } \text{n\~ao}(x\in B) & \text{ por De Morgan (proposicional)} \\ \Rightarrow& x\in C \text{ e } x\not\in A \text{ e } x\not\in B & \text{ por defini\c{c}\~ao} \\ \Rightarrow& x\in C \text{ e } x\not\in A \text{ e } x\in C \text{ e } x\not\in B & \text{ por defini\c{c}\~ao} \\ \Rightarrow& x \in (C\setminus A )\cap (C\setminus B) & \text{ por defini\c{c}\~ao de }\cap \end{array}$

Para provar ${(ii)}$ basta notar que a recíproca de todas as implicações no argumento acima são verdadeiras.

Das duas inclusões segue a igualdade. $\Box$

Complementos

Seja ${A}$ um conjunto. O equivalente em teoria de conjuntos da negação lógica é ${\{x : x\not\in A\}}$ , que é conhecido como o complemento de A. Se permitimos complementos, estamos necessariamente trabalhando dentro de um Universo, uma vez que o complemento do conjunto vazio deve conter todos os objetos possíveis.

Essa abordagem é possível quando trabalhamos dentro de um contexto onde o universo está entendido, pro exemplo, os Inteiros formam o universo da Teoria Elementar de Números e os Reais formam o universo da Análise na reta. Mas, nós corremos o risco de se quisermos trabalhar com diferentes classes de objetos ao mesmo tempo. Contudo, um universo na Teoria dos Conjuntos é muito maior do que qualquer coisa que possamos usar e, mais que isso, é consequência dos axiomas que tal construção

não é conjunto

fazendo complementos não muito útil. A solução usual é usarmos a diferença de conjuntos com complementos relativos, como no enunciado das Leis de De Morgan acima.

Exercício 22 Seja ${R}$ um conjunto de conjuntos. Denote por ${\bigcup R}$ a união dos elementos de ${R}$ , isto é, se ${A=\{a,b,c,\}}$ , por exemplo, então ${\bigcup A = a \cup b\cup c}$ .

Tome ${R= \bigg\{ \Big\{\{1\},\{1,2\} \Big\}, \Big\{ \{1\},\{1,3\} \Big\}, \Big\{ \{2\},\{2,3\} \Big\} \bigg\}}$

Escreva os conjuntos ${\bigcup R}$ e ${\bigcup\bigcup R}$ .

5.10. Conjunto das partes

${2^A}$ denota o conjunto formado por todos os subconjuntos de ${A}$ , isto é,

$\displaystyle B\in 2^A \Leftrightarrow B\subseteq A \ \ \ \ \ (31)$

conjunto das partes de ${A}$ .

Algumas referências usam ${{\raisebox{.15\baselineskip}{\Large\ensuremath{\wp}}}(A)}$ ou ${\mathcal P(A)}$ . Aqui usaremos ${2^A}$ e ${{\raisebox{.15\baselineskip}{\Large\ensuremath{\wp}}}(A)}$ conforme a conveniência.

Exercício 23 Descreva o conjunto das partes do conjunto vazio. Descreva o conjunto das partes do conjunto ${\{a\}}$ .

5.11. Axiomática de ZFC

A teoria dos conjuntos utilizada na matemática é definida por uma coleção de axiomas que nos permitem construir, essencialmente a partir do zero, um universo grande o suficiente para manter todas a matemática sem contradições aparentes, evitando os paradoxos que podem surgir na teoria intuitiva dos conjuntos.

Um dos problemas com a teoria dos conjuntos ingênuos é que a especificação irrestrita de conjuntos é muito forte, levando a contradições. Na teoria axiomática conjuntos a especificação é mais restritiva. Vamos descrever os axiomas da teoria ZFC abaixo, mas na prática você só precisa que pode construir conjuntos por ${(a)}$ listando seus elementos, ${(b)}$ tomando a união de outros conjuntos, ${(c)}$ tomando o conjunto de todos os subconjuntos de um conjunto, ou ${(d)}$ usando algum predicado para selecionar elementos ou subconjuntos de alguns conjunto. Os pontos de partida para este processo são o conjunto vazio e o conjunto ${{\mathbb N}}$ de todos os números naturais. Se você não consegue construir um conjunto desses princípios as chances são de que o seu objeto não é um conjunto.

Lembremos que na teoria axiomática tudo é conjunto, não há distinção entre elementos e conjuntos. A ideia é que podemos representar qualquer entidade como conjunto.

Extensionalidade: Quaisquer dois conjuntos com os mesmos elementos são iguais.

$\displaystyle \forall a \forall b ((\forall x(x\in a \leftrightarrow x\in b))\rightarrow a=b)$

Existência: O conjunto vazio é um conjunto.

$\displaystyle \exists a\forall x(x\not\in a)$

Par: Dados conjuntos ${y}$ e ${z}$ , ${\{y, z\}}$ é um conjunto.

$\displaystyle \forall y\forall z\exists a\forall x(x\in a \leftrightarrow x=y \lor x=z)$

União: Para qualquer ${A = \{x,y,z,\dots\}}$ conjunto, ${\bigcup A = x \cup y \cup z \cup\dots}$ é conjunto.

$\displaystyle \forall z\exists a\forall x(x\in a \leftrightarrow \exists y(x\in y \land y\in z))$

Partes: Para qualquer conjunto ${A}$ , o conjunto ${{\raisebox{.15\baselineskip}{\Large\ensuremath{\wp}}}(A) = \{B : B\subset A\}}$ das partes de ${A}$ existe.

$\displaystyle \forall y\exists a \forall x(x\in a \leftrightarrow x\subseteq y)$

Especificação: Dados um conjunto ${A}$ e um predicado ${P}$ , o conjunto ${\{x\in A: P(x)\}}$ existe.

$\displaystyle \forall y\exists a\forall x(x\in a \leftrightarrow x\in y \land P(x))$

Infinito: Existe um conjunto que tem ${\emptyset}$ como um membro e também tem ${x\cup \{x\}}$ sempre que ${x}$ é membro (isto dá uma codificação de ${{\mathbb N}}$ , ${\emptyset}$ representa ${0}$ e ${x\cup \{x\}}$ representa ${x + 1}$ . Efetivamente, define cada número natural como o conjunto de todos números menores, e.g., ${0=\emptyset}$ , ${1=\{0\}}$ , ${2=\{0,1\}}$ , ${3 = \{0, 1, 2\} = \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}}$ .

$\displaystyle \exists a( \emptyset \in a \land \forall x(x\in a \rightarrow x\cup\{x\}\in a))$

Sem esse Axioma, só obtemos conjuntos finitos.

Fundação: Cada conjunto não vazio ${A}$ tem um elemento ${B}$ com ${A\cap B = \emptyset}$ .

$\displaystyle \forall a ( a\neq\emptyset \rightarrow \exists b(b\in a \land a\cap b=\emptyset))$

Substituição: Se ${A}$ é um conjunto e ${R (x, y)}$ é um predicado com a propriedade: ${\forall x\exists ! y R (x, y)}$ , então ${\{y : \exists xR (x, y)\}}$ é um conjunto.

$\displaystyle \forall x \exists ! y R(x,y) \rightarrow \forall b \exists a \forall z (z\in a \leftrightarrow (\exists x\in b)R(x,z))$

Escolha: Para qualquer conjunto formado de conjuntos não-vazios ${A}$ existe uma função ${f}$ que atribui para cada ${x}$ em ${A}$ algum ${f (x)\in x}$ .

Notemos a forma diferente com que se escreve um conjunto por especificação, com respeito a teoria intuitiva. Agora não temos mais o paradoxo de Russell pois se

$\displaystyle S=\{x\in A : x\not\in x\}$

então ${S\in S}$ se e só se ${S\in A}$ e ${S\not\in S}$ o que não é contraditório: se ${S\in S}$ temos ${S\not\in S}$ , uma contradição, logo ${S\not\in S}$ ; agora, se ${S\in A}$ temos uma contradição, logo ${S\not\in A}$ ; mas ${S\not\in S \land S\not\in A}$ não é contradição. Como subproduto temos o fato já mencionado de que em teoria dos conjuntos não há conjunto universo.

Teorema ${\neg \exists y\forall x( x\in y)}$ .

De fato, se existisse então tomaríamos-o por ${A}$ no argumento acima o que daria uma contradição pois ${S\not\in A}$ .

5.12. Par ordenado e Produto cartesiano

Sejam ${a\in A}$ e ${b\in B}$ . Pelo axioma do Par ${\{a,b\}}$ é conjunto e por Extensionalidade ${\{a,b\}=\{b,a\}}$ .

Por par ordenado entendemos um par de elementos de modo que a ordem em que tais elementos se apresentam importam e, usualmente, denotamos-o por ${(a,b)}$ , de modo que ${(a,b)\neq (b,a)}$ exceto quando ${a=b}$ . Também, denotamos por ${A\times B}$ o conjunto de todos os tais pares ${(a,b)}$ com ${a\in A}$ e ${b\in B}$ , isto é,

$\displaystyle A\times B = \big\{(a,b) : a\in A ~ e~b\in B\big\}$

chamado de produto cartesiano de ${A}$ com ${B}$ .

Agora, nessa seção, vamos justificar essas definições na teoria dos conjuntos.

A definição mais simples de par ordenado em termos de conjunto como foi dada pelo matemático polonês Kazimierz Kuratowski

$\displaystyle (a,b) = \big\{ \{a\}, \{a,b\} \big\}. \ \ \ \ \ (32)$

Notemos que se ${a\in A}$ e ${b\in B}$ então ${\{a\}=\{a,a\}}$ e ${\{a,b\}}$ são conjuntos pelo axioma do Par, o qual também nos dá que ${\big\{ \{a\}, \{a,b\} \big\}}$ é conjunto.

Ainda ${\{a\} \in {\raisebox{.15\baselineskip}{\Large\ensuremath{\wp}}}(A\cup B)}$ e ${\{a,b\} \in {\raisebox{.15\baselineskip}{\Large\ensuremath{\wp}}}(A\cup B)}$ , portanto ${\big\{ \{a\}, \{a,b\} \big\} \subseteq {\raisebox{.15\baselineskip}{\Large\ensuremath{\wp}}}(A\cup B)}$ , ou seja, ${\big\{ \{a\}, \{a,b\} \big\} =(a,b)\in {\raisebox{.15\baselineskip}{\Large\ensuremath{\wp}}}\big( {\raisebox{.15\baselineskip}{\Large\ensuremath{\wp}}}(A\cup B)\big)}$ , portanto, existe o conjunto cujos elementos são todos os pares ${(a,b)}$ com ${a\in A}$ e ${b\in B}$ , é o conjunto dada pela especificação

$\displaystyle \Big\{ z\in {\raisebox{.15\baselineskip}{\Large\ensuremath{\wp}}} \big( {\raisebox{.15\baselineskip}{\Large\ensuremath{\wp}}}(A\cup B) \big) : \exists x\exists y(x\in A \land y\in B\land z=(x,y)) \Big\}$

sempre que ${A}$ e ${B}$ são ambos não vazio.

Exercício Construa a partir dos axiomas a união $A\cup B$ , dados os conjuntos $A$ e $B$ .

Agora, precisamos mostrar que a definição (32) faz o que promete, isto é

Teorema 32 Se ${(a,b)=(x,y)}$ então ${a=x}$ e ${b=y}$ .

Para provar o teorema usaremos o seguinte resultado auxiliar

Lema 33 Se ${\{a,x\}=\{a,y\}}$ então ${x=y}$ .

Demonstração do lema: Exercício. $\Box$

Demonstração do teorema: A prova do teorema é por casos, em 2 deles: (1) ${a=b}$ e (2) ${a\neq b}$ .

Suponha que ${(a,b)=(x,y)}$ , isto é, ${\{\{a\},\{a,b\}\} = \{\{x\},\{x,y\}\}}$

Caso 1. Se ${a=b}$ então ${(a,b)= \{\{a\}\}}$ .

Se ${(a,b)=(x,y)}$ então ${\{\{x\},\{x,y\}\}}$ só tem um elemento e esse elemento é ${\{a\}}$ , ou seja, ${\{x\} = \{x,y\}}$ e ${\{x\} = \{a\}}$ . Portanto ${x=y}$ e ${x=a}$ , ou seja e ${\{\{a\}\} = \{\{x\},\{x,y\}\}}$ , portanto, ${\{x\} = \{x,y\}}$ e ${\{x,y\} = \{a\}}$ , logo ${a=x=y=b}$ . Caso 2. ${a\neq b}$ .

Se ${\{\{a\},\{a,b\}\} = \{\{x\},\{x,y\}\}}$ então ${\{x\}\in \{\{a\},\{a,b\}\}}$ . Se ${\{x\}\in \{\{a\},\{a,b\}\}}$ então ${\{x\} = \{a\}}$ ou ${\{x\} = \{a,b\}.}$ Se ${a\neq b}$ então ${\{x\} = \{a\}}$ .

Se ${\{\{a\},\{a,b\}\} = \{\{x\},\{x,y\}\}}$ e ${\{x\} = \{a\}}$ então ${\{x,y\} = \{a,b\}}$ , pelo lema acima. Se ${\{x\} = \{a\}}$ então ${x=a}$ .

Se ${\{x,y\} = \{a,b\}}$ e ${x=a}$ , então ${y=b}$ , pelo lema acima.

Portanto ${x=a}$ e ${y=b}$ . $\Box$

Como no produto cartesiano os pares são ordenados, temos que ${A \times B\neq B \times A}$ (exceto quando ${A = B}$ ou ${A = \emptyset}$ ou ${B = \emptyset}$ ).

Podemos definir recursivamente o produto cartesiano de mais de dois conjuntos. De um modo geral, se ${A_1,A_2,\dots,A_n}$ são conjuntos não vazios

$\displaystyle \begin{array}{rcl} \prod_{i=1}^n A_i = \begin{cases} A_1 &\text{ se }n=1\\ \left( \prod_{i=1}^{n-1} A_i \right)\times A_n &\text{ se }n>1 \end{cases} \end{array}$

Definimos ${(a_1,a_2,\dots,a_n)=(a_1)}$ se ${n=1}$ e ${(a_1,a_2,\dots,a_n)=((a_1,\dots,a_{n-1}),a_n)}$ se ${n>1}$ então

$\displaystyle \prod_{i=1}^n A_i =A_1 \times A_2 \times \cdots \times A_n= \big\{ (a_1,a_2,\dots,a_n) : a_i\in A_i (\forall i)\big\}.$

No caso em que os conjuntos ${A_1,A_2,\dots,A_n}$ são iguais a ${A}$ denotamos por ${A^n}$ o produto cartesiano ${\prod_{i=1}^n A_i .}$

Há uma definição para o produto cartesiano de uma quantidade infinita de conjuntos não vazios e provar que esse produto cartesiano resulta num conjunto não vazio depende do axioma da Escolha.

Relações e funções

Uma relação é um subconjunto de um produto cartesiano. Se ${R\subseteq A\times B}$ então ${A}$ é chamado de domínio e ${B}$ de contradomínio da relação.

Usualmente, ao invés de escrevermos ${(x,y)\in R}$ escrevemos ${x\mathop{R}y}$ , por exemplo, ${3<4}$ ao invés de ${(3,4)\in <}$ . Por exemplo, se ${A}$ é um conjunto então ${R = \{ (x,B)\in A\times 2^A : x\in B\}}$ é uma relação e ${x\mathop{R} B}$ é o mesmo que ${x\in B}$ .

O domínio e a imagem de ${R}$ são os conjuntos

$\displaystyle \begin{array}{rcl} \mathrm{dom}(R) &=& \{x\in A : \exists y\in B,~ x\mathop{R}y \}\\ \mathrm{im}(R) &=& \{y\in B : \exists x\in B,~ x\mathop{R}y \} \end{array}$

Uma relação ${R\subseteq A \times B}$ é uma função se para cada ${x\in A}$ existe um único ${y\in B}$ tal que ${(x,y)\in R}$ , nesse caso escrevemos ${R:A\rightarrow B}$ , o único ${y}$ tal que ${(x,y)\in R}$ é denotado por ${R(x)}$ é dito o valor que a função assume em ${x}$ .

O conjunto de todas as função de ${A}$ em ${B}$ é um subconjunto de ${{\raisebox{.15\baselineskip}{\Large\ensuremath{\wp}}}(A\times B)}$ denotado por ${B^A}$ .

Exercício 24 Verifique a partir dos axiomas de ZFC que ${B^A}$ é conjunto.