Essa série ainda pode se dizer um esboço, já que ainda há muito o que se discutir, ainda não sei pôr fórmulas em um blog, e o texto está muito difícil de entender para quem conhece pouca matemática avançada. Vou tentar fazer uma versão mais didática.
O passo que vai além dos busy beavers com oráculos é bem problemático. Isso porque, digamos, numa discussão, muitos poderiam argumentar que o tal número não está bem definido.
A sugestão é a seguinte: vamos tomar F(n) o maior número que pode ser determinado por uma fórmula contendo n símbolos. Isso dependeria da teoria, de seu alfabeto. Se o alfabeto é finito, existe um número finito de fórmulas com n símbolos. Mas poderíamos usar infinitoas símbolos pra variáveis sem problemas, porque se trocarmos apropriadamente as variáveis, as fórmulas ficam tecnicamente idênticas, permitindo pegar apenas uma quantidade finita de fórmula. Cada fórmula determina um número natural ou não, descartamos as que não determinam um único número natural, e pegamos dentro os números determinados o que for maior.
Como teoria e alfabeto, tomemos ZFC com o alfabeto que mencionei antes. Com os naturais identificados com os elementos que mencionei antes. Mas isso é suficiente? Primeiro, temos que saber quando uma afirmação determina um único número natural. Pra isso, poderíamos dizer que uma fórmula só determina um número natural quando a teoria pode provar que existe um único número natural com aquela propriedade. Pra ser mais preciso, diremos então que vamos aceitar a fórmula P(x), com uma única variável livre x, quando existir um teorema do tipo (Existe unico x(x é natural e P(x)). Assim, pra cada fórmula desse tipo está determinado um único número, certo? Não exatamente. Como teoria, apenas estamos garantindo que o referido número com aquela propriedade existe e é único. Mas não é suficiente só as fórmulas e as regras de inferência pra determinar que número é esse. A princípio, o que criamos foi só fórmulas. Podíamos então pensar assim: já que só temos fórmulas, então tomemos fórmulas que especifiquem cada número natural (uma fórmula pra 0, outra pra {0}, outra pra {0,{0}}, etc), e dizemos que P(x) está associada ao número associado à formula que se pode provar que {P(x) se e somente se Q(x)), onde Q é uma das fórmulas associadas ao números. Esse passo resolve o problema. Mas não vai muito longe: BB_2 cresce bem mais rápido.
Então temos que ir além de só trabalharmos com fórmulas. Precisamos de modelos. Precisamos de conjuntos onde as relações estão definidas e satisfazem as fórmulas da teoria dos conjuntos. Mas que modelo utilizaríamos. Poderíamos pensar: vamos exigir que P(x) assuma o mesmo valor em todos os modelos. Mas pra isso precisaríamos definir como poderíamos interpretar universalmente o que seria o mesmo elemento em dois modelos diferentes, já que os modelos podem ser totalmente distintos entre si. Se isso for feito, não resolve. Um teorema devido a Gödel nos daria que se todos os modelos o número é o mesmo, então vai dar pra provar isso na teoria. E isso cairia na definição anterior, de fórmulas associadas a números.
Então a situação é a seguinte: precisamos de um modelo específico. Isso não pode ser determinado por uma teoria (de lógica de primeira ordem). Teria que ser concebido intuitivamente. Aí que entra o obscurantismo. Eu vou tentar usar aqui o universo de Von Neumann, mas esse conceito para muitos pode não ser algo absoluto. Normalmente, a maioria das pessoas pensaria nos naturais como um conceito absoluto, mas o universo de Von Neumann geraria mais questionamentos. Apesar de que, eu não acredito na existência completa do universo de Von Neumann (ele tem cara de "o conjunto de todos os conjuntos", e isso pode-se provar que não existem, mas aí os matemáticos "roubam" e chamas isso de classe, proibindo o universo de pertencer a coinjuntos, o que vai contra a minha intuição, onde qualquer coleção deveria também ser elemento de conjuntos comuns), mas seus segmentos inciais certamente existem.
Bom, pra determinar o universo de Von Neumann (que os matemáticos chamam de "V"), começamos com o conjunto vazio, 0. Depois, tomamos V_1=Partes(0), isso é, o conjunto formado pelos subconjuntos de 0. E depois V_2=partes(V_1). E prosseguimos assim até o infinito. Precisamos agora apelar pro conceito absoluto de ordinais (outra coisa controversa), e determinar que para cada ordinal limite a, definimos V_a como a união dos V_b para b menor que a. Assim, tomamos V como a classe (como eu disse, pode-se provar que V não pode ser um conjunto) união de todos os V_b para b variando em todos os ordinais (totalidade em si que também não é conjunto, mas é classe). Mas eu já disse que não concordo com o conceito de "classe", ao menos se tentarmos dar uma noção absoluta de conjunto, de modo que o conceito absolutista de V não existe, mas existem os V_b para ordinais b inferiores. Então eu vou tomar B como o menor ordinal inacessível (o menor ordinal tal que seu cardinal não é união de cardinais menores, e se um cardinal k é menor que ele então partes(k) é menor também). Esse B é tal que V_B é modelo da teoria dos conjuntos. Assim tomemos então esse modelo.
Agora vamos finalmente definir: ZFC(n) é o maior número natural tal que exista uma fórmula F(x) tal que n é o único número natural que satisfaz aquela fórmula, ou seja, tal que F(n) é verdade no modelo V_B e F(x) não é verdade para todos os outros x diferentes de n. Para cada fórmula com essa propriedade, associamos um único número n. A interpretação dos números n é a que foi especificada, assim como o alfabeto da teoria. Vou definir "Zefecegol" como ZFC(número de Graham), e "Zefecegolplex" como ZFC(Zefecegol), usando o modelo V_B. Um problema sério disso tudo é saber se realmente existem ordinais inacessíveis. Sua definição não é construtiva, de modo que pode ser que eles não existam. Mas sem ele, fica difícil construir um modelo de ZFC usando os V_a's. Precisaríamos de um conceito mais fraco e mais restrito de modelo pra ZFC. Mas eu acredito nos inacessíveis, acho natural que exista um modelo mínimo satisfazendo os axiomas da teoria e a interpretação natural desse modelo levaria a crer que ele tem cardinalidade inacessível.
Dá pra ir além disso? Dá sim. Uma forma é inserir um predicado funcional ZFC(n) representando a nossa função, já que essa função é indefinível em ZFC. Assim, se definirmos o predicado como ZFC sendo um único caracter, surge ZFC_1(n). ZFC_a(n), na notação C de Taranovsky, ZFC_a(n)=ZFC_(a(n))(n), a(n) n-ésimo ordinal da sequência que determina a, assim chegando ao monstruoso ZFC_CX(número de Graham). Não vou dar nome a isso por enquanto, se é que essa coisa existe. Poderíamos pensar em aumentar o ordinal de V_a, mas não sei se isso funciona direito. Acho inclusive que usar o modelo V_a para a muito grande poderia não mudar o número em nada. Não ficou claro ainda se aumentar o número de conjuntos existentes nos produz definições mais potentes pra ZFC(n). Assim, dar o próximo salto é preciso muita criatividade. Uma é usar uma notação intuitiva que vá bem além de CX. Acho que dá pra fazer isso com ordinais além do ordinal de Church Kleene (primeiro ordinal não-computável), usando as definições de máquina de Turing. Mas vamos deixar isso pra depois. Agora passamos a pensar em um método mais eficiente. Um é tentar produzir ordinais contáveis gigantescos e sequências fundamentais pra eles. Mas é melhor criar um conceito novo. Uma sugestão é a lógica de segunda ordem. Mas o obscurantismo aumenta ainda mais. É necessário definir uma semântica da lógica de segunda ordem. Se for possível quantificar em relação à fórmulas da teoria, acho que isso pode criar paradoxos. Eu preferiria pensar em novos símbolos, X,Y,Z... para subconjuntos de V_B, e F,G,H para funções de V_B^n->V_B, e relações P,Q,R para relações em V_B^n (subconjuntos de V_B^n). Assim o conceito de conjunto de verdades a respeito de ZFC muda para incluir os conceitos de lógica de segunda ordem. Aí algumas fórmulas vão definir um número único em V_B, aí depois podíamos construir a função ZFC²(n). E podemos então incluir uma fórmula ZFC²(n) aumentando o poder da teoria e definindo ZFC²_1(n). Daí, ZFC²_CX(número de Graham). E depois? Lógica de terceira ordem. Funções de funções de V_B, relações de relações... Não tenho muito ânimo pra definir isso precisamente. Imagino que se possa ir, lógica de vigésima ordem, daí botar lógica de ordem a, para um dado ordinal a... Isso acaba caindo em lógica infinitária. Talvez seja um salto interessante. Mas eu acho que daí a lógica de segunda ordem acaba codificando essas coisas. Teria que se ter muita criatividade e inteligência pra ir a saltos mais largos. Saltar além da lógica de segunda ordem parece provocar paradoxos. Pelo menos nesse caso de definição de número grande. O próprio conceito de lógica infinitária pode ser codificado em lógica de primeira ordem. Desse modo, pode ser não que derivemos uma contradição, mas que acabemos por construir um método que pode facilmente ser codificado em lógica de primeira de outra forma, mas que seja mais eficiente. Assim, fechemos por enquanto o caixão com ZFC²_CX(Graham), com as definições e encerremos nossa jornada rumo ao infinito (ou melhor, rumo a aleph_0, o primeiro cardinal contável). Mais tarde, tentarei fazer uma versão mais didática e detalhada dessa série.
segunda-feira, 7 de março de 2011
quinta-feira, 3 de março de 2011
Números Grandes e Maiores Ainda (6)
Saltemos um nível e saimos do esquema computável. Normalmente, usar formas combinatórias como iterar funções, criar arranjos, vetores, matrizes que iteram em cada entrada, etc, quase sempre são computáveis. Definamos então a função BB(n) como a Busy Beaver, que é o maior número de 1's que uma Máquina de Turing com até n estados pode computar. Digite "Máquina de Turing" na wikipédia português. É um dispositivo com poder de executar a maioira das operações que conhecemos. Os computadores atuais usam algoritmos que podem ser simulados por uma Máquina de Turing. A função BB(n) não é computável. Por exemplo, não podemos escrever um programa de computador que calcule BB(n) para cada n dado. Ela cresce, portanto, mais rápido que qualquer função citada anteriormente. Mas se quisermos definir um número bem grande, tomar BB(100) por exemplo pode não funcionar. Já tentei fazer uma máquina de Turing que calcula a função de Ackerman (digamos a função a[b]c, para b finito), e ela tinha mais de 4 mil estados. Não escrevi isso diretamente, mas fui iterando vários conceitos um no outro e um efeito multiplicativo me dava uma máquina com muitos estados. O número de Graham, portanto, certamente é menor que BB(4500). Mas evidências indicam que BB(25) já seria mais que suficiente. É difícil compactar a linguagem que usamos pra descrever alguma coisa em um número pequeno de estados. Mas, de qualquer forma, é de se esperar que para um texto com 1000 caracteres, 1 milhão de estados seria suficiente pra representar a máquina. Digamos que a função 10^n nos daria uma segurança em representar uma função definida em um texto com n caracteres (desde que essa função seja computável, é claro). Resumindo, BB(10^n), é uma função bem interessante, e BB(Googolplex) nos daria um número satisfatoriamente grande. Poderia chamá-lo de Superbusyplex.
E como ir alémn disso?
O próximo passo, é inserir a função BB(n) numa máquina de turing. Já que essa função não é computável, inseri-la no sistema de funções computáveis daria um salto bem grande. Vou definir uma coisa agora. Definimos uma máquina de Turing com função extra f(n), como uma máquina de Turing com a seguinte estrutura: tem a fita e todos os estados e tal, mais um estado extra. Esse estado, uma vez que um outro estado passe a função pra ele, terá uma sequência de 1's na fita que segue do leitor dele da esquerda pra direita. A sequência termina com o primeiro 0. A sequência começa na posição o leitor se encontra. Se a sequência começar com 0, o número associado é 0. Se começar com 1, o número associado é o número de 1's seguidos que vem a partir do leitor até o primeiro 0 após os 1's conecutivos. O que o estado extra faz é substituir a sequência de 1's com n algarismos por uma sequência com f(n) algarismos 1, sem sobrescrever o restante da fita que se encontra à direita (apenas empurrando-a para direita, ou recuando se f(n)
BB_2(n) definido usando a mesma lógica com oráculo BB_1. E para um ordinal limite a, definimos BB_a(n)=BB_a(n)(n). Por exemplo, BB_2w(5)=BB_w+5(5)= BB de máquinas de turing com oráculo BB_w+4. E, é claro, BB_w(n)=BB_n(n).
Pensemos então no BB_CX(número de graham) com notação de sequências fundamentais da notação C de Taranovsky, o "Absurdgol". E Absurdgolplex = BB_CX(Absurdgol). Não digo que paro por aqui. Mas é quase isso. Os passos que vou dar daqui pra frente, são obscuros. Creio que BB_CX(graham) seja bem definido certinho, mas os do próximo capítulo já começa a suscitar a dúvida. Os motivos explicarei depois. Ir além desses números (sem cair no referido obscurantismo) parece muito difícil. Ainda não tive uma idéia clara, parece que não dá pra saltar além disso sem soltar uma notação avançada de ordinais. E transcender a idéia dos Busy Beaver com oráculos parece muito difícil mesmo. Teria que dar um jeito de diagonalizar esse argumento, ou criar um mecanismo que generalize isso. Máquinas de Turing de tempo infinito parece ser um caminho. Fica por enquanto pra próxima.
E como ir alémn disso?
O próximo passo, é inserir a função BB(n) numa máquina de turing. Já que essa função não é computável, inseri-la no sistema de funções computáveis daria um salto bem grande. Vou definir uma coisa agora. Definimos uma máquina de Turing com função extra f(n), como uma máquina de Turing com a seguinte estrutura: tem a fita e todos os estados e tal, mais um estado extra. Esse estado, uma vez que um outro estado passe a função pra ele, terá uma sequência de 1's na fita que segue do leitor dele da esquerda pra direita. A sequência termina com o primeiro 0. A sequência começa na posição o leitor se encontra. Se a sequência começar com 0, o número associado é 0. Se começar com 1, o número associado é o número de 1's seguidos que vem a partir do leitor até o primeiro 0 após os 1's conecutivos. O que o estado extra faz é substituir a sequência de 1's com n algarismos por uma sequência com f(n) algarismos 1, sem sobrescrever o restante da fita que se encontra à direita (apenas empurrando-a para direita, ou recuando se f(n)
BB_2(n) definido usando a mesma lógica com oráculo BB_1. E para um ordinal limite a, definimos BB_a(n)=BB_a(n)(n). Por exemplo, BB_2w(5)=BB_w+5(5)= BB de máquinas de turing com oráculo BB_w+4. E, é claro, BB_w(n)=BB_n(n).
Pensemos então no BB_CX(número de graham) com notação de sequências fundamentais da notação C de Taranovsky, o "Absurdgol". E Absurdgolplex = BB_CX(Absurdgol). Não digo que paro por aqui. Mas é quase isso. Os passos que vou dar daqui pra frente, são obscuros. Creio que BB_CX(graham) seja bem definido certinho, mas os do próximo capítulo já começa a suscitar a dúvida. Os motivos explicarei depois. Ir além desses números (sem cair no referido obscurantismo) parece muito difícil. Ainda não tive uma idéia clara, parece que não dá pra saltar além disso sem soltar uma notação avançada de ordinais. E transcender a idéia dos Busy Beaver com oráculos parece muito difícil mesmo. Teria que dar um jeito de diagonalizar esse argumento, ou criar um mecanismo que generalize isso. Máquinas de Turing de tempo infinito parece ser um caminho. Fica por enquanto pra próxima.
Números Grandes e Maiores Ainda (5)
Passando disso tudo, fica difícil de prosseguir. Parece muito difícil achar artigos na internet com notação razoavelmente compreensível de ordinais que vá além da notação C do Taranovsky. Procurei bastante, parece tudo embolado e sem sentido, faltou paciêcia pra procurar algo melhor, ou mesmo tentar entender as notações esquisitas que eu vi por aí, que parecem ir bem além do dito cujo (mesmo o próprio artigo que descrevi possui uma notação mais poderosa, mas de difícil compreensão e clareza).Assim, na maioria das vezes encerro minha jornada em ordinais computáveis no CX (nome que o autor do artigo não deu).
Pensemos então, em um novo método de definir números grandes. Ainda estamos no escopo do computável. Vou falar de algo desconhecido (entre não matemáticos) agora, o sistema axiomático ZFC (teoria dos conjuntos). O sistema axiomático em si é bem definido assim como a lógica de primeira ordem, então não vou enumerar os axiomas agora. Procure na Wikipédia em inglês "Zermelo–Fraenkel set theory". Assim, definamos ZFC_C(n)=O maior número k para o qual existe um algoritmo que calcula k e é tal que exista uma demonstração de tamanho menor ou igual a n (número de caracteres), que esse algoritmo pára. Como o conjunto dos números naturais, entendemos o conjunto (onde 0 é conjunto vazio) {0,{0}(num 1),{0,{0}}(num 2), {0,{0},{0,{0}}}(num 3), etc}.Assim,0 é o conjunto vazio, 1={0}, 2={0,1}, 3={0,1,2}, etc. Usamos em ZFC os carcteres básicos {Existe (E de costas), ParaTodo (A de cabeça pra baixo), Ou (v), Não (¬), E(^), Implica(->), Parênteses (()), Igual(=), Pertence (e), Variáveis(x,y,z,... podemos tomar infinitas)}. Definir o que seria uma demonstração é meio complicado, não vou fazer isso agora. Daí para algum conjunto de regras de inferência nos daria alguma função bem definida ZFC_C(n), ficando assim nossa função indefinida a priori. Mas imaginando que temos um conjunto de regras de inferência, fica definida demonstração como uma sequência de teoremas onde cada teorema ou é um axioma (daí é necessário especificar como ficarão os axiomas, já que existem vários equivalentes resultando no mesmo sistema ZFC), ou se deduz diretamente de uma regra de inferência dos axiomas anteriores. Veja também que faltou precisar o que é um algoritmo (veremos isso daqui a pouco). Assim, temos nossa referida função. Essa função é computável (se ZFC for consistente, o que a maioria dos matemáticos espera ser) . É só rodar um programa que verifica todas as demonstrações que possuem tamanho menor ou igual a n, de que algum referido algoritmo pára. Assim é só depois rodar todos esses algoritmos e ver quem calcula o número maior. Acho que o tamanho do programa que faz isso é imenso, imagino que daria alguns megabytes pra escrever isso em Pascal, por exemplo. Por isso, é difícil ver pessoas usando esse tipo de função em disputas de número maior na internet. Eu mesmo não pude determiná-lo com precisão, já que precisaria escrever a notação dos algoritmos e as regras de inferência. (imagino que essa deva ser a parte mais difícil de entender de um aspirante a matemático nesse texto).
Queria muito definir ZFC_C(número de Graham) como o "Compzfcgol" mas não posso, por enquanto. Fica pra próxima.
Pensemos então, em um novo método de definir números grandes. Ainda estamos no escopo do computável. Vou falar de algo desconhecido (entre não matemáticos) agora, o sistema axiomático ZFC (teoria dos conjuntos). O sistema axiomático em si é bem definido assim como a lógica de primeira ordem, então não vou enumerar os axiomas agora. Procure na Wikipédia em inglês "Zermelo–Fraenkel set theory". Assim, definamos ZFC_C(n)=O maior número k para o qual existe um algoritmo que calcula k e é tal que exista uma demonstração de tamanho menor ou igual a n (número de caracteres), que esse algoritmo pára. Como o conjunto dos números naturais, entendemos o conjunto (onde 0 é conjunto vazio) {0,{0}(num 1),{0,{0}}(num 2), {0,{0},{0,{0}}}(num 3), etc}.Assim,0 é o conjunto vazio, 1={0}, 2={0,1}, 3={0,1,2}, etc. Usamos em ZFC os carcteres básicos {Existe (E de costas), ParaTodo (A de cabeça pra baixo), Ou (v), Não (¬), E(^), Implica(->), Parênteses (()), Igual(=), Pertence (e), Variáveis(x,y,z,... podemos tomar infinitas)}. Definir o que seria uma demonstração é meio complicado, não vou fazer isso agora. Daí para algum conjunto de regras de inferência nos daria alguma função bem definida ZFC_C(n), ficando assim nossa função indefinida a priori. Mas imaginando que temos um conjunto de regras de inferência, fica definida demonstração como uma sequência de teoremas onde cada teorema ou é um axioma (daí é necessário especificar como ficarão os axiomas, já que existem vários equivalentes resultando no mesmo sistema ZFC), ou se deduz diretamente de uma regra de inferência dos axiomas anteriores. Veja também que faltou precisar o que é um algoritmo (veremos isso daqui a pouco). Assim, temos nossa referida função. Essa função é computável (se ZFC for consistente, o que a maioria dos matemáticos espera ser) . É só rodar um programa que verifica todas as demonstrações que possuem tamanho menor ou igual a n, de que algum referido algoritmo pára. Assim é só depois rodar todos esses algoritmos e ver quem calcula o número maior. Acho que o tamanho do programa que faz isso é imenso, imagino que daria alguns megabytes pra escrever isso em Pascal, por exemplo. Por isso, é difícil ver pessoas usando esse tipo de função em disputas de número maior na internet. Eu mesmo não pude determiná-lo com precisão, já que precisaria escrever a notação dos algoritmos e as regras de inferência. (imagino que essa deva ser a parte mais difícil de entender de um aspirante a matemático nesse texto).
Queria muito definir ZFC_C(número de Graham) como o "Compzfcgol" mas não posso, por enquanto. Fica pra próxima.
Numeros Grandes e Maiores Ainda (4)
Pra deixar as coisas mais claras, vou postar aqui umas definições.
Vamos usar w para o omega minusculo, o primeiro ordinal infinito, e O para Omega maiusculo, o primeiro ordinal não contável.
Meu sistema notacional vai até o Bachmann Howard Ordinal. Os simbolos primitivos são 0,1,w,O,+,^,psi. psi(a) é o menor ordinal que não pode ser representado usando as operações +,^, e os numeros 0,O,1,w. Por exemplo, psi(0)=epsilon_0.
A sequência fundamental a(n) para o ordinal limite a, mantém intactos todos os monômios menos um, o menor. Se o ultimo monômio é b, ele é substituído por b(n).
Cada monômio do tipo w^(a+1) é substituído por n*w^a. w é substituído por n. Para um w^a, com a limite, w^a é substituído por w^(a(n)). Podiamos perguntar como seria O^2, já que não é do tipo w^a, mas podemos reduzir qualquer monômio para o tipo w^a. Por exemplo, O^2=w^(2O) (já que w^O=O). Às vezes, trabalhamos com ordinais não contáveis, por exemplo, 2O. E não existe sequência que converge pra eles. Mas existe uma hipersequência de ordinais contáveis, com domínio em todos os ordinais contáveis, que converge pra 2O. Definimos, assim, por exemplo O(s)=s (só que s pode ser qualquer ordinal). Também separamos o monômio w^a, e se a tiver cofinalidade O, então botamos w^a(s)=w^(a(s)). Já psi(0)(n)=w^w...^w com n w's. psi(a+1)(n)=w^...^w^(psi(a)+1) com n-1 w's. psi(a)(n)=psi(a(n)) para a de cofinalidade w. Considere A de cofinalidade O. Então psi(A)(1)=psi(A(1)), psi(A)(2)=psi(A(psi(A)(1))), psi(A)(3)=psi(A(psi(A)(2))), etc
Já para o Bachman Howard Ordinal, limite de (1) psi(O+1), (2) psi(w^(O+1)), (3) psi(w^w^(O+1)), etc.
É um pouco diferente das sequências fundamentais do artigo da wikipédia "Ordinal Collapsing Functions", e precisei definir isso porque não fica claro se ele começa as sequências fundamentais por um ou zero (isso faz uma enorme diferença no final).
Feito isso, defino meu número Beagagol como sendo 10[Bachman-Howard]100, usando a notação acima. Lembrando que a[b]c=a[b(c)]a para ordinais limites b. Tentar calculá-lo gera sérios problemas, ficamos com uma torre imensa de w's e não fica claro quando começamos a iteração realmente. Lembrando que as funções [a] crescem mais rápido quanto maior o ordinal, e o salto de uma pra outra é realmente bem grande, (veja por exemplo saltar de multiplicação por exponenciação). Mas infelizmente a grandeza desse número é tão estranha que não conseguimos nem dar passos básicos em relação aos cálculos iniciais pra bcalcular o número. Tente, por exemplo, calcular "Beagagol" em casa. Eu normalmento só consigo ir muito adiante pra [w^3], ou forçando um pouco a barra [w^w^w]. Pra ir mais longe, definamos Beagagolplex=10[Bachman-Howard]Beagagol.
Para dar um saltinho a mais, vou mencionar novamente o artigo http://web.mit.edu/dmytro/www/other/OrdinalNotation.htm. Usarei a notação C(a,b,c), que não usa os grandes Omegas, porque essa notação não ficou clara como funciona pra mim. Para cada ordinal a na notação defino a(n) como sendo o maior ordinal menor que a que contém até n iterações 'C'. E defino o CX como o ordinal limite dessa notação, dentre os que são de grau de admissibilidade 0. E CX(n), semelhantemente, é o menor ordinal de amissibilidade 0 na notação C que possui no máximo n iterações 'C'.
Assim defino o "Taranovgol" como 10[CX]100, e o Taranovgolplex como 10[CX]Taranovgol. Espero que o Dmytro Taranovsky, autor do artigo, não me mate por isso.
Vamos usar w para o omega minusculo, o primeiro ordinal infinito, e O para Omega maiusculo, o primeiro ordinal não contável.
Meu sistema notacional vai até o Bachmann Howard Ordinal. Os simbolos primitivos são 0,1,w,O,+,^,psi. psi(a) é o menor ordinal que não pode ser representado usando as operações +,^, e os numeros 0,O,1,w. Por exemplo, psi(0)=epsilon_0.
A sequência fundamental a(n) para o ordinal limite a, mantém intactos todos os monômios menos um, o menor. Se o ultimo monômio é b, ele é substituído por b(n).
Cada monômio do tipo w^(a+1) é substituído por n*w^a. w é substituído por n. Para um w^a, com a limite, w^a é substituído por w^(a(n)). Podiamos perguntar como seria O^2, já que não é do tipo w^a, mas podemos reduzir qualquer monômio para o tipo w^a. Por exemplo, O^2=w^(2O) (já que w^O=O). Às vezes, trabalhamos com ordinais não contáveis, por exemplo, 2O. E não existe sequência que converge pra eles. Mas existe uma hipersequência de ordinais contáveis, com domínio em todos os ordinais contáveis, que converge pra 2O. Definimos, assim, por exemplo O(s)=s (só que s pode ser qualquer ordinal). Também separamos o monômio w^a, e se a tiver cofinalidade O, então botamos w^a(s)=w^(a(s)). Já psi(0)(n)=w^w...^w com n w's. psi(a+1)(n)=w^...^w^(psi(a)+1) com n-1 w's. psi(a)(n)=psi(a(n)) para a de cofinalidade w. Considere A de cofinalidade O. Então psi(A)(1)=psi(A(1)), psi(A)(2)=psi(A(psi(A)(1))), psi(A)(3)=psi(A(psi(A)(2))), etc
Já para o Bachman Howard Ordinal, limite de (1) psi(O+1), (2) psi(w^(O+1)), (3) psi(w^w^(O+1)), etc.
É um pouco diferente das sequências fundamentais do artigo da wikipédia "Ordinal Collapsing Functions", e precisei definir isso porque não fica claro se ele começa as sequências fundamentais por um ou zero (isso faz uma enorme diferença no final).
Feito isso, defino meu número Beagagol como sendo 10[Bachman-Howard]100, usando a notação acima. Lembrando que a[b]c=a[b(c)]a para ordinais limites b. Tentar calculá-lo gera sérios problemas, ficamos com uma torre imensa de w's e não fica claro quando começamos a iteração realmente. Lembrando que as funções [a] crescem mais rápido quanto maior o ordinal, e o salto de uma pra outra é realmente bem grande, (veja por exemplo saltar de multiplicação por exponenciação). Mas infelizmente a grandeza desse número é tão estranha que não conseguimos nem dar passos básicos em relação aos cálculos iniciais pra bcalcular o número. Tente, por exemplo, calcular "Beagagol" em casa. Eu normalmento só consigo ir muito adiante pra [w^3], ou forçando um pouco a barra [w^w^w]. Pra ir mais longe, definamos Beagagolplex=10[Bachman-Howard]Beagagol.
Para dar um saltinho a mais, vou mencionar novamente o artigo http://web.mit.edu/dmytro/www/other/OrdinalNotation.htm. Usarei a notação C(a,b,c), que não usa os grandes Omegas, porque essa notação não ficou clara como funciona pra mim. Para cada ordinal a na notação defino a(n) como sendo o maior ordinal menor que a que contém até n iterações 'C'. E defino o CX como o ordinal limite dessa notação, dentre os que são de grau de admissibilidade 0. E CX(n), semelhantemente, é o menor ordinal de amissibilidade 0 na notação C que possui no máximo n iterações 'C'.
Assim defino o "Taranovgol" como 10[CX]100, e o Taranovgolplex como 10[CX]Taranovgol. Espero que o Dmytro Taranovsky, autor do artigo, não me mate por isso.
Números Grandes e Maiores Ainda (3)
Como usar agora os números ordinais para definir números grandes??
Faremos o seguinte. Usaremos a notação a[b]c, aonde a e c são naturais e b é ordinal.
a[1]b=a+b. a[b+1]c=a[b]a[b]...[b]a com c "a"s. Exemplo 3[4w+2]4=3[4w+1]3[4w+1]3[4w+1]3.
A direção em que opermos é da direita pra esquerda, que é onde vai mais rápido. No caso, temos a[b+1]3=a[b](a[b]a) e a[b+1]4=a[b](a[b](a[b]a)). Quando temos um ordinal limite b, definimos a[b]c como a[b(c)]a. Exemplo: a[2w]3=a[2w(3)]a=a[w+3]a. Usamos assim, a sequência fundamental.
Defino aqui o meu número como sendo 10[Bachman-Howard]100, que eu chamo de "Beagagol". Mais tarde irei defini-lo mais precisamente. Existem ordinais bem maiores, mas há formas de ir mais longe que tudo isso. Veremos isso depois.
Vamos agora verificar a grandeza desses números experimentalmente. Boa parte das pessoas já ouviu falar do Googolplex. Um Googol, é um seguido de cem zeros. Bem maior que o número de átomos do universo. Já um googoloplex é um seguido de um googol de zero, ou seja, 10^googol, 10^(10^100). É maior, por exemplo, que todas as imagens possíveis de serem exibidas por uma tela de computador comum. Dizer "número de átomos do universo" parece ir muito bem, pois pra muitos é grande mesmo. Mas isso é só pra começar. Googolplex não pode ser escrito nem mesmo usando todos os átomos do universo, pois tem um googol de zeros. Na minha notação, googol=10[3]100. E Googolplex=10[3](10[3]100). O número 10[4]4 seria 10[3](10[3](10[3]10)), 10^(10^(10^10)), que é maior que 10^(10^(100))=10^(10^(10^2)), portanto maior que Googolplex. Poucos conhecem o Número de Graham. É conhecido por ser o maior número jamais utilizado em uma prova matemática (o que não é exatamente verdade, há artigos indo bem além dele, como os de Harvey Friedman), mas quase certamente é o maior número que possui um nome minimalmente conhecido (não valendo os blogueiros que definem números maiores ainda ou artigos que sejam extremamente desconhecidos). Bom começamos, usando a minha notação, com 3[6]3=n1. Depois definimos n2=3[n1]3, e assim por diante. O número de Graham é o n64. Ele é menor que 3[w+1]65. Para ver como ele é grande, observe o seguinte. Começamos com a operação [1], correspondente a "+". Depois temos a operação [2] que é "*". Depois temos [3], que é a potência "^". A potência é tão rápida que com três números já definimos googolplex. Repara que o n1 que inicia a sequência é 3[6]3, onde usamos a sexta operação, que inimaginavelmente mais rápida que a função potência. Vamos tentar calcular, 3[5]3. Temos 3[5]3=3[4](3[4]3). E 3[4]3=3[3]3[3]3=3^(3^3)=3^27=7625597484987. Então 3[5]3=3[4]7625597484987= 3[3]3[3]...[3]3=3^3^3...3 com 7625597484987 3s. Ou seja, a notação do 3[5]3 é uma torre de potências com mais de 7 trilhões de 3s empilhados. Se não convenceu de que é grande, uma torre com quatro 10s empilhados é maior que um googolplex. Pra que gosta de conta, uma torre com 5 três já passa de longe o googolplex. Podemos fazer uma sequência. n1=3, n2=3^3=27, n3=3^3^3>7 trilhões, n4=3^3^3^3>googol,... E fechamos com n7625597484987. Bom, esse é o 3[5]3.
Já o primeiro número da sequência de Graham é o 3[6]3, que nada mais é que 3[5]3[5]3=
3[4]3[4]...[4]3 (3[5]3 vezes). Lembrando que a operação [4] é a que vem depois da potência (assim como potência vem depois da multiplicação), ou seja combinação de potências. E é executada 3[5]3 vezes. O n2 da sequência de Graham é o 3[n1]3, ou seja, 3[3[6]3]3, que é 3 operado com 3 na 3[6]3-ésima operação. Vendo a velocidade da 6ª operação, fica como exercício imaginar a velociade desse super-operação.
Bom, aqui vimos números ordinais e não os usamos ainda. Como vimos, o primeiro ordinal infinito é w. Então a[w]b=a[b]a. Exemplo, 3[w]15=3[15]3. Podemos analizar o w+1. 3[w+1]5=3[w]3[w]3[w]3[w]3=3[3[3[3[3]3]3]3]3=3[3[3[27]3]3]3. Lembrando que o cálculo passa pelo grande 3[27]3. O número de Graham é um pouco menor que 3[w+1]65=3[w]3[w]3...[w]3 65 vezes. Já [w+2] é a operação que itera vários [w+1]. Vamos dar um salto e tentar calcular 3[w^2]3. Temos 3[w^2]3=3[3w]3=3[2w+3]3=3[2w+2](3[2w+2]3)=3[2w+1]...[2w+1]3 (3[2w+2]3 vezes). Isso porque nem chegamos em [2w]. Por exemplo, 3[2w]20=3[w+20]3, que é a vigésima operação após a super operação [w].
Terminamos por aqui já que tentar calcular coisas como 3[Gamma_0]3 daria uma imensa dor de cabeça.
Veremos mais tarde, maneiras diferentes de se criar coisas enormes, que colocam números como o "Beagagol" no chinelo.
Faremos o seguinte. Usaremos a notação a[b]c, aonde a e c são naturais e b é ordinal.
a[1]b=a+b. a[b+1]c=a[b]a[b]...[b]a com c "a"s. Exemplo 3[4w+2]4=3[4w+1]3[4w+1]3[4w+1]3.
A direção em que opermos é da direita pra esquerda, que é onde vai mais rápido. No caso, temos a[b+1]3=a[b](a[b]a) e a[b+1]4=a[b](a[b](a[b]a)). Quando temos um ordinal limite b, definimos a[b]c como a[b(c)]a. Exemplo: a[2w]3=a[2w(3)]a=a[w+3]a. Usamos assim, a sequência fundamental.
Defino aqui o meu número como sendo 10[Bachman-Howard]100, que eu chamo de "Beagagol". Mais tarde irei defini-lo mais precisamente. Existem ordinais bem maiores, mas há formas de ir mais longe que tudo isso. Veremos isso depois.
Vamos agora verificar a grandeza desses números experimentalmente. Boa parte das pessoas já ouviu falar do Googolplex. Um Googol, é um seguido de cem zeros. Bem maior que o número de átomos do universo. Já um googoloplex é um seguido de um googol de zero, ou seja, 10^googol, 10^(10^100). É maior, por exemplo, que todas as imagens possíveis de serem exibidas por uma tela de computador comum. Dizer "número de átomos do universo" parece ir muito bem, pois pra muitos é grande mesmo. Mas isso é só pra começar. Googolplex não pode ser escrito nem mesmo usando todos os átomos do universo, pois tem um googol de zeros. Na minha notação, googol=10[3]100. E Googolplex=10[3](10[3]100). O número 10[4]4 seria 10[3](10[3](10[3]10)), 10^(10^(10^10)), que é maior que 10^(10^(100))=10^(10^(10^2)), portanto maior que Googolplex. Poucos conhecem o Número de Graham. É conhecido por ser o maior número jamais utilizado em uma prova matemática (o que não é exatamente verdade, há artigos indo bem além dele, como os de Harvey Friedman), mas quase certamente é o maior número que possui um nome minimalmente conhecido (não valendo os blogueiros que definem números maiores ainda ou artigos que sejam extremamente desconhecidos). Bom começamos, usando a minha notação, com 3[6]3=n1. Depois definimos n2=3[n1]3, e assim por diante. O número de Graham é o n64. Ele é menor que 3[w+1]65. Para ver como ele é grande, observe o seguinte. Começamos com a operação [1], correspondente a "+". Depois temos a operação [2] que é "*". Depois temos [3], que é a potência "^". A potência é tão rápida que com três números já definimos googolplex. Repara que o n1 que inicia a sequência é 3[6]3, onde usamos a sexta operação, que inimaginavelmente mais rápida que a função potência. Vamos tentar calcular, 3[5]3. Temos 3[5]3=3[4](3[4]3). E 3[4]3=3[3]3[3]3=3^(3^3)=3^27=7625597484987. Então 3[5]3=3[4]7625597484987= 3[3]3[3]...[3]3=3^3^3...3 com 7625597484987 3s. Ou seja, a notação do 3[5]3 é uma torre de potências com mais de 7 trilhões de 3s empilhados. Se não convenceu de que é grande, uma torre com quatro 10s empilhados é maior que um googolplex. Pra que gosta de conta, uma torre com 5 três já passa de longe o googolplex. Podemos fazer uma sequência. n1=3, n2=3^3=27, n3=3^3^3>7 trilhões, n4=3^3^3^3>googol,... E fechamos com n7625597484987. Bom, esse é o 3[5]3.
Já o primeiro número da sequência de Graham é o 3[6]3, que nada mais é que 3[5]3[5]3=
3[4]3[4]...[4]3 (3[5]3 vezes). Lembrando que a operação [4] é a que vem depois da potência (assim como potência vem depois da multiplicação), ou seja combinação de potências. E é executada 3[5]3 vezes. O n2 da sequência de Graham é o 3[n1]3, ou seja, 3[3[6]3]3, que é 3 operado com 3 na 3[6]3-ésima operação. Vendo a velocidade da 6ª operação, fica como exercício imaginar a velociade desse super-operação.
Bom, aqui vimos números ordinais e não os usamos ainda. Como vimos, o primeiro ordinal infinito é w. Então a[w]b=a[b]a. Exemplo, 3[w]15=3[15]3. Podemos analizar o w+1. 3[w+1]5=3[w]3[w]3[w]3[w]3=3[3[3[3[3]3]3]3]3=3[3[3[27]3]3]3. Lembrando que o cálculo passa pelo grande 3[27]3. O número de Graham é um pouco menor que 3[w+1]65=3[w]3[w]3...[w]3 65 vezes. Já [w+2] é a operação que itera vários [w+1]. Vamos dar um salto e tentar calcular 3[w^2]3. Temos 3[w^2]3=3[3w]3=3[2w+3]3=3[2w+2](3[2w+2]3)=3[2w+1]...[2w+1]3 (3[2w+2]3 vezes). Isso porque nem chegamos em [2w]. Por exemplo, 3[2w]20=3[w+20]3, que é a vigésima operação após a super operação [w].
Terminamos por aqui já que tentar calcular coisas como 3[Gamma_0]3 daria uma imensa dor de cabeça.
Veremos mais tarde, maneiras diferentes de se criar coisas enormes, que colocam números como o "Beagagol" no chinelo.
Números Grandes e Maiores Ainda (2)
Números Ordinais
Números Ordinais são um conceito da Teoria dos Conjuntos, que generalizam o processo de contagem. São conjuntos bem ordenados, ou seja, cada subconjunto de ordinais tem um menor elemento. A classe de todos os ordinais é tão grande que não é um conjunto. Para cada conjunto de ordinais, existirá o próximo ordinal, o menor ordinal fora desse conjunto.
Vamos conhecê-los melhor.
Começamos a contagem com 1,2,3... Dado o conjunto dos naturais, teremos um próximo elemento, w. Daí seguimos, w+1,w+2,w+3,..., formando outro conjunto seguido por 2w. Continuamos a contagem, 2w, 3w, 4w, cada um com infinitos números entre um e outro (não como os números reais, cada elemento possui um sucessor imediato, mas pode haver infinitos elementos antes dele), seguindo o conjunto nw devemos ter mais um sucessor, w² (escreveremos w^2). Daí temos, w^2, 2w^2, ... w^3,...,w^4,...,...,w^w.
E não para por aí. Continuamos com w^w+1, w^w+2, w^2w, w^w^w, w^w^w^w,... e ?
Daí temos um problema porque não existe uma operação elementar para usarmos para w.
Daí, usamos epsilon_0, como valor de convergência. Daí continuamos w^epsilon_0, epsilon_0^epsilon_0,....(?)...., epsilon_1. Continuamos e então temos, epsilon_1, epsilon_2, epsilon_3,... epsilon_w. Continuamos, nada impede que tenhamos epsilon_epsilon_0, por exemplo. Continuando, epsilon_epsilon _..._epsilon_0, convergiria para quanto?
Precisamos definir funções novas. Alguém poderia ir em http://en.wikipedia.org/wiki/Large_countable_ordinal, pra ver se consegue notações novas. Criamos a função de Veblem pra isso, w^a seria phi_0(a), epsilon_a seria phi_1(a), phi_n+1(a) o a-ésimo ordinal não representável por phi_n. O ordinal que é maior que todos os phi_n seria phi_w(0), mas podendo colocar qualquer ordinal em phi, chegaríamos em ordinais maiores. O limite de tudo isso é o ordinal Gamma_0. Ir além disso pode ficar muito difícil pra um iniciante, mas fica como exercício pro leitor procurar no google coisas como "Ordinal Collapsing Function", para conhecer ordinais como o ordinal de Bachmann-Howard. Em português se achará zero sobre isso, mas em inglês tem tudo.
Todos os ordinais acima são computáveis e contáveis. Existem uns maiores como o w1CK de Church Kleene, que não é computável, e o w_1, que não é contável (existem coisas beeem maiores que esses). Curiosamente usar ordinais não contáveis é útil pra criar grandes ordinais contáveis computáveis.
Sequência Fundamental
Sem as sequências fundamentais, fica inútil usar ordinais para definir números grandes. Para cada ordinal limite (ordinal que não é sucessor de outro ordinal), devemos determinar uma sequência fundamental que converge pra esse ordinal. Assim, poderíamos para o ordinal a, definirmos a(n). a sequência a(1), a(2), a(3),... terá como sucessor imediato o ordinal a.
Vejamos casos específicos. a sequência para o polinômio ordinal mz*w^z+...+mk*w^k, será mz*w^z+...+(m(k+1))*(w^k+1)+((mk)-1)*w^k+n*w^(k-1). Se ficar difícil de entender, exemplo, a sequência do ordinal w^4+2*w^3 é w^4+w^3+n*w^2. Para termos mais gerais (antes de epsilon_0), fazemos o seguinte: separamos o termo com a menor potência, digamos m*w^a. Se a for um ordinal sucessor, a-1 existe, então a sequência fica (m-1)*w^a+n*w^(a-1), exemplo, 4w^(2w+2) fica 3w^(2w+2)+n*w^(2w+1).
E para além de epsilon_0? Para o próprio epsilon_0 seria 0,1,w,w^w,w^w^w...
Pro resto, fica como exercício para o leitor ver na wikipédia inglês "Veblen function" e "Ordinal Collapsing Function".
Números Ordinais são um conceito da Teoria dos Conjuntos, que generalizam o processo de contagem. São conjuntos bem ordenados, ou seja, cada subconjunto de ordinais tem um menor elemento. A classe de todos os ordinais é tão grande que não é um conjunto. Para cada conjunto de ordinais, existirá o próximo ordinal, o menor ordinal fora desse conjunto.
Vamos conhecê-los melhor.
Começamos a contagem com 1,2,3... Dado o conjunto dos naturais, teremos um próximo elemento, w. Daí seguimos, w+1,w+2,w+3,..., formando outro conjunto seguido por 2w. Continuamos a contagem, 2w, 3w, 4w, cada um com infinitos números entre um e outro (não como os números reais, cada elemento possui um sucessor imediato, mas pode haver infinitos elementos antes dele), seguindo o conjunto nw devemos ter mais um sucessor, w² (escreveremos w^2). Daí temos, w^2, 2w^2, ... w^3,...,w^4,...,...,w^w.
E não para por aí. Continuamos com w^w+1, w^w+2, w^2w, w^w^w, w^w^w^w,... e ?
Daí temos um problema porque não existe uma operação elementar para usarmos para w.
Daí, usamos epsilon_0, como valor de convergência. Daí continuamos w^epsilon_0, epsilon_0^epsilon_0,....(?)...., epsilon_1. Continuamos e então temos, epsilon_1, epsilon_2, epsilon_3,... epsilon_w. Continuamos, nada impede que tenhamos epsilon_epsilon_0, por exemplo. Continuando, epsilon_epsilon _..._epsilon_0, convergiria para quanto?
Precisamos definir funções novas. Alguém poderia ir em http://en.wikipedia.org/wiki/Large_countable_ordinal, pra ver se consegue notações novas. Criamos a função de Veblem pra isso, w^a seria phi_0(a), epsilon_a seria phi_1(a), phi_n+1(a) o a-ésimo ordinal não representável por phi_n. O ordinal que é maior que todos os phi_n seria phi_w(0), mas podendo colocar qualquer ordinal em phi, chegaríamos em ordinais maiores. O limite de tudo isso é o ordinal Gamma_0. Ir além disso pode ficar muito difícil pra um iniciante, mas fica como exercício pro leitor procurar no google coisas como "Ordinal Collapsing Function", para conhecer ordinais como o ordinal de Bachmann-Howard. Em português se achará zero sobre isso, mas em inglês tem tudo.
Todos os ordinais acima são computáveis e contáveis. Existem uns maiores como o w1CK de Church Kleene, que não é computável, e o w_1, que não é contável (existem coisas beeem maiores que esses). Curiosamente usar ordinais não contáveis é útil pra criar grandes ordinais contáveis computáveis.
Sequência Fundamental
Sem as sequências fundamentais, fica inútil usar ordinais para definir números grandes. Para cada ordinal limite (ordinal que não é sucessor de outro ordinal), devemos determinar uma sequência fundamental que converge pra esse ordinal. Assim, poderíamos para o ordinal a, definirmos a(n). a sequência a(1), a(2), a(3),... terá como sucessor imediato o ordinal a.
Vejamos casos específicos. a sequência para o polinômio ordinal mz*w^z+...+mk*w^k, será mz*w^z+...+(m(k+1))*(w^k+1)+((mk)-1)*w^k+n*w^(k-1). Se ficar difícil de entender, exemplo, a sequência do ordinal w^4+2*w^3 é w^4+w^3+n*w^2. Para termos mais gerais (antes de epsilon_0), fazemos o seguinte: separamos o termo com a menor potência, digamos m*w^a. Se a for um ordinal sucessor, a-1 existe, então a sequência fica (m-1)*w^a+n*w^(a-1), exemplo, 4w^(2w+2) fica 3w^(2w+2)+n*w^(2w+1).
E para além de epsilon_0? Para o próprio epsilon_0 seria 0,1,w,w^w,w^w^w...
Pro resto, fica como exercício para o leitor ver na wikipédia inglês "Veblen function" e "Ordinal Collapsing Function".
Números grandes e maiores ainda (reedição)
Sabe aquela brincadeira de ganha quem disser o maior número?
Tenho descoberto maneiras de se definir números tão grandes que só com um auxílio de números ordinais ou outros conceitos avançados pra poder definir.
Pra quem não sabe o que é um número ordinal, leia: http://en.wikipedia.org/wiki/Ordinal_number
Por exemplo, depois de contar: 1,2,3,4... temos um número pra representar depois desses : w (se tivesse mais recurso pra escrever no blog escreveria omega). De certa forma podemos considerar esse o primeiro ordinal infinito. Depois vem w+1,w+2,... aí depois de todos esses 2w. Assim podemos continuar indefinidamente sem parar. Para mais leia o artigo da Wikipédia.
Pra começar, um exemplo:
Tomemos Fo(x)=x! pra todo número natural x. Depois F1(x)=F1(...(F1(x)...) com x iterações da função F0. Depos tomamos F2 seguindo a mesma lógica, e assim F3, F4...
Por exemplo, F2(4)=F1(F1(F1(F1(4)))) sendo que F1(4)=4!!!!
Então já dá pra imaginar como fica F50(5), por exemplo. A vantagem do ordinal é não se limitar a números naturais: podemos definir Fw. Digamos então que Fw(x)=Fx(x). Por exemplo, Fw(100)=F100(100). Então continua: F[w+1]é a função que se segue, depois F[w+2],...,F[2w] (define-se F[2w](x)=F[w+x](x)); depois F[2w+1], F[2w+2], ... F[3w],... F[w²], etc.
Continua...
Tenho descoberto maneiras de se definir números tão grandes que só com um auxílio de números ordinais ou outros conceitos avançados pra poder definir.
Pra quem não sabe o que é um número ordinal, leia: http://en.wikipedia.org/wiki/Ordinal_number
Por exemplo, depois de contar: 1,2,3,4... temos um número pra representar depois desses : w (se tivesse mais recurso pra escrever no blog escreveria omega). De certa forma podemos considerar esse o primeiro ordinal infinito. Depois vem w+1,w+2,... aí depois de todos esses 2w. Assim podemos continuar indefinidamente sem parar. Para mais leia o artigo da Wikipédia.
Pra começar, um exemplo:
Tomemos Fo(x)=x! pra todo número natural x. Depois F1(x)=F1(...(F1(x)...) com x iterações da função F0. Depos tomamos F2 seguindo a mesma lógica, e assim F3, F4...
Por exemplo, F2(4)=F1(F1(F1(F1(4)))) sendo que F1(4)=4!!!!
Então já dá pra imaginar como fica F50(5), por exemplo. A vantagem do ordinal é não se limitar a números naturais: podemos definir Fw. Digamos então que Fw(x)=Fx(x). Por exemplo, Fw(100)=F100(100). Então continua: F[w+1]é a função que se segue, depois F[w+2],...,F[2w] (define-se F[2w](x)=F[w+x](x)); depois F[2w+1], F[2w+2], ... F[3w],... F[w²], etc.
Continua...
Assinar:
Comentários (Atom)