Notas sobre conjuntos, funções e cardinalidade
(semana 1 do curso)
Roberto Imbuzeiro Oliveira∗
8 de Janeiro de 2014
1
Conjuntos e funções
Neste curso procuraremos fundamentar de forma precisa os fundamentos
mais básicos do Cálculo. Para fazer isto com todo o rigor, terı́amos que em
primeiro lugar apresentar de forma adequada toda a Teoria de Conjuntos: de
fato, todo objeto matemático que apresentarmos nestas notas será descrito
por conjuntos, de uma forma ou de outra. Não teremos tempo de seguir
esta abordagem ideal no curso, mas procuraremos esclarecer alguns pontos
relacionados nestas notas.
1.1
O que é (ou não é) conjunto
Um conjunto X é uma “entidade abstrata”sobre a qual se pode fazer perguntas do tipo “x ∈ X”? A interpretação que damos a esta pergunta é “x
pertence a X?”; se a resposta for “sim”, dizemos que x é elemento de X.
Exemplo 1 (Exemplos intuitivos) N (números naturais), Z (inteiros),
R (reais), Q (racionais), o conjunto de alunos desta turma.
No final das contas, qualquer afirmação feita a respeito de um conjunto
é na verdade a respeito dos elementos que ele contem ou não contem. Por
exemplo, dois conjuntos X e Y são iguais se todos os elementos de um são
elementos de outro. Em sı́mbolos1 :
X=Y: ∀x : x ∈ X ⇔ x ∈ Y
∗
1
IMPA, Rio de Janeiro, RJ, Brazil, 22430-040.
O sı́mbolo ∀ significa “para todo”e ⇔ significa “se e somente se”.
1
Da mesma forma, X ⊂ Y se todo elemento de X é também elemento de Y .
Em sı́mbolos:
X⊂Y: ∀x : x ∈ X ⇒ x ∈ Y.
Intuitivamente, um conjunto X representa uma coleção de elementos. Existe
uma coleção vazia, simbolizada por ∅, tal que
∀x : x 6∈ ∅.
De fato, só pode existir um conjunto vazio (exercı́cio). No entanto, há
coleções que não são conjuntos: por exemplo, não existe um conjunto cujos
elementos incluem todos os conjuntos que existem. Isto está relacionado
ao fato que, dado um conjunto X, podemos obter um subconjunto Y ⊂ X
via especificação: se P é uma propriedade que cada x ∈ X pode ou não
satisfazer, então:
Y ≡ {x ∈ X : X satisfaz P }
é subconjunto de X. De fato, neste curso todo conjunto com o qual trabalharemos será ou declarado conjunto conhecido (no caso de N) ou então
obtido de um outro conjunto via especificação e produtos cartesianos.
Os leitores interessados numa melhor compreensão da Teoria de Conjuntos podem procurar os seguintes livros:
• Keith Devlin. The Joy of Sets.
• Paul Halmos. Naı̈ve Set Theory. (Este livro é considerado um clássico.)
1.2
Funções são conjuntos
Em geral uma função entre os conjuntos A e B é simbolizada por f : A → B.
Informalmente, ela dá uma regra que associa a cada elemento a ∈ A um
elemento f (a) ∈ B. Recordamos que os conjuntos A e B são respectivamente
chamados de domı́nio e contradomı́nio de f .
Observe que as definições de domı́nio e contradomı́nio são parte da definição de f
Esta definição informal tem alguns problemas. O mais óbvio deles é que
a palavra “regra”tem de ser usada num sentido muito amplo para que ela
valha. É f (x) = x2 é uma “regra”clara que associa a cada x ∈ R o seu
quadrado, mas outras funções podem ser muito mais complicadas ou não
ter regra nenhuma 2 .
2
Esta última afirmação será esclarecida mais adiante no curso. A ideia é que existem
muito mais funções de N em {0, 1}, por exemplo, do que qualquer regra escrita seria capaz
de descrever.
2
Um livro de Teoria de Conjuntos contornaria este problema – e faria jus
à nossa afirmação de que tudo é conjunto – através da seguinte derfinição 3 .
Definição 1 Uma função com domı́nio A e contradomı́nio B é um subconjunto G ⊂ A × B com a seguinte propriedade:
∀a ∈ A ∃! b ∈ B : (a, b) ∈ G.
(1)
De que forma isto corresponde à ideia intuitiva? Veja que, por um lado,
se f e função o conjunto
Gf ≡ {(a, f (a)) : a ∈ A} (chamado de gráfico de f )
satisfaz a definição acima, pois a cada a ∈ A corresponde um único b (que é
o b = f (a)).
Por outro lado, dado G ⊂ A × B que satisfaz (1), podemos tomá-lo
como o gráfico de alguma f descrita pela seguinte “regra abstrata”: se
queremos saber quem é f (a), procuramos o único par (a, b) ∈ G contendo a
e concluı́mos b = f (a). Dito de outro modo, G é uma tabela que nos diz o
valor de f (a) para cada a ∈ A.
No final das contas, o que vimos é que o conceito intuitivo de função encontra uma expressão rigorosa dentro da Teoria de Conjuntos. Este mesmo
princı́pio se aplica a essencialmente todos os outros conceitos da Matemática.
Na maior parte do tempo trabalharemos como se o conceito intuitivo fosse
verdadeiro, retornando apenas ocasionalmente à definição formal.
Observação 1 Dada f : A → B e A0 ⊂ A, em geral definimos a restrição
de f a A0 como a função dada pela mesma regra que f , mas restrita aos
elementos de A0 . Note que, no âmbito da nossa definição, isto pode ser
expresso como:
G0 ≡ G ∩ (A0 × B) = {(a, b) ∈ G : a ∈ A0 }.
2
Conjuntos finitos e cardinalidades
Aqui nesta seção elucidamos o material no Cap 1 do “Elon pequeno”que se
refere a cardinalidades. Tomamos como fatos conceitos como a ordem de N,
a tricotomia da ordem e o fato que todo conjunto A ⊂ N que não é vazio
tem um elemento mı́nimo. Antes disto, recordamos alguns fatos.
Sejam A e B conjuntos e f : A → B uma função. Recorde que f : A → B
é:
3
∃! significa “existe um único”.
3
• injetiva se para quaisquer a, c ∈ A, “a 6= c”⇒“f (a) 6= f (c)”;
• sobrejetiva se para qualquer b ∈ B existe um a ∈ A com f (a) = b;
• bijetiva se é injetiva e sobrejetiva.
Exercı́cio 1 Prove que injetividade e sobrejetividade são preservadas pela
composição de funções.
Lembramos ainda que f ◦ g denota a composição de funções f : B → C
e g : A → B.
Dado n ∈ N, escreva [n] := {i ∈ N : i ≤ n}. Às vezes chamaremos
este conjunto de In , como nos livros do Elon (a notação do colchete vem se
firmando como padrão).
2.1
O finito e o infinito
Definição 2 (Finitude e infinitude) Dizemos que um conjunto X é finito se X é vazio ou se existem n ∈ N uma f : X → In que é injetiva (dizemos que f atesta a finitude de X). X é dito infinito quando esta função
não existe.
Observe alguns fatos simples:
• Se X é finito, qualquer Y ⊂ X é finito. De fato, se f : X → [n] atesta
a finitude de X, a restrição de f a Y atesta a finitude de Y (pois a
restrição de uma função injetiva também é injetiva).
• Se X, C são conjuntos, C é finito e existe g : X → C injetiva, então
X também é finito. De fato, se f atesta a finitude de C, f ◦ g atesta
a finitude de X.
• Bijeções preservam a finitude e a infinitude de conjuntos. Segue do
fato acima, juntamente com o fato que uma função bijetiva é injetiva
e tem inversa injetiva.
• Se X ⊂ N é limitado, então X é finito. A afirmação de que X é
limitado significa que existe p ∈ N com ∀x ∈ X : x ≤ p. Neste caso,
vemos que X ⊂ [p], portanto a f : X → [p] que leva cada x ∈ X nele
mesmo atesta a finitude de X.
4
2.2
Cardinalidade de conjuntos finitos
Definição 3 (Cardinalidade) Seja X um conjunto finito. A cardinalidade de X, denotada por |X|, é definida como |X| = 0 se X = ∅ e |X| = n se
n ∈ N é o menor natural para o qual existe uma função injetiva f : X → [n].
(Este valor existe porque o conjunto dos n ∈ N tal que existe tal injeção não
é vazio, posto que X é finito.)
A ideia intuitiva é que a cardinalidade conta o número de elementos de
um conjunto. O teorema a seguir mostra isto num caso particular.
Teorema 1 |[m]| = m para qualquer m ∈ N.
Prova: Note que a função identidade é uma injeção de [m] em [m], logo
|[m]| ≤ m.
Resta provar que não podemos ter |[m]| < m. Dito de outro modo,
queremos provar que todo número natural n ∈ N satisfaz a seguinte propriedade:
P(n): Não existe função injetiva f : [m] → [n] para qualquer
natural m > n. (Em forma contrapositiva: se f : [m] → [n] é
injetiva, m ≤ n.)
A prova desta propriedade para todo n ∈ N será por indução em n.
Base: Se n = 1, [n] = {1}. Tome m > 1. Veja que 1 ∈ [m] e portanto
1, m são dois elementos distintos de [m]. Isto implica que não pode haver
f : [m] → {1} injetiva.
Passo indutivo. Suponha n ≥ 1 é tal que vale P(n). Vamos provar que P(n + 1) também vale. Para isso fixaremos m ∈ N tal que existe
f : [m] → [n + 1] injetiva e provaremos m ≤ n + 1. Temos três casos.
Caso 1. n + 1 6∈ Imagem(f ). Neste caso f pode ser encarada como uma
função f 0 : [m] → [n]. Como P(n) vale, isto implica que m ≤ n e portanto
m ≤ n + 1.
Caso 2. f (m) = n + 1. Neste caso, a ideia é retirar m e notar que
passamos a ter uma função injetiva de [m − 1] em [n].De feito, como f é
injetiva, nenhum i < m pode ter f (i) = n + 1. Deste modo, a restrição de f
5
a [m − 1] é injetiva e tem imagem contida em [n + 1]\{n + 1} = [n]. No entanto, como [n] satisfaz P(n), isto implica que m−1 ≤ n, ou seja, m ≤ n+1.
Caso 3. Agora considere o caso em que f (a) = n+ 1 para algum a ∈ [m],
a 6= m. A ideia é trocar a e m de lugar para voltar ao caso anterior. Mais
exatamente, seja g : [m] → [m] tal que g(a) = m, g(m) = a e g(r) = r
para todos os demais elementos de [m]. Veja que esta g é uma bijeção e que
portanto a composição f ◦ g : [m] → [n] é injetiva e satisfaz f ◦ g(m) = n + 1.
Assim voltamos ao caso acima, em que já concluı́mos que m ≤ n + 1. 2
Teorema 2 Seja X um conjunto finito que não é vazio. Então qualquer
função injetiva f : X → [|X|] é uma bijeção.
Prova: Seja f : X → [|X|] injetiva. Vamos supôr (para chegar a uma
contradição) que f não é sobrejetiva. Então existe i ∈ [|X|] tal que i 6= f (x)
para qualquer x ∈ X.
Temos agora dois casos a considerar: i = |X| e i 6= |X|. Se i = |X|, vemos
que a imagem de f está contida em [|X| − 1]. Redefinindo o contradomı́nio
de f como [|X| − 1], vemos que existe g : X → [|X| − 1] (definida por
g(x) = f (x) para todo x ∈ X) que é injetiva. Isto contradiz a minimalidade
de |X|.
Suponha agora que i 6= |X|. Neste caso, como i ∈ [|X|] temos i < |X|.
Considere agora uma g : X → [|X| − 1] definida da seguinte forma:
i
se f (x) = |X|;
g(x) :=
f (x) se não.
É um exercı́cio verificar que g de fato tem contradomı́nio [|X|−1] e é injetiva.
Deste modo, também neste caso temos uma contradição: existe f : X →
[|X| − 1] injetiva, o que contradiz a minimalidade de |X|.
As contradições excluem todos os casos possı́veis, de modo que concluı́mos que a premissa – “existe f : X → [|X|] injetiva, mas não sobre” – é
falsa. Isto é exatamente o que desejávamos mostrar. 2
Exercı́cio 2 Conclua dos teoremas acima que, se X 6= ∅ é conjunto finito,
existe um único n ∈ N para o qual há uma bijeção b : X → [n].Além disto,
este n é precisamente a cardinalidade de X.
Antes de prosseguir, enunciamos um corolário importante dos resultados
acima.
6
Corolário 1 Se A e B são finitos, então há uma função injetiva f : A → B
se e somente se |A| ≤ |B|; e vice-versa.
Prova: Sabemos que há bijeções h : B → [|B|] e g : A → [|A|]. Se existe tal
f , note que h ◦ f ◦ g −1 é função injetiva de [|A|] em [|B|]. Desta forma, a
cardinalidade de [|A|] (que é |A|) é menor que a de [|B|] (que é |B|). Por
outro lado, se |A| ≤ |B|, vemos que f := h−1 ◦ g é função injetiva entre A e
B. 2
Exercı́cio 3 Mostre que |A| < |B| sempre que A ⊂ B com B finito e A 6=
B.
Exercı́cio 4 Mostre que, se A e B são finitos e A ∩ B = ∅, então |A ∪ B| =
|A| + |B|.
2.3
Conjuntos enumeráveis
Nesta seção discutiremos uma classe de conjuntos possivelmente infinitos,
mas que ainda assim podem ser “contados” de algum jeito.
Definição 4 (Enumerabilidade) Um conjunto X é dito enumerável se X
é vazio ou existe f : X → N injetiva. (Neste caso dizemos que f atesta a
enumerabilidade de X.)
Eis algumas consequências simples desta definição, que deixamos como
exercı́cios:
• Todo subconjunto de um conjunto enumerável é enumerável.
• N e todos os seus subconjuntos são enumeráveis.
Falar do que seria a “cardinalidade” de um conjunto enumerável infinito
não é tarefa muito simples. No entanto, vimos no caso finito que a cardinalidade de X é atestada por alguma bijeção b : X → [n]. Do mesmo modo, o
teorema a seguir nos diz que um conjunto enumerável infinito sempre tem
uma bijeção com N.
Teorema 3 Todo conjunto infinito enumerável tem uma bijeção com N.
Esta é uma das primeiras demonstrações realmente difı́ceis do curso,
portanto teremos bastante cuidado.
7
Prova: Seja X infinito enumerável e seja f : X → N uma função injetiva
que atesta isto. Chame de J a imagem de f . Como f é injetiva, X e J estão
em bijeção (dito de outro modo, quando restringimos o contradomı́nio de f
a sua imagem, o que obtemos é uma bijeção.). Em particular, J é infinito.
No restante da prova vamos provar que há uma bijeção entre J e N, o que
implica que há uma bijeção4 entre X e N.
Reiteramos: a partir de agora nosso objetivo é provar que
Se J ⊂ N é infinito, então há uma bijeção entre J e N.
A ideia básica é que a bijeção levará o menor elemento de J em 1, o
segundo menor elemento em 2, o terceiro menor elemento em 3 e assim por
diante. Esta é uma maneira bem natural de conceber a bijeção; mas há
outra maneira de escrevê-la que é mais conveniente.
b: J
j
→ N
.
7
→
b(j) := |[j] ∩ J|
Em palavras: b(j) conta quantos elementos de J são menores ou iguais a j.
Note que b é uma função bem definida. Afinal, [j] é sempre finito, logo
[j] ∩ J o é e podemos falar da cardinalidade deste conjunto. Além disto,
a cardinalidade é sempre > 0 porque j ∈ [j] ∩ J e portanto [j] ∩ J 6= ∅.
Concluı́mos que |[j] ∩ J| ∈ N sempre.
Mostraremos que b é uma bijeção em duas partes.
b é injetiva. Dados dois elementos distintos j, k ∈ J, temos j < k ou
k < j. Vamos supôr que vale j < k, pois o outro caso é análogo. Veja que
[j] ∪ {k} ⊂ [k]. Como k ∈ J, temos [k] ∩ J ⊂ ([j] ∪ {k}) ∩ J = ({j} ∩ J) ∪ {k}.
Em outras palavras, [k] ∩ J tem pelo menos um elemento a mais que [j] ∩ J.
O exercı́cio implica que:
b(k) = |[k] ∩ J| > |[j] ∩ J| = b(j).
b é sobrejetiva. Vamos provar por indução que qualquer n ∈ N está na imagem de B.
Base: 1 ∈ Imagem(b). De fato, como J 6= ∅, J tem um menor elemento j1 ∈ J. Veja que [j1 ] ∩ J tem j1 como único elemento elemento;
4
Você consegue ver porque isto é verdade? O ponto é que podemos compôr as bijeções
entre X e J e entre J e N!
8
caso contrário, existiria j ∈ ([j1 ] ∩ J) ∩ {j1 } = [j1 − 1] ∩ J e tal j seria
necessariamente menor que j1 (contradição). Vemos, portanto, que
b(j1 ) = |[j1 ] ∩ J| = |{j1 }| = 1.
Passo indutivo: supondo que n ∈ Imagem(b), provaremos agora que
n + 1 ∈ Imagem(b). Para isto tomamos j ∈ J com b(j) (o que existe pela
hipótese de indução). A ideia é que o “próximo elemento” de J será levado
em n + 1.
Sendo mais precisos, notamos que J 6⊂ [j], posto que J não é finito, de
modo que J\[j] não é vazio. Seja k o menor elemento de J\[j]. Afirmamos
que b(k) = n + 1. De fato, veja que:
[k] ∩ J = A ∪ B com A := ([j] ∩ J) e B := ({j + 1, . . . , k} ∩ J).
A tem b(j) = n elementos. B contem k (já que k ∈ J) e nenhum outro
elemento, pois qualquer i ∈ {j + 1, . . . , k − 1} ∩ J seria um elemento de J\[j]
menor do que k. Deduzimos que |B| = 1. Como A e B são disjuntos, o
exercı́cio 4 nos diz que
b(k) = |[k] ∩ J| = |A ∪ B| = |A| + |B| = b(j) + 1 = n + 1.
Portanto n + 1 ∈ Imagem(b), CQD.
2
Observação 2 A prova acima nos dá uma bijeção crescente entre J e N.
Uma prova seguindo o Elon nos permitiria provar que se U é qualquer conjunto infinito, existe V ⊂ U infinito e enumerável.
2.4
As partes de um conjunto e a existência de conjuntos
não enumeráveis
Nesta seção provaremos um dos fatos fundamentais a respeito de “cardinalidades de conjuntos infinitos”: que existem conjuntos não enumeráveis.
Isto quer dizer que existem conjuntos infinitos I que são maiores do que
N no seguinte sentido: existe uma injeção de N em I, mas não há injeção
de I em N. Este resultado (e a técnica de demonstração a seguir) foram
contribuições seminais de Georg Cantor aos Fundamentos da Matemárica
A existência de conjuntos não enumeráveis segue de um resultado distinto
que apresentamos a seguir. Recorde que, dado um conjunto X, podemos definir um conjunto cujos elementos são os subconjuntos de X. Este conjunto
é chamado de conjunto das partes de X e denotado por P(X). Em sı́mbolos,
P(X) := {A conjunto : A ⊂ X}.
9
Exercı́cio 5 Prove que P(X) é finito se e somente se X é finito.
Teorema 4 Para qualquer conjunto X, não pode existir uma função sobrejetiva de X em P(X).
Em particular, isto implica que P(N) não está em bijeção com N. Como
P(N) é infinito (pelo exercı́cio), o Teorema 3 implica que ele não é enumerável.
Prova: [do Teorema 4] A ideia desta prova é o chamado “truque diagonal”de
Cantor. Na verdade várias ideias relacionadas recebem este mesmo nome;
entre os muitos pontos em comum está o espanto que elas causam em quem
nunca as viu. Digo sem exagero que a ideia da demonstração abaixo é algo
que você deverá levar pelo resto da vida em algum canto da mente. Para
enfatizar isto, vamos primeiro apresentar a prova “a jato” e depois refletir
um pouco sobre ela, para entender por que ela faz algum sentido.
A prova. Dada uma função F : X → P(X), vamos provar que ela não é
sobrejetiva mostrando que existe A ∈ P(X) (isto é, um subconjunto de X)
diferente dos conjuntos F (x) para x ∈ X. De fato, A é definido da seguinte
maneira:
A := {x ∈ X : x 6∈ F (x)}.
Isto faz sentido porque, para cada x, F (x) é um subconjunto de X. Notamos ainda que qualquer x ∈ X pertence a um (e apenas um) dos conjuntos A, F (x). Portanto A 6= F (x) para todo x ∈ X e deduzimos que
A 6∈ Imagem(F ).
Refletindo sobre a prova. De que forma podemos construir um A que não
está na imagem de F ? Precisamos que, para cada x ∈ X, exista um y ∈ X
tal que y ∈ A e y 6∈ F (x) ou vice-versa. Afinal, dois conjuntos são diferentes
se e somente se há algum elemento que só está em algum deles.
A ideia de Cantor foi fazer a escolha mais simples para y, que é y = x.
Esta decisão não é nada óbvia, mas, uma vez tomada, ela nos dá a saı́da.
Se queremos que x esteja em exatamente um dos dois conjuntos
A, F (x), devemos definir A de modo que x ∈ A ⇔ x 6∈ F (x).
É exatamente desta forma que definimos A na nossa prova.
10
2