Princípios de Indução e Cardinalidade

Indução Princípios de Indução Seja x x A x 1 A 0 A A W A W Se Então x 0 y xy A x A x W σ Σ x A x σ A e Princípio 3 Princípio 2 Princípio 1 Função definida por Indução νxσ n νx σ νε 0 ν Wn ℕ Exemplo ν123 em Σ4 ν123 4 ν12 3 ν12 4 ν1 2 ν1 4 νε 1 4 0 1 1 ν123 4 4 ν1 2 3 ν123 4 4 1 2 3 ν123 42 1 41 2 40 3 ν123 4 6 3 27 Operações com Funções f f f g g f f g Composição f X Y g f X Z x zx y f y z g para algum y Y g fx z g fx fx x f g g f g f A composição é fechada nas funções funções totais e funções injetivas g Y Z Se e Combinação f Wr Ws f g Wrt Wsu gy fx x f g y x y fx gy f g Se g Wt Wu e f gx y fx gy f g Operação f g f g Wr Wst gx fx x f g fx gx f g x x f Wr Ws Se g Wr Wt e f g x fx gx Exponenciação f Wr Wr y vezes f x0 x f x y f yx f x y f f fx f Se f Wr1 Wr f x y 1 f f x y Definição por indução f x0 x x f f yx y x y x y f Repetição fx1 x pois f 0x y x y f Wr1 Wr1 fx y x f kx y x 1x Wr Se não existir k é indefinida fx y Em outras palavras é repetidamente aplicada até que o último argumento seja 1 f Se Seja k o menor valor para f Wr1 Wr f x y x y 1 f x y não sim x y f Repetição Exemplo gy f0y 1 y 3 se y é múltiplo de 3 caso contrário f07 f14 f21 2 fx y x 1y 3 gy f05 f12 f20 f30 f40 g6 g4 f Todo infinito é igual Grande Hotel Hilbert Infinitos Quartos Lotado Infinitas pessoas 1 2 3 4 5 6 David Hilbert Matemático Inglês Grande Hotel Hilbert Infinitos Quartos Lotado Infinitas pessoas Infinitos Novos Hóspedes 1 2 3 4 5 6 Cardinalidade A a2 b2 b1 a3 a1 B b3 bijeção h A B cdA cdB Cardinalidade A a2 b2 b1 a3 a1 B b3 injeção h A B cdA cdB b4 O que é cardinalidade A cardinalidade de um conjunto é a medida de seu tamanho Para um conjunto finito é o número de elementos A a1 ak cdA k E para o conjunto infinito cdℕ ℵ0 Conjuntos que tem bijeção com possuem cardinalidade ℕ ℵ0 Cardinalidade Exemplo cdE cdℕ E ℕ E Conjunto de numeros pares hx 2x h ℕ E Logo um conjunto e um de seus subconjuntos podem ter mesma cardinalidade isso acontece apenas com conjuntos infinitos ℕ 2 4 2 3 1 E 6 Conjuntos contáveis Conjuntos finitos ou com cardinalidade são contáveis ℵ0 a0 a1 a2 e hai i ℕ é contável e infinito se e somente se ele pode ser escrito como uma sequência A Enumeração Bijeção Propriedades A cda1 ak cdb1 bj k j cdA cdB cdB cdA cdA cdB cdA ℵ0 A é finito cdA ℵ0 é contável Exercício 1 ℤ é contável ℕ 1 1 0 1 0 ℤ 2 2 3 2 4 cdℕ cdℤ ℵ0 ℕ ℤ Exercício 2 é contável A x yx y ℕ 00 01 02 10 11 12 20 21 22 cdA cdℕ ℵ0 Exercício 3 ℚ é contável hpq p q cdℕ cdℤ cdℚ ℵ0 ℕ ℤ ℚ Cardinalidade ℵ0 cdE cdℕ cdℤ cdA cdℚ ℵ0 A x yx y ℕ E Conjunto de numeros pares Exercício 4 O conjunto de palavras de um alfabeto é contável W Σ ν Σ ℕ cdW cdℕ ℵ0 Exercício 5 O conjunto de programas escritos em qualquer linguagem de programação é contável SIM Pois para qualquer linguagem existe um alfabeto finito Σ onde cada programa está em Σ O conjunto de todos os programas possíveis é infinito pois os programas podem ter qualquer tamanho Exercício 6 A f f é função total f ℕ ℕ é contável f0 f00 f01 f02 f03 f1 f10 f11 f12 f13 f2 f20 f21 f22 f23 f3 f30 f31 f32 f33 x f difere de fx na entrada x fx fxx 1x f fi A Georg Cantor Diagonal de Cantor cdA ℵ0 Conjuntos Incontáveis cdA ℵ₀