Gödel's incompleteness theorems

[Spun off from Monday's toughie, first-order logic. This one's just on the border of comprehensibility, but kind of in the way that Reykjavik borders New York.]
In mathematical logic, Gödel's incompleteness theorems are two celebrated theorems about the limitations of formal systems, proved by Kurt Gödel in 1931 .These theorems show that there is no complete, consistent formal system that correctly describes the natural numbers, and that no sufficiently strong system describing the natural numbers can prove its own consistency....

Gödel's theorems are theorems in first-order logic, and must ultimately be understood in that context. In formal logic, both mathematical statements and proofs are written in a symbolic language, one where we can mechanically check the validity of proofs so that there can be no doubt that a theorem follows from our starting list of axioms. In theory, such a proof can be checked by a computer, and in fact there are computer programs that will check the validity of proofs. (Automatic proof verification is closely related to automated theorem proving, though proving and checking the proof are usually different tasks.)

To be able to perform this process, we need to know what our axioms are. We could start with a finite set of axioms, such as in Euclidean geometry, or more generally we could allow an infinite list of axioms, with the requirement that we can mechanically check for any given statement if it is an axiom from that set or not (an axiom schema). In computer science, this is known as having a recursive set of axioms. While an infinite list of axioms may sound strange, this is exactly what's used in the usual axioms for the natural numbers, the Peano axioms: the inductive axiom is in fact an axiom schema — it states that if zero has any property and whenever any natural number has that property, its successor also has that property, then all natural numbers have that property — it does not specify which property and the only way to say in first-order logic that this is true of all properties is to have infinitely many statements.

Gödel's first incompleteness theorem shows that any such system that allows you to define the natural numbers is necessarily incomplete: it contains statements that are neither provably true nor provably false.

The existence of an incomplete system is in itself not particularly surprising. For example, if you take Euclidean geometry and you drop the parallel postulate, you get an incomplete system (in the sense that the system does not contain all the true statements about Euclidean space). A system can be incomplete simply because you haven't discovered all the necessary axioms.

What Gödel showed is that in most cases, such as in number theory or real analysis, you can never create a complete and consistent finite list of axioms, or even an infinite list that can be produced by a computer program. Each time you add a statement as an axiom, there will always be other true statements that still cannot be proved as true, even with the new axiom. Furthermore if the system can prove that it is consistent, then it is inconsistent.

It is possible to have a complete and consistent list of axioms that cannot be produced by a computer program (that is, the list is not computably enumerable). For example, one might take all true statements about the natural numbers to be axioms (and no false statements). But then there is no mechanical way to decide, given a statement about the natural numbers, whether it is an axiom or not.

Gödel's theorem has another interpretation in the language of computer science. In first-order logic, theorems are computably enumerable: you can write a computer program that will eventually generate any valid proof. You can ask if they have the stronger property of being recursive: can you write a computer program to definitively determine if a statement is true or false? Gödel's theorem says that in general you cannot.

Many logicians believe that Gödel's incompleteness theorems struck a fatal blow to David Hilbert's program towards a universal mathematical formalism which was based on Principia Mathematica. The generally agreed upon stance is that the second theorem is what specifically dealt this blow. However some believe it was the first, and others believe that neither did....

[More....]

Lift

[This is either a bad article, or a hard subject. You decide.]
The lift force, lifting force or simply lift consists of the sum of all the fluid dynamic forces on a body perpendicular to the direction of the external flow approaching that body.

Sometimes the term dynamic lift (dynamic lifting force) is used in reference to the vertical force resulting from the relative motion of the body and the fluid, as opposed to the static lifting force resulting from the buoyancy.

The most straightforward and frequently-mentioned application of lift is the wing of an aircraft. However there are many other common, if less obvious, uses such as propellers on both aircraft and boats, rotors on helicopters, fan blades, sails on sailboats and even some kinds of wind turbines.

While the common meaning of the term "lift" suggests an "upwards" action, in fact, the direction of lift (and its definition) does not actually depend on the notions of "up" and "down", e.g., as defined with respect to the direction of the gravity. Specifically, the term negative lift refers to the lift force directed "down".

There are a number of ways of explaining the production of lift, all of which are equivalent. That is, they are different expressions of the same underlying physical principles....

[More....]

First-order logic

[A theme week? Well, why not. Let's start with extremely difficult subjects, things that make your head spin. So here's #1:]
First-order logic (FOL), also known as first-order predicate calculus (FOPC), is a system of deduction extending propositional logic (equivalently, sentential logic). It is in turn extended by second-order logic.

The atomic sentences of first-order logic have the form P(t₁, ..., t_n) (a predicate with one or more "arguments") rather than being propositional letters as in propositional logic. This is usually written without parentheses or commas, as below.

The new ingredient of first-order logic not found in propositional logic is quantification: where φ is any sentence, the new constructions ∀x φ and ∃x φ -- read "for all x, φ" and "for some x, φ" -- are introduced. For convenience in explaining our intentions, we write φ as φ(x) and let φ(a) represent the result of replacing all (free) occurrences of x in φ(x) with a, then ∀x φ(x) means that φ(a) is true for any value of a and ∃x φ(x) means that there is an a such that φ(a) is true. Values of the variables are taken from an understood universe of discourse; a refinement of first-order logic allows variables ranging over different kinds of objects.

First-order logic has sufficient expressive power for the formalization of virtually all of mathematics. A first-order theory consists of a set of axioms (usually finite or recursively enumerable) and the statements deducible from them. The usual set theory ZFC is an example of a first-order theory, and it is generally accepted that all of classical mathematics can be formalized in ZFC. There are other theories that are commonly formalized independently in first-order logic (though they do admit implementation in set theory) such as Peano arithmetic....

[More....]

The tryptophan turkey

[From non-Wik haunts: Feeling sleepy? Don't look to the bird.]
"Turkey does contain tryptophan, an amino acid which is a natural sedative. But tryptophan doesn't act on the brain unless it is taken on an empty stomach with no protein present, and the amount gobbled even during a holiday feast is generally too small to have an appreciable effect. That lazy, lethargic feeling so many are overcome by at the conclusion of a festive season meal is most likely due to the combination of drinking alcohol and overeating a carbohydrate-rich repast, as well as some other factors...."

[More....]

Centurion Card

[For when you get phat money.]
The Centurion Card, popularly known as the Black Card, is American Express's most exclusive charge card. Urban legends of a special, black-colored card offering dignitaries and celebrities unlimited spending power and after-hours access to high-end stores circulated in the 1980s. [1] While the rumors were false, American Express decided to capitalize on them by launching the Centurion Card in October 1999 to selected holders of The Platinum Card®, with an annual fee originally at $1,000.

The card is available only by invitation and, as of January 1, 2006, requires minimum annual spending of $250,000 on another American Express card and exceptional credit history among other requirements. Certain requirements have been known to be waived for major celebrities and business figures. "Charter" cardmembers that joined at the $1000/year annual fee are "grandfathered" at that rate as long as they hold the card. If they cancel and re-join, it will be at the higher rate. As of 2006 the annual new cardholder fee was $2,500 and it is estimated that there are fewer than 10,000 cards issued worldwide. The card offers numerous exclusive privileges, including complimentary companion airline tickets on trans-Atlantic flights, personal shoppers at retailers such as Escada, Gucci and Saks Fifth Avenue, access to airport clubs, first class flight upgrades, membership in Sony's Cierge personal shopping program, and dozens of other elite club memberships. Centurion membership also includes personal services including a personal concierge and travel agent. The program offers many hotel benefits, including a free one-night's stay in every Mandarin Oriental hotel worldwide (excluding the New York City property) once a year....

The card is available both as a personal and a business card. A new Centurion card crafted from anodized titanium [2] is being issued as a replacement for all U.S. Centurion plastic cards in the first half of 2006. Centurion members in other countries have previously received this titanium card....

Several rappers have referenced use and possession of the black card in their lyrics. For example, Kanye West's lyric, "She was like, 'Oh my God, is that a black card?' / I turned around and replied 'Why yes, but I prefer the term "African American Express"'", and Bow Wow's reference in the track "I Think They Like Me (Remix)" with the line "I ain't got to act hard / I'm under 21 with a black card"....

[More....]

Other: page view rank vs number of employees

pages	employees	company	(subsidiary sites)
1	10000	Yahoo!	(Hotjobs, Flickr , etc)
2	90000	TimeWarner	(AOL, CNN, Netscape, etc)
3	10000	Google	(YouTube, Blogger, etc)
4	70000	Microsoft	(MSN, Hotmail, etc)
5	50000	News Corp	(Myspace, Fox, IGN, etc)
6	12000	eBay	(Paypal, Skype, etc)
7	23	craigslist	(N/A)
8	25000	BBC	(N/A)
9	130000	Disney	(ESPN, Go, ABC, etc)
10	12000	Amazon	(IMDB, A9, etc)

[More(via SVN)]

Halloween

[When your magic is most potent.]
Halloween is a tradition celebrated on the night of October 31, most notably by children dressing in costumes and going door-to-door collecting sweets, fruit, and other treats. It is celebrated in parts of the Western world, most commonly in the United States, Canada, the UK, Ireland, and with increasing popularity in Australia and New Zealand, as well as the Philippines. In recent years, Halloween is also celebrated in parts of Western Europe, such as Belgium and France. Halloween originated as a Pagan festival among the Celts of Ireland and Great Britain with Irish, Scots, Welsh and other immigrants transporting versions of the tradition to North America in the 19th century. Most other Western countries have embraced Halloween as a part of American pop culture in the late 20th century.

The term Halloween, and its older spelling Hallowe'en, is shortened from All-hallow-even, as it is the evening before "All Hallows' Day"^[1] (also known as "All Saints' Day"). The holiday was a day of religious festivities in various northern European Pagan traditions, until Popes Gregory III and Gregory IV moved the old Christian feast of All Saints Day from May 13 to November 1. In Ireland, the name was All Hallows' Eve (often shortened to Hallow Eve), and though seldom used today, it is still a well-accepted label. The festival is also known as Samhain or Oíche Shamhna to the Irish, Calan Gaeaf to the Welsh, Allantide to the Cornish and Hop-tu-Naa to the Manx. Halloween is also called Pooky Night in some parts of Ireland, presumably named after the púca, a mischievous spirit.

Many European cultural traditions hold that Halloween is one of the liminal times of the year when spirits can make contact with the physical world and when magic is most potent (e.g. Catalan mythology about witches, Irish tales of the Sídhe).....

Halloween did not become a holiday in America until the 19th century, where lingering Puritan tradition meant even Christmas was scarcely observed before the 1800s. North American almanacs of the late 18th and early 19th centuries make no mention of Halloween in their lists of holidays.^[11] The transatlantic migration of nearly two million Irish following the Irish Potato Famine (1845–1849) brought the holiday and its customs to America. Scottish emigration from the British Isles, primarily to Canada before 1870 and to the United States thereafter, brought that country's own version of the holiday to North America.

When the holiday was observed in 19th-century America, it was generally in three ways. Scottish-American and Irish-American societies held dinners and balls that celebrated their heritages, with perhaps a recitation of Robert Burns' poem "Halloween" or a telling of Irish legends, much as Columbus Day celebrations were more about Italian-American heritage than Columbus. Home parties would center around children's activities, such as bobbing for apples and various divination games, particularly about future romance. And finally, pranks and mischief were common on Halloween....

There is little primary documentation of masking or costuming on Halloween in America, or elsewhere, before 1900.^[15] Mass-produced Halloween costumes did not appear in stores until the 1930s, and trick-or-treating became a fixture of the holiday in the 1950s, although commercially made masks were available earlier.

[More....]