Incompleteness Theorems, Large Cardinals, and Automata over Infinite WordsReport as inadecuate




Incompleteness Theorems, Large Cardinals, and Automata over Infinite Words - Download this document for free, or read online. Document in PDF available to download.

1 Equipe de Logique Mathématique IMJ - Institut de Mathématiques de Jussieu 2 IMJ-PRG - Institut de Mathématiques de Jussieu - Paris Rive Gauche

Abstract : We prove that there exist some 1-counter Büchi automata A n for which some elementary properties are independent of theories like T n =: ZFC + - There exist at least n inaccessible cardinals - , for integers n ≥ 1. In particular , if T n is consistent, then - LA n is Borel - - LA n is arithmetical - - LA n is ω-regular - - LA n is deterministic - , and - LA n is unambiguous - are provable from ZFC + - There exist at least n+1 inaccessible cardinals - but not from ZFC + - There exist at least n inaccessible cardinals -. We prove similar results for infinitary rational relations accepted by 2-tape Büchi automata.

Keywords : Automata and formal languages logic in computer science models of set theory incompleteness Theorems large cardinals inaccessible cardinals independence from the axiomatic system - ZFC + there exist n inaccessible cardinals - . 2-tape Büchi automaton 1-counter Büchi automaton infinite words





Author: Olivier Finkel -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents