Monday, November 03, 2008 ... Français/Deutsch/Español/Česky/Japanese/Related posts from blogosphere

More really is the same thing

A previous article about the same topic:

Laughlin vs reductionism
In September 2008, Mile Gu et al. posted a preprint called
More really is different
which is an updated version of the 1972 article by Phil W. Anderson,
More is different.
In the new paper, they declare that it is possible to create a physical system that mimics a Turing machine. And because there are many difficult and undecidable statements about the Turing machines, the physical system they design also hides a lot of questions that cannot be decided by pure thought applied to the fundamental laws of physics, they say.

I have never understood why people like to amuse themselves with similarly bizarre statements.

Gödel's incompleteness theorem

My countrymate Kurt Gödel has shown that every axiomatic system that is at least as powerful as set theory including integers admits a proposition that can be neither proved nor disproved within the system itself. But it seems to me that what many people don't understand is the fact that at the very same moment when the proposition is shown to be unprovable, it is also proved to be correct - within a slightly extended system of logical methods.

The proposition is a refined version of the sentence "this proposition cannot be proved within the given axiomatic system". It's clear that this statement cannot be proved - because provable statements have to be correct which would mean that it cannot be proved (because that's what the sentence says): a contradiction. Also, the statement cannot be disproved because it would be false which would mean that it can be proven - another contradiction.

So the statement can be neither proven nor disproved within the system. But because the statement says nothing else - it says that it cannot be proven - the statement is clearly true. ;-) Gödel's theorem only shows the inevitable limitations of a fixed axiomatic system. It doesn't prove the limits of rational thinking. And I am confident that it is not possible to prove limits of rational thinking because there are no such limits.

Languages and particular "technologies" and "methods" may have limitations but rational thinking per se cannot have any limitations.

You know, some people thought that Fermat's Last Theorem (FLT) would never be proven or disproven because it is analogous to one of those undecidable propositions due to Gödel. I think that such expectations have always been completely irrational and unsubstantiated. FLT is a very well-defined proposition about integers that is clearly either correct or wrong. If it is wrong, there must exist a counterexample. It must be possible to write it down, at least if you forget that our Universe cannot contain more than 10^{120} digits (de Sitter entropy bound) - a fact that hopefully has nothing to do with universal limitations of mathematics. If the theorem is correct, and you bet it is, there may exist a proof and laziness is the only well-understood reason to think that the proof would never be found. Of course, today we know that a proof of FLT exists but some people will only move their statements about the limitations of rational thinking by a few meters.

All the undecidable statements in the context of Gödel's theorems are constructed to exploit a weakness of a particular system of axioms (or language). But there can always exist complementary logical methods that make it possible - and often very easy - to decide about the validity of such statements.

Unknown properties of ground states

Mile Gu et al. argue that some of the systems they consider have ground states whose properties cannot be determined. That's a very strange comment. If a system (a Hilbert space and a Hamiltonian) is fully well-defined, the question about the ground state has an answer. It may be difficult to find it out but it clearly can't be impossible in principle. If formal calculations are too hard and if smart tricks and dualities are unavailable, one may always try numerical calculations or an experiment.

The ground state may either be unique or degenerate. Both options are possible and potentially interesting. None of them makes the questions about the system "undecidable". Materials may behave as Fermi liquids, Bose-Einstein condensates, crystals, or quasicrystals. There's no problem in either. And several different "regimes" may want to co-exist. In that case, we usually deal with phase transitions. They are a part of theoretical physics that is close to condensed matter physics but that doesn't mean that they can't be studied fully rationally, by an application of mathematical methods to the elementary laws.

Quite on the contrary: a major goal of a fundamental physicist's thinking is to determine the different kinds of behavior that a physical system may exhibit. These new phenomena often deserve new concepts, new vocabulary, new (often approximate) equations. They might be called "emergent" by some people. But if they're emergent, that doesn't mean that they can't be derived from a more fundamental theory. Quite on the contrary: the word "emergent" is essentially equivalent to "derived" in this context.

In fact, when Anderson says "more is different", he wants you to believe that "more is more difficult". But in fact, a key insight of modern theoretical physics is that "many is usually easier". If we consider a new limit where something goes to infinity, there typically exists a new dual description of the situation that drastically simplifies. In many cases, the validity of this new description can be proved rigorously. In others, the proof is not yet available but we are basically certain that the dual description is correct. Thermodynamics as a large N limit of statistical physics is an example of the first group; the AdS/CFT correspondence for a large N is an example of the latter group even though a complete proof of the equivalence could emerge soon.

In the reductionist scheme of the world, we are not really aware of a major "gap" that would allow us to confidently say that life cannot be derived from the basic equations of quantum mechanics. Our understanding is not perfect but it is good enough to make the existence of a big gap with dragons very unlikely.

Sociology and the role of history and initial conditions

Even though the complicated effects may be reduced to the elementary processes in principle, it is obvious that different scientists are specialized to understand the world at different levels. Some people care about the fundamental questions; others are interested in numerous composite, usually approximate notions that are independent of the underlying microscopic details. Some people are good at something, others are good are something else.

But none of these things implies that there is something wrong with reductionism.

When we study a class of questions, we need to know several things that can be, roughly speaking, categorized to
  • basic objects and concepts
  • basic relationships and forces between them and other laws
  • history or initial conditions
  • conventions and terminology
Now, a physicist - especially a fundamental physicist - will discard the last entry, conventions and terminology. Almost by definition, they're not a part of physics. They're still needed for people to communicate with others but they're the part that belongs to sociology, not a part of the truth about a natural science. On the other hand, the first category - basic objects - are meant to be essentially mathematical concepts. They're whatever is needed to create a mathematically rigorous framework.

People in other disciplines won't view the difference between the "basic objects" and "terminology" so sharply. Why? It's because they're more sloppy. A part of the sloppiness is justified by the inevitably sloppy character of the questions they're interested in; a part of the sloppiness is not justified by anything.

If you go from fundamental physics all the way to humanities, the importance of the fourth category, "conventions and terminology", will increase. Once you get to the literary criticism, the importance of the latter group will be so huge that, in fact, many of the people will tell you that it is impossible for science to have any meat at all; by "meat", I mean the objective and rigorous "basic concepts". Well, they have never seen any "meat", certainly not in their own discipline, so they suppose that no one else has seen it either. This is a completely opposite attitude to that of fundamental physicists because the latter folks completely dismiss "conventions and terminology" as not being a part of science.

But even if we talk about more serious disciplines such as condensed matter physics, it is true that the difference between the "basic concepts" and "terminology" gets obfuscated a bit. The more "emergent" discipline we consider, the more obfuscated these differences are.

We have spent some time with "basic objects" and "conventions". What about the other categories?

The "basic laws" exist in all disciplines except that the more "emergent" disciplines usually talk about less rigorous, less reliable, and less regular "basic laws" than the laws of fundamental physics. But again, the laws can be derived from more fundamental levels of knowledge i.e. from more "microscopic" disciplines. Even the laws of thermodynamics can be derived from statistical physics even though people like Sean Carroll will never understand how is that possible. Quite typically, what we want to derive is not even accurately formulated so it is not surprising that there is no rigorous proof, either. But this fuzziness of the proofs is due to the inherent fuzziness of the very questions that the emergent disciplines study, not due to a failure of reductionism.

Finally, I haven't discussed the "history and initial conditions" yet.

Once again, it is supposed to play almost no role in particle physics. Experiments are repeatable and the physical laws we're interested in are universally valid. However, the more emergent discipline we consider, the more important "history and initial conditions" typically become.

Physicians study the human body (and do much more material things with it, but we don't want to go in this direction here). Can we derive the approximate DNA of humans from the elementary laws of physics? The answer is obviously No. The humans only evolved the way they did because of millions of coincidences in the evolution of life. Most of them were unpredictable due to the inherent probabilistic character of quantum mechanics.

Nevertheless, whenever you want to predict or retrodict something about the humans, you should better know what the humans are - what is their anatomy, physiology, psychology, and DNA code. This information about the human characteristics may be sold as history or as the information about the world at a particular moment (initial conditions). This important information about the human character will never be derived from the fundamental laws of physics because, as we can prove, the probabilistic nature of the relevant quantum events is indisputable.

Different disciplines need "history" to different extents but I would say that condensed matter physics doesn't need much of it. The more "repeatable" the evidence in a discipline is, the less the discipline depends on the "history". Both particle physics and condensed matter physics are supposed to be "fully repeatable" so they're not about the history.

On the other hand, evolution of animals is not quite "reproducible" in practice which is why the historical component is rather important - although evolutionary biology is surely not just about the history. This component will never be derived from the fundamental laws but there's nothing shocking or disappointing about this fact, either. Random events are not supposed to be predictable.

I could continue up to the history of the civilization where the relative importance of the historical component is even higher. Nevertheless, even this discipline needs to understand some laws (of human behavior etc.). Many of them may be (approximately) derived from more fundamental disciplines.

Fundamental physics itself may depend on the "history", too. The more the anthropic people are correct, the more important a role the "history" played in the selection of the Universe around us from the landscape of the full theory. The more important the "history" was, including its details, the less explainable various crucial features of the world will be.

Let's not forget that the world can also be much more explainable than what almost anyone thinks: the initial conditions of the Universe, normally understood as the information added on top of the laws of physics, can actually be another law of physics (Hartle-Hawking state etc.). However, even this state only tells us about the probabilities and we're not quite sure how essential the probabilistic character of such predictions is.

Summary

If you allow me to summarize, all the accurate results of a discipline can be reduced to mathematical procedures applied to the basic laws of more fundamental disciplines (i.e. to fundamental physics). However, the conventions, terminology (including the useful emergent concepts), and history (including random events that turned out to be important) cannot be derived from the more fundamental disciplines and they play increasingly important roles in increasingly "emergent" disciplines.

But none of these things is an equally good "supplement" of the basic laws of physics. Indeed, the basic laws of physics are supposed to be "complete". In principle, they answer all questions that can be answered. Any independent additional law that would be just "added" would make the union logically inconsistent. The freedom to play this game that avoids contradictions is limited to the conventions, terminology, and history.

Add to del.icio.us Digg this Add to reddit

snail feedback (11) :


reader Zephir said...

Prof. Laughlin's stance should be understood by the way, it has no meaning to try to extrapolate the theories too far, until we don't understand their postulates well.

It's not a reductionistic stance, rather sort of logical optimization of approach.

For example, when we start to develop a formal theory from two or more sets of mutually inconsistent postulates, we'll always finish in singular landscape of many possible solutions, because of poorly conditioned condition at the very beginning.

Under such circumstances has no meaning to develop some extrapolations based on consecutive logic too deeply - we should rather develop the supersymmetric part of theory, based on parallellistic approach, i.e. the intuition.


reader gh said...


But because the statement says nothing else - it says that it cannot be proven - the statement is clearly true. ;-)


I think you're wrong here.

--gh


reader Lumo said...

Dear gh, could you please provide us with a little bit more than just your apparently untrue proposition created by negating someone else's correct proposition? In your current form, your contribution is just noise here.


reader gh said...

Lubos.

First:
Gödel's theorem only shows the inevitable limitations of a fixed axiomatic system.

Starting with "a fixed axiomatic system" is usually called "mathematics".

Again:
I am confident that it is not possible to prove limits of rational thinking because there are no such limits.

You asserted what you claimed to be able to prove.

In the second case your argument is circular. Thomas Aquinas used the same technique in one of his proofs of the existence of God. He assumed there was a first cause and identified it with God, thus proving the existence of God, which he had just assumed.

I bring up Aquinus, only to illustrate that we are in danger of descending into religious arguments. Certain topics in philosophy are difficult to approach directly -- see the writings of Jose Ortega y Gasset



--gh


reader Lumo said...

Dear gh,

starting with an axiomatic axiomatic system is just one of conditions of doing mathematics. But starting with one fixed axiomatic system can be a very small portion of mathematics, especially if the axiomatic system is not "powerful" enough.

In this case, the axiomatic systems under considerations are incomplete only in the sense that one, very contrived type of statements, specifically designed to be undecidable by the system, remains undecidable by the system. However, in other cases, a fixed axiomatic system may be much more limited. For example, the old-fashioned axioms of Euclidean geometry miss 99.9% of the topics in modern geometry.

There is nothing religious about the statements above. They are inseparable ingredients of rational thinking.

I don't think that you have shown a glimpse of evidence that there is anything incorrect or "circular" about any of my arguments, and the evaporation of your attention somewhere to religion, Aquinus, and Ortega indicates that you really don't want to (or can't) focus on the real topic that is being discussed here.

Best wishes
Lubos


reader gh said...

especially if the axiomatic system is not "powerful" enough

Godel's proof is valid for any system, "powerful enough" to include arithmetic. Making the system more "powerful" does not help.

I think we have a different idea about what consists of "religious" arguments so I'll just drop that.

To me, the second quote in my previous post is pretty clearly a circular argument on it's face and if you can't see that then this conversation can only degenerate into a discussion of syntax and semantics, topics which are far beyond my pay-grade ;-).

--gh


reader Lumo said...

Gh: "Making the system more "powerful" does not help."

LM: Well, it depends what one needs a help with. If he wants to decide whether the particular statement undecidable by the given axioms is true or not, which is what we wanted, making the system more powerful - using a logic that couldn't be used within the original system - surely does help, and I have very explicitly proven that it does. The "unprovable" proposition constructed by Gödel is true because it is equivalent to the statement that it was unprovable within the smaller system, which it was. The system itself couldn't see whether it was able to prove it, but I can.

You haven't found any mistake in the arguments leading to this conclusion and you are just bullshitting around.

Concerning your accusations of circularity, you first accused *me* of having written something circular. But you have neither identified what was circular nor provided us with any evidence that the thing was circular. Instead, you began to talk about Aquinas, God, and religion who have clearly nothing to do with this very technical debate.

I pointed it out, and you completely changed your statement about circularity. Now, it is your statement ("second quote"), not mine, that is supposed to be circular. Well, that's a difference. However, your new assertion is nonsensical, too, because your comments above didn't include anything such as "the second quote", and even if they did, these quotes clearly have nothing to do with the topic of the provability of mathematical propositions within various systems of logic.

So please be aware that this is the end of the discussion and further comments from you that will look as noise much like your previous comments will be rejected because I don't want the individual pages of postings on this blogs to be overflooded with garbage.


reader Csaba Szepesvári said...

``But it seems to me that what many people don't understand is the fact that at the very same moment when the proposition is shown to be unprovable, it is also proved to be correct - within a slightly extended system of logical methods.''

This might confuse some people as it seems to suggest that once you prove that a statement is undecidable, you have also proved that it is true. This is not true in general.

A famous example is Euclid's parallels postulate and the (reduced) Euclidean geometry when this particular axiom is left out. If you add the converse statement to the reduced set of axioms, you get non-Euclidean geometry, a very useful and widely studied system that on the top seems to fit well the way our universe works.
Another example is that the continuum hypothesis (CH) is undecidable in ZF and in fact there are alternatives to the CH that together with ZF make up other consistent systems.

So what seems to be true is that in many cases undecidable statements represent real alternatives. Does this mean that there are limits of rational thinking (i.e., what you can derive)? Yes, definitely. However, a rational agent may just consider all possible alternatives and then reject those that do not seem to match experience when such experience becomes available.


reader Lumo said...

Dear csaba, no doubt about that. Different systems of axioms about objects can be useful and interesting.

But your examples, like the Euclidean and non-Euclidean geometry, are about axioms that manifestly can be incomplete and are incomplete.

On the other hand, Gödel incompleteness theorem refers to statements about objects such as integers and their sets where a clear Yes/No answer simply should exist in each case. It's a place in maths where we didn't expect incompleteness because every integer either has some discrete property or not.

It is this case, axiom systems where the incompleteness seems counterintuitive, where I claim that one answer is preferred, even if it is not proved in a the pre-agreed system of axiomatic rules.


reader Csaba Szepesvári said...

Dear Lumo,

Should every statement about natural numbers be true or false? To a Platonist the answer is obviously yes. Should the cardinality of continuum be exactly located on the aleph scale? Where else could it be? At least, this is what a Platonist thinks.

Platonism is the normal way we (mathematicians) work. As Podniask says here, Platonism on weekdays, Advanced Formalism on weekends when we think about mathematics (quote abbreviated).

On another note, take a Gödel sentence s for a consistent theory T. We know that neither s, nor the NOT s is a logical consequence of T. Hence, we can add both s and NOT s to T and get a consistent theory.

Perhaps it is surprising that we can add NOT s and still get a consistent theory. So why can we do this? Can it be that when we add NOT s we get an inconsistent theory? Assume this holds. Take any model M of T. Then since T' = (T,NOT s) is inconsistent, M cannot be a model of T'. But this means that NOT s does not hold in M and therefore s holds in M (a statement must be either true or false in any model). Since M was arbitrary, this means that s is a logical consequence of T (s holds in every model of T). However, by assumption neither s, nor NOT s is a logical consequence of T, hence we got a contradiction, proving that T, NOT s cannot be inconsistent.

That is, you cannot really tell if s is true or false. It can be either way. When we say we see that it is true, we are Platonist:)


reader Lumo said...

Dear Csaba, I understand and agree with all the things you say, except that I don't consider these things - like the Continuum Hypothesis - to be propositions about integers.

You know, a "wider" Platonist may believe in the existence of those vast sets of all functionals on functions on reals, or whatever.

While these visualizations are helpful, I am not really promoting the belief of this kind. I am a Platonist in the narrow sense who believes in the existence of mathematical objects that can actually be described by finite rules.

All these objects are, by construction, countable. Yes, I can say that various prescriptions define a function which is an element of a huge set of functions, in the sense of cardinality. Yet, I don't necessarily say that the remaining elements of the large set have to "exist".

All these questions about their existence are "unphysical" in my sense. The word "unphysical" has a very particular meaning for the mathematical approach: the word means that mathematicians shouldn't be surprised if these statements are undecidable. It doesn't matter. They are inconsequential, too.

Already the very statement that the "real numbers are uncountable" - which is just the first, trivial step towards asking things like the continuum hypothesis - is just a linguistic curiosity for me.

The set of those real numbers whose existence I take "really seriously" - those that can actually and accurately be described by a finite rule, a finite algorithm - is clearly countable. The precise labelling of those numbers by integers depends on the "language" we choose but it seems clear to me - and I don't know any counterevidence - that all natural real numbers that appear anywhere, in calculus or physics, have a finite label according to any language.

By choosing different language (axiomatic system, algorithms), you can "construct" numbers that would be "unconstructable" in a previous language (by the modified diagonal trick) but all these numbers are "physically uninteresting", and moreover, we should eventually see that all these numbers are "constructible" with some language.

One could try to create new strange numbers by constructing real numbers that avoid all algorithms in the classes above, and so on, but the more we're doing these tricks, the more unnatural real numbers we will construct. Moreover, I think that all of these are in my class, anyway.

The question whether the real numbers are countable or not is already unphysical.

I can imagine that only the "constructible", describable real numbers exist. And if I avoid all investigation into the particular labeling of these real numbers by integers ;-), I also avoid all the additional real numbers that are normally used to prove that the real numbers are uncountable.

You may think that I am just hiding my head into sand but I am not. This rule gives me a pretty good picture which questions about integers - or any constructible reals or any constructible more complicated objects - are actually physical. The rest is not necessarily physical and I don't insist that they should be decidable.

But there is a very clear class of questions - which contains e.g. all questions that anyone would ever care in geometry, calculus, algebra, or physics - that simply have to be decidable. Do you agree that even before the proof of Fermat's Last Theorem was known, it was unthinkable that the proposition of the theorem was undecidable?

I think that it obviously had to be decidable. Now, someone could choose different (weaker) axioms about integers where FLT would be undecidable. But I would have trouble classifying him as a mathematician - he would perhaps be a generalized logician but not mathematician in my counting. I simply believe that all mathematicians must agree about the narrow class of propositions about integers.

It's the hard core of mathematics, and I am convinced that every meaningful statement in mathematics can be pretty much boiled down to these solid, surely decidable statements about integers. We can also imagine things based on larger sets that are "not" integers but that's just a helpful trick for our intuition. Real maths can work with the "linguistic" description of all these objects in terms of finite sequences of math symbols. And with these rules, everything I care about has to be decidable.