Recursion: an endless journey

There is a feature that I consider explicitly great: Recursion.

In linguistics, Recursion is a fundamental feature of human language that allows it to generate infinitely many sentences or phrases using a finite set of rules and vocabulary. In linguistic terms, recursion refers to the property that a linguistic element (such as a sentence, noun phrase, or verb phrase) can contain an instance of itself or be embedded within another instance of its own type. This was pointed out by Noam Chomsky.

Examples of Recursion in Language:

Nested Sentences:

1. "The cat sleeps."
2. "The cat that the dog chased sleeps."
3. "The cat that the dog that the boy owns chased sleeps."

In this example, each relative clause (that the dog chased, that the boy owns) is embedded within the previous clause. This can continue indefinitely.

Recursive Phrases:

1. "My friend’s brother’s car’s engine..."

This is a recursive use of possessive phrases, where each noun phrase contains another noun phrase.

Embedded Clauses:

1. "She said that he believes that the Earth is round."

Here, the clause "that he believes" is embedded within the clause "that she said."

Why is Important in Language?

• Generativity: Recursion enables the generative power of language, allowing speakers to create an infinite number of sentences using a finite set of rules and words.
• Expressiveness: It allows for complex expressions and nuanced meanings, as clauses can be nested to provide additional information or context.
• Hierarchical Structure: Recursion reflects the hierarchical nature of language, where phrases and sentences are built up from smaller units in a structured, rule-based way.

Is Recursion Universal in Language?

The topic of recursion in linguistics was popularized by Noam Chomsky, who argued that recursion is a universal feature of human language and a key component of the human capacity for language (part of his theory of "Universal Grammar"). However, there is some debate among linguists:

• Pirah? Language: Linguist Daniel Everett argued that the Pirah? language, spoken by an indigenous people in the Amazon, lacks recursive structures. This claim has been controversial and sparked discussions about whether recursion is truly universal, especially Chomsky's followers.

Recursion in Programming and Formal Grammar:

In formal grammar (e.g., context-free grammars), recursion is represented by rules like

• S→aSb?∣?ε: This recursive rule can generate strings like "ab," "aabb," "aaabbb," etc

In programming, recursion is a function that calls itself, allowing for tasks like traversing data structures (e.g., trees).

What happens with Mathematics?

Mathematics exhibits recursive properties in various ways. While recursion in mathematics might not look exactly the same as in programming or language, it is a fundamental concept that appears in several areas:

1. Recursive Definitions in Mathematics

Mathematics often uses recursive definitions to describe sequences, functions, and structures. A recursive definition specifies an object in terms of simpler instances of the same object.

Example: Factorial

The factorial function n! is defined recursively. This definition states that to compute n!, you multiply n by the factorial of n?1. This is a classic recursive process.

Example: Fibonacci Sequence

The Fibonacci sequence is another well-known example. The sequence is defined in terms of its previous two values, demonstrating recursion.

2. Recursive Functions in Mathematical Logic

In mathematical logic and the theory of computation, recursive functions (also known as computable functions) are functions that can be defined using recursion. These functions can be computed by a recursive algorithm.

• Primitive Recursive Functions: A subset of recursive functions that can be defined using basic functions (e.g., zero function, successor function) and are closed under composition and recursion.
• General Recursive Functions: These are more powerful and can include functions defined with unbounded searches (e.g., using the minimization operator).

3. Fractals: Recursive Geometric Structures

Fractals are a classic example of recursive structures in mathematics. They are defined by applying a recursive process, where a pattern is repeated at different scales.

Example: Sierpiński Triangle

The Sierpiński triangle is created recursively:

1. Start with an equilateral triangle.
2. Remove the middle triangle formed by connecting the midpoints of each side.
3. Repeat the process for the remaining triangles.

This recursive construction leads to a self-similar, infinitely complex shape.

4. Proof by Mathematical Induction

Mathematical induction is a form of recursion used in proofs.

5. Recursive Sequences and Series

Many sequences and series are defined recursively. For example:

• Arithmetic Sequence
• Geometric Sequence

These recursive definitions build the entire sequence based on previous terms.

6. Recursive Structures in Set Theory

In set theory, recursion is used to define complex sets from simpler ones.

Example: Von Neumann Construction of Natural Numbers

The natural numbers can be defined recursively using sets: This recursive definition builds each natural number based on the previous one.

7. Recursion in Mathematical Logic and Computability Theory

In computability theory, recursion plays a central role in defining recursively enumerable sets and recursive functions. A set is recursively enumerable if there is a Turing machine that lists all the elements of the set, and recursive functions are those that can be computed by an algorithm.

Again, what happens with Mathematics? Is Mathematics Globally Recursive?

We are recursevily inquiring about whether the global structure of mathematics itself can be considered recursive in the sense that:

• New mathematical discoveries often turn out to be special cases of broader, more general theories developed later.
• The process of mathematical discovery seems to involve a kind of recursion, where previous results are incorporated into new, more comprehensive frameworks.

In a sense, yes, the global structure of mathematics exhibits a recursive pattern. This recursion is seen in the way mathematical theories are often generalized and expanded over time. Let’s break this down:

1. Specialization and Generalization

The history of mathematics often follows a recursive pattern of specialization followed by generalization:

• A theorem or result is discovered and proven in a specific context (a special case).
• Later, a broader theory is developed that encompasses the original result as a special case.

Example: Calculus and Real Analysis

• The early work of Newton and Leibniz on calculus was based on intuitive ideas about limits and infinitesimal changes.
• Later, these ideas were formalized in the rigorous framework of real analysis by mathematicians like Cauchy, Weierstrass, and Riemann. The original concepts of calculus became special cases within the broader theory of limits and continuity.

Example: Fermat’s Last Theorem

Initially, this was a conjecture for specific values of n. In the 20th century, it was shown to be a consequence of the modularity theorem, a much deeper and more general theory that connects elliptic curves and modular forms.

2. Recursive Expansion of Mathematical Frameworks

Mathematics often expands recursively by embedding previous theories into more general frameworks:

• Group Theory: Initially developed to solve polynomial equations, it later became a special case of abstract algebra, which itself is part of broader structures like category theory.
• Euclidean Geometry: Euclidean geometry was extended to non-Euclidean geometries, and then further generalized in the context of differential geometry and topology.
• Set Theory: Cantor’s set theory was developed to understand infinity, but it later became a foundational framework for almost all of modern mathematics, incorporating number theory, analysis, and algebra.

This recursive embedding of theories is a hallmark of the way mathematics evolves.

3. Hierarchical and Recursive Nature of Mathematics

Mathematics is inherently hierarchical, with layers of abstraction and generalization. Each layer often builds on the previous ones, recursively incorporating earlier results:

• Category Theory: A highly abstract branch of mathematics that attempts to unify different fields (e.g., algebra, topology) by describing their structures in a general, recursive framework.
• Model Theory: In mathematical logic, model theory studies the relationships between formal theories and their interpretations (models). It often shows that specific structures (e.g., groups, fields) can be seen as special cases of more general logical frameworks.

4. The Recursive Process of Mathematical Discovery

The process of mathematical discovery can be viewed as recursive:

• Mathematicians start with concrete problems and find solutions (base cases).
• As more problems are solved, patterns emerge, leading to conjectures and generalizations.
• New theories are developed that encompass these patterns, often recursively incorporating earlier results.
• This process continues indefinitely, suggesting a recursive, self-similar structure to the growth of mathematical knowledge.

5. G?del’s Incompleteness Theorems: A Recursive Perspective

G?del’s incompleteness theorems highlight a recursive aspect of mathematical truth:

• Any sufficiently expressive formal system cannot prove all true statements about itself; there are always truths that lie outside its formal reach.
• This implies that the process of formalizing mathematics is inherently recursive: when we expand our system to capture more truths, new unprovable statements emerge, necessitating further extensions.

This recursive nature of formal systems suggests that the structure of mathematical truth may itself be fundamentally recursive.

6. Mathematics as an Infinite Recursive Process

If we view the entire body of mathematics as a structure that is constantly growing and incorporating new theories, then mathematics can be seen as an infinite recursive process:

• Each new discovery can become a special case of a future, more general theory.
• The process of generalization and specialization is recursive, with each level of abstraction building on and embedding previous levels.

In this sense, mathematics is not just self-similar but self-referential, much like a recursive function that calls itself with simpler or smaller inputs.

So, it never ends?

The process of discovery and generalization in mathematics is, in a sense, never-ending. Mathematics appears to be an infinite recursive process, continually building upon itself without a clear termination point. Here’s why:

1. Infinite Depth of Abstraction

• Mathematics is built on a foundation of abstraction, and each new level of abstraction often leads to more general theories and frameworks.
• There is no inherent upper limit to the levels of abstraction we can construct. Every generalization can itself be generalized further.
• For example: Numbers → Polynomials → Rings → Fields → Algebras → Categories → Higher Categories. This chain of abstractions can continue indefinitely, as new mathematical concepts are discovered.

2. G?del’s Incompleteness Theorems: Incompleteness and Recursion

• G?del’s incompleteness theorems suggest that no formal system of mathematics can ever be complete. There will always be true mathematical statements that cannot be proven within the system.
• To prove these statements, we often need to expand the system, introducing new axioms or frameworks. However, this expanded system will also have its own unprovable truths, creating a recursive process.
• This implies that the pursuit of mathematical truth is inherently open-ended.

3. The Frontier of Mathematical Research

• The frontier of mathematical research is always expanding. When a problem is solved, it often leads to new questions or reveals deeper underlying structures.
• Famous examples include: Hilbert’s Problems: In 1900, David Hilbert posed 23 unsolved problems, many of which have inspired entire fields of research. Even though some have been solved, new questions have emerged from the solutions. The Langlands Program: This ambitious set of conjectures seeks to unify number theory and representation theory. It has inspired decades of research and continues to evolve, revealing new connections and questions.

4. Recursion in Mathematical Theories

• Mathematical theories often expand recursively. A new theory may encompass previous results as special cases, but it also opens up a broader landscape of questions.
• For instance: Classical Mechanics was generalized by Quantum Mechanics, which was then further generalized by Quantum Field Theory. However, even Quantum Field Theory is not the end; researchers are now exploring theories like String Theory, which aims to unify physics at an even deeper level.

5. Infinite Complexity and the Nature of Mathematical Objects

• Many mathematical objects exhibit infinite complexity, such as fractals, irrational numbers, or the Mandelbrot set. These objects cannot be fully described or explored in finite terms.
• The recursive structure of these objects suggests that there is always more to discover, even within a single object.

6. The Philosophy of Mathematics: Platonism and Formalism

• Platonism: From a Platonic perspective, mathematical truths exist in an abstract realm, independent of human discovery. In this view, the process of discovering mathematics is infinite because the mathematical "universe" itself is infinite.
• Formalism: From a formalist perspective, mathematics is a creation of human thought, built upon axioms and rules. However, because we can always create new axioms and rules, the process of constructing mathematics is potentially infinite.

7. Mathematics as a Living, Growing Structure

• Mathematics is not static; it evolves over time. New areas of study emerge, sometimes unexpectedly, from the solution of a problem or the discovery of a new concept.
• For example: The discovery of complex numbers opened up entirely new fields like complex analysis and contributed to the development of quantum mechanics.The invention of non-Euclidean geometry led to the theory of relativity and the modern understanding of space-time.

Conclusion: An Endless Journey

Mathematics can be seen as an endless journey of exploration, driven by the recursive process of discovering new truths, generalizing existing results, and uncovering deeper structures. Each new theorem or theory not only answers existing questions but also creates new ones, pushing the frontier of knowledge further.

In this sense, mathematics is like an infinite fractal: the more you zoom in, the more detail and complexity you find, with no ultimate endpoint in sight. As long as there are mathematicians to ask questions and seek answers, the process of mathematical discovery is unlikely to ever come to an end.

Glad to hear your thoughts!