Week 2 [2023-04-13 Thu]

Our analysis is woefully inadequate.

It fails to predict that a sentence like John is hungry and sleepy entails John is hungry and John is sleepy, or that John is not tired entails It is not the case that John is tired.

To see this, note that we do not analyse the internal structure of sentences, so that a sentence like John is hungry is treated as a single lexical item, p_7 say, with features \(\textsf{s}}\), and that John is not hungry is also a lexical item, perhaps p_2, with the same features.

In order to predict relations between sentences, we need to introduce connections between them, and there are no formal connections between lexical items. Our strategy here is simply a continuation of our previous one: connections between expressions are established by building them from connected pieces.

So if John is not hungry is built from some of the same lexical items as John is hungry, their meanings will then be related in some way.

Consider the lexical items below and their semantic types.

Lexeme	Features	Meaning : Type
John	\(\textsf{d}\)	\(\textbf{j} : e\)
is	\(\hbox{ =}\textsf{pred}.\textsf{d}\!\!\hbox{ =}.\textsf{s}\)	\(\lambda A,a.a\in A : \texttt{Set}(e)\rightarrow e\rightarrow t\)
hungry	\(\textsf{pred}\)	\(\textbf{H}:\texttt{Set}(e)\)

Here we treat hungry as denoting a set of individuals—to evaluate the truth of sentences involving the word hungry, we need to know who is hungry. John is treated as an individual, and is simply combines the meaning of the predicate with the meaning of its subject.

The boolean words are treated as set theoretic operations:

Lexeme	Features	Meaning : Type
not	\(\hbox{ =}\textsf{pred}.\textsf{pred}\)	\(\lambda A.\overline{A} : \texttt{Set}(e)\rightarrow \texttt{Set}(e)\)
and	\(\hbox{ =}\textsf{pred}.\textsf{pred}\!\!\hbox{ =}.\textsf{pred}\)	\(\lambda A,B.A\cap B:\texttt{Set}(e)\rightarrow \texttt{Set}(e)\rightarrow \texttt{Set}(e)\)

The new categories we have created map onto semantic types in the following manner: \(\left[

\begin{array}{r@{$\ \mapsto\ $}l} \textsf{s} & t \\ \textsf{d} & e \\ \textsf{pred} & \texttt{Set}(e) \end{array}

\right.\)

Unifying lexical items

Now we are in a pickle. We have two sets of lexical items for what are intuitively the same words:

Lexeme	Features	Meaning : Type
not	\(\hbox{ =}\textsf{s}.\textsf{s}\)	\(\lambda p.\neg p : t\rightarrow t\)
and	\(\hbox{ =}\textsf{s}.\textsf{s}\!\!\hbox{ =}.\textsf{s}\)	\(\lambda p,q.p\wedge q :t\rightarrow t\rightarrow t\)
not	\(\hbox{ =}\textsf{pred}.\textsf{pred}\)	\(\lambda A.\overline{A} : \texttt{Set}(e)\rightarrow \texttt{Set}(e)\)
and	\(\hbox{ =}\textsf{pred}.\textsf{pred}\!\!\hbox{ =}.\textsf{pred}\)	\(\lambda A,B.A\cap B\texttt{Set}(e)\rightarrow \texttt{Set}(e)\rightarrow \texttt{Set}(e)\)

In the ideal world, we would have a single lexical entry for each word:

Lexeme	Features	Meaning : Type
not	\(\hbox{ =}\alpha.\alpha\)	???
and	\(\hbox{ =}\alpha.\alpha\!\!\hbox{ =}.\alpha\)	???

Here, we have used variables for feature names, to indicate that e.g. not can combine with any category. However, it is not clear what it should mean! We need to find a single semantic value that generalizes predicate and sentential negation.

As the domains t and Set(e) have no elements in common, any general meaning that can be assigned to the boolean words must somehow be ignoring the details of these domains, and instead leveraging some abstract structure these domains share.

Both domains have a natural order relationship that can be defined on them:

t

\(p \le q\) iff p implies q

Set(e)

\(A \le B\) iff \(A \subseteq B\)

Both orders are in fact partial orders: they are reflexive, antisymmetric, and transitive.

To come up with a domain independent characterization of the meanings of our logical connectives, we must try to reformulate their meanings in these two domains without using anything other than this shared structure. We cannot do much with just a less than or equal to relation, but we shall try. Since all we can do is compare elements with one another, let us introduce terminology for this relation. If \(a \le b\), I will call a a lower bound for b, and b an upper bound for a. Generalizing somewhat, if a is less than or equal to every element in a set B, we say that a is a lower bound for B, and similarly if b is greater than or equal to every element in a set A, b is an upper bound for A. Now let us begin with and and or. Consider in the domain of truth values:¹

• b and c is always a lower bound for b and c

  b	c	b and c
  1	1	1
  1	0	0
  0	1	0
  0	0	0

  in fact, whenever there are multiple lower bounds for b and c, as in the case of b=c=1, where both 0 and 1 are lower bounds, we choose the greatest (aka biggest) such element, namely 1.

• b or c is always an upper bound for b and c

  b	c	b or c
  1	1	1
  1	0	1
  0	1	1
  0	0	0

  and again, whenever there are multiple upper bounds, as in the case of b=c=0, where both 0 and 1 are, we choose the least (aka smallest) such element, namely 0.

Now in the domain of sets, we have that:

• A and B is always lte (recall: a subset of) A and of B. Moreover, it is not just any subset (the emptyset is a subset of every set), but the greatest such.
• A or B is always gte (recall: a superset of) A and of B. Moreover, it is not just any superset (the entire universe is a superset of every set), but the least such.

We can advance the claim that:

• and denotes the greatest lower bound operation.
• or denotes the least upper bound operation.

A poset that has greatest lower bounds and least upper bounds for every pair of elements is called a lattice (German: Verband).

Readings

• MSL chapter 8