Pode-se definir conjunto finito não vazio como um conjunto que não é
equipotente a um subconjunto próprio (1.1.7). Um conjunto é infinito se e só se é
equipotente a algum subconjunto próprio.
1.1.8 Teorema. O conjunto  é infinito.
D. Prova-se por contradiçãoÞ
 Á g, pois, por A7, " − .
Se  fosse finito, existiria uma bijecção de 8 para .
Poderíamos então escrever  œ Ö3" ß 3# ß á ß 38 ×Þ
Por A1, teríamos: = ³ 3"  3#  á  38 − Þ
Mas, então sería 3" ß 3# ß á ß 38  = o que implicaria, por A10, = Â , contradição.
O conjunto  é equipotente a 8"  œ Ï8 , para todo 8 − Þ De facto, a
aplicação
0 À  Ä 8"  œ Ï8 œ Ö8  B À B − × tal que:
B È 0 ÐBÑ œ 8  B
é uma bijecção (provar).
Logo, os conjuntos 8"  œ Ï8 , 8 −  são infinitos.
Note-se que, para qualquer 7 − ß
# 8 œ # Ð7   78 Ñ œ # Ö7ß 7  "ß á ß 7  8×Þ
1.1.9 Teorema. O conjunto T dos números primos é infinito..
D. Prova-se por contradição.
Suponhamos que o conjunto T dos números primos é finito.
Então, como T Á g, seria T œ Ö:" ß :# ß á ß :8 ×Þ
Seja 7 ³ :" :# á :8  ". Tem-se 7 − , pelos axiomas para .
Mas, como 7  ", 7 seria divisível por algum número primo :3 − T (pelo T.
fundamental da aritmética)Þ Como um número primo divisor de 7 é necessariamente divisor de :" :# á :8 , por 1.3.3 da Parte I, :3 sería também divisor de "ß
contradiçãoÞ
1.1.10 Teorema. Para qualquer conjunto infinito E, existe uma aplicação
injectiva de  para EÞ
Nota. A cardinalidade de  é denotada pelo símbolo i! (i letra do alfabeto
hebraico que se lê "alef"). O conjunto ‘ dos números reais não tem cardinalidade
i! . Embora exista uma aplicação injectiva  ä ‘ (por 1.1.10), não existe
nenhuma aplicação bijectiva entre estes conjuntos. A cardinalidade de ‘ é
simbolizada por i" Þ
1.2 Cardinalidade da união finita de conjuntos finitos disjuntos e do
produto cartesiano finito de conjuntos finitos
Se E e F são conjuntos disjuntos tais que #E œ 7 e # F œ 8, podemos
representá-los por E œ Ö+" ß á ß +7 × e F œ Ö," ß á ß ,8 ×.
Seja 0 À 7 Ä E a bijecção tal que 0 Ð3Ñ œ +3 e seja 1 À 8 Ä F a bijecção tal
que 1Ð4Ñ œ ,3 . Obtemos uma bijecção
2 À 78 Ä E  F ,
definindo
2Ð3Ñ œ 0 Ð3Ñ, a 3 Ÿ 7;
2Ð7  4Ñ œ ,4 ß a4 Ÿ 8Þ
Temos assim a seguinte proposição:
1.2.1 Proposição. Se E e F são conjuntos finitos disjuntos, tem-se:
# ÐE † FÑ œ #E  # FÞ
Prova-se, por indução, a extensão desta proposição a um número 7 de conjuntos
finitos disjuntos.
1.2.2 Proposição. Se E" ß E# ß á ß Em é uma família finita de conjuntos finitos
disjuntos, então
# ÐE" † E# † â † Em Ñ œ #E"  # E#  â  #E7 Þ
1.2.3 Corolário. Se E" ß E# ß á ß Em é uma família finita de conjuntos finitos
disjuntos, todos com cardinalidade 8, então
# ÐE" † E# † â † Em Ñ œ 78Þ
Vamos agora ver que o produto cartesiano de um conjunto finito E por um
conjunto finito F
E ‚ F œ ÖÐ+ß ,Ñ À + − Eß , − F×
é união de uma família de conjuntos disjuntos, todos com a mesma cardinalidadeÞ
Seja E œ Ö+" ß á ß +7 × e F œ Ö," ß á ß ,8 ×. Tem-se:
E ‚ F œ ÖÐ+" ß ,3 Ñ À " Ÿ 3 Ÿ 8× † â † ÖÐ+7 ß ,3 Ñ À " Ÿ 3 Ÿ 8×
œ ÖÐ+ ß , Ñ À " Ÿ 4 Ÿ 7× † â † ÖÐ+ ß , Ñ À " Ÿ 4 Ÿ 7×Þ
4
"
4
8
Assim E ‚ F é união de 7 conjuntos disjuntos, todos com cardinalidade 8 e é
também a união de 8 conjuntos disjuntos com cardinalidade 7Þ Por 1.2.3,
obtemos que # E ‚ F œ 78Þ
1.2.4 Proposição. Se E e F são conjuntos finitos, então
# ÐE ‚ FÑ œ #E † # FÞ
Prova-se, por indução, a generalização desta proposição a uma família finita de
conjuntos finitos:
1.2.5 Proposição. Se E" ß E# ß á ß Em é uma família finita não vazia de conjuntos
finitos não vazios, então
# ÐE" ‚ E# ‚ â ‚ Em Ñ œ #E" ‚ # E# ‚ â ‚ #E7 Þ
Como caso particular temos que:
1.2.6 Corolário. Se E" ß E# ß á ß Em é uma família finita de conjuntos finitos,
todos com cardinalidade 8, então
# ÐE" ‚ E# ‚ â ‚ Em Ñ œ 87 Þ
Se E" œ E# œ â œ Em œ F , escreve-se F 7 em vez de E" ‚ E# ‚ â ‚ Em .
O conjunto das aplicações de um conjunto E num conjunto F , é denotado por
FE .
Se E œ Ö+" ß á ß +7 ×ß o conjunto F E (ou o conjunto F 7 , abreviado F 7 Ñ pode
ser identificado com o conjunto de todas as sequências de 7 elementos de F , i.e.
existe uma bijecção entre esses conjuntos. Masß o conjunto de todas as
sequências de 7 elementos de F pode ser interpretado como o conjunto de todas
as escolhas ordenadas com repetição de 7 elementos do conjunto FÞ
1.2.7 Proposição. Se E é um conjunto com 7 elementos e F é um conjunto com
8 elementos, então o conjunto F E de todas as aplicações de E em F é
equipotente ao conjunto de todas as escolhas ordenadas com repetição de
7 elementos do conjunto F e tem 87 elementos.
Em particular, sendo E œ Ö+" ß á ß +7 × e F œ Ö!ß "×, cada aplicação 0 À E Ä F
determina uma sequência Ð0 Ð+" Ñß á ß 0 Ð+7 ÑÑ constituída por de zeros e uns.
Seja cÐEÑ o conjunto de todos os subconjuntos de E.
Se a cada aplicação 0 À E œ Ö+" ß á ß +7 × Ä Ö!ß "× fazemos corresponder o
subconjunto de E Ö+3 − E À 0 Ð+3 Ñ œ "×, obtemos uma bijecção
Ä c ÐEÑ (provar).
FE ä
1.2.8 Proposição. Se # E œ 7 e # F œ #, então F E é equipotente ao conjunto
cÐEÑ de todos os subconjuntos de E. Tem-se
# cÐEÑ œ #7 Þ
1.3 Injecções como escolhas ordenadas sem repetição
Dado um conjunto F , o conjunto das escolhas ordenadas sem repetição
de 7 elementos de F pode ser identificado com o conjunto das aplicações
injectivas ou injecções de 7 em F .
Há 8 escolhas possíveis da imagem de ". Para cada uma dessas escolhas há 8  "
escolhas possíveis para a imagem de #Þ Para cada escolha da imagem de " e de #
há e 8  # escolhas possíveis da imagem de $, e assim sucessivamente.
A demonstração rigorosa faz-se por indução.
1.3.1 Proposição. O número de escolhas ordenadas sem repetição de 7
elementos de um conjunto F com 8 elementos é a cardinalidade do conjunto
das injecções 7 para F e é dado por
8 † Ð8  "Ñ † Ð8  #Ñ † â † Ð8  7  "ÑÞ
Exemplo
O número de possiveis escolhas de 11 jogadores num conjunto de 23 é
23 ‚ ## ‚ #" ‚ â ‚ "$. Este é também o número de aplicações injectivas de
qualquer conjunto com 11 elementos num conjunto com 23 elementos.
1.3.2 Corolário. O número de escolhas ordenadas sem repetição de 8 elementos
de um conjunto F com 8 elementos é igual à cardinalidade do conjunto das
bijecções de 8 para 8 e é dado por
8x ³ 8 † Ð8  "Ñ † Ð8  #Ñ † â † # † "Þ
Cada bijecção de F œ Ö," ß á ß ,8 × em F é chamada uma permutação de F
As escolhas ordenadas sem repetição de 8 elementos de um conjunto F com 8
correspondem às diferentes ordenações desses elementos.
Exemplo
Permutações de $ :
id œ Œ
"#$
"#$
"#$
, !" œ Œ
, !# œ Œ
" # $
2 1 $
2 $ "
!$ œ Œ
"#$
"#$
"#$
, !% œ Œ
, !& œ Œ


"$#
$1#
$ # "
Seja F œ 8 = Ö"ß #ß á ß 8×.
A permutação identidade, id œ Œ
" # $á8
, deixa fixos todos os elementos
" # $á8
" # $á8  "8
Uma permutação Œ
diz-se um ciclo de comprimento 8, e é
#$% á 8 " 
denotado por Ð" # $ % á 8  " 8Ñ, ou por Ð# $ % á 8  " 8 "Ñ, ou á
Uma permutação que coincide com a identidade excepto para dois elementos é
chamada transposição. A restrição de uma transposição aos dois elementos que
não ficam fixos é um ciclo de comprimento #. Se 3 e 4 são os elementos que não
ficam fixos, a transposição é denotada por Ð3 4ÑÞ
Cada transposição coincide com a sua inversa.
No exemplo dado acima, !# œ Ð" # $Ñß !% œ Ð$ # "Ñ são ciclos de comprimento
3 e são bijecções inversas uma da outra.
!" œ Ð" #Ñß !$ œ Ð# $Ñß !& œ Ð" $Ñ são transposições.