I Like Philosophy

Math is but a Vast but Simple First Order Theory... Technical philosophy has a lot in common with mathematics, via a set of symbolic systems called formal logic. A remarkable fact revealed by formal logic is that nearly all (and maybe ALL) of mathematics can be reduced to a tiny number of primitive notions. A primitive notion is one that cannot be defined in terms of other notions. All reasoning requires primitive notions grounded in our everyday human experience. Philosophy can reduce the scope of common sense, but not its importance.

Here are the primitive notions:
* There exist a bunch of abstract ob<x>jects. Later, we will assume that there are infinitely many such ob<x>jects. These abstract ob<x>jects are commonly referred to as "sets."
* There is a single binary relation that may connect one such ob<x>ject with another. This binary relation is commonly called "set membership." There is only one kind of atomic formula: "set a is a member of set b";
* It is possible to assert that something holds for all sets. This is called universal quantification. Universal quantification is governed by a few simple axioms (I spare you the details).
* An atomic formula having quantified variables has one of two truth values, True or False.
* Well formed statements can be True, False, or contingent.
* There is a unary functor, NOT, that when applied to a True statement, turns it into a False one. And vice versa. This trivial notion is strangely powerful.
* Statements having truth values can be combined via the binary functor AND. True AND True yields True. All other combinations of truth values by means of AND yield False. The mathematical structure of AND, NOT, and True is the Boolean algebra [b]2[/b]. (Math and logic can be grounded in other combinations of functors, but NOT and AND are, in my view, the easiest to understand. Also, no matter what functors are selected, [b]2[/b] retains its primacy.)

Here's all we need to assume about AND and NOT:
* AND commutes and associates;
* True AND x = x ;
* NOT(x) AND x = NOT(True) ;
* x AND NOT (x AND y) = x AND NOT(y) .

Setting aside the notion of set, the above is a fragment of a formal system called first order logic.

Now assume the following facts about the set membership relation:
* This relation is not symmetrical (if a is a member of b, b cannot be a member of a), and not transitive (from a being a member of b, and b being a member of c, we cannot infer that a is a member of c);
* Sets having the same members are identical. If two sets differ only by the order in which their members are listed, they are the same set. If two sets differ only by how many copies they have of one or more members, they are the same set. This is called the principle of extensionality;
* Given a set, its union set and power set exist. The union set of x is the set formed by taking the union of all members of x. The power set of x is the set of all possible subsets of x ;
* If the domain of a function is a set, its range is as well. This axiom is curiously powerful. For most purposes, it can be replaced by 2 axioms. One states that given any two sets, their union exists. The other asserts that given any set x, all subsets of x describable by first order logic exist;
* There exists an infinite set, defined as a set that can be put into a one-to-one correspondence with a proper subset of itself;
* It is always possible to construct a set by selecting a single member from each of an infinite number of sets. This constructed set is called a choice set, and this axiom is called the axiom of choice;
* There is an axiom that rules out, among other things, a set being a member of itself. This is not strictly necessary.

The above assumptions make up the standard axiomatic set theory, known as [b]ZFC[/b], assumed to ground all of mathematics except category theory.

Most of standard university mathematics can be grounded in set axioms considerably weaker than the above. A fair bit of the strength of the above axioms is only required by advanced set theory itself.

So mathematics requires at minimum:
* The notion of a truth value;
* The unary functor NOT and the binary functor AND that operate on truth values;
* At least 3 universally quantified variables ranging over a domain consisting of abstract ob<x>jects called sets;
* A bit of axiomatic machinery governing universal quantification. Universal generalisation and instantiation will do;
* A way of connecting one abstract ob<x>ject with another, called "set membership." There is a set having no members, called the empty set. All other sets have "members";
* Set membership is governed by a number of proper axioms. One of these axioms forces the domain to have infinite cardinality. Another axiom (the one assuring that the power set of every set exists) assures the existence of Cantor's infinite hierarchy of infinities. Standard applied mathematics does not require this profusion of infinite sets.

There is a sense in which a first order theory whose quantified variables nest less than 3 deep is mathematically trivial (i.e., such theories are generally decidable). All of mathematics, starting with the set theory axioms described above, can be reduced to statements whose quantified variables nest no more than 3 deep. The startling conclusion of this sort of thinking is that mathematics is a vast first order theory requiring no more than an infinite domain and a quite modest fragment of first order logic: a single binary predicate letter that is neither symmetric nor transitive, and a mere 3 quantified variables. This is the minimum machinery required for a first order theory to be undecidable. Skeptics are invited to peruse:
http://us.metamath.org/mpegif/mmset.html

Starting with the above system, take away the axiom of infinity. Having eliminated infinite sets, the axiom of choice and the axiom that rules out self-membered sets are no longer necessary. Replace the axiom about the domain and range of functions with an action asserting that given some set, any subset describable using the first order language of set theory exists. The resulting system suffices for all finite and discrete mathematics, which includes all of computer science. A remarkable fact is that this system can be proved free of contradiction. All of the philosophical perplexities of mathematics, including the notorious issues raised by Godel, are due to the use of infinite sets. This is why I have time for finitism; it results in a fragment of mathematics which we know to be trouble-free.

The centrality of first order logic emerged at Gottingen around 1920-30. (The logic of Frege, and of Russell-Whitehead, was second order and thus more treacherous. Also not clearly understood before the 1950s.) Axiomatic set theory is mainly the work of Zermelo, 1908-1930. That his axioms sufficed for nearly all of mathematics was not generally appreciated before the 1950s. (The text Suppes 1960 was an important introduction to axiomatic set theory for my generation.) That mathematics requires quantified variables nesting no more than 3 deep was discovered by Tarski and his students starting in the 1940s, but was not fully explicated until the landmark monograph Tarski and Givant (1987).

consa01 · 70-79, M

Logic was Aristotle plus some pedantic details, for over 2000 years. The syllogism ruled the roost. George Boole was groping towards a math formalization of this traditional logic 150 years ago, but did not get it quite right. Peirce and Jevons and DeMorgan got it right in the 1860s, but few people noticed.

In 1879, an obscure German math prof paid to have an 80pp pamphlet published. His name was Gottlob Frege. His notation was totally weird, and reviewers did not much like his work. It soon went out of print, and was seldom cited before the 1940s. Even the Library of Congress did not acquire a copy of Frege's 1879 book until 1964. But this is where modern logic began. The first to appreciate Frege was Betrand Russell, starting around 1900.

C S Peirce, teaching at Johns Hopkins, came up with related ideas using a notation that was much less intimidating. Peirce's importance was ignored until the 1980s, because Russell and Whitehead did not cite him (they should have). Peirce is the most important American philosophical thinker of all time. His Harvard degree was in chemistry, and he earned his living as an astronomer, then in gravity measurements. He spent the last 20 years of his life in desperate proverty. He was largely self-taught in philosophy and math, although it helped that his father held the math chair at Harvard.

Much of what I wrote above is about axiomatic set theory. Set theory was almost entirely devised by Georg Cantor in Germany, between 1870 and 1900. A younger German named Zermelo recast a lot of Cantor's theory into axiomatic form in 1908. This theory underwent major amendments in 1922 and 1930. The final form of the theory is known as ZFC. Between 1910 and 1950, a number of competing approaches were proposed. But now the dust has settled, and ZFC has attained canonical status. This is a curious fact because Zermelo's axioms are a bit of a cludge. More elegant systems have been proposed, but have failed to catch on.

The idea that ZFC suffices to ground (almost all) mathematics was more hope than fact until the monograph by Suppes (1960), which has been taken much further by the Metamath website, which includes formal symbolic computer checked proofs of nearly 10,000 core theorems of modern mathematics. The proofs start from first order logic augmented by the axioms of ZFC.

The last century saw huge ferment in math foundations. I doubt that the ferment is over. A major failed foundational project is category theory. I am surprised at how few mathematicians know set theory and first order logic well. For a long time, I believed that NFU would make a breakout. Now I suspect that the theory S that George Boolos proposed in 1989 deserves much more attention than it has gotten. There is also Randall Holmes's "pocket set theory," sufficient for nearly all undergraduate and applied math.

Tjent

Thanks for a lucid and fascinating intro lecture to first order logic. I have always been interested in Western philosophy but only lately developed a keen interest in formal logic. I am reading an excellent text called "Introduction to Logic" by Harry Gensler - highly recommended for other novices.

I've also been reading Salul Kripke's "Naming and Necessity" lectures - enjoyable and thought provoking discussion on the nature of proper names, definite desc<x>riptions and the fixing of reference, with lots of logic ("necessary a posteriori truths"!) along the way.

After finishing with these books I'd like to dig in to first order logic or set theory. Some titles on Amazon look promising; but is there anything you would recommend on the subject?

Incidentally, I'm also quite interested in probability/induction theory, especially in it's philosophical aspects.

consa01 · 70-79, M

Logic from a more philosophical point of view: see if you can find any books by Benson Mates. Among other things, Mates was a Leibniz expert.
Set theory: Rudy Rucker's "Infinity and the Mind".

Most human reasoning is, BTW, inductive not deductive. We reason from probable causes to likely effects all the time. The closest we have to an "inductive logic" is Bayesian reasoning.