Generic Gӧdel’s Incompleteness Theorem

Abstract

Gӧdel’s incompleteness theorem asserts that if formal arithmetic is consistent then there exists an arithmetic statement such that neither the statement nor its negation can be deduced from the axioms of formal arithmetic. Previously [3], it was proved that formal arithmetic remains incomplete if, instead of the set of all arithmetic statements, we consider any set of some class of “almost all” statements (the class of so-called strongly generic subsets). This result is strengthened as follows: formal arithmetic is incomplete for any generic subset of arithmetic statements (i.e., a subset of asymptotic density 1).