b'\n_START_ARTICLE_\nLema de Konig\n_START_PARAGRAPH_\nO Lema de K\xc3\xb6nig ou Lema da Infinitude de K\xc3\xb6nig \xc3\xa9 um teorema da teoria dos grafos creditado a D\xc3\xa9nes K\xc5\x91nig (1936). Ele fornece uma condi\xc3\xa7\xc3\xa3o suficiente para que um grafo infinito tenha um ramo infinitamente longo. Os aspectos desse teorema relacionados \xc3\xa0 computabilidade t\xc3\xaam sido minuciosamente estudados por pesquisadores da l\xc3\xb3gica matem\xc3\xa1tica, especialmente na teoria da computabilidade. Tal teorema tamb\xc3\xa9m desempenha papeis importantes na matem\xc3\xa1tica construtiva e na teoria da prova.\n_START_SECTION_\nAfirma\xc3\xa7\xc3\xa3o do Lema\n_START_PARAGRAPH_\nSe G \xc3\xa9 um grafo conectado com um n\xc3\xbamero infinito de n\xc3\xb3s tal que cada n\xc3\xb3 possui grau finito (isto \xc3\xa9, tem um n\xc3\xbamero de n\xc3\xb3s adjacentes finito), ent\xc3\xa3o G possui uma ramifica\xc3\xa7\xc3\xa3o simples infinitamente longa, isto \xc3\xa9, uma ramifica\xc3\xa7\xc3\xa3o que n\xc3\xa3o possui n\xc3\xb3s repetidos._NEWLINE_Um caso especial dessa afirma\xc3\xa7\xc3\xa3o que acontece comumente \xc3\xa9 que toda \xc3\xa1rvore) que possui uma quantidade infinita de n\xc3\xb3s, em que cada um possui grau finito, possui ao menos uma ramifica\xc3\xa7\xc3\xa3o simples que \xc3\xa9 infinita._NEWLINE_Perceba que o grau dos n\xc3\xb3s deve ser finito mas n\xc3\xa3o precisa ser delimitado: \xc3\xa9 poss\xc3\xadvel que um n\xc3\xb3 tenha grau 10 enquanto outro possui grau 100, um terceiro possui grau 1000 e assim por diante.\n_START_SECTION_\nProva\n_START_PARAGRAPH_\nPara a prova, assuma que o grafo consiste de uma quantidade infinita de n\xc3\xb3s n_i e \xc3\xa9 conectado._NEWLINE_Comece com qualquer n\xc3\xb3 n_1. Cada n\xc3\xb3 do conjunto infinito de n\xc3\xb3s de G pode ser alcan\xc3\xa7ado a partir de n_1 atrav\xc3\xa9s de um caminho simples e cada caminho desse deve come\xc3\xa7ar com um dos n\xc3\xb3s do conjunto finito de n\xc3\xb3s adjacentes a n_1. Deve haver um desses n\xc3\xb3s adjacentes pelo qual um conjunto infinito de n\xc3\xb3s pode ser alcan\xc3\xa7ado sem passar por n_1. Se n\xc3\xa3o existisse, ent\xc3\xa3o o grafo inteiro seria a uni\xc3\xa3o de um conjunto finito de conjuntos finitos e, portanto, finito, contradizendo a suposi\xc3\xa7\xc3\xa3o de que o grafo \xc3\xa9 infinito. Devemos, portanto, escolher um desses v\xc3\xa9rtices e cham\xc3\xa1-lo n_2._NEWLINE_Agora um n\xc3\xbamero infinito de n\xc3\xb3s de G pode ser alcan\xc3\xa7ado a partir de n_2 atrav\xc3\xa9s de um caminho simples que n\xc3\xa3o utiliza o n\xc3\xb3 n_1. Cada caminho desse deve come\xc3\xa7ar com um n\xc3\xb3 do conjunto finito de n\xc3\xb3s adjacentes a n_2. Ent\xc3\xa3o um argumento similar ao apresentado acima mostra que deve haver um desses n\xc3\xb3s adjacentes atrav\xc3\xa9s do qual uma quantidade infinita de n\xc3\xb3s pode ser alcan\xc3\xa7ada; escolha um e chame de n_3._NEWLINE_Continuamente desta maneira, uma caminho simples infinito pode ser constru\xc3\xaddo atrav\xc3\xa9s de indu\xc3\xa7\xc3\xa3o matem\xc3\xa1tica. A cada passo, a hip\xc3\xb3tese de indu\xc3\xa7\xc3\xa3o afirma que existe uma quantidade infinita de n\xc3\xb3s alcan\xc3\xa7\xc3\xa1veis por um caminho simples a partir de um n\xc3\xb3 em particular v_i que n\xc3\xa3o passa por um dos n\xc3\xb3s de um conjunto finito de n\xc3\xb3s. O argumento de indu\xc3\xa7\xc3\xa3o \xc3\xa9 que um dos n\xc3\xb3s adjacentes n_i satisfaz a hip\xc3\xb3tese de indu\xc3\xa7\xc3\xa3o, mesmo quando n_i \xc3\xa9 adicionado ao conjunto finito._NEWLINE_O resultado desse argumento de indu\xc3\xa7\xc3\xa3o \xc3\xa9 que para todo k \xc3\xa9 \xc3\xa9 poss\xc3\xadvel escolher um n\xc3\xb3 n_k da maneira descrita pela constru\xc3\xa7\xc3\xa3o. O conjunto de n\xc3\xb3s escolhidos na constru\xc3\xa7\xc3\xa3o \xc3\xa9 ent\xc3\xa3o uma cadeia no grafo por que cada um foi escolhido para ser adjacente ao n\xc3\xb3 anterior e a constru\xc3\xa7\xc3\xa3o garante que o mesmo n\xc3\xb3 nunca \xc3\xa9 escolhido duas vezes._NEWLINE_Esta prova normalmente n\xc3\xa3o \xc3\xa9 considerada uma prova por constru\xc3\xa7\xc3\xa3o por que em cada passo utiliza uma prova por contradi\xc3\xa7\xc3\xa3o para estabelecer que existe um n\xc3\xb3 adjacente a partir do qual uma quantidade infinita de n\xc3\xb3s pode ser alcan\xc3\xa7ada. Fatos sobre aspectos computacionais do lema sugerem que nenhuma prova pode ser dada que pudesse ser considerada prova por constru\xc3\xa7\xc3\xa3o pelas escolas fundamentais da matem\xc3\xa1tica construtiva.\n_START_SECTION_\nRela\xc3\xa7\xc3\xb5es com a matem\xc3\xa1tica construtiva e compacidade\n_START_PARAGRAPH_\nO famoso teorema de E. L. J. Brower \xc3\xa9, de um ponto de vista cl\xc3\xa1ssico, a contrapositiva de uma forma do lema de Konig. Um subconjunto "S" \\{0,1\\}^{<\\omega}\\, \xc3\xa9 chamado um "bar", se alguma fun\xc3\xa7\xc3\xa3o de \\omega para \\{0,1\\} tem algum segmento inicial em "S". Um "bar" \xc3\xa9 destac\xc3\xa1vel se toda sequ\xc3\xaancia est\xc3\xa1 tamb\xc3\xa9m no bar ou n\xc3\xa3o est\xc3\xa1 no bar (essa suposi\xc3\xa7\xc3\xa3o \xc3\xa9 necess\xc3\xa1ria porque \xc3\xa9 teorema \xc3\xa9 ordinariamente considerado em situa\xc3\xa7\xc3\xb5es onde a lei da exclus\xc3\xa3o m\xc3\xbatua n\xc3\xa3o \xc3\xa9 considerada). Um bar \xc3\xa9 uniforme se existe algum numero "N" tal que toda fun\xc3\xa7\xc3\xa3o de \\omega to \\{0,1\\} tenha um segmento inicial no bar de tamanho no m\xc3\xa1ximo N. O teorema de Brower diz que todo bar destac\xc3\xa1vel \xc3\xa9 uniforme._NEWLINE_Isto pode ser provado numa configura\xc3\xa7\xc3\xa3o cl\xc3\xa1ssica, considerando um bar como uma cobertura aberta do espa\xc3\xa7o topol\xc3\xb3gico compacto \\{0,1\\}^\\omega. Cada sequ\xc3\xaancia no par representa um conjunto b\xc3\xa1sico aberto do espa\xc3\xa7o, e estes conjuntos b\xc3\xa1sicos abertos cobrem o espa\xc3\xa7o por suposi\xc3\xa7\xc3\xa3o. Pela compacidade, isto cobre uma finita subcobertura. O "N" do teorema de Brower pode ter o valor do tamanho do maior sequ\xc3\xaancia cujo conjunto b\xc3\xa1sico aberto est\xc3\xa1 na subcobertura finita. Esta prova topol\xc3\xb3gica pode ser usada na matem\xc3\xa1tica cl\xc3\xa1ssica para mostrar que a seguinte forma do teorema de Konig \xc3\xa9 v\xc3\xa1lida: para todo numero natural "K", toda subarvore infinita da \xc3\xa1rvore \\{0,\\ldots,k\\}^{<\\omega}\\, tem um caminho infinito.\n_START_SECTION_\nRela\xc3\xa7\xc3\xa3o com o Axioma da Escolha\n_START_PARAGRAPH_\nO Lema de Konig pode ser considerado um princ\xc3\xadpio de escolha; a primeira prova acima ilustra a rela\xc3\xa7\xc3\xa3o do lema com o Axioma da depend\xc3\xaancia de escolha. A cada passo da indu\xc3\xa7\xc3\xa3o, um v\xc3\xa9rtice com uma propriedade particular deve ser selecionado. Embora seja provado que ao menos um v\xc3\xa9rtice apropriado existe, se existir mais de um v\xc3\xa9rtice com tal caracter\xc3\xadstica, pode n\xc3\xa3o haver escolha can\xc3\xb4nica._NEWLINE_Se o grafo for cont\xc3\xa1vel, os v\xc3\xa9rtices s\xc3\xa3o bem ordenados e qualquer um pode escolher can\xc3\xb4nicamente o menor v\xc3\xa9rtice apropriado. Nesse caso, o lema de Konig \xc3\xa9 demonstr\xc3\xa1vel em aritm\xc3\xa9tica de segunda ordem com compreens\xc3\xa3o aritm\xc3\xa9tica, e , provado logicamente pela teoria dos conjuntos de Zermelo-Fraenkel._NEWLINE_O lema de Konig \xc3\xa9 essencialmente a restri\xc3\xa7\xc3\xa3o do axioma da depend\xc3\xaancia de escolha a toda rela\xc3\xa7\xc3\xa3o "R" tal que para cada "x" h\xc3\xa1 apenas um n\xc3\xbamero finito de z tal que xRz. Embora o axioma da escolha seja, em geral, mais forte que o o princ\xc3\xadpio da depend\xc3\xaancia de escolha, esta restri\xc3\xa7\xc3\xa3o de depend\xc3\xaancia de escolha \xc3\xa9 equivalente a restri\xc3\xa7\xc3\xa3o do axioma de escolha. Em particular, quando a ramifica\xc3\xa7\xc3\xa3o em cada n\xc3\xb3 \xc3\xa9 feita em um subconjunto finito de um conjunto arbitr\xc3\xa1rio supostamente n\xc3\xa3o cont\xc3\xa1vel, a forma do lema de Konig diz "Toda toda \xc3\xa1rvore infinita de ramifica\xc3\xa7\xc3\xa3o finita tem um caminho infinito" \xc3\xa9 equivalente ao princ\xc3\xadpio de que cada conjunto cont\xc3\xa1vel de conjuntos finitos tem uma fun\xc3\xa7\xc3\xa3o de escolha. Essa forma do axioma da escolha (e por isso do lema de Konig) n\xc3\xa3o \xc3\xa9 provada na teoria dos conjuntos de Zermelo-Fraenkel.'