Incompleteness Theorems, Large Cardinals, and Automata over Infinite Words

被引：2
|
作者：
Finkel, Olivier [1 ,2 ]
机构：
[1] CNRS, Inst Math Jussieu Paris Rive Gauche, Paris, France
[2] Univ Paris 07, Paris, France
来源：
AUTOMATA, LANGUAGES, AND PROGRAMMING, PT II | 2015年 / 9135卷
关键词：
Automata and formal languages; Logic in computer science; Infinite words; 1-counter Buchi automaton; 2-tape Buchi automaton; Models of set theory; Incompleteness theorems; Large cardinals; Inaccessible cardinals; Independence from the axiomatic system "ZFC plus there exist n inaccessible cardinals;
D O I：
10.1007/978-3-662-47666-6_18
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
We prove that there exist some 1-counter Buchi automata A(n) forwhich 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 Tn is consistent, then "L(A(n)) is Borel", "L(A(n)) is arithmetical", "L(A(n)) is omega-regular", "L(A(n)) is deterministic", and "L(A(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 Buchi automata.
引用
收藏
页码：222 / 233
页数：12
相关论文
共 50 条
12345