# Does Tarski Indefinability theorem impose a computational lower bound on the axiomatization of the reality?

Based on the Tarski's Indefinability Theorem (TA in standard model is not arithmetic (no FOL formula can represent TA,

a formula represent a predicate relation definition: under Tarski's first order language structure, for every element of the Universe (0,1, 2,....) n there exists a FOL formula P_n such that standard model satisfies P_n if and only if n is in the relation set)

and so not recursive enumerable), is it reasonable to pose the following argument:

Assuming real world fits into some formal system (use Phi to refer any possible things into the system, which can be categorized into some groups by some syntactical formalism) then since the real world contains the standard model, which means TA is also in the True group and so True group will not be arithmetic, not recursive enumerable, and also not axiomatizable at least in the sense of modern day of Turing Machine.

On the other hand, if real world does not fit into any formal system, then at least in the sense of modern day of Turing Machine, given there is no syntactical formalism, TM cannot even encode or compute it. (I know this direction's argument is sloppy, I really have little experience on the computation procedure if something cannot fit into formal system)

So the conclusion is, for the axiomatization of real world, if it wants to explain everything, then it must entail the computation more than the level of Turing Machine, and the concept of axiomatization needs to be adjusted, which given todays computation it's quite impossible.

And this basically implies the imperfection of physics in a theoretical sense where as long as our axiomatization of physics is within the power of Turing Machine, then it cannot explain everything in reality.

• What do you mean by true (Skolem) arithmetic "TA in standard model is not arithmetic"? According to its WP source: true arithmetic is the set of all true first-order statements about the arithmetic of natural numbers... written Th(N). This set is, equivalently, the (complete) theory of the structure N. As for Tarski' truth undefinability theorem, it doesn't limit some metalanguage to define truth for your object language (and recursively so on), but it does imply you cannot have a theory of everything with only one language to express all truths there are per Tarski's theory... Dec 21, 2021 at 23:00
• Real world definitely does not fit into a first order formal system that the theorem applies to, not even natural languages do. Higher order systems, as well as first order systems that do not satisfy its conditions are well-known, so nothing needs to be adjusted. The theorem says, basically, that including a truth predicate into a formal language of a certain precise sort leads to contradictions, no grand conclusions about explaining things follows from that. It may well be that the reality is too complex to be formalized, but it will not be for reasons involved in Tarski's theorem. Dec 21, 2021 at 23:52
• Please note in addition to above fact that the set TA of all true arithmetic sentences is undefinable in arithmetic, it's also undecidable, and even unsemidecidable (not recursively enumerable, ie, not Σn type for any n in Kleene's arithmetic hierarchy), thus TA is complete but not a recursively axiomatizable (computable) theory and thus is of very limited use compared to incomplete but recursively axiomatizable theory PA or its higher order variants such as ACA0 which is closed under Turing jump operator... Dec 22, 2021 at 6:25
• Nice catch, I added the definition of representation in the post. But still, given reality entails standard models (at least from my standpoint it exists as a concept in reality), wonders me the computation lower bound (or even the notion of axiomtization) for reality. Dec 22, 2021 at 6:35
• "imperfection" of physics is obvious, also if we use only an informal sense of perfection, and "it cannot explain everything" is a fact. Having said that, what do you mean with "today's computation it's quite impossible"? In what sense are you using the word "computation"? The algorithm on you Iphone locating your position uses satellite triangulation data corrected according to Relativity theory and the result is quite precise: this is an impressive example (one of many) of computation based on physical theory. Dec 22, 2021 at 15:28