# Construction

One of the important ideas of mathematics, especially since Gödel proved his theorem, concerns itself with the question can one construct it ?

The question is most graphically illustrated by some of the results of the late 19th and early 20th centuries, in which entities were shown to exist but not be constructible, for various senses of exist and construct, and some very strange results were proven feasible (such as the Banach-Tarsky decomposition of the sphere).

Concern over these lead to a re-assessment of the axioms used to prove existence; attention rapidly focussed on the axiom of choice and the law of the excluded middle (a.k.a. reductio ad absurdum). The former, choice, says that, for any collection, C, of disjoint non-empty collections, there exists a monic mapping which maps each member, a, of C to a member of a; while this is provable without the axiom whenver C is finite (or so I'm told), it's needed as an axiom as soon as infinite collections join in. Reductio says that every statement is decidable - i.e. either true or false; equivalently, that not(not(a)) implies a for all a.

The remedies sought have included various approaches to specifying what exists in terms which indicate how one may construct an entity. For example, any finite collection whose members we have already constructed, we can construct that collection; in particular, the empty collection is constructible, as is the successor of any constructible collection. This enables us to construct the natural numbers as 0 = empty = {}, 1 = {0}, 2 = {0,1}, ... 1+n = {0,...,n}, ... thereby ensuring there is an infinite (which, at least to me, means non-constructible) collection of constructibles.

In the mean time, folk have learned to treat familiar logic with more skepticism - especially in so far as it involves reductio or (trans-finite) choice. If we are entirely to discard reductio, we're going to need to settle on new axioms - new foundations - which suffice to prove sensible things without needing reductio to complete the proofs. This is an area which, while interesting, I have studied only in passing - it's a foundational issue, not directly pertinent to how physics uses the tools it takes from mathematics, so not one of my high priorities.

## Strong Induction

One of the notions of constructible is the principle of strong induction: if knowing that all members of a constructible collection possess some property suffices to imply that the collection also posesses that property, then all constructible collections must possess that property. What this is saying is best expressed in terms of the collection, call it Q, of constructible collections which lack the given property; every collection lacking the given property has a member lacking the given property, so we can't construct any until we've constructed at least one; strong induction says we can infer, from this, that we can't construct any, so Q is empty.

Written by Eddy.