Geodesic
Generic incompleteness of formal arithmetic
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 12 (2015), pp. 185-189.

Voir la notice de l'article provenant de la source Math-Net.Ru

Famous Gödel's incompleteness theorem states that formal arithmetic (if it is consistent) has a statement that is unprovable and incontrovertible by any recursive systems of axioms. In this paper we prove that Gödel's theorem remains true if we restrict the set of all arithmetic statements by some natural subsets of “almost all” statements (so called strongly generic sets).
Keywords: formal arithmetic, generic complexity. 
@article{SEMR_2015_12_a5,
     author = {A. N. Rybalov},
     title = {Generic incompleteness of formal arithmetic},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {185--189},
     publisher = {mathdoc},
     volume = {12},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2015_12_a5/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - Generic incompleteness of formal arithmetic
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2015
SP  - 185
EP  - 189
VL  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2015_12_a5/
LA  - ru
ID  - SEMR_2015_12_a5
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T Generic incompleteness of formal arithmetic
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2015
%P 185-189
%V 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2015_12_a5/
%G ru
%F SEMR_2015_12_a5
A. N. Rybalov. Generic incompleteness of formal arithmetic. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 12 (2015), pp. 185-189. http://geodesic.mathdoc.fr/item/SEMR_2015_12_a5/

[1] J. D. Hamkins, A. Miasnikov, “The halting problem is decidable on a set of asymptotic probability one”, Notre Dame Journal of Formal Logic, 47:4 (2006), 515–524 | DOI | MR

[2] I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain, “Generic-case complexity, decision problems in group theory and random walks”, Journal of Algebra, 264:2 (2003), 665–694 | DOI | MR

[3] I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain, “Average-case complexity for the word and membership problems in group theory”, Advances in Mathematics, 190 (2005), 343–359 | DOI | MR

[4] A. Myasnikov, A. Rybalov, “Generic complexity of undecidable problems”, Journal of Symbolic Logic, 73:2 (2008), 656–673 | DOI | MR

[5] A. Rybalov, “On the strongly generic undecidability of the Halting Problem”, Theoretical Computer Science, 377 (2007), 268–270 | DOI | MR

[6] A. Rybalov, “Generic Complexity of Presburger Arithmetic”, Theory of Computing Systems, 46:1 (2010), 2–8 | DOI | MR

[7] A. Rybalov, “Generic complexity of first-order theories”, Siberian Electronic Mathematical Reports, 8 (2011), 168–178 | MR

[8] A. Rybalov, “On generic undecidability of Hilbert's tenth problem”, Herald of Omsk University, 4 (2011), 19–22

[9] A. Rybalov, “On generic complexity of the Boolean truthfulness problem”, Herald of Omsk University, 4 (2012), 36–40

[10] A. Rybalov, “Generic complexity of the Diophantine problem”, Groups Complexity Cryptology, 5:1 (2013), 25–30 | DOI | MR

[11] A. Rybalov, “On generic complexity of the Boolean satisfiability problem”, Herald of Omsk University, 4 (2013), 52–56