Limits to Mathematical Modeling in Social Sciences
By Francisco A. Doria
The synthesis of the calculus of n-variables and of n-dimensional geometry is the basis of what Seldon once called “my little algebra of humanity”
(apud I. Asimov, Second Foundation)
Hari Seldon is a fictional character created by Isaac Asimov for his Foundation series of romances. A highly unlikely character, we may add: a politician with mathematical skills, who developed the discipline of psycho-history, or the mathematical description of social processes and of the evolution of history.
Asimov later tells us a bit more about the workings of psychohistory: it’s basically a nonlinear dynamical system, and, in later books from the Foundation series, he incorporates into Seldon’s creation some stuff from chaos theory.
Chaos Theory & Nonlinear Systems
In 1963, Edward Lorenz published his famous paper on deterministic chaos, “Deterministic Non-Periodic Flow.” The title itself is an understatement, or perhaps a discreet disguise: for Lorenz discusses a system of three autonomous differential equations with just two second-degree nonlinearities, which exhibits a very complex, apparently chaotic, behavior, that hinders the prediction of the time-evolution of our system.
Social systems have long been modeled by autonomous differential equations with low-degree nonlinearities, as in competition models conceived out of the Lotka–Volterra equations. Those particular equations are nonlinear but predictable, that is, with Lotka–Volterra systems at hand, we know that nonlinearities aren’t sufficient for a dynamical system to exhibit chaotic behavior. (But they are a necessary condition.) So, there arose the question of an algorithmic procedure to anticipate whether a nonlinear system would exhibit chaotic behavior.
The nonexistence of such an algorithm was proved, under very general conditions, by da Costa and Doria in 1991. So, not only nonlinear systems may turn out to be unpredictable; we cannot even say (for arbitrary systems and conditions) whether they will be unpredictable or not! Moreover, there will be systems that are chaotic in one model for mathematics, and perfectly predictable in another model.
The Gödel Phenomenon
Here the Gödel phenomenon enters the picture. If we could make calculations with infinite precision, we would be able to predict with all required sharpness the future behavior of chaotic systems. But there will be situations where not one of these calculations is possible.
When the Gödel phenomenon enters the game, no calculations to predict the future behavior of the system might be possible.
So, we have a higher-order difficulty here — one that wasn’t anticipated by our fictional sage, Hari Seldon. Chaotic systems are deterministic: therefore, given infinitely precise calculations, all future behavior can be predicted. However, when the Gödel phenomenon enters the game, no calculations to predict the future behavior of the system might be possible because we have no algorithms to perform them; no algorithms exist (and the standard concept for mathematical proof subsumes an algorithmic construction).
Undecidability in Mathematical Economics
Alan Lewis and K. Velupillai, among others, were pioneers in the discussion of undecidability and incompleteness in mathematical economics. Now we know that, for example, equilibrium prices in efficient markets are noncomputable, in the general case. In 1998, Tsuji, da Costa, and Doria entered the fray, with their result on the incompleteness of game theory — which is valid for a wide range of axiomatizations of Nash games and analogous theories.
The reason for such a vast presence of Gödel-like phenomena in mathematical economics is simple: they follow from a Rice-like theorem, which can be proved for the language of classical analysis, which is the language used by mathematical economists when exhibiting their wares.
So, undecidability and incompleteness creep up everywhere in economics and in the social sciences and seem to hinder the predictive character of mathematics in those theories.
Undecidability and incompleteness creep up everywhere in economics and in social sciences.
Undecidability doesn’t mean total ignorance about a mathematical object: it only forbids the existence of a general algorithm or a general recipe — for specific problems, ad hoc solutions may be possible, of course. But science is made of general laws, of general computational procedures, and our question is: are such general laws possible in the (mathematical) social sciences? If so, how useful are these general procedures? Do they tell us something really interesting about the social world, as much as a system’s Lagrangian tells us a lot about the system’s physical behavior?
Does Incompleteness Matter?
Gödel published his remarkable incompleteness theorems in 1931. Gödel’s reasoning was immediately recognized as correct, even if surprising, and several researchers then asked for its scope: since Gödel’s argument exhibited an undecidable sentence that didn’t quite reflect everyday mathematical fact or facts (see below), there was some hope that undecidable sentences might be circumscribed to a very pathological realm within arithmetic theory or its extensions.
Alas, this proved not to be true.
Gödel’s great 1931 paper, “On formally undecidable sentences of Principia Mathematica and related systems,” has two main results. Suppose that the axiomatic theory we consider contains “enough arithmetic”:
- If the axiomatic theory we consider is consistent, then there is in it a sentence that can neither be proved nor be disproved (always within the axiomatic framework we have chosen). However, that sentence can be easily seen to be true in the standard model for arithmetic.
- If the same theory is consistent, then we cannot (within it) prove a sentence that asserts the theory’s consistency.
Gödel’s undecidable sentence is weird and doesn’t seem to have an everyday mathematical meaning. It is constructed as follows:
- He first shows that the sentence “G cannot be proved” can be formalized within his axiomatic framework.
- Then he diagonalizes it. The sentence he obtains is interpreted as “I cannot be proved.” The sentence is true, but — as said doesn’t have an obvious everyday mathematical meaning.
The second incompleteness theorem can be seen as a kind of corollary to the first one. Briefly, for a theory based on classical first-order logic, it is consistent if and only if it doesn’t prove a contradiction. It proves a contradiction if and only if it proves all its sentences. However, an incomplete theory doesn’t prove at least two of its sentences, say G and ¬G . (For a more detailed discussion, see Chaitin et al. 2011.)
Gödel incompleteness may be one of the chief hindrances, besides nonlinearity, in the prediction of the future behavior of systems representing social phenomena.
Gödel incompleteness may be one of the chief hindrances (besides nonlinearity) in the prediction of the future behavior of those systems in our current formal representations of social phenomena. So, our knowledge about society may also have computational, predictive limits imposed by the Gödel phenomenon.
Incompleteness in S
Patrick Suppes argues that there is no essential difference between “a piece of pure mathematics and a piece of theoretical science.” We argue that Gödel-like phenomena occur everywhere and in rather intuitive contexts within the language of classical analysis. They therefore necessarily occur within any theory where the underlying language is that of classical analysis.
Gödel-like phenomena occur everywhere and in rather intuitive contexts within the language of classical analysis.
As Suppes (1988) remarks:
… axiomatic methods are now widely used in foundational investigation of particular sciences, as well as in the pursuit of certain general questions of methodology, especially those concerning probability and induction. The use of such methods permits us to bring to the philosophy of science the standards of rigor and clarity that are very much an accepted part of the closely related discipline of logic.
Axiomatic systems like Zermelo–Fraenkel set theory, or Peano Arithmetic, can be formulated as computer programs that list (i.e., recursively enumerate) all theorems of the theory. These theories are machines that produce theorems — the sentences that are valid in the theory.
So, suppose that S is one such axiomatic theory. Suppose that S is able to talk about computer programs, that is, we can talk about partial recursive functions in the language of S. We are interested in the recursive functions that are total, that is, which are defined for all natural numbers 0, 1, 2, . . ..
Then we try listing (i.e., we try to recursively enumerate) all S-total recursive functions, that is, those recursive functions that S can recognize as total, or better, which S can prove to be total. This is the starting point of our argument, which stems from Kleene (1936):
- We need two preliminary suppositions: (1) first, axiomatic system S is supposed to be consistent (i.e., it doesn’t prove a contradiction such as, e.g., 0 ≠ 0). (2) Also, S must be sound, that is, S doesn’t prove sentences that are false in the standard interpretation for arithmetic.
- Start the program that lists the theorems of S.
- Pick up those theorems that say: “Function f is total and computable.”
- Out of that, we can build another list, f₀ , f₁ , f₂ , . . ., of S-total computable functions (functions that are proved as such in S), together with their values:
f₀(0), f₀(1), f₀(2), f₀(3), …
f₁(0), f₁(1), f₁(2), f₁(3), …
f₂(0), f₂(1), f₂(2), f₂(3), …
f₃(0), f₃(1), f₃(2), f₃(3), …
… - Now define a function F:
F(0) = f₀(0) + 1
F(1) = f₁(1) + 1
F(2) = f₂(2) + 1
… - F is different from f₀ at value 0, from f₁ at 1, from f₂ at 2, and so on.
We can now conclude our reasoning. The f₀ , f₁ , f₂ , . . . functions are said to be provably total in our theory S, as they are proved to be total functions and appear as such in the listing of the theory’s theorems. However, F cannot be provably total in S, since it differs at least once from each function we have listed. Yet F is obviously computable and total in the standard model for arithmetic, and given programs for the computation of f₀ , f₁ , f₂ , . . . we can compute F too.
So the sentence “F is total” cannot be proved in our theory.
Also, if we suppose that the theory is sound, that is, if it doesn’t prove false facts, then the sentence “F isn’t total” cannot be proved too, as F is clearly total in the so-called standard model for arithmetic. Therefore, it is an undecidable sentence within our theory S.
Ladies and gentlemen:
“F is total” and “F isn’t total” are examples of the Gödel incompleteness phenomenon in S: they are sentences that can neither be proved nor disproved within S. And because of the soundness of our theory, “F is total” is, we may say, naively true in the standard interpretation for the arithmetics of S.
We call “F is total” and “F isn’t total” undecidable sentences in S. This example is quite simple and has an obvious mathematical meaning: it talks about computer programs and their domains. So, Gödel incompleteness does matter, after all.
Gödel incompleteness does matter, after all.
We can say that any two Zermelo–Fraenkel axiomatizations as sketched above, have the same undecidable sentences. This means that, for a wide variety of constructions, choosing a particular axiomatics is just a matter of taste. It won’t affect the results we can derive (or that we can’t derive) from our axiomatic framework. For more details, see da Costa and Doria (2007).
Axiomatization of Social Sciences
We can extend the preceding techniques to several scientific domains. For example, the bulk of economics, as presented, say, in Samuelson’s Foundations of Economic Analysis (Samuelson, 1967), or some specific results, such as the Nash equilibrium theorem (da Costa and Doria, 2005), easily fit within our construction.
Tsuji et al. (1998) show that it may be impossible to compute equilibria in finite games. Our results, therefore, entail the incompleteness of the theory of Arrow–Debreu equilibria and the incompleteness of the theory of finite games with Nash equilibria.
Equilibrium prices in competitive markets are in general noncomputable.
Whenever we describe social phenomena by dynamical systems, uncertainties in forecasting are usually supposed to be due to the nonlinearities in the systems considered, that is to say, they are related to the sensitivity those systems exhibit when small changes are made in the initial conditions. Linear systems do not have that kind of behavior, and so are supposed to be strictly deterministic.
Our results contradict that belief. We argue that equilibrium prices in competitive markets are in general noncomputable, and so fall outside the scope of the techniques available in the usual formal modeling tools; competitive market equilibrium is, however, equivalent to determining a minimax solution for a noncooperative game, which is a linear problem. So, there are also obstacles to forecasting when one deals with linear systems.
Application: Economic Planning
Those results have an immediate consequence for a question of both historical and practical importance: the controversy on economic planning between Ludwig von Mises and Oskar Lange (see, on that controversy, Seligman (1971, I, p. 115ff)).
The central problem of economic planning is an allocation problem. Very frequently, allocation is to be done on the basis of maximizing (or minimizing) simple functions over finite sets. We proved that trouble is to be expected even when the problem of planning is reduced to the problem of determining equilibria in finite noncooperative Nash games, which is formally equivalent to the determination of equilibrium prices in a competitive market.
Building on Rice’s theorem, da Costa and Doria (2014) show that for any set of policies, there will be a state of the economy for which the action of those policies will be algorithmically unpredictable. So, the main argument by Lange in favor of a planned economy (by the way, an argument also shared by von Mises) clearly breaks down. Lange thought that given the (possibly many) equations defining an economy, a huge and immensely powerful computer would always be able to figure out the equilibrium prices, therefore allowing (at least theoretically) the existence of an efficient global policymaker. However, our results (as well as the weaker previous results by Lewis (1991) and Lewis and Inagaki (1991)) disprove Lange’s conjecture.
Those who argue that “the market knows better” may find strong theoretical support in our conclusions.
Therefore, those who argue that “the market knows better” may find strong theoretical support in our conclusions (or in Lewis’ already quoted results), since the equilibrium point is reached (at least according to theory) while we cannot, in general, compute it beforehand.
Conclusion: Dealing with Undecidability
We conclude this short article by asking: How to deal with undecidabilities?
There are two possible opposing views concerning Gödel-like undecidable statements in mathematics.
Following the first view, Gödel-like undecidable sentences are usually seen as warning posts that indicate blocked routes in axiomatic systems; according to that viewpoint, they mean that one can’t go farther along some direction. They were already known to appear in lost back-alleys; yet, as told here, the authors had long striven to show that the incompleteness phenomenon is part of the actual practice in any axiomatized science, and their endeavor proved a fruitful one when they showed that simple questions in dynamical systems theory (“Given a dynamical system, can we check whether it is chaotic? Can we prove that it is chaotic?”) led to undecidability and incompleteness (see da Costa and Doria, 1991). We call that the “negative” viewpoint, since it is usually supposed to imply that incompleteness means that there is an essential deficit in our knowledge when it is obtained through some formal system.
Assuredly incompleteness means that we can’t compute some result. But should we take that fact as some kind of absolute obstacle to our knowledge of the world through formal languages?
Undecidable sentences are seen as degrees of freedom, as bifurcation points in our theories that reveal inner freedom and open possibilities.
The second point of view is the “optimistic” one; it is the position adopted by the author. Undecidable sentences are seen as degrees of freedom, as bifurcation points in our theories. They reveal some kind of inner freedom in the possibilities we have when trying to describe the world within a formal system. They show the existence of open possibilities, choices available in the formalism; they cannot be looked upon as limitations to our knowledge.
This article is based on Doria (2017).
References
- Chaitin, G. J., da Costa, N. C. A., & Doria, F. A. (2011). Gödel’s way. CRC Press.
- da Costa, N. C. A., & Doria, F. A. (1991). Undecidability and incompleteness in classical mechanics. International Journal of Theoretical Physics, 30, 1041–1073.
- da Costa, N. C. A., & Doria, F. A. (1994). Suppes predicates and the construction of unsolvable problems in the axiomatized sciences. In P. Humphreys (Ed.), Patrick Suppes: Mathematician, Philosopher. Kluwer Academic Publishers.
- da Costa, N. C. A., & Doria, F. A. (2005). Computing the future. In K. V. Velupillai (Ed.), Computability, complexity, and constructivity in economic analysis. Blackwell.
- da Costa, N. C. A., & Doria, F. A. (2014). On an extension of Rice’s theorem and its applications in mathematical economics. Advances in Austrian Economics, 18, 237–257.
- Doria, F. A. (Ed.). (2017). The limits of mathematical modeling in the social sciences: The significance of Gödel’s incompleteness phenomenon. World Scientific.
- Gödel, K. (1931). On formally undecidable propositions of Principia Mathematica and related systems. (B. Meltzer & R.B. Braithwaite, Trans.). Dover Publications.
- Kleene, S. C. (1936). General recursive functions of the natural numbers. Mathematische Annalen, 112, 727–742.
- Lewis, A. A. (1991). On Turing degrees of Walrasian models and a general impossibility result in the theory of decision making (Preprint). University of California at Irvine, School of Social Sciences.
- Lewis, A. A., & Inagaki, Y. (1991). On the effective content of theories (Preprint). University of California at Irvine, School of Social Sciences.
- Samuelson, P.A. (1967) Foundations of Economic Analysis: With a New Introduction. Atheneum.
- Seligman, B. B. (1971). Main currents in modern economics, I–III. Quadrangle Books.
- Suppes, P. (1988). Scientific structures and their representation (Preliminary version). Stanford University.
- Tsuji, M., da Costa, N. C. A., & Doria, F. A. (1998). The incompleteness of the theory of games. Journal of Philosophical Logic, 27, 553–568.
Francisco Antônio de Moraes Accioli Dória (b. 1945) is a Brazilian mathematician, philosopher, and genealogist. He received his B.S. in Chemical Engineering from the Federal University of Rio de Janeiro (UFRJ), Brazil, in 1968 and then got his doctorate from the Brazilian Center for Research in Physics (CBPF), advised by Leopoldo Nachbin in 1977. Dória worked for a while at the Physics Institute of UFRJ, and then left to become a Professor of the Foundations of Communications at the School of Communications, also at UFRJ. Dória held visiting positions at the University of Rochester (NY), Stanford University (CA), and the University of São Paulo (USP). He is currently Professor of Communications, Emeritus, at UFRJ and a member of the Brazilian Academy of Philosophy.
His main achievement (with Newton da Costa) is the proof that chaos theory is undecidable (published in 1991), and when properly axiomatized within classical set theory, is incomplete in the sense of Gödel.