Comment author: [deleted] 08 June 2015 03:43:58PM *  6 points [-]

I recently stumbled upon the Wikipedia entry on finitism (there is even ultrafinitism). However, the article on ultrafinitism mentions that no satisfactory development in this field exists at present. I'm wondering in which way the limitation to finite mathematical objects (say a set of natural numbers with a certain largest number n) would limit 'everyday' mathematics. What kind of mathematics would we still be able do (cryptography, analysis, linear algebra …)?

In response to comment by [deleted] on Open Thread, Jun. 8 - Jun. 14, 2015
Comment author: TezlaKoil 08 June 2015 09:43:34PM *  16 points [-]

Is such a long answer suitable in OT? If not, where should I move it?

tl;dr Naive ultrafinitism is based on real observations, but its proposals are a bit absurd. Modern ultrafinitism has close ties with computation. Paradoxically, taking ultrafinitism seriously has led to non-trivial developments in classical (usual) mathematics. Finally: ultrafinitism would probably be able to interpret all of classical mathematics in some way, but the details would be rather messy.

1 Naive ultrafinitism

1.1. There are many different ways of representing (writing down) mathematical objects.

The naive ultrafinitist chooses a representation, calls it explicit, and says that a number is "truly" written down only when its explicit representation is known. The prototypical choice of explicit representation is the tallying system, where 6 is written as ||||||. This choice is not arbitrary either: the foundations of mathematics (e. g. Peano arithmetic) use these tally marks by necessity.

However, the integers are a special^1 case, and in the general case, the naive ultrafinitist insistance on fixing a representation starts looking a bit absurd. Take Linear Algebra: should you choose an explicit basis of R3 that you use indiscriminately for every problem; or should you use a basis (sometimes an arbitary one) that is most appropriate for the problem at hand?

1.2. Not all representations are equally good for all purposes.

For example, enumerating the prime factors of 2*3*5 is way easier than doing the same for ||||||||||||||||||||||||||||||, even though both represent the same number.

1.3. Converting between representations is difficult, and in some cases outright impossible.

Lenstra earned $14,527 by converting the number known as RSA-100 from "positional" to "list of prime factors" representation.

Converting 3\^\^\^3 from up-arrow representation to the binary positional representation is not possible for obvious reasons.

As usual, up-arrow notation is overkill. Just writing the decimal number 100000000000000000000000000000000000000000000000000000000000000000000000000000000 would take more tally-marks than the number of atoms in the observable universe. Nonetheless, we can deduce a lot of things about this number: it is an even number, and its larger than RSA-100. Nonetheless, I can manually convert it to "list of prime factors" representation: 2\^80 * 5\^80.

2 Constructivism

The constructivists were the first to insist that algorithmic matters be taken seriously. Constructivism separates concepts that are not computably equivalent. Proofs with algorithmic content are distinguished from proofs without such content, and algorithmically inequivalent objects are separated.

For example, there is no algorithm for converting Dedekind cuts to equivalence classes of rational Cauchy sequences. Therefore, the concept of real number falls apart: constructively speaking, the set of Cauchy-real numbers is very different from the set of Dedekind-real numbers.

This is a tendency in non-classical mathematics: concepts that we think are the same (and are equivalent classically) fall apart into many subtly different concepts.

Constructivism separates concepts that are not computably equivalent. Computability is a qualitative notion, and even most constructivists stop here (or even backtrack, to regain some classicality, as in the foundational program known as Homotopy Type Theory).

3. Modern ultra/finitism

The same way constructivism distinguished qualitatively different but classically equivalent objects, one could starts distinguishing things that are constructively equivalent, but quantitatively different.

One path leads to the explicit approach to representation-awareness. For example, LNST^4 explicitly distinguishes between the set of binary natural numbers B and the set of tally natural numbers N. Since these sets have quantitatively different properties, it is not possible to define a bijection between B and N inside LNST.

Another path leads to ultrafinitism.

The most important thinker in modern ultra/finitism was probably Edward Nelson. He observed that the "set of effectively representable numbers" is not downward-closed: even though we have a very short notation for 3\^\^\^3, there are lots of numbers between 0 and 3^^^3 that have no such short representation. In fact, by elementary considerations, the overwhelming majority of them cannot ever have a short representation.

What's more, if our system of notation allows for expressing big enough numbers, then the "set of effectively representable numbers" is not even inductive because of the Berry paradox. In a sense, the growth of 'bad enough' functions can only be expressed in terms of themselves. Nelson's hope was to prove the inconsistency of arithmetic itself using a similar trick. His attempt was unsuccessful: Terry Tao pointed out why Nelson's approach could not work.

However, Nelson found a way to relate unexpressibly huge numbers to non-standard models of arithmetic^(2).

This correspondence turned out to be very powerful, leading to many paradoxical developments: including finitistic^3 extension of Set Theory; a radically elementary treatment of Probability Theory and a new ways of formalising the Infinitesimal Calculus.

4. Answering your question

What kind of mathematics would we still be able do (cryptography, analysis, linear algebra …)?

All of it; modulo translating the classical results to the subtler, ultra/finitistic language. This holds even for the silliest versions of ultrafinitism. Imagine a naive ultrafinitist mathematician, who declares that the largest number is m. She can't state the proposition R(n,2^(m)), but she can still state its translation R(log_2 n,m), which is just as good.

Translating is very difficult even for the qualitative case, as seen in this introductory video about constructive mathematics. Some theorems hold for Dedekind-reals, others for Cauchy-reals, et c. Similarly, in LNST, some theorems hold only for "binary naturals", others only for "tally naturals". It would be even harder for true ultrafinitism: the set of representable numbers is not downward-closed.

This was a very high-level overview. Feel free to ask for more details (or clarification).


^1 The integers are absolute. Unfortunately, it is not entirely clear what this means.

^2 coincidentally, the latter notion prompted my very first contribution to LW

^3 in this so-called Internal Set Theory, all the usual mathematical constructions are still possible, but every set of standard numbers is finite.

^4 Light Naive Set Theory. Based on Linear Logic. Consistent with unrestricted comprehension.

Comment author: ChristianKl 25 May 2015 03:36:38PM 1 point [-]

I think time sense is best developed via setting intention.

If you set down to meditate, instead of using a timer you can set the goal of meditating for 20 minutes. That skill is trainable and with time you can get +1/-1.

It would also be interesting to couple on of those sleep stage based alarm clocks with a query for a guess of the current time when you awake.

Comment author: TezlaKoil 25 May 2015 05:13:54PM 0 points [-]

If you set down to meditate, instead of using a timer you can set the goal of meditating for 20 minutes. That skill is trainable and with time you can get +1/-1.

Interesting. I don't meditate, but I'll try this in other contexts (probably in tasks related to giving talks) and see how my time sense improves.

Comment author: LizzardWizzard 25 May 2015 11:15:23AM 0 points [-]

I can understand the compass part, it can be very useful and save your life onetime, but time-sense? For what the heck you might need this? In peoples world people wear watches or have timers on their smartphones, and in the world there's no people there's no time

Comment author: TezlaKoil 25 May 2015 02:30:51PM *  1 point [-]

In my case, the answer is simple: tutoring, teaching and lecturing. The feedback of watches and timers is completely inadequate: I can't "profile", I can't adjust my tempo in real time, et c.

Not to say that I prefer to have this information subconsciously. The information from the compass anklet was far more useful (and efficient) than glancing at my smartphone's compass every second would have been.

Comment author: Elo 25 May 2015 09:37:52AM 1 point [-]

I believe that having the magnet closer to your nerves gives you more sensation. the ability to sense if wires are live; the ability to feel the hum of a microwave or a laptop charger.

I know of someone who had one which was getting infected so he removed it; he described it as "like being blind" to be without it. (I can contact him and see if he can comment here if you are interested)

Comment author: TezlaKoil 25 May 2015 10:00:35AM 0 points [-]

I can contact him and see if he can comment here if you are interested

I would be very interested in hearing about his experience, especially since I'd love to replicate something like this externally.

Comment author: Vaniver 21 May 2015 06:59:40PM 4 points [-]

Wearing a vibrating compass anklet for a week. It improved my navigational skills tremendously.

Did you find the navigational skills lingered when you were in the same places (i.e. if you wore it around campus, you would then have a good map of campus) or did the improvement in skill disappear when you stopped wearing it?

Comment author: TezlaKoil 21 May 2015 07:22:03PM *  9 points [-]

The skills lingered, and for some amount of time, I was able to "feel" where the compass would be pointing in many places I visited while wearing the anklet.

From memory, I'm still able to tell the general direction of the magnetic north in many places.

Comment author: James_Miller 21 May 2015 06:08:47PM 3 points [-]

I would love to buy an already assembled anklet or belt vibrating compass that can fit both a child and adult for <$200.

Comment author: TezlaKoil 21 May 2015 06:56:08PM *  6 points [-]

I think the pre-assembled NorthPaw is available for $199 + shipping.

Comment author: TezlaKoil 21 May 2015 12:32:43PM *  19 points [-]

I have tried:

  • Wearing a vibrating compass anklet for a week. It improved my navigational skills tremendously. I have low income, but I would definitely buy one if I could afford it.

  • Listening to a 60 bpm metronome on a Bluetooth earpiece for a week (excluding showers). I got used to the sound relatively quickly, but I most definitely did not acquire an absolute sense of time. However, I noticed that during boring activities such as filling out paperwork, the ticking itself seems to slow down.

I will try:

  • Wearing an Oculus Rift that shows the Fourier Transform of what I would normally see. I'd like to know if I can get used to it, and if it improves my mathematical intuition.
Comment author: TezlaKoil 21 May 2015 12:12:36PM *  1 point [-]

The most well known and simple example is an implanted magnet, which would alert you to magnetic fields (the trade-off being that you could never have an MRI).

Can't we achieve the same objective by wearing a magnet ring or a magnet bracelet, without the serious downsides of having an implant?

Comment author: Lumifer 11 May 2015 07:03:42PM *  1 point [-]

Cosmetic changes can be highly functional. Ask any girl :-)

On a slightly more serious note, I tend to think of tranhumanist modifications as ones which confer abilities that unenhanced humans do not have. Opening beer bottles isn't one of them.

Comment author: TezlaKoil 12 May 2015 12:23:59AM *  4 points [-]

Would you consider a Wikipedia brain implant to be a transhumanist modification? After all, ordinary humans can query Wikipedia too!

In response to Truth is holistic
Comment author: TezlaKoil 23 April 2015 07:33:28PM *  11 points [-]

First of all, let me issue a warning: model-theoretic truth is a mathematical notion, which (a priori) doesn't have anything to do with the real-world sense of truth!

A short introduction to model theory follows. It is not LW quality, but hopefully it's good enough to answer some questions about MrMind's post. Prerequisites: merely some familiarity with formal reasoning, but I guess knowing the Mental Concepts of Model Theory doesn't hurt.

The 1st part is the general introduction to model theory, the examples about non-standard models are in the 2nd and 3rd parts.

1 Models explained

Axioms are the starting points of formal reasoning. A collection (system) of axioms is inconsistent if it is possible to prove a contradiction using them. E.g. consider the following system of three axioms.

  1. All men are mortal.
  2. Socrates is a man.
  3. Socrates is not mortal.

This system is inconsistent, because the contradiction "Socrates is mortal and Socrates is not mortal" is a consequence of the axioms. On the other hand, the following system (from now on referred to as the example system) is not inconsistent:

  1. All men are mortal.
  2. Socrates is a man.

Inconsistent systems are liars: the conclusions derived from them cannot be trusted. ^1 Axiomatic systems can be defined for many specific purposes (mathematics, ethics, et c.). Hopefully I don't have to explain why an inconsistent system of ethics would be disastrous. We would like some assurance that our frameworks are not inconsistent: proofs of consistency!

Proofs of consistency are possible because mathematicians have agreed upon a powerful axiomatic system, the Set Theory ZFC that they believe to be consistent. ^3

Take any axiomatic theory S. Sometimes, you can re-label the axioms of S to be about mathematical objects. This is possible if

  1. All quantifiers that occur in the axioms can be restricted to range over some given set M (in the example system, you would replace "All men" with "All men belonging to the set M*").

  2. Each symbol occuring in the axioms can be identified with an element of the set M (in the example system you would interpret the word "Socrates" to refer to some specific element of the set M).

  3. Each predicate occuring in the axioms can be identified with a subset of the set M (in the example system you would interpret "is a man" by a subset of M, and "is mortal" by another subset of M).

  4. The sentences of S, when interpreted this way, are consequences of the axioms of ZFC.

Such sets M, whenever they exist, are called the models of S. The set of numbers less than 5 {0,1,2,3,4} is a model of the example system, because you can

  1. Interpret the symbol "Socrates" as referring to the number 1.

  2. Interpret the predicate "is a man" as the subset of odd numbers; this means that you consider 1 and 3 men, but not 0, 2 and 4.

  3. Interpret the predicate "is mortal" as the subset of numbers less than 4; this means that you consider 0, 1, 2 and 3 to be mortals, but not 4.

  4. Now, the sentence "All men are mortal" means "All odd numbers in M are less than 3", which is a true mathematical statement that you can prove using the axioms of ZFC.

  5. The sentence "Socrates is a man" means "The number 1 is odd", which is again a true mathematical statement that can be proved from the axioms of ZFC.

The relabeling interprets the axioms and consequences of S as true mathematical statements (the form of the statements is preserved, even if meaning is not). If a contradiction follows from the axioms of S, then it can be relabeled into a contradiction in mathematics (ZFC). Therefore, every axiomatic system that has a model is at least as consistent as mathematics itself: giving a model amounts to giving a consistency proof. We say that this consistency proof is relative to ZFC.

It can be demonstrated that Model Theory is the most general method of giving consistency proofs (relative to ZFC): if ZFC proves that a system is consistent then the system has a model, and vice versa.

^1 There are also consistent liars. Observing an inconsistency is sufficient to conclude that an axiom system is a liar, but it is not necessary.

^2 Observe that we still have no assurance about the consistency of this general-purpose system.

^3 This is not entirely true, but it is a reasonable non-technical explanation.

^4 Unfortunately, the satisfaction relation "satisfied in a model" is commonly referred to as true in a model. Worst of all, "X is satisfied in the standard model" is sometimes abbreivated to X is true, giving these results a false aura of deep philosophical relevance.

Comment author: TezlaKoil 23 April 2015 07:34:07PM *  10 points [-]

2. A multitude of models

As a general rule, consistent theories have multiple models. Models have more consequences than the theories they model: for example, our model of the example system proves that there are only 2 men, even though this does not follow from the axioms. A sentence follows from the axioms only if it is satisfied in every possible model of S. ^4

Even the axiomatic theory of natural number arithmetic, which we would think is absolute, has multiple models. Mathematicians have agreed on a standard model (the so-called set of natural numbers), but it is easy to prove that other models exist:

Extend the theory of arithmetic (PA) with a new constant K, and the following (infinitely many) axioms.

 0 < K
1 < K
2 < K
...
65534 < K
65535 < K
...

Surprisingly, the resulting theory PAK is consistent. Proofs are finite: any proof of a contradiction in PAK would use only finitely many axioms, so there is a largest number n such that n < K is used in the proof. Therefore, K can be replaced in the proof by n + 1, yielding a proof of a contradiction in PA itself! Since arithmetic is consistent, there is no proof of contradiction in PAK.

We have shown that PAK is consistent relative to ZFC. Therefore, it has a model. A model of PAK is a model of arithmetic, but it is clearly not the standard model. Therefore, arithmetic has a non-standard model, which contains the standard integers, as well as non-standard integers (such as the one corresponding to our constant K). In a sense, the non-standard models contain "infinite" numbers that the model cannot distinguish from the real, finite numbers.

The existence of non-standard models is a serious issue: There are situations where the standard model has no counterexamples to a statement, but some non-standard model has. This means that the statement ought to follow from the axioms of arithmetic, but we cannot prove it because it fails in a weird, non-standard model.

For example, some non-standard models disagree with the following statement (the Ramsey theorem), which is satisified by the standard model.

For any non-zero natural numbers n, k, m we can find a natural number N such that if we color each of the n-element subsets of S = {1, 2, 3,..., N} with one of k colors, then we can find a subset Y of S with at least m elements, such that all n element subsets of Y have the same color, and the number of elements of Y is at least the smallest element of Y.

Another, more accessible example is whether you can kill the Hydra or not. You can kill the hydra in the standard model, but many non-standard models disagree. If you would number all the hydras in a non-standard model, the counterexamples would be numbered by non-standard numbers such as K in the proof above.

We need to add new axioms to the axiomatic system of arithmetic, so that it corresponds more faithfully to the standard model. However, our work is never over: as a consequence of Gödel's incompleteness theorem, new axioms can rule out some non-standard models, but never all of them.

3. Generalised models and Hamkins' paper

So far:

  • Consistency relative to ZFC is a useful notion: giving a model allows us to prove that our theories are as consistent as mathematics itself.

  • Arithmetic has multiple models. There is a so-called standard model of arithmetic, which is not some real-world or transcendent notion. It is merely a set that mathematicians have agreed to call the standard model. The axioms of arithmetic are unable to exactly describe the standard model: they always describe the standard model plus some other "junk" models.

Do we know that ZFC is consistent? The short answer: we don't and we can't. By Gödel's incompleteness, if ZFC is consistent then it has no models. However, by adding new axioms to ZFC (e. g. large cardinal axioms). we can create set theories that have generalised notions of models. While ZFC has no models, it does have generalised models.

Unlike arithmetic, ZFC itself has no agreed-upon standard generalised model. There is not even a standard system in which we construct generalised models. In all of the above, we have refused to choose a specific model of ZFC (i. e. we did not use the phrase "satisfied in a generalised model of ZFC" or any semantically equivalent sentences). We used the notion of provability in ZFC (which is absolute).

If we replace provability in ZFC with "satisfiability in some specific model", we are suddenly able to prove more properties about the standard model of arithmetic (similarly to how we can prove more theorems about numbers by passing to the standard model of arithmetic from the axioms of arithmetic). Unfortunately, it is well-known (and intuitively obvious) that if you and I choose different generalised models, our conclusions (about these previously undecidable properties) can disagree.

The paper of Hamkins collects some stronger results: our conclusions can disagree even if our chosen generalised models are very similar. For example

  • There are two generalised models which agree upon the elements that constitute the standard model, yet disagree on the properties of these elements.

  • There are two generalised models which agree upon the elements that constitute the standard model, agree upon the properties of the addition operation, yet disagree about the properties of the multiplication operations.

and so on... Unfortunately, the proofs of these rely on powerful lemmas, so I can't instantiate them to produce explicit examples.

Anyway, this should be enough to get you started.

View more: Prev | Next