Arrow's impossibility theorem is provable, basically social choice is impossible given several fairly sound requirements: 3 or more things to choose between and transitivity of choice.
C isn't a proof, agreed. Although its acceptance is well seen by observation. And physics hasn't theorems in the same sense as mathematics. Bad choice on my part. Heisenberg is directly provable from Schrödinger's equation Decidability is provable by showing the acceptance set of TMs is countably infinite while the possible languages is continuously infinite (integers vs reals) NoFreeLunch simply shows that random methods (GAs etc) have inputs that are no better managed than uniformly random guessing. But fortunately, the pessimal inputs are rare and NFL did us the favor of finding where to look for tractable stochastic algorithms. Whew! On Tue, Apr 16, 2013 at 4:13 PM, Barry MacKichan < barry.mackic...@mackichan.com> wrote: > Actually, Godel said "that the axioms [have to]->[can't] be very > carefully chosen." The theorem says that any mathematical system that > contains the integers cannot be both complete and self-consistent. It is > unique in the list of 'impossibility' theorems in that it has a > mathematical proof. The others in your list are all contingent on some form > of observation. > > It's sort of like saying all sets of equations have to be overdetermined > or underdetermined or both. Except its really hits at the roots of the > mathematical enterprise. They say its announcement hit Bertrand Russell > really hard. > > -Barry > > > > On Apr 16, 2013, at 3:49 PM, Owen Densmore <o...@backspaces.net> wrote: > > One has to be careful with nearly all the "impossibility" theorems: > Arrow's voting, the speed of light, Godel, Heisenberg, decidability, > NoFreeLunch, ... and so on. > > To tell the truth, Godel .. it seems to me .. says to the > practicing mathematician that the axioms have to be very carefully chosen. > > > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com >
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com