## Saturday, April 30, 2011

### An Overview of Logic and the Philosophy of Mathematics

“There are things which seem incredible to most men who have not studied mathematics.”
-- Aristotle

Logic originated with the ancient Greek philosopher Aristotle. The Greek word for instrument is Organon. The collection of Aristotle’s logical writings is known as the Organon. The Prior Analytics contains the most systematic discussion of formal logic. The Metaphysics is Aristotle’s treatise on the science of existence, i.e., being as such. It includes a detailed analysis of the various ways in which a thing can be said to be. In the Posterior Analytics, Aristotle laid down the basics of the scientific method.

Aristotelean logic
According to Aristotelean logic, the basic unit of reasoning is the syllogism.

·         Identity. Everything is what it is and acts accordingly. In symbols:

·         A is A.

·         Non-contradiction. It is impossible for a thing both to be and not to be. A given predicate cannot both belong and not belong to a given subject in a given respect at a given time. Contradictions do not exist. Symbolically:

·         A and non-A cannot both be the case.

·         Either-or. Everything must either be or not be. A given predicate either belongs or does not belong to a given subject in a given respect at a given time. Symbolically:

·         Either A or non-A.

·         Logic is the science of correct reasoning. What then is reasoning? According to Aristotle (Topics, 100a25), reasoning is any argument in which certain assumptions or premises are laid down and then something other than these necessarily follows.  Thus logic is the science of necessary inference.

·         Above the gateway to Plato’s academy appeared a famous inscription:

Let no one who is ignorant of geometry enter here.

·         The objects that are studied in mathematics tend to be somewhat abstract and remote from everyday perceptual experience. Plato seemed to insist that mathematical objects, like the Platonic forms or essences, must be perfectly abstract and have a separate, non-material kind of existence.

·         Aristotle dissected and refuted this view in books M and N of the Metaphysics. According to Aristotle, the geometrical square is a significant aspect of the square floor tile, but it can only be understood by discarding other irrelevant aspects such as the exact measurements, the tiling material, etc. (Ancient Greek Geometry)

·         Philosophical intrinsicism may play out as mathematical Platonism. Philosophical subjectivism may play out as mathematical constructivism. Nominalism may play out as formalism. Our modern notion of a formal theory is a variant of Aristotle’s concept of scientific method.

·         According to formalism, mathematics is only a formal game, concerned solely with algorithmic manipulation of symbols. Under this view, the symbols of the predicate calculus do not denote predicates or anything else. They are merely marks on paper, or bits and bytes in the memory of a computer. Therefore, mathematics cannot claim to be any sort of knowledge of mathematical objects. Indeed, mathematical objects do not exist at all, and the profound questions debated by Plato and Aristotle become moot. Mathematics is nothing but a kind of blind calculation.

·         Constructivism, the idea that mathematical knowledge can be obtained by means of a series of purely mental constructions. Under this view, mathematical objects exist solely in the mind of the mathematician, so mathematical knowledge is absolutely certain. However, the status of mathematics viz a viz the external world becomes doubtful. An extreme version of constructivism is so solipsistic that it does not even allow for the possibility of mathematical communication from one mind to another.

·         Mathematics abounds with such questions, mathematical problem or question of a yes/no nature, for which the answer is currently unknown. The Godel incompleteness phenomenon suggests that such questions will always exist.

·         Set-theoretical Platonism. According to this variant of the Platonic doctrine, infinite sets exist in a non-material, purely mathematical realm. By extending our intuitive understanding of this realm, we will be able to cope with chaos issuing from the Godel incompleteness phenomenon. The most prominent and frequently cited authority for this kind of Platonism is Godel himself.

·         Three competing 20th century doctrines: formalism, constructivism, set-theoretical Platonism. None of these doctrines are philosophically satisfactory, and they do not provide much guidance for mathematically oriented scientists and other users of mathematics. As a result, late 20th century developed a split view, a kind of Kantian schizophrenia, which is usually described as “Platonism on weekdays, formalism on weekends”.

·         The great mathematician David Hilbert anticipated such a renovation in his 1925 essay, On the Infinite. Hilbert was aware that, according to modern physics, the physical universe is finite. Yet infinite sets were playing an increasingly large role in the mathematics of the day. Hilbert therefore recognized that the most vulnerable chink in the armor of mathematics was the infinite. In order to defend what he called “the honor of human understanding”, Hilbert proposed to develop a new foundation of mathematics, in which formal theories of infinite sets, such as Ts, would be rigorously justified by reference to the finite. This is Hilbert’s program of finitistic reductionism.

·         Aristotle’s distinction between actual and potential infinity. An actual infinity is something like an infinite set regarded as a completed totality. A potential infinity is more like a finite but indefinitely long, unending series of events. According to Aristotle, actual infinities cannot exist, but potential infinities exist in nature and are manifested to us in various ways, for instance the indefinite cycle of the seasons, or the indefinite divisibility of a piece of gold.

·         The finitistic reduction which Hilbert desired cannot be carried out. This follows from Godel’s incompleteness theorem. The remarkable results obtained by Godel in 1931 caused the philosophical ideas of Hilbert’s 1925 essay to fall into disrepute. Hilbert’s grand foundational program appeared to be dead, broken beyond hope of repair.

·         Recent foundational research has revealed that, although Ts is not finitistically reducible, there are other formal theories which are finitistically reducible, in the precise these other formal theories turn out to be adequate for a very large portion of mathematics. They do not encompass actual infinities such as ’omega’ but they do include the main results of arithmetic and geometry and allied disciplines. Roughly speaking, a formal theory is said to be finitistically reducible if it can be embedded into some very restricted formal theory such as Ta, which is physically meaningful and makes absolutely no reference to actual infinity.

·         The German philosopher Gottlob Frege published a remarkable treatise, the Begriffsschrift (“concept script”). Instead of Frege’s system, first-order logic or the predicate calculus is a streamlined system.

·         In order to recognize that a formula x  is logically valid, it suffices to construct what is known as a proof tree for x, or equivalently a refutation tree for !x. This is a tree which carries !x at the root. Each node of the tree carries a formula. The growth of the tree is guided by the meaning of the logical operators appearing in x. New nodes are added to the tree depending on what nodes have already appeared.

·         Corresponding to each of the seven logical operators, there are prescribed procedures for adding new nodes to the tree. We apply these procedures repeatedly until they cannot be applied any more. If explicit contradictions (An explicit contradiction is a pair of formulas of the form ,x,!x )  are discovered along each and every branch of the tree, then we have a refutation tree for !x. Thus !x is seen to be logically impossible. In other words, x is logically valid. The class of logically valid formulas is known to be extremely complicated. Indeed, this class is undecidable. Undecidability result is known as Church’s theorem.

·         Among the most basic mathematical concepts are: number, shape, set, function, algorithm, mathematical axiom, mathematical definition, mathematical proof.

·         Euclid’s ELEMENTS begins with 21 definitions, five postulates, and five common notions.

·         “Euclidean geometry” refers to the familiar geometry in which the angles of a triangle sum to 180 degrees, as distinct from the “non-Euclidean” (i.e., hyperbolic) geometry" developed by Bolyai and Lobachevsky in the 19th century.

·         Let Tg be the formal theory based on Tarski’s axioms. Tarski’s formal theory for Euclidean15 plane geometry: Tg. Altogether Tarski presents twelve axioms, plus an additional collection of axioms expressing the idea that a line is continuous.

·         Tarski has demonstrated that Tg is complete. This means that, for any purely geometrical statement x, either x or !x is a theorem of Tg. Thus we see that the axioms of Tg suffice to answer all yes/no questions of Euclidean plane geometry. Combining this with the completeness theorem of Godel, we find that Tg is decidable: there is an algorithm which accepts as input an arbitrary statement of plane Euclidean geometry, and outputs “true” if the statement is true, and “false” if it is false.

·         The contrast between the completeness of formal geometry and the incompleteness of formal arithmetic are striking. Let Ta be formal theory for arithmetic formal theory for arithmetic. Any formal theory which includes Ta is necessarily either inconsistent or incomplete. Thus there is no hope of writing down enough axioms or developing an algorithm to decide all arithmetical facts. This is a variant of the famous 1931 incompleteness theorem of Godel

·         One approach to a unified mathematics is to straightforwardly embed arithmetic into geometry, by identifying whole numbers with evenly spaced points on a line. This idea was ancient Greeks. Another approach is to explain geometry in terms of arithmetic and algebra, by means of coordinate systems, like latitude and longitude on a map. This idea was by Rene Descartes and Karl Weierstrass. Both approaches give rise to essentially the same formal theory, known as second-order arithmetic. This theory includes both Ta and Tg and is adequate for the bulk of modern mathematics. Whether to make geometry more fundamental than arithmetic or vice versa?

·         A set is a collection of objects called the elements of the set. Two sets are identical if and only if they have the same elements. This principle is known as extensionality. Among the axioms of Ts is an axiom of infinity asserting the existence of the infinite set. The set-theoretical approach to arithmetic and geometry is admittedly somewhat artificial. However, the idea of basing all of mathematics on one simple concept, sets, is not yet fully understood and is a topic of current research. The idea of set-theoretical foundations gave rise to the “new math” pedagogy of the 1960’s.