# Is mathematics context-free?

Anyone who deals with mathematics knows intuitively that it is a different kind of thinking than ordinary common-sense thinking that intelligent people use every day to understand and make decisions in the world.

I would like to understand what separates ordinary common-sense thinking from mathematical thinking, and I have a guess that ordinary common-sense thinking is in essence contextual, while mathematics in in essence non-contextual.

For instance, pure mathematicians do not care about the context of a mathematical equation, how the equation relates to the real world, when trying to solve the equation, but ordinary intelligent people almost always care about the context of statements made in daily life.

So I thought that perhaps the Chomsky hierarchy might help me answer this question. This gives a mathematical definition of languages which are context-sensitive and context-free. So my question is "Can the structure of mathematics, as represented by ZFC (or perhaps the Peano axioms), be represented as a context-free language."

Has any work been done on this?

• I have not downvoted the question, but find it very unclear. How do you want to derive a language? You need production rules (string-rewriting) for this. Specify the alphabet, maybe the set on non-terminals, if you are talking about deriving via a grammar... – Peter Leupold Sep 19 '18 at 6:59
• @PeterLeupold, I would think the ZFC axioms already specify all of this information, right? Or at least it should be easy to derive this information from the axioms, I would think. – Craig Feinstein Sep 20 '18 at 4:01
• "Anyone who deals with mathematics knows intuitively that it is a different kind of thinking than ordinary common-sense thinking that intelligent people use every day to understand and make decisions in the world. " -- citation needed. – Raphael Sep 20 '18 at 16:59
• Finally, "context-free" has a very precise meaning in the theory of formal languages. It is unlikely to map to your philisophical ideas. – Raphael Sep 20 '18 at 17:01

Let me quote the question.

Can the structure of mathematics, as represented by ZFC (or perhaps the Peano axioms), be represented as a context-free language?

I would like to clarify that the phrase "the structure of mathematics" could be understood as mathematical structures or as a philosophical term whose definition is up in the air in everybody's mind. While everybody is entitled to define or understand that phrase in their own terms, I object to the view "the structure of mathematics, as represented by ZFC (or perhaps the Peano axioms)" because of its ambiguity and its likely misleading connotations. Mathematics is larger than what can be represented by ZFC. Even assuming the view that mathematics is all about ZFC, the clearer way to express that view is "all statements in mathematics, as generated by ZFC (or perhaps the Peano axioms)".

Let me also emphasize that the questions "what is mathematics?" and "what is mathematical thinking?" have been asked thousands of times if not billions of times since the birth of mathematics. Numerous articles, books, videos etc have been produced about them. Checking whether it is context-free sounds like a new cool line of thinking to me on first look, though.

Here is an equivalent of version of the question.

Is the set of all statements generated by ZFC (or by the Peano axioms) a context-free language?

Here is my answer. No, the statements generated by ZFC or the Peano axioms is not a context-free language. It is, in fact, undecidable. Please note that any context-free language is decidable.

In fact, any consistent formal system within which a certain amount of elementary arithmetic can be carried out is undecidable. Note that the subject of previous sentence should, if one wants to know the exact meaning of "a certain amount", be understood according to "Gödel's Incompleteness Theorems" by Panu Raatikainen, 2015, Stanford Encyclopedia of Philosophy. The Peano axioms is just one of the many formal systems where enough elementary arithmetic can be carried out. The most upvoted answer to why Peano arithmetic is undecidable shows that the undecidability of Peano arithmetic (and, in fact, that of any consistent formal within which a certain amount of elementary arithmetic can be carried out) follows from the way the proof of Gödel's incompleteness theorem goes. I would encourage you to read that well-written answer.

Please note there is a serious ambiguity or inconsistency in the original question and the equivalent version given above. By common understanding of a context-free language, it has a finite set of terminal symbols and a finite set of production rules. Since there are infinitely many natural numbers in Peano axioms, which are considered as terminal symbols, we have infinitely many terminal symbols in the statements generated by Peano axioms. There are a few approaches to resolve this technicality so that we could obtain a non-vacuous question as intended by OP. For example, we can replace Peano axioms by a set of axioms where each positive number is defined as the successor of the number that is one smaller than it (then we need infinitely many axioms). For another approach, we can introduce a bit of set theory and define $$1$$ as the set $$\{0\}$$, $$2$$ as the set $$\{0, 1\}$$, $$3$$ as the set $$\{0, 1, 2\}$$, and so on (then it might not be called Peano axioms by common views, I believe). For still another approach, we can extend context-free language to include language with (countably) infinite many terminals. In whichever reasonably way we resolve this technicality, the answer should remain negative following the same line of arguments.