## 1. Pre-History


Before we begin our discussion of propositional functions, it will
be helpful to note what came before their introduction. In
traditional logic, the role of propositional functions is
approximately held by terms. In traditional logic, statements such as
'dogs are mammals' are treated as postulating a relation between the
terms 'dogs' and 'mammals'.


A term is treated either extensionally as a class of objects or
intensionally as a set of properties. The 'intent' of the
term 'dog' includes all the properties that are included
in the intent of 'mammal'. The intensional treatment of
'dogs are mammals' interprets this sentence as true
because the semantic interpretation of the subject is a
*superset* of the interpretation of the predicate. On the
extensional treatment of the sentence, however, the sentence is true
because the interpretation of the subject (the class of dogs) is a
*subset* of the interpretation of the predicate (the set of
mammals).


These two treatments of the predicate are typical of the two
traditions in traditional logic--the intensional and the
extensional traditions. Logicians who can be counted among the
intensional logicians are Gottfried Leibniz, Johann Lambert, William
Hamilton, Stanley Jevons, and Hugh MacColl. Among the extensional
logicians are George Boole, Augustus De Morgan, Charles Peirce, and
John Venn.


The treatment of terms in the intensional logic tradition property
of certain sentences might seem strange to modern readers. The
intension of a predicate, in 20th Century philosophy, includes only
those properties that any competent speaker of a language would
associate with that predicate. These properties are not enough to
make true ordinary statements like 'every dog in my house is
asleep'. But we can make sense of the intensional view of terms by
considering its origins. One of the founders of the intensional logic
tradition is Leibniz, who thinks that all truths are grounded in the
nature of individuals. The complete concept of an individual contains
everything that is true of it. Building on this, we can see that the
complete concept of a term will include enough to ground any truth
about it as well.


In both the intensional and extensional logic traditions, we see
theories of complex terms. In the extensional tradition, disjunctive
and conjunctive terms are interpreted by taking the union and
intersection of classes. The conjunctive term
*AB* is interpreted as the intersection of the class *A*
and the class
*B* and the extension of the disjunctive term *A+B* is
understood as the union of the extensions of
*A* and *B*. 


In the intensional tradition, the reverse holds. The
term *AB* is interpreted as the union of the properties in the
intent of
*A* and the intent of *B* and *A+B* is
interpreted as the intersection of the properties in
*A* and *B*. This reversal makes sense, since more
things fit a smaller number of properties and fewer things fit a
larger number of properties.


Although some of the logicians working in term logic have very
complicated treatments of negation, we can see the origin of the
modern conception in the extensional tradition as well. In Boole and
most of his followers, the negation of a term is understood as the
set theoretic complement of the class represented by that term. For
this reason, the negation of classical propositional logic is often
called 'Boolean negation'.


## 2. The Logic of Relatives


In Charles Peirce's 'Logic of Relatives' (1883), we see a
move towards an understanding of terms as functions. One problem with
traditional term logic is that it lacks the ability to deal with
relations. Peirce's logic of relatives is meant to remedy that. He
adds terms to Boolean algebra that represent relations, and gives an
extensional interpretation of them. They are not propositional
functions in the full sense. Peirce's relatives are 'common
names' that represent classes of pairs of objects (1883, 328).
Thus, the logic of relatives represents a generalization of
traditional logic rather than a departure from it.


Peirce extends the algebra of terms to deal with particular
features of relations. Like other terms, we can have conjunctive,
disjunctive, and negative terms. Where
*f* and *g* are relatives, then *fg* represents
the class of pairs (*I*,*J*) such that *I* bears both
*f* and *g* to *J*. Similarly, the disjunctive
relative, *f*+*g* is such that it represent
(*I*,*J*) if *I* bears either
*f* or *g* to *J* and *f'*--the negation of the
term *f*--represents the class of pairs (*I*,*J*) such that
*f* does not hold between them. Peirce also has a composition
operator, ; , such that
*f*;*g* names (*I*,*J*) if there is some
entity *K* such that *f* names (*I*,*K*)
and
*g* names (*K*,*J*).


In 'The Critic of Arguments' (1892), Peirce adopts a
notion that is even closer to that of a propositional function. There
he develops the concept of the 'rhema'. He says the rhema
is like a relative term, but it is not a term. It contains a copula,
that is, when joined to the correct number of arguments it produces
an assertion. For example, '\_\_ is bought by \_\_ from \_\_ for \_\_' is a
four-place rhema. Applying it to four objects
*a*, *b*, *c*, and *d* produces the assertion that *a* is bought by *b* from *c* for *d* (ibid. 420). 


One especially interesting point about Peirce's rhema is that he
uses the same chemical analogy as Frege does when they discuss the
relation between relations and their arguments. They both compare
relations (and properties) to 'atoms or radicals with
unsaturated bonds'. What exactly this analogy says of relations
or properties, either in Frege or Peirce is somewhat unclear.



See the entry on Peirce's logic, for
a more complete exposition of his work. 


## 3. Propositional Functions and the Birth of Mathematical Logic


In the work of Giuseppe Peano (1858-1932), we find another
important step towards the modern notion of a propositional
function. Although his work is not as sophisticated as Frege's (see
below), it is important because it is influential particularly on
Bertrand Russell. 


In his 'Principles of Arithmetic Presented by a New
Method' (1889), Peano introduces propositional connectives in the
modern sense (an implication, negation, conjunction, disjunction, and
a biconditional) and propositional constants (a verum and a falsum).



More important for us is his treatment of quantification. Peano
allows propositions to contain variables, that is to say, he utilizes
open formulas. He does not give an interpretation of open
formulas. He does not tell us what they represent. But they are used
in his theory of quantification. Peano only has a universal
quantifier. He does not define an existential quantifier in the
'Principles'. The quantifier is always attached to a
conditional or biconditional. Quantified propositions are always of
the form



> 
> *A* [?]*x*,*y*,... *B*
> 
> 
> 


or



> 
> *A* =*x*,*y*,... *B*
> 
> 
> 


Peano reads '*A* [?]*x*,*y*,...
*B*' as saying 'whatever
*x*,*y*,... may be, from the proposition *A* one
deduces *B*' and '=' is Peano's biconditional, that he
defines in the usual way from the conditional and conjunction. But he
provides us with no more interpretation than that. He refers to
variables as 'indeterminate objects', but does not discuss
what this or what a proposition (or propositional function) that
contains propositional objects might be.


## 4. Fregean Functions and Concepts


In Frege we have a fairly general interpretation of sentences as
expressing functions applying to arguments. The view that I explore
here is one that he develops in the 1890s.


Consider the sentence



> 
> My dog is asleep on the floor.
> 
> 
> 


This sentence, like all linguistic expressions, has
both a sense and a referent. Its sense is an abstract object--a
thought. Its referent is its truth value (which at the moment is the
True). We will discuss Frege's analysis of the thought soon, but right
now let us look at the referents of the expressions that make up this
sentence.


The expression 'my dog', according to Frege, is a
singular term. It picks out an object (my dog, Zermela). The
expression 'is asleep on the floor' refers to a
*concept*. Concepts are functions. In this case, the concept is
a function from objects to truth values (which are also objects). So,
we can treat the above sentence as representing the concept \_\_
*is asleep on the floor* as applying to the object *my
dog*. 


Frege's concepts are very nearly propositional
functions in the modern sense. Frege explicitly recognizes them as
functions. Like Peirce's rhema, a concept is
*unsaturated*. They are in some sense incomplete. Although
Frege never gets beyond the metaphorical in his description of the
incompleteness of concepts and other functions, one thing is clear:
the distinction between objects and functions is the main division in
his metaphysics. There is
*something* special about functions that makes them very
different from objects.


Let us consider 'my dog is asleep on the floor'
again. Frege thinks that this sentence can be analyzed in various
different ways. Instead of treating it as expressing the application
of \_\_ *is asleep on the floor* to *my dog*, we can think
of it as expressing the application of the concept



> 
> *my dog is asleep on* \_\_
> 
> 


to the object



> 
> *the floor*
> 
> 


(see Frege 1919). Frege recognizes what is now a
commonplace in the logical analysis of natural language.
*We can attribute more than one logical form to a single
sentence*. Let us call this the
**principle of multiple analyses**. Frege does not claim
that the principle always holds, but as we shall see, modern type
theory does claim this.


With regard to the sense of sentences, they are also the result of
applying functions to objects. The sense of 'my dog' is an
abstract object. The sense of 'is asleep on the floor' is
a function from individual senses, like that of 'my dog',
to thoughts (see Frege 1891). The sense of 'is asleep on the
floor' is a *conceptual sense*. It would seem that the
principle of multiple analyses holds as much for senses as it does for
referents. Frege, however, sometimes talks as if the senses of the
constituent expressions of a sentence are actually contained somehow
in the thought. It is difficult to understand how all such senses
could be in the thought if there are different ways in which the
sentence can be analyzed into constituent expressions.



In addition to concepts and conceptual senses, Frege
holds that there are extensions of concepts. Frege calls an extension
of a concept a 'course of values'. A course of values is
determined by the value that the concept has for each of its
arguments. Thus, the course of values for the concept \_\_ *is a
dog* records that its value for the argument Zermela is the True
and for Socrates is the False, and so on. If two concepts have the
same values for every argument, then their courses of values are the
same. Thus, courses of values are extensional.


For more about Frege's theory of concepts and its relation to his logic, see
the entry on Frege's theorem and foundations for arithmetic.


## 5. The Emergence of Propositional Functions


The term 'propositional function' appears in print for
the first time in Bertrand Russell's
*Principles of Mathematics* (1903). Russell introduces the
notion through a discussion of kinds of propositions. Consider
propositions of the type that says of something that it is a dog. This
is the kind '*x* is a dog'. This kind is a
propositional function that takes any object *o* to the
proposition that *o* is a dog.


In this period, Russell holds that propositions are entities that
have individuals and properties and relations as constituents. The
proposition that Socrates is a man has Socrates and the property of
being a man as constituents. In complex propositions the relation
between propositional function and the proposition is less
clear. Like Frege, Russell allows the abstraction of a propositional
function from any omission of an entity from a proposition. Thus, we
can view the proposition




> 
> *if Socrates drinks hemlock he will die* 
> 
> 


as representing the application of the function



> 
> *x drinks hemlock [?] x will die* 
> 
> 


to Socrates, or the function



> 
> *Socrates will drink x* [?] *Socrates will die*
> 
> 


to hemlock, and so on. In other words, Russell accepts the
principle of multiple analyses.


In the *Principles*, the quantifier 'all' is analyzed as a
part of referring phrases that pick out classes (1903, 72). This, we
can see, is a hold-over from the 19th Century extensional logicians
(see Section 1). But in slightly later works, such as 'On
Denoting' (1905), propositional functions are said to be
constituents of universal propositions. According to this analysis the
proposition expressed by sentences such as 'All dogs bark' is made up
of the propositional function *x is a dog* [?] *x
barks* and a function (of propositional functions) that is
represented by the quantifier phrase 'all'. Quantified propositions
are interesting for us because they contain propositional functions as
constituents.


It is unclear whether Russell holds that propositional functions
also occur as constituents in singular propositions like
*if Socrates drinks hemlock he will die*. These propositions do
contain properties, like
*dies*, and relations, like *drinks*, but it is
controversial as to whether Russell thinks that these are
propositional functions (see Linsky 1999 and Landini 1998).


## 6. Propositional Functions in Simple Type Theory


While writing the *Principles of Mathematics*, Russell
discovered the paradox that now bears his name. Before we get to
Russell's paradox, let us discuss some the method
of **diagonalization** by which this and many other paradoxes are
generated.


The power set of a set *S*, *S* contains all
the subsets of *S*. Georg Cantor (1845-1918) used the method of
diagonalization to show that for any set *S*,
*S* is larger than *S*.


Here is Cantor's proof. Suppose that *S*
and *S* are the same size. Then, by the set-theoretic
definition of "same size" (more correctly, 'same
cardinality') there is a one-to-one **surjection**
between *S* and *S*. This means that there is a
function that matches up each member of *S* with a unique
member of *S* so that there are no members of
*S* left over. Let us call this
function, *f*. Then, if *x* is a member
of *S*, *f*(*x*) is in *S*. Now,
since *S* is the power set of *S*, it may be
that *x* is in *f*(*x*) or it may not be
in *f*(*x*). Let us now define a set *C*:



> 
> *C* = {*x* [?] *S*: 
> *x* [?] *f*(*x*)}
> 
> 
> 


Clearly, *C* is a subset of *S*, so it is in
*S*. By hypothesis, *f* is **onto**--for
every member *y* of *S*, there is
an *x* [?] *S* such
that *f*(*x*) = *y*. Thus there must be
some *c* [?] *S* such that



> 
> *f*(*c*) = *C*
> 
> 
> 


Now, either



> 
> *c* [?] *C*
> 
> 
> 


or



> 
> *c* [?] *C*.
> 
> 
> 


Suppose that *c* is in *C*. Then, by the definition
of *C*, *c* is not in
*f*(*c*). That is to say, *c*
[?] *C*. But, if *c* is not in *C*,
then *c* [?] *f*(*c*). So, by the definition
of *C*, *c* is in *C*. Thus,



> 
> *c* is in *C* if and only if *c* is not
> in *C*.
> 
> 


Therefore, the assumption that a set is the same size
as its power set leads to a paradox, and so this assumption must be
false.


Cantor's theorem has important consequences for the theory of
propositional functions. Consider a model for a (first-order) logical
language that has a domain *D*. The variables of the language
range over members of *D*. Now let us add predicate variables
to the language. These stand for propositional functions. How are we
to interpret them in the model? The standard way of doing so--that
is inherited from the extensional logic tradition--is to have
predicate variables range over subsets of the domain. A model in which
predicate variables range over all subsets of the domain is called a
'standard model' for second-order logic. Cantor's theorem
tells us that the domain for predicate variables in the standard model
is larger than the domain for individual variables. If we have
predicates of predicates, then the domain for third order predicates
is even larger. And so on.


Russell's paradox is very closely related to Cantor's
theorem. There are two versions of the paradox: (1) the class
version; (2) the propositional function version. I only discuss the
propositional function version of the paradox.


In his early writings, Russell wants logic to be a
universal science. It should allow us to talk about properties
of everything. By this he means that the variables in logic should be
taken to range over all entities. But propositional functions,
at least in the *Principles*, are entities. So variables
should range over them. Now consider the predicate
*R* such that,



> 
> 
> ([?]*x*)(*Rx* =
> !*xx*)
> 
> 
> 
> 


(Russell's predicate *R* is very similar to
Cantor's set *C*.) If we instantiate
and substitute *R* for *x*, we obtain



> 
> *RR* [?] !*RR*
> 
> 


It seems, then, that the treatment of variables as
completely general together with the liberty to define propositional
functions by means of any well-formed formula enables us to derive a
contradiction.


Russell blocks the contradiction in
the *Principles* by the introduction of a theory of types. This
is a simple theory of types, that only distinguishes between the types
of various propositional functions (or, in its class-form, of
classes). Let us depart from Russell's own exposition of the theory
of types in order to give a more rigorous and more modern version of
the theory. This will make my presentations of the ramified theory of
types and more modern versions of type theory easier.


We'll use one basic type, *i* (the type of individuals) and
define the types as follows:


1. *i* is a type;
2. if *t*1,..., *t**n*
are types, then so is
<*t*1,..., *t**n*>, 
 where *n* [?] 0.
3. Nothing else is a type except by repeated applications of
(1) and (2).


The type
<*t*1,..., *t**n*>
is the type of a relation among entities of
types *t*1,..., *t**n*.
But, for simplicity, we will interpret this as the type of a function
that takes these entities to a proposition. (Note that
when *n* = 0, then the empty type, < >, is
the type for propositions.) This definition incorporates the idea of a
well-founded structure. There are no cycles here. We cannot have a
function that takes as an argument a function of the same or higher
type. Thus, simple type theory bans the sort of self-application that
gives rise to Russell's paradox.


The type hierarchy corresponds neatly to the hierarchy of domains
that we saw in our discussion of Cantor's theorem. A unary predicate
has the type <*i*>; its domain is *D*--the set
of individuals. A unary predicate of predicates has the type
<<*i*>>, and this corresponds to the domain of
subsets of *D*. And so on.


For more, 
see the entry on
 Russell's paradox.


## 7. Propositional Functions in Ramified Type Theory


After the *Principles*, however, Russell comes to believe
that the simple theory of types is insufficient. The reason for
it has to do with the
 *liar paradox*. Suppose that '*L*' is a name
for the proposition:



> 
> *L* is false.
> 
> 


This statement is false if and only if it is true.
The problem here has something to do with self-reference, but it
cannot be avoided by the simple theory of types alone. For simple
types only give us a hierarchy of types of propositional functions.
In simple type theory, all propositions have the same type. 


The idea behind ramified type theory is to introduce a
hierarchy of propositions as well. On this view, propositions and
propositional functions have an
*order*. If a propositional function is applied to a
proposition of a particular order, then it yields a proposition of a
higher order. And every function must have a higher order than its
arguments. Thus, we avoid the liar paradox by banning a proposition
from occurring within itself. If a proposition *p* occurs
within another proposition, as the argument of a function such as
*x is false*, then the resulting proposition is of a higher
order than *p*.


Unfortunately, Russell never gives a precise formulation of
ramified type theory. Perhaps the best formulation is due to Alonzo
Church (1976).[1]


Almost at the same time as he adopts the ramified theory of types,
Russell abandons propositions. From about 1908 until 1918, although
Russell retains the idea that there are true propositions, he denies
that there are false ones. When we think about something that is
false, say, *Zermela is a cat*, we are not thinking about a
false proposition, but rather the objects of our thought are just
Zermela and the property of being a cat. It might seem odd to have a
hierarchy especially designed to stratify the propositions and then
claim that there are no propositions. Some interpreters, however,
have claimed that Russell's denial of the existence of propositions
should not be taken seriously and that there are very good reasons to
read *Principia* as being largely a theory of propositions
(see Church 1984).


One reason to take the ramified theory of types seriously (even
without accepting propositions) is that it can be usefully
incorporated into a substitutional theory of quantification. On the
substitutional interpretation of the quantifiers, a universally
quantified formula such as ([?]*x*)*Fx* is true if
and only if all of its instances
*Fa*1, *Fa*2, *Fa*3,...
are true. Similarly, ([?]*x*)*Fa* is true if and
only if at least one of its instances is true.



Consider a substitutional interpretation of quantifiers with
variables ranging over predicates, as in the formula,
([?]*P*)*Pa*. This formula is true if and only if all
of its instances are true. On a simple theory of types, the type of
the variable
*P* is <*i*>, since its arguments are all
individuals (or singular terms). But the simple type of the function,
([?]*P*)*Px* is also <i>. So an instance of
([?]*P*)*Pa* is ([?]*P*)*Pa*
itself. A substitutional interpretation of the quantifiers requires
that instances be simpler than the formulas of which they are
instances. In this case, all we find out is that a particular formula
is true only if it is true. This is uninformative and it seems
viciously circular.


To block this sort of circularity, we can turn to the ramified
theory of types. On the ramified theory, the propositional function
([?]*P*)*Px* is of order 2, because of the presence
of the quantifier binding a variable of order 1. In this way, the
ramified theory forces formulas to be simpler (at least in terms of
order) than the formulas of which they are instances (see Hazen and
Davoren 2000).


## 8. What is a Propositional Function in Russell?


After 1905, we see in Russell a parsimonious inclination. He wants
to eliminate entities from his ontology. Some time between 1908 and
1910 he begins to deny the existence of propositions and this denial
continues until he develops a theory of propositions as structures of
images or words in (1918). What, then, is the fate of propositional
functions? It might seem difficult to understand what a propositional
function is without the existence of propositions, but Russell's view
is, not that complicated. Russell only rejects false propositions. He
retains facts in his ontology. Propositional functions, in
*Principia*, are what we now call 'partial
functions'. That is to say, they do not always have values. For
example, the propositional function
*\_\_ is a dog* does not have a value for the Sydney Opera House
taken as an argument, but it does have a value when my dog is taken as
its argument. So, the rejection of false propositions does not cause a
serious problem for the theory of propositional functions in
Russell.


Having dealt with that problem, let us go on to see what Whitehead
and Russell think the nature of propositional functions is. In
*Principia*, they say:



> 
> By a 'propositional function' we mean something which
> contains a variable *x*, and expresses a proposition as soon
> as a value is assigned to *x*. That is to say, it differs from a
> proposition solely by the fact that it is ambiguous: it contains a
> variable of which the value is unassigned. (1910, 38).
> 
> 
> 


In this passage, it seems as though they are saying that a
propositional function is an ambiguous proposition. In light of the
rejection of propositions, this view is especially hard to
understand. Urquhart (2003) says that for Whitehead and Russell, a
propositional function is something rather like a formula. This seems
right, since propositional functions contain variables.


But what exactly are propositional functions in *Principia*?
This is a matter of heated debate among Russell scholars. Perhaps the
most influential interpretation is the constructive interpretation,
due to Kurt Godel (1944). On this interpretation, propositional
functions are human constructs of some sort. They depend on our
ability to think about them or refer to them. A version of the
constructive interpretation can also be found in Linsky (1999). There
is also a more nominalist interpretation in Landini (1998). On the
realist side, are the interpretations given by Alonzo Church (1984)
and Warren Goldfarb (1989). Goldfarb thinks that the logical theory of
*Principia* is motivated by Russell's attempt to find the real
nature of propositional functions and that this nature is independent
of our thinking about it. Goldfarb has a good point, since Russell's
logic is supposed to be a perspicuous representation of the way things
are. But Russell often seems to deny that propositional functions are
real entities.


## 9. Possible Worlds and Propositional Functions


Jumping ahead some decades, adding possible worlds together with
set theory to the logicians' toolbox has provided them with a very
powerful and flexible framework for doing semantics.


First, let us recall the modern notion of a function. A function is
a set of ordered pairs. If <*a*,*b*> is in a
function
*f*, this means that the value of *f* for the
argument *a* is
*b* or, more concisely, *f*(*a*) = *b*. By
the mathematical definition of a function, for each argument of a
function there is one and only one value. So, if the ordered pair
<*a,b*> is in a function
*f* and so is <*a*,*c*>, then *b* is the
same thing as *c*.


The construction of propositional functions begins with possible
worlds and the assumption that there are sets. Let us call the set of
possible worlds
*W*. A proposition is a set of possible worlds. The proposition
that Zermela barks, for example, is all the sets of worlds in which
Zermela barks. We also need to assume that there is a set
*I* of possible individuals (i.e., the individuals that exist in
at least one possible world). We now have all the materials to
construct a simple type-theoretic hierarchy of functions.



The usual treatment of the meaning of predicates differs slightly
from the manner I have described here. Usually, the intension of a
predicate is taken to be a function from possible worlds to sets of
individuals (or sets of ordered pairs of individuals for binary
relations, ordered triples for three place relations, and so
on). Strictly speaking, these functions are not propositional
functions because they do not take propositions as values. But for
each such function, we can construct an 'equivalent'
propositional functions by using a process called
'Currying' after the logician Haskell Curry. Let's start
with a function
*f* from worlds to sets of individuals. Then we can construct
the corresponding propositional function
*g* as follows. For each world *w* and
individual *i*, we construct
*g* so that



> 
> *w* is in *g*(*i*) if and only
> if *i* is in *f*(*w*).
> 
> 


So, the more standard treatment of the meanings of
predicates is really equivalent to the use of propositional
functions.


## 10. Montague Semantics


Now that we have a whole hierarchy of propositional functions, we
should find some work for them to do. One theory in which
propositional functions do good work is Montague semantics, developed
in the late 1960s by Richard Montague.


In order to understand Montague's method we need to
understand *lambda abstraction*. For the formula
*A*(*x*) we read the expression
l*x*[*A*(*x*)] as a predicate expression. It
extension (in a given possible world) is the set of things that
satisfy the formula
*A*(*x*). Lambda abstractors are governed by two rules,
known as a-conversion and b-reduction:



> 
> (a-con) *A*(*a*) (a formula with *a* free
> for *x*) can be replaced by
> l*x*[*A*(*x*)]*a*.
> 
> 



> 
> (b-red)
> l*x*[*A*(*x*)]*a* can be replaced by
> *A*(*a*) (where *x* is free for *a*
> in *A*(*x*)).
> 
> 


Because of the equivalence between a formula *A*(*x*) and
l*x*[*A*(*x*)]*a*, one might wonder why add
lambda abstractors to our language. In Montague semantics, the answer
has to do with the very direct way that he translates expressions of
natural languages into his logical language. We will discuss that
soon, but first let us learn a bit about Montague's
*intensional logic*.


Montague adds two other pieces of notation to his
language: [?] and  [?]. The
expression [?]l*x*[*Fx*] represents
a function from worlds to sets of individuals. Given a possible world
*w*, [?]l*x*[*Fx*] represents a function that takes
*w* to the extension of l*x*[*Fx*]. The
operator [?] takes expressions of the form
[?]l*x*[*Fx*] 'down' to
their extensions at the world in which the expression is being
evaluated. For example, the extension of
[?][?]l*x*[*Fx*]
at *w* is just the same as the extension of
l*x*[*Fx*] at *w*.


What is so special about Montague semantics is that it can be used
in a very direct way as a semantics for large fragments of natural
languages. Consider the following sentence:



> 
> Zermela barks.
> 
> 


The meaning of this sentence is understood in Montague
semantics as a structure of the meanings of its constituent
expressions. Montague represents the meanings of expressions using
translation rules. Here we use the following translation rules:



> 
> **Zermela** translates into
> l*P*[([?]*P*)*z*]
> 
> 



> 
> **barks** translates
> into [?]*B*
> 
> 


Now we can construct a formula that gives the meaning
of 'Zermela barks':



> 
> l*P*[([?]*P*)*z*][?]*B*
> 
> 


Notice that in constructing the sentence we place the
expressions in the same order in which they occur in English. The use
of lambda abstracts allows us to reverse the order of two expressions
from the way in which they would appear in ordinary statements of a
formal logical language (that does not have lambdas). Now we can use
b-reduction to obtain:



> 
> ([?][?]*B*)*z*
> 
> 


And now we apply Montague's rule to
eliminate [?][?]:



> 
> *Bz*
> 
> 


In this process we start with an expression that has the same order
of expressions as the original English sentence and then reduce it to
a very standard formula of logic. This tells us that the truth
condition of the sentence 'Zermela barks' is the set of
worlds that is the proposition expressed by *Bz*. Of course we
knew that independently of Montague's work, but the point is that the
Montague reduction shows us how we can connect the surface grammar of
English sentences to the formula of our logical language. The formula
of standard logic, moreover, displays its truth-conditions in a very
perspicuous way. So, the Montague reduction shows us the connection
between sentences of natural languages to their truth conditions.


## 11. Categorial Grammar


Categorial grammars were first constructed in the 1930s by Kazamir
Ajdukiewicz (1890-1963), and developed by Yehoshua Bar Hillel
(1915-1975) and Joachim Lambek (1922-) in the 1950s an
1960s. Categorial grammars are logical tools for representing the
syntax of languages.


In categorial grammar, the syntax of languages is represented using
a different sort of generalization of the functional notation than in
Montague semantics. In Montague Semantics, the lambda abstractor is
used to move the meaning of an expression to the location that the
expression occupies in a sentence. In categorial grammar, predicates
and many other sorts of expressions are taken to be functions of
sorts. But there is a distinction in categorial grammar between two
sorts of application of a function to its arguments. 


Let's see how this works. Let's start with the primitive types CN
(common noun) and NP (noun phrase). The indefinite article 'a' takes
a common noun (on its right) and returns a NP. So it has the type
NP/CN. The common noun 'dog', of course, has the type CN. We write
'*A* has the type *T*' as
'*A*[?]*T*'. So we have,



> 
> **a** [?] NP/CN
> 
> 


and



> 
> **dog** [?] CN
> 
> 


In order to put these two sequents together, we can
use a form of the rule modus ponens which says that from a sequent *X*
[?] *A*/*B* and a sequent *Y* [?] *B*, we can derive the sequent *X*.*Y*
[?] *A*. We can use this rule to derive:



> 
> **a**.**dog** [?] NP
> 
> 


Moreover, an intransitive verb has the type NP\S,
where S is the type of sentences. The backslash in NP\S means that the
expression takes an argument of type NP
*on the left side* and returns an expression of type S. The
verb 'barks' is intransitive, that is,



> 
> **barks** [?] NP\S
> 
> 


The version of modus ponens that we use with the backslash is
slightly different. It tells us that from *X* [?] *A*\*B* and *Y* [?]
*A* we can derive *Y*.*X* [?] *B*. So we now can obtain,



> 
> (**a**.**dog**).**barks** [?] S
> 
> 


This says that 'a dog barks' is a sentence.


The logics used to describe grammars in this way
are substructural logics.


What is of interest to us here is that in categorial grammars
determiners such as 'a' and verbs are thought of as functions, but
they can differ from one another in terms of whether they take
arguments on their right or on their left. In the set theoretic
concept of function as a set of ordered pairs, functions are thought
of just in terms of their correlating arguments with values. A
function, as it is understood in categorial grammar has more
structure than this. This is an interesting generalization of the
notion of a function as it is used in logic. We can see that it also
has important links to the concept of a propositional function,
especially as it is used in Montague semantics.


In categorial grammar we can attribute more than one type to a
single expression in a language. Let us call this the
**principle of multiple types**. Here is an example due to Mark
Steadman. Consider the sentence



> 
> I dislike, and Mary enjoys musicals.
> 
> 


The transitive verbs 'dislike' and 'enjoys' have the
type (NP\S)/NP, that is, they take a noun phrase on their right and
return a verb phrase. But in the case of 'I dislike, and Mary enjoys
musicals' the verbs are separated from their object and joined to
their objects. Steadman deals with this by raising the type of the
subjects 'I' and 'Mary'. Usually, we treat these words as having the
type NP, but here they have the type S/(NP\S). This is the type of an
expression that takes a verb phrase on its right and returns a
sentence. Steadman then uses a rule that makes the backslash
transitive and derives that 'I.dislike' has the type S/NP, which takes
a noun phrase (such as 'musicals') on its right an returns a
sentence.


We can see that the principle of multiple types also holds if
analyze sentences other type theories, such as the simple theory of
types. For consider the sentence



> 
> Mary eats a hamburger.
> 
> 


In interpreting this sentence we can take 'Mary' to be
of type *i*, but we can also take it to be of type
*<<i>>*, that is, the type of a propositional
function on propositional functions of individuals. We can also raise
the type of 'eats a hamburger' to
*<<<i>>>*, a propositional function on
propositional functions on propositional functions on individuals. And
so on. The principle of multiple types and the principle of multiple
analyses together show that a single expression or sentence can be
interpreted as having a very large number of logical forms.


## 12. Conclusion


This brief history of propositional functions shows that they are
useful entities and that they have played a central role in logic as
it is used in philosophy and linguistics. I have omitted the more
mathematical uses of propositional functions, for example, in
Russell's and Ramsey's constructions of classes, and in treatments of
general models for higher-order logic. But the topic of propositional
functions is a big one and we can't cover it all in a single
encyclopedia article.