= 27d567bc2d48d9f40e9ccc20ea370b15)
paper-machine comments on The Pascal's Wager Fallacy Fallacy - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (121)
You reference a popular idea, something like "The integers are countable, but the real number line is uncountable." I apologize for nitpicking, but I want to argue against philosophers (that's you, Eliezer) blindly repeating this claim, as if it was obvious or uncontroversial.
Yes, it is strictly correct according to current definitions. However, there was a time when people were striving to find the "correct" definition of the real number line. What people ended up with was not the only possibility, and Dedekind cuts (or various other things) are a pretty ugly, arbitrary construction.
The set containing EVERY number that you might, even in principle, name or pick out with a definition is countable (because the set of names, or definitions, is a subset of the set of strings, which is countable).
The Lowenheim-Skolem theorem says (loosely interpreted) that even if you CLAIM to be talking about uncountably infinite things, there's a perfectly self-consistent interpretation of your talk that refers only to finite things (e.g. your definitions and proofs themselves).
You don't get magical powers of infinity just from claiming to have them. Standard mathematical talk is REALLY WEIRD from a computer science perspective.
That's not the Lowenheim-Skolem Theorem. You've confused finite with countable (i.e. finite or countably infinite). Here's a simple example of a theory that can't be satisfied with a finite model.
Any model that satisfies this must have at least 1 element by axiom 1. Call it 0. s(0) != 0 so the model must have at least 2 elements. s(s(0)) != s(0) by axiom 2. So the model has at least 3 elements.
Suppose we have n distinct elements in our model, all obtained from applying s to 0 the appropriate number of times. Then we need one more, since s(s(...(s(n))) [applied n times] != s(s(...s(n))) [applied n-1 times] (this follows from axiom 2.)
So any model that satisfies these axioms must be infinite. (Incidentally, you can get theories that specify the natural numbers with more precision: see http://en.wikipedia.org/wiki/Robinson_Arithmetic).
Mathematicians routinely use "infinite" to mean "infinite in magnitude". For example, the concept "The natural numbers" is infinite in magnitude, but I have picked it out using only 19 ascii characters. From a computer science perspective, it is a finite concept - finite in information content, the number of bits necessary to point it out.
Each of the objects in the set of the Peano integers is finite. The set of Peano integers, considered as a whole, is infinite in magnitude, but finite in information content.
Mathematician's routine speech sometimes sounds as if a generic real number is a small thing, something that you could pick up and move around. In fact, a generic real number (since it's an element of an uncountable set) is infinite in information content - they're huge, and impossible to encounter, much less pick up.
Lowenheim-Skolem allows you to transform proofs that, on a straightforward reading, claim to be manipulating generic elements of uncountable sets (picking up and moving around real numbers for example), with proofs that claim to be manipulating elements of countable sets - that is, objects that are finite in information content.
In that tranformation, you will probably introduce "objects" which are something like "the double-struck N", and those objects certainly still satisfy internal predicates like "InfiniteInMagnitude(the double-struck N)".
However, you're never forced to believe that mathematicians are routinely doing impossible things - you can always take a formalist stance, pointing out that mathematicians are actually manipulating symbols, which are small, finite-in-information-content things.
Löwenheim-Skolem only applies to first-order theories. While there are models of the theory of real closed fields that are countable, referring to those models as "the real numbers" is somewhat misleading, because there isn't only one of them (up to model-theoretic isomorphism).
Also, if you're going to measure information content, you really need to fix a formal language first, or else "the number of bits needed to express X" is ill-defined.
Basically, learn model theory before trying to wield it.
I don't know model theory, but isn't the crucial detail here whether or not the number of bits needed to express X is finite or infinite? If so, then it seems we can handwave the specific formal language we're using to describe X, in the same way that we can handwave what encoding for Turing Machines generally when talking about Kolmogorov complexity, even though to actually get a concrete integer K(S) representing the Kolmogorovo complexity of a string S requires us to use a fixed encoding of Turing Machines. In practice, we never actually care what the number K(S) is.
Let's say I have a specific model of the real numbers in mind, and lets pretend "number of bits needed to describe X" means "log2 the length of the shortest theory that proves the existence of X."
Fix a language L1 whose constants are the rational numbers and which otherwise is the language of linear orders. Then it takes a countable number of propositions to prove the existence of any given irrational number (i.e., exists x[1] such that x[1] < u[1], ..., exists y[1] such that y[1] > v[1], ..., x[1] = y[1], ... x[1] = x[2], ..., where the sequences u[n] and v[n] are strict upper and lower bounding sequences on the real number in question).
Now fix a language L2 whose constants are the real numbers. It now requires one proposition to prove the existence of any given irrational number (i.e., exists x such that x = c).
The difference between this ill-defined measure of information and Kolomogrov complexity is that Turing Machines are inherently countable, and the languages and models of model theory need not be.
(Disclaimer: paper-machine2011 knew far more about mathematical logic than paper-machine2016 does.)
Whether a theory proves the existence of X may be an undecideable question.
How many bits it takes to describe X is an undecidable question when defined in other ways, too.
The definition "length of the shortest program which minimizes (program length + runtime)" isn't undecideable, although you could argue that that's not what we normally mean by number of bits.
Adding program length and runtime feels to me like a type error.