Boa noite Francisco Antônio,
No ano 2015 tentei obter algum novo resultado sobre alguma axiomática para as funções totais recursivas (como é de práxis vou me referir a elas como funções recursivas). Sabia que pelos teoremas da incompletude de Gödel a axiomática não poderia ser completa (ver por exemplo a seção 7.8 do livro de Rogers). Como é bem sabido que o conjunto de índices das funções recursivas é produtivo pensei em tentar obter algum resultado que conectasse aritmética com os conjuntos produtivos e assim ocupar esse resultado para as funções recursivas, mas desisti quando vi que essa conexão já tinha sido estudada no artigo [1] de Horowitz. Aparentemente a tese de doutorado dele (baixo a orientação do Smullyan) foi sobre isso, mas não consegui na época ter acesso a essa tese. Logo disso procurei outras alternativas para estudar as funções recursivas. Provavelmente possa ser do seu interesse o artigo [2], que eu acabei descartando na época por fugir muito da minha área de conhecimento. [1] Horowitz, B.M. Arithmetical analogues of productive and universal sets. Zeitschr. f. math. Logik und Grundlwen d. Math, 203—210, 1982. [2] Fairtlough, M. and Wainer, S. Hierarchies of provably recursive functions. In Handbook of proof theory, 1998. Caso você consiga algum novo resultado sobre este assunto gostaria muito que você o compartilhasse nesta lista. Atenciosamente, Claudio Callejas. 2017-02-20 8:34 GMT-03:00 Francisco Antonio Doria <[email protected]>: > Cito o resultado de Shoenfield: PA + regra omega equivale a PA + regra > omega recursiva. > > Sho en eld has shown that PA > > rule PA > The sequent calculus enriched with the recursively restricted rule in > place of the rule > [image: page2image17432] [image: page2image17600] > > The rule is said to b e constructive if there is a recursive > > n f n is a G odel > > numb er of P n where P n is de ned Takeuti This is equivalent > [image: page2image20360] > > is equivalent to PA recursively restrict > > 2017-02-20 8:24 GMT-03:00 Francisco Antonio Doria <[email protected]>: > >> Pois é, minha dúvida é essa, pois juntar a regra omega tout court é >> bastante, e a regra de Shoenfield - que eu saiba - prova as sentenças >> aritméticas verdadeiras (no modelo standard). >> >> 2017-02-20 8:11 GMT-03:00 Claus Akira Horodynski Matsushigue < >> [email protected]>: >> >>> >>> Prezado Dória.... >>> >>> >>> >>> > Como se sabe, ZF, ZFC, e mesmo PA (aritmética de Peano) não servem >>> > para axiomatizarmos a teoria da computação, já que uma infinidade de >>> > funções recursivas terão propriedades formalmente indecidíveis mas >>> > trivialmente verdadeiras. A gente fica sem poder provar uma >>> infinidade de >>> > propriedades óbvias. >>> >>> Sim! >>> >>> > Alguém já viu uma axiomática para a teoria da computação como PA + >>> Regra omega de Shoenfield? >>> >>> Mão, não é suficiente. Acho que já conversamos isso aqui na lista. >>> >>> >>> Forte abraço, Claus >>> >>> >>> >>> 2017-02-19 2:19 GMT-03:00 Francisco Antonio Doria <[email protected]>: >>> >>>> Como se sabe, ZF, ZFC, e mesmo PA (aritmética de Peano) não servem para >>>> axiomatizarmos a teoria da computação, já que uma infinidade de funções >>>> recursivas terão propriedades formalmente indecidíveis mas trivialmente >>>> verdadeiras. A gente fica sem poder provar uma infinidade de propriedades >>>> óbvias. >>>> >>>> Alguém já viu uma axiomática para a teoria da computação como PA + >>>> Regra omega de Shoenfield? >>>> >>>> -- >>>> Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos >>>> Grupos do Google. >>>> Para cancelar inscrição nesse grupo e parar de receber e-mails dele, >>>> envie um e-mail para [email protected]. >>>> Para postar nesse grupo, envie um e-mail para [email protected]. >>>> Acesse esse grupo em https://groups.google.com/a/di >>>> map.ufrn.br/group/logica-l/. >>>> Para ver essa discussão na Web, acesse https://groups.google.com/a/di >>>> map.ufrn.br/d/msgid/logica-l/CA%2BuR7BLUEnW7aLShc8j5qtYZM54y >>>> vjBZsNV7LWNxSvRcN-cgMQ%40mail.gmail.com >>>> <https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CA%2BuR7BLUEnW7aLShc8j5qtYZM54yvjBZsNV7LWNxSvRcN-cgMQ%40mail.gmail.com?utm_medium=email&utm_source=footer> >>>> . >>>> >>> >>> -- >>> Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos >>> Grupos do Google. >>> Para cancelar inscrição nesse grupo e parar de receber e-mails dele, >>> envie um e-mail para [email protected]. >>> Para postar nesse grupo, envie um e-mail para [email protected]. >>> Acesse esse grupo em https://groups.google.com/a/di >>> map.ufrn.br/group/logica-l/. >>> Para ver essa discussão na Web, acesse https://groups.google.com/a/di >>> map.ufrn.br/d/msgid/logica-l/CAJh6kGVQ7TNkt9Fs%3DjmzC0bib1%2 >>> Bg-WH7md0_3%3DhfP3SVVBKXCA%40mail.gmail.com >>> <https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAJh6kGVQ7TNkt9Fs%3DjmzC0bib1%2Bg-WH7md0_3%3DhfP3SVVBKXCA%40mail.gmail.com?utm_medium=email&utm_source=footer> >>> . >>> >> >> >> >> -- >> fad >> >> ahhata alati, awienta Wilushati >> > > > > -- > fad > > ahhata alati, awienta Wilushati > > -- > Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos > Grupos do Google. > Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie > um e-mail para [email protected]. > Para postar nesse grupo, envie um e-mail para [email protected]. > Acesse esse grupo em https://groups.google.com/a/ > dimap.ufrn.br/group/logica-l/. > Para ver essa discussão na Web, acesse https://groups.google.com/a/ > dimap.ufrn.br/d/msgid/logica-l/CA%2BuR7BKeoi46ZO174WPmMiUFSgZhY0 > J2AgVx1bUpt3DExcrUiQ%40mail.gmail.com > <https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CA%2BuR7BKeoi46ZO174WPmMiUFSgZhY0J2AgVx1bUpt3DExcrUiQ%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > -- Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" dos Grupos do Google. Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para [email protected]. Para postar neste grupo, envie um e-mail para [email protected]. Visite este grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/. Para ver esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAE_57e36YREnwiVv2MjqA6xC5PHYXH3D04o7nuE0vJx4M7Je4w%40mail.gmail.com.
