On a "Humean" Best System Account (BSA) of laws of nature, the fundamental laws are the axioms of the system of laws that best combines brevity and informativeness.
An interesting consequence of this is that, very likely, no amount of
advances in physics will
suffice to tell us what the fundamental laws are: significant advances
in mathematics will also be needed. For suppose that after a lot of
extra physics, propositions formulated in sentences p1, ..., pn
are the physicist’s best proposal for the fundamental laws. They are
simple, informative and fit the empirical data really well.
But we would still need some very serious mathematics. For we would need to know there isn’t a simpler collection of sentences {q1, ..., qm} that is logically equivalent to {p1, ..., pn} but simpler. To do that would require us to have a method for solving the following type of mathematical problem:
- Given a sentence s in some formal language, find a simplest sentence s′ that is logically equivalent to s,
in the case of significantly non-trivial sentences s.
We might be able to solve (1) for some very simple sentences. Maybe there is no simpler way of saying that there is only one thing in existence than ∃x∀y(x=y). But it is very plausible that any serious proposal for the laws of physics will be much more complicated than that.
Here is one reason to think that any credible proposal for fundamental laws is going to be pretty complicated. Past experience gives us good reason to think the proposal will involve arithmetical operations on real numbers. Thus, a full statement of the laws will require including a definition of the arithmetical operations as well as of the real numbers. To give a simplest formulation of such laws will, thus, require us to solve the problem of finding a simplest axiomatization of the portions of arithmetic and real analysis that are needed for the laws. While we have multiple axiomatizations, I doubt we are at all close to solving the problem of finding an optimal such axiomatization.
Perhaps the Humean could more modestly hope that we will at least know a part of the fundamental laws—namely the part that doesn’t include the mathematical axiomatization. But I suspect that even this is going to be very difficult, because different arithmetical formulations are apt to need different portions of arithmetic and real analysis.
If we assume that human beings are not more computationally capable than Turing machines, is the optimal axiomatization problem even likely to be decidable? There is a known problem that might have relevance to this one (I'm not sure, though): Given a Turing machine M, let [M] denote the length of the string describing M. Say that M is minimal if there is no Turing machine M' equivalent to M such that [M'] < [M]. The problem of determining whether or not M is minimal is undecidable and in fact also unrecognizable. Perhaps a reduction can be made from this problem to the problem of optimal axiomatization? Note that I haven't fully thought this through, but this result about minimal Turing machines sprang to mind as I read this post, so I thought I would share. :-)
ReplyDeleteVery interesting!
DeleteI bet you're right that the optimal axiomatization problem is not decidable in general. But we probably can get solutions in special cases.
For instance, there is no shorter axiomatization of "there is one entity" in FOL than Ayx=a (assuming a syntax that doesn't require a quantifier to be set off from an atomic formula with parens or a space or anything like that). Proof: It can be shown that any consistent sentence that doesn't use = has a model with more than one entity. So the axiomatization must include =. Any consistent sentence that has no quantifiers has a model with more than one entity. So there must be a quantifier. Thus, we need to have a minimum of two characters for a quantifier, and three for a formula with =, so we need a minimum of 5, and that's what my proposed sentence has. With a little more work, one can show that all optimal axiomatizations are of the form Axx=a or Axa=x for some name a.
Here's a result in the other direction. Let's make up a language for creating schematic axiomatizations. This language includes FOL statements for ordinary axioms, as well as some terminology S(s,c) for including a schema s subject to some conditions c (e.g., s might be a formula with a blank inside it, and then c specifies how the blank is to be filled out).
Theorem: Suppose Q is the optimal schematic axiomatization of a theory that contains a sufficiently large fragment of set theory. Let n be the length of Q. Let Opt(T,n) be the proposition that the optimal recursive axiomatization of T is n. Then Opt(T,n) cannot be proved from T.
Proof: We assume that the fragment T of set theory is large enough to have no finite models and contain enough arithmetic for the Second Incompleteness Theorem and to run the following argument: No consistent schematic axiomatization of length 4 or less is such as to have no finite models. For it can't be schematic, as the schematic ones always have length 5 or more. So it must be non-schematic. But any sentence that is consistent and has no finite models has at least one quantifier. If it is of length 4 or less, it must be of the form qxFx for a quantifier x and a unary predicate F. Every such sentence has finite models. So, n is at least 5. Now, if n is at least 5, then Opt(T,n) proves that T is consistent, since any inconsistent theory can be axiomatized with length 4: ~a=a.
So, T can't prove Opt(T,n).
Could one maybe hope for the decidability of the following proposition, though? "If Con(T), then Opt(T,n)"? I doubt it, but it's not so trivial then.
This comment has been removed by the author.
ReplyDelete