232 lines
12 KiB
Markdown
232 lines
12 KiB
Markdown
---
|
|
title: The Many Functions of Functor
|
|
---
|
|
|
|
Although I became most familiar with the word through exposure to
|
|
Category Theory, I knew that "functor" had at least a couple of other
|
|
meanings in other contexts. I'd looked up its history before, but
|
|
neglected to write it down. Now I won't have to do it again!
|
|
|
|
The Players: Carnap, Quine, Tarski
|
|
----------------------------------
|
|
|
|
According to a number of sources, "functor" entered the lexicon via
|
|
the work of [Rudolf Carnap][RC]. Carnap studied philosophy, physics,
|
|
and mathematics at university, including several courses in
|
|
mathematics and logic from Gottlob Frege. He later studied the theory
|
|
of relativity at Berlin, where Einstein was professor of physics.
|
|
|
|
His dissertation concerned an axiomatic system for space-time theory,
|
|
which was written from a philosophical point of view. Thereafter he
|
|
became involved with the [Vienna Circle][VC] of philosophers and ended
|
|
up as a leading member. This group advanced the philosophy of logical
|
|
positivism and was deeply concerned with the philosophy and practice of
|
|
science.
|
|
|
|
In 1929, Carnap met [Alfred Tarski][AT], a Polish logician from the
|
|
[Lvov-Warsaw school of philosophy][LW] who was developing a logical
|
|
basis for the meaning of truth. A few years later, he moved to Prague
|
|
to become a professor and wrote the 1934 book *The Logical Syntax of
|
|
Language*, which contains (as far as I am aware) the first use of
|
|
"functor". I will return to the book in a moment, after making a few
|
|
more of Carnap's connections apparent.
|
|
|
|
In Prague, Carnap met the philosophers [Willard van Orman Quine][WQ]
|
|
and Charles Morris. When World War II broke out, they helped Carnap
|
|
escape to the United States, where he remained. Tarski escaped Poland
|
|
to the USA as well, and the trio of Carnap, Quine, and Tarski were
|
|
thus able to meet (along with other leading philosophers and
|
|
logicians) for a [year at Harvard][CTQ] to work on the leading issues
|
|
of analytical philosophy.
|
|
|
|
Carnap's Logical Syntax of Language
|
|
-----------------------------------
|
|
|
|
As part of his desire to put the practice of science on firm logical
|
|
ground, Carnap wanted to have an appropriate understanding of language
|
|
that could be used to properly express scientific truths.
|
|
[Logical Syntax][LSL] creates a formal system, a meta-language, with
|
|
which to reason about constructs of natural language.
|
|
|
|
The meta-language defines syntactic constructs belonging to four
|
|
categories:
|
|
|
|
1. A fixed set of 11 symbols
|
|
2. (Numerical) variables
|
|
3. Constant numerals
|
|
4. Predicates
|
|
5. Functors
|
|
|
|
The point was to remove ambiguity of names and to add precision by
|
|
designating things numerically as much as possible.
|
|
|
|
### Basic forms
|
|
|
|
Designation of *things* was done positionally by numerical coordinates
|
|
rather than by symbolic name. Positional numerals were defined
|
|
inductively from `0` designating the initial position and primes
|
|
marking successive positions. The traditional Arabic numerals were
|
|
introduced as shorthand, as well as the possibility of tupling numbers
|
|
to represent higher-dimensional positions.
|
|
|
|
Expressing properties of things was done via *predicates* over
|
|
positions. These could express direct properties of things or
|
|
relationships between things, but in a symbolic manner via the
|
|
name-form of the predicate.
|
|
|
|
In order to represent properties numerically, the idea of *functor*
|
|
was introduced. Functors were similar in form to predicates, in that
|
|
they had a name-form and took numeric arguments, but instead of
|
|
representing facts and/or relations they represented another numeric
|
|
value.
|
|
|
|
### Expressions
|
|
|
|
Valid combinations of the basic forms create expressions. Two
|
|
important kinds of expressions were "sentences" and "numerical
|
|
expressions."
|
|
|
|
Sentences express logical truth value, so the expression of a
|
|
predicate form is a sentence. Some of the symbols are combining forms
|
|
that create sentences as well, such as equations.
|
|
|
|
Expressions of functors, on the other hand, are always numerical
|
|
expressions. Numeric expression was very important to Carnap for the
|
|
precise transmission of scientific detail, so he valued this precision
|
|
of functor expression over the more "vague" relative or symbolic
|
|
nature of predicate expressions.
|
|
|
|
Although Carnap's concept of functor seems similar to that of a
|
|
mathematical function, it is actually quite different. Functions are
|
|
always a fixed relation between numbers, but functors may represent
|
|
numerical observations of the world as well, such as the example given
|
|
early on of the *temperature-functor* that has the numeric value of
|
|
the temperature of its argument.
|
|
|
|
Connection to Category Theory
|
|
-----------------------------
|
|
|
|
[Saunders Mac Lane][SM], one of the founders of Category Theory, was
|
|
an associate of Carnap's at the University of Chicago and was given
|
|
the English translation of *Logical Syntax of Language* in 1938 for
|
|
review. He was not particularly interested in the philosophical
|
|
aspects of Carnap's usage of "functor", but in it he saw a perfect
|
|
candidate to resolve a similar [notational dilemma][TO] in Category
|
|
Theory.
|
|
|
|
So, the Category Theory notion of "functor" is related to Carnap's
|
|
original usage by similarity of role, as a stand-in for something
|
|
"function-like" in some aspect, rather than being related by
|
|
definition or usage. Steve Awodey, an associate of Mac Lane's and a
|
|
category theorist himself, [remarked][CCC] that the word "functor" may
|
|
end up being "Carnap's most far-reaching contribution to modern
|
|
mathematics."
|
|
|
|
Quine's Predicate-Functor Logic
|
|
-------------------------------
|
|
|
|
Quine, Tarski, and Carnap [conversed][CTQ] about Carnap's logical
|
|
syntax while they were together at Harvard, and it seems to have
|
|
influenced Quine's thinking about logic. He certainly adopted the term
|
|
"functor", though he expanded its meaning. Quine thought that Carnap's
|
|
connective symbols, e.g. the equality symbol that generates equations,
|
|
should be replaced by more general operators that construct sentences
|
|
via composition.
|
|
|
|
Quine later referred to these operators as "predicate-functors"
|
|
(possibly following Carnap's convention of naming a sort of functor by
|
|
its domain, e.g. "temperature-functor") and developed an [algebraic
|
|
logic][ALP] based around them.
|
|
|
|
He later gave a more [general definition][ML] to the term "functor"
|
|
itself, encompassing this new role as a generator of sentences rather
|
|
than a numeric relation. It should also be noted that while Carnap was
|
|
concerned with discussing language in general, including natural
|
|
language, Quine was primarily interested in formal logic systems. In
|
|
particular, his Predicate Functor Logic was an alternative to
|
|
Combinatory Logic that avoided higher-order functions and the
|
|
resulting encroachment of set theory into the system, which he viewed
|
|
as outside the scope of logic.
|
|
|
|
Categorical Grammar
|
|
-------------------
|
|
|
|
Tarski's early career was influenced by his thesis advisor
|
|
[Stanislaw Lesniewski][SL] and also by the other prominent Lvov-Warsaw
|
|
philospher [Kazimierz Ajdukiewicz][KA]. Lesniewski worked in the field
|
|
of ontology and was particularly interested in semantic categories;
|
|
this use of "category" is due to Husserl and can be traced back to
|
|
Aristotle.
|
|
|
|
Ajdukiewicz applied the notion of categories to the syntax of language
|
|
to create the field of [categorical grammar][CG]. The syntactic
|
|
structure was thought to determine the semantic meaning in reasonable
|
|
languages, thus the borrowed categorical terminology.
|
|
|
|
Syntactic categories are an equivalence class of expressions such that
|
|
a sentence containing one of these sentences remains a sentence when
|
|
it is substituted for any other expression that is a member of the
|
|
same category. As such, syntactic categories are essentially the same
|
|
as the types of Russell.
|
|
|
|
There are two kinds of categories; basic categories, which are
|
|
enumerated in the definition of the language, and all others are
|
|
complex (derived) categories. Expressions in complex categories are
|
|
created by combining other expressions via a special kind of "functor"
|
|
expression. These other expressions are called "arguments" to the
|
|
functor, and the new compound expression is the functor's "value".
|
|
|
|
Although Ajdukiewicz's early work on syntactic categories predated
|
|
*Logical Syntax of Language*, it seems likely that the field of
|
|
Categorical Grammar was influenced both directly via the text, which
|
|
shared similar goals, and probably also via the influence of Tarski
|
|
and Quine who made use of it (if not for precisely the same purposes)
|
|
in their own work.
|
|
|
|
Categorical Grammar is primarily concerned with matters of natural
|
|
language, but Joachim Lambek's work on the [Lambek Calculus][LC] drew
|
|
it somewhat back towards mathematics and logic. Lambek Calculus
|
|
resembles in some ways Alonzo Church's Lambda Calculus (of the simply
|
|
typed variety), Quine's Functor Predicate Logic, and combinatory
|
|
logic.
|
|
|
|
Of parenthetical interest is the fact that the logicians of the
|
|
Lvov-Warsaw school preferred to place their functors at the front of
|
|
their arguments; by this practice they allowed expressions to be
|
|
unambiguous without parentheses. This practice became known as "Polish
|
|
Notation", which is familiar to many users of Hewlett Packard
|
|
calculators by way of its similarly bracketless Reverse Polish
|
|
Notation.
|
|
|
|
Functors in Programming
|
|
-----------------------
|
|
|
|
The use of functor via its Category Theory interpretation is familiar
|
|
to many functional programmers today. It has a direct, though not
|
|
all-encompassing, presence in Haskell via the Functor type class.
|
|
Perhaps not quite so familiar is the linguistic interpretation as used
|
|
by [Prolog][PRO]. And the SML Module language uses the term functor;
|
|
although this can be interpreted in the categorical sense, it also
|
|
makes sense from the perspective of Quine's Predicate Functor
|
|
Logic. C++'s use of functor to mean "function-like object" seems to be
|
|
another repurposing of the word along the lines of Mac Lane's.
|
|
|
|
[RC]: http://www.iep.utm.edu/carnap/ "IEP: Rudolf Carnap"
|
|
[VC]: http://www.iep.utm.edu/viennacr/ "IEP: Vienna Circle"
|
|
[AT]: http://plato.stanford.edu/entries/tarski/ "SEP: Alfred Tarski"
|
|
[LW]: http://plato.stanford.edu/entries/lvov-warsaw/ "SEP: Lvov-Warsaw School"
|
|
[WQ]: http://plato.stanford.edu/entries/quine/ "SEP: Willard van Orman Quine"
|
|
[CTQ]: http://d-scholarship.pitt.edu/7768/ "Carnap, Tarski, and Quine's Year Together: Logic, Science, and Mathematics"
|
|
[LSL]: http://books.google.com/books?id=3e3gAwAAQBAJ&lpg=PP1&dq=rudolf%20carnap&pg=PA14#v=onepage&q=functor&f=false "Google Books: Logical Syntax of Language"
|
|
[SM]: http://www-news.uchicago.edu/releases/05/050421.maclane.shtml "Saunders Mac Lane, Mathematician, 1909-2005"
|
|
[TO]: http://books.google.com/books?id=41bHxtHxjUAC&lpg=PA69&ots=Vj9lsB_gf2&dq=carnap%20functor&pg=PA70#v=snippet&q=%22metamathematical%20expression%22&f=false "Tool and Object: A History and Philosophy of Category Theory"
|
|
[CCC]: http://books.google.com/books?id=DR5DAwAAQBAJ&lpg=PA197&ots=hUJG4tMAo7&dq=carnap%20logische%20syntax%20der%20sprache%20english&pg=PA197#v=onepage&q=functor&f=false "The Cambridge Companion to Carnap"
|
|
[CTQ]: http://books.google.com/books?id=s14AAwAAQBAJ&lpg=PA139&ots=-2_K3d7uP-&dq=quine%20carnap%20functor&pg=PA145#v=snippet&q=Quine%20statement%20composition&f=false "Carnap, Tarski, and Quine at Harvard"
|
|
[ALP]: http://books.google.com/books?id=YReOv31gdVIC&lpg=PA283&dq=%22Algebraic%20Logic%20and%20Predicate%20Functors%22&pg=PA283#v=onepage&q=%22Algebraic%20Logic%20and%20Predicate%20Functors%22&f=false "Algebraic Logic and Predicate Functors"
|
|
[ML]: http://books.google.com/books?id=liHivlUYWcUC&lpg=PP1&dq=quine&pg=PA129#v=onepage&q=functor&f=false "Methods of Logic"
|
|
[CG]: http://books.google.com/books?id=iVVAAAAAQBAJ&lpg=PA234&ots=P6VDNfpt8Q&dq=frege%20functor&pg=PA7#v=onepage&q=functor&f=false "Categorical Grammar"
|
|
[SL]: http://plato.stanford.edu/entries/lesniewski/ "SEP: Stanisław Leśniewski"
|
|
[KA]: http://en.wikipedia.org/wiki/Kazimierz_Ajdukiewicz "Kazimierz Ajdukiewicz"
|
|
[LC]: http://ling.umd.edu/~alxndrw/CGReadings/lambek-58.pdf "The Mathematics of Sentence Structure"
|
|
[PRO]: http://www.cse.unsw.edu.au/~billw/prologdict.html#functor "Prolog Functor"
|