***

Literature:

[1] "J. Komara and P. J. Voda. Lecture Notes in Theory of Computability. 2001."
[2] "V. Svejdar. Logika: neúplnost, slozitost a nutnost. Academia Praha, 2002"

***

Theorem
"Partially computable predicates are exactly \Sigma_1-definable predicates"

Proof: see Par(s). 7.2.28-7.2.31 in [1], pg(s). 127-138

***

Theorem (Tarski)
"Arithmetical truth cannot be defined in arithmetic"

Proof: see Theorem 4.3.10 in [2], pg. 317

***

Theorem
"Robinson arithmetic is \Sigma_1-complete"

Proof: see Lemma 4.4.6 in [2], pg. 325
       see Theorem 4.4.2 in [2], pg. 324

***

Theorem
"Predicate calculus is undecidable"

Proof: see Theorem 4.4.9 in [2], pg. 328

***

Incompleteness Theorem (Godel)
"Any axiomatizable \Sigma_1-sound extension of Robinson arithmetic is \Pi_1-incomplete"

Proof: see Theorem 4.4.8 in [2], pg. 327

***