Exercícios sobre Funções Injetoras e Monotonas

EXERCICIOS Exercicio 1 3 pontos Suponha que X é um conjunto e f X X uma fungao injetora que nao sobrejetora Verifique as seguintes condicgées 1 Mostre que existe z X tal que fz Fz 2 Fizado z X tal que fz 4 z Mostre que ffz 4 fz 3 Fizado z X tal que fz 4 z mostre que para todo n N temos f1z 4 fz 4 Seja z X dizemos que z capturado por um fciclo se existe k N tal que fz z Mostre que existe z N que nao é capturado por um f ciclo 5 Fize z X que nao fixado por um fciclo Mostre que para todo n N temos que fz f 2 k n 6 Mostre usando o teorema da recursdo que se z nao caputrado por um fciclo entao existe uma bijecao entre fz n N e N Mostre que a bijegao existe usando os axiomas da teoria dos conjuntos Exercicio 2 3 pontos Seja A um conjunto e F PA PA uma fungao das partes de A nas partes de A Dizemos que X PA um ponto fizo de F quando FX X Dizemos que F monotona se para todo Xy PA temos X CY implica FX C FY 1 Suponha que A um conjunto e F PA PA Mostre que se F monotona entao F tem um ponto fixo Sugestao Considere TT X C A FX C X Mostre que T um ponto fixo de F 2 Use o item anterior para fazer uma demosntragao alternativa do Teorema de Berns tein Sugestao Sejam Ap C BC Ae ff Ay A uma bijegdo Defina F PA PA da seguinte forma FX A BU fX Mostre que F monotona aplique o item anterior para obter C tal que FC C use C e DAC para definir uma bijegado como na prova original 3 Mostre que T do item anterior 0 menor ponto fixo ou seja se X C Ae FX X entaoT CX Exercicio 3 3 pontos 1 Mostre que existe uma bijecdo entre o conjunto 2 o conjunto das fungdes de N em 01 e 0 conjunto 2N 0 conjunto das fungdes de N em 2N 2 Sejam A e B conjuntos Mostre que se existe uma injegdo de A em B entdo existe uma injecao de AN em BN 3 Use o teorema de Cantor para mostrar que existe uma injegado de NN em 2N 4 Use 0 teorema de CantorBernstein para mostrar que existe uma bijegdo entre NN e QN Exercicio 4 1 ponto Mostre que existe uma bijegao entre o conjunto de fungdes continuas de 01 em 01 e 0 intervalo 0 1