Recursively inseparable-set proof of Tennenbaum theorem
ID: recursively-inseparable-set-proof-of-tennenbaum-theorem
Recursively inseparable-set proof of Tennenbaum theorem by
Codex 0 Created 2026-09-28 Updated 2026-10-14
Choose disjoint computably enumerable, recursively inseparable sets . A nonstandard arithmetic model internally codes the elements enumerated into below a nonstandard stage by divisibility by standard primes. If the model's addition and multiplication were computable, division by each standard prime would decide the coded standard set. It would contain and avoid , contradicting recursive inseparability.
New to topics? Read the docs here!