\documentclass[10pt,a4paper]{article}
\usepackage[landscape]{geometry}
\usepackage{synttree}
\usepackage{fullpage}

\begin{document}
\begin{center}
{\em Andreas van Cranenburgh 0440949 \\
Structures for Semantics, assignment 1, \\
University of Amsterdam, February 2010}
\end{center}

\subsection*{Exercise 1}

(1) Well-formed. 
$ \lambda x \lambda R((M(R(x)) = Q) $

(2) Well-formed. 
$ M(Q) = M(Q)$

(3) Well-formed.
$ M(Q) = Q $

(4) Well-formed.
$ \neg ( \exists y ( P(y) \land z \neq y)) $

(5) Not well-formed, because $z$ with type $e$ is applied when type $<e, t>$ was expected.

(6) Well-formed. $ \exists y1 (R(y)(y1)) $

(7) Well-formed. $ P(y) \land \forall y1 ( Q(y1) \rightarrow R(y)(y1)) $
%((lambda x ((p x) ^ (forall y (q y) -> ((r x) y)))) y)

(8) Well-formed. $ \exists y (P(j) \rightarrow \exists w (R(j)(w) \land B(y) \land Q(y))) $
% (exists y ((lambda z ((lambda x ((p x) -> (exists w ((r x) w)))) j) ^ ((lambda x ((b x) ^ (q x)) ) z) )  y))

\subsection*{Exercise 2}

(a) The functions that can be defined in $D_{\langle e, t\rangle}$ are the members of the set defined as: 

%$\displaystyle{\prod_{x \in D}\{<x, t> | t \in \{0, 1\}\}}$

%or alternatively:

$\displaystyle{\prod_{x \in D}\{x\} \times \{0, 1\}}$

To wit: $ \{ \\
 \{ \langle d_1, 0\rangle , \langle d_2, 0\rangle , \langle d_3, 0\rangle \}, \\ 
 \{ \langle d_1, 0\rangle , \langle d_2, 0\rangle , \langle d_3, 1\rangle \}, \\
 \{ \langle d_1, 0\rangle , \langle d_2, 1\rangle , \langle d_3, 0\rangle \}, \\
 \{ \langle d_1, 0\rangle , \langle d_2, 1\rangle , \langle d_3, 1\rangle \}, \\
 \{ \langle d_1, 1\rangle , \langle d_2, 0\rangle , \langle d_3, 0\rangle \}, \\
 \{ \langle d_1, 1\rangle , \langle d_2, 0\rangle , \langle d_3, 1\rangle \}, \\
 \{ \langle d_1, 1\rangle , \langle d_2, 1\rangle , \langle d_3, 0\rangle \}, \\
 \{ \langle d_1, 1\rangle , \langle d_2, 1\rangle , \langle d_3, 1\rangle \}  \\
\} $

(b) With only variables one can only specify the empty and universal functions: 
%, ie., $\{d_1, d_2, d_3\} \times \{0, 1\} $. INCORRECT

\begin{itemize}
\item $ \{\langle d_1, 1\rangle , \langle d_2, 1\rangle , \langle d_3, 1\rangle \} =_{def} \lambda x (x = x) $

\item $ \{\langle d_1, 0\rangle , \langle d_2, 0\rangle , \langle d_3, 0\rangle \} =_{def} \lambda x (x \neq x) $
\end{itemize}

(c)
With the constant for $d_3$ we can define functions singling out this individual, viz. the $d_3$ 
identity function and its negation:

\begin{itemize}
\item $ \{\langle d_1, 0\rangle , \langle d_2, 0\rangle , \langle d_3, 1\rangle \} =_{def} \lambda x (x = a) $

\item $ \{\langle d_1, 1\rangle , \langle d_2, 1\rangle , \langle d_3, 0\rangle \} =_{def} \lambda x (x \neq a) $
\end{itemize}

(d) Using the constant $P = \{ \langle d_1, 1\rangle , \langle d_2, 0\rangle , \langle d_3, 1\rangle \}$, we can trivially specify the function described by $P$, as well as its negation:

\begin{itemize}
\item $ \{\langle d_1, 1\rangle , \langle d_2, 0\rangle , \langle d_3, 1\rangle \} =_{def} \lambda x P(x) $
\item $ \{\langle d_1, 0\rangle , \langle d_2, 1\rangle , \langle d_3, 0\rangle \} =_{def} \lambda x \neg P(x) $
\end{itemize}

Less trivially, we can specify the remaining functions:

\begin{itemize}
\item $ \{ \langle d_1, 0\rangle , \langle d_2, 1\rangle , \langle d_3, 1\rangle \} =_{def} 
	\lambda x (x = a \lor \neg P(x) )$
\item $ \{ \langle d_1, 1\rangle , \langle d_2, 0\rangle , \langle d_3, 0\rangle \} =_{def}
	\lambda x (x \neq a \land P(x) )$
\end{itemize}

\subsection*{Exercise 3}
%quantifiers

\begin{itemize}
\item $ \forall x_e \varphi_t =_{def} \lambda \varphi (\lambda x \varphi = \lambda y \top) $

\item $ \exists x_e \varphi_t =_{def} \neg \forall x \neg \varphi $
\end{itemize}

\subsection*{Exercise 4}
%ditransitive verbs

(a)

lexicon:

every $ \lambda P \lambda Q  \forall x [ Px \land Qx ] $

girl $ girl $

gives (reading one)
$ \lambda B.\lambda C.\lambda A C(\lambda x A(\lambda z(B(\lambda y.(give(x)(y)(z)))))) $

gives (reading two)
$ \lambda B \lambda C.\lambda x.C (\lambda z.B(\lambda y.(give(z)(y)(x)))) $

mary $ \lambda P.P(mary) $

a $ \lambda P.\lambda Q.\exists x [ Px \land Qx ] $

book $ book $

where $A, B, C $ are of type $ \langle \langle e, t \rangle , t \rangle $

Instead of the complicated rule system of EMG I use only two rules:
when the left child can be applied to the right, do so, and vice versa.

\pagebreak
Reading one:

\branchheight{0.7in}
\synttree[
{\begin{tabular}{c} S \\ 
$ \exists x [book(x) \land \forall y [girl(y) \rightarrow (give(x)(mary)(y))]] $ \\ $ t $ \end{tabular}}
[{\begin{tabular}{c} NP \\
$ \lambda Q \forall x (girl(x) \rightarrow Qx) $ \\
$ \langle \langle e, t \rangle , t \rangle $ \end{tabular}}
[{\begin{tabular}{c}every \\ 
$ \lambda P \lambda Q \forall x (Px \rightarrow Qx) $ \\
$ \langle \langle e, t \rangle , \langle \langle e, t \rangle , t \rangle \rangle $\end{tabular}}] 
[{\begin{tabular}{c}
girl
\\ $ girl $ \\
$ \langle e, t \rangle $ \end{tabular}}]] 
[{\begin{tabular}{c} VP \\
$ \lambda A.\exists x [book(x) \land A(\lambda z (give(x)(mary)(z)))] $ \\
$ \langle \langle \langle e, t \rangle , t \rangle , t \rangle $ \end{tabular}}
[
{\begin{tabular}{c} VP \\ 
$ \lambda C \lambda A.C(\lambda x A(\lambda z (give(x)(mary)(z)))) $ \\
$ \langle \langle \langle e, t \rangle ,t \rangle , \langle \langle \langle e, t \rangle , t \rangle , t \rangle \rangle $ \end{tabular}}
[
{\begin{tabular}{c}
gives \\ 
$ \lambda B \lambda C \lambda A.C(\lambda x A(\lambda z (B(\lambda y.(give(x)(y)(z)))))) $ \\
$ \langle \langle \langle e,t \rangle ,t \rangle , \langle \langle \langle e, t \rangle ,t \rangle , \langle \langle \langle e, t \rangle , t \rangle , t \rangle \rangle \rangle % !@#$!%^ this
$
\end{tabular}}] [NP 
[
{\begin{tabular}{c}
Mary \\ 
$ \lambda P.P(mary)$ \\
$ \langle \langle e, t \rangle t \rangle $ \end{tabular}}
]]] [
{\begin{tabular}{c}
NP 
\\ $ \lambda Q \exists x [book(x) \land Qx] $ \\
$ \langle \langle e, t \rangle , t \rangle $ \end{tabular}}
[{\begin{tabular}{c}
a
\\ $ \lambda P \lambda Q \exists x (Px \land Qx) $ \\ 
$ \langle \langle e, t \rangle , \langle \langle e, t \rangle , t \rangle \rangle $ \end{tabular}}] 
[
{\begin{tabular}{c}
book 
\\ $ book $ \\ $ \langle e,t\rangle $ \end{tabular}}
]]]]

\pagebreak
Reading two:

\synttree[
{\begin{tabular}{c} S \\ 
$ \forall x [girl(x) \rightarrow \exists y [book(y) \land (give(y)(mary)(x))]] $ \\ $ t $ \end{tabular}}
[{\begin{tabular}{c} NP \\
$ \lambda Q \forall x (girl(x) \rightarrow Qx) $ \\
$ \langle \langle e, t \rangle , t \rangle $ \end{tabular}}
[{\begin{tabular}{c}every \\ 
$ \lambda P \lambda Q \forall x (Px \rightarrow Qx) $ \\
$ \langle \langle e, t \rangle , \langle \langle e, t \rangle , t \rangle \rangle $\end{tabular}}] 
[{\begin{tabular}{c}
girl
\\ $ girl $ \\
$ \langle e, t \rangle $ \end{tabular}}]] 
[{\begin{tabular}{c} VP \\
$ \lambda x.\exists y [book(y) \land (give(y)(mary)(x))] $ \\
$ \langle e, t \rangle $ \end{tabular}}
[
{\begin{tabular}{c} VP \\ 
$ \lambda C.\lambda x.C(\lambda z (give(z)(mary)(x))) $ \\
$ \langle \langle \langle e, t \rangle ,t \rangle , \langle e, t \rangle \rangle $ \end{tabular}}
[
{\begin{tabular}{c}
gives \\ 
$ \lambda B \lambda C.\lambda x.C (\lambda z.B(\lambda y.(give(z)(y)(x)))) $ \\
$ \langle \langle \langle e, t \rangle ,t \rangle , \langle \langle \langle e, t \rangle , t \rangle , t \rangle \rangle % !@#$!%^ this
$
\end{tabular}}] [NP 
[
{\begin{tabular}{c}
Mary \\ 
$ \lambda P.P(mary)$ \\
$ \langle \langle e, t \rangle t \rangle $ \end{tabular}}
]]] [
{\begin{tabular}{c}
NP 
\\ $ \lambda Q \exists x [book(x) \land Qx] $ \\
$ \langle \langle e, t \rangle , t \rangle $ \end{tabular}}
[{\begin{tabular}{c}
a
\\ $ \lambda P \lambda Q \exists x (Px \land Qx) $ \\ 
$ \langle \langle e, t \rangle , \langle \langle e, t \rangle , t \rangle \rangle $ \end{tabular}}] 
[
{\begin{tabular}{c}
book 
\\ $ book $ \\ $ \langle e,t\rangle $ \end{tabular}}
]]]]

\pagebreak






















(b)
More lexicon:

John $ \lambda P.P(john) $

hits $ \lambda A.\lambda x.A(\lambda y.(hits(y)(x))) $

with (reading one) $ \lambda A.\lambda B.\lambda P.A(\lambda y.B(\lambda x.using(y)(P(x)))) $

with (reading two) $ \lambda A.\lambda B.\lambda P.A(\lambda y.B(\lambda x.has(x)(y) \land P(y))) $


Reading one, first, failed attempt, where $using$ modifies the $hits$ predicate:

%\synttree[S [NP [John]] [VP [VP [hits] [NP [a] [boy]]] [PP [with] [NP [a] [book]]]]]
\synttree[{\begin{tabular}{c} S \\
$ \exists x [book(x) \land \exists y [ boy(y) \land using(x)(hits(y)(john))]] $ \\
$ t $ \end{tabular}}
[NP [
{\begin{tabular}{c} John
\\ $ \lambda P.P(john) $ \\
$ \langle \langle e, t \rangle t \rangle $ \end{tabular}}
]] 
[{\begin{tabular}{c}VP \\
%$ \lambda B.\lambda Q.\exists x [book(x) \land B(\lambda z.using(x)(Q(z)))] $ \\
%$ \lambda y.(\exists x [boy(x) \land hit(y)(x)]) $ \\
$ \lambda z \exists x [book(x) \land \exists y [ boy(y) \land using(x)(hits(y)(z))]] $ \\
$ \langle e, t \rangle $ \end{tabular}}
[{\begin{tabular}{c} VP \\ 
$ \lambda y.(\exists x [boy(x) \land hits(y)(x)]) $ \\
$ \langle e, t \rangle $ \end{tabular}}
[{\begin{tabular}{c} hits \\
$ \lambda A.\lambda x(A(\lambda y(hits(y)(x)))) $ \\
$ \langle \langle \langle e, t \rangle , t \rangle , \langle e, t \rangle \rangle $ \end{tabular}} ]
[{\begin{tabular}{c} NP \\
$ \lambda Q \exists x (boy(x) \land Qx) $ \\
$ \langle \langle e, t \rangle t \rangle $ \end{tabular}}
[{\begin{tabular}{c} a
\\ $ \lambda P \lambda Q \exists x (Px \land Qx) $ \\ 
$ \langle \langle e, t \rangle , \langle \langle e, t \rangle , t \rangle \rangle $ \end{tabular}}]
[{\begin{tabular}{c} boy \\
$ boy $ \\
$ \langle e, t \rangle $ \end{tabular}}]]] 
[{\begin{tabular}{c} PP \\
$ \lambda B.\exists x [book(x) \land B(\lambda P.\lambda z.using(x)(P(z)))] $ \\
$ \langle \langle e, t \rangle , \langle e, t \rangle \rangle $ % NP -> NP 
\end{tabular}}
[{\begin{tabular}{c} with \\
$ \lambda A.\lambda B.(A(\lambda y.B(\lambda P.\lambda x.using(y)(P(x))))) $ \\
$ \langle \langle \langle e, t \rangle , t \rangle , \langle \langle e, t \rangle , \langle e, t \rangle \rangle \rangle $ % NP -> VP -> VP
\end{tabular}} ] 
[{\begin{tabular}{c} NP \\
$ \lambda Q \exists x [book(x) \land Qx]$ \\
$ \langle \langle e, t \rangle , t \rangle $ \end{tabular}}
[{\begin{tabular}{c} a
\\ $ \lambda P \lambda Q \exists x (Px \land Qx) $ \\ 
$ \langle \langle e, t \rangle , \langle \langle e, t \rangle , t \rangle \rangle $ \end{tabular}} ]
[{\begin{tabular}{c} book \\
$ book $ \\
$ \langle e, t \rangle $ \end{tabular}}
]]]]]

\pagebreak
Reading one, second attempt, where $using$ is a separate predicate:

with (reading one) : $ \lambda A.\lambda P.\lambda B.A(\lambda y.B(\lambda x.using(y)(x) \land (P(x)))) $

%\synttree[S [NP [John]] [VP [VP [hits] [NP [a] [boy]]] [PP [with] [NP [a] [book]]]]]
\synttree[{\begin{tabular}{c} S \\
$ \exists x [book(x) \land using(x)(john) \land \exists y [ boy(y) \land hits(y)(john)]] $ \\
$ t $ \end{tabular}}
[NP [
{\begin{tabular}{c} John
\\ $ \lambda P.P(john) $ \\
$ \langle \langle e, t \rangle t \rangle $ \end{tabular}}
]] 
[{\begin{tabular}{c}VP \\
%$ \lambda B.\lambda Q.\exists x [book(x) \land B(\lambda z.using(x)(Q(z)))] $ \\
%$ \lambda y.(\exists x [boy(x) \land hit(y)(x)]) $ \\
$ \lambda A.\exists x [book(x) \land A(\lambda z.(using(x)(z) \land \exists y [ boy(y) \land hits(y)(z)])] $ \\
$ \langle e, t \rangle $ \end{tabular}}
[{\begin{tabular}{c} VP \\ 
$ \lambda z.(\exists x [boy(x) \land hits(x)(z)]) $ \\
$ \langle e, t \rangle $ \end{tabular}}
[{\begin{tabular}{c} hits \\
$ \lambda A.\lambda x(A(\lambda y(hits(y)(x)))) $ \\
$ \langle \langle \langle e, t \rangle , t \rangle , \langle e, t \rangle \rangle $ \end{tabular}} ]
[{\begin{tabular}{c} NP \\
$ \lambda Q \exists x (boy(x) \land Qx) $ \\
$ \langle \langle e, t \rangle t \rangle $ \end{tabular}}
[{\begin{tabular}{c} a
\\ $ \lambda P \lambda Q \exists x (Px \land Qx) $ \\ 
$ \langle \langle e, t \rangle , \langle \langle e, t \rangle , t \rangle \rangle $ \end{tabular}}]
[{\begin{tabular}{c} boy \\
$ boy $ \\
$ \langle e, t \rangle $ \end{tabular}}]]] 
[{\begin{tabular}{c} PP \\
$ \lambda P.\lambda B.\exists x [book(x) \land B(\lambda z.using(x)(z) \land P(z))] $ \\
$ \langle \langle e, t \rangle , \langle e, t \rangle \rangle $ % NP -> NP 
\end{tabular}}
[{\begin{tabular}{c} with \\
$ \lambda A.\lambda P.\lambda B.(A(\lambda y.B(\lambda x.using(y)(x) \land P(x)))) $ \\
$ \langle \langle \langle e, t \rangle , t \rangle , \langle \langle e, t \rangle , \langle e, t \rangle \rangle \rangle $ % NP -> VP -> VP
\end{tabular}} ] 
[{\begin{tabular}{c} NP \\
$ \lambda Q \exists x [book(x) \land Qx]$ \\
$ \langle \langle e, t \rangle , t \rangle $ \end{tabular}}
[{\begin{tabular}{c} a
\\ $ \lambda P \lambda Q \exists x (Px \land Qx) $ \\ 
$ \langle \langle e, t \rangle , \langle \langle e, t \rangle , t \rangle \rangle $ \end{tabular}} ]
[{\begin{tabular}{c} book \\
$ book $ \\
$ \langle e, t \rangle $ \end{tabular}}
]]]]]


\pagebreak
Reading two: 

\synttree[
{\begin{tabular}{c}
S \\
$ \exists x [book(x) \land \exists y [ boy(y) \land has(x)(y) \land (hits(y)(john))]] $ \\
$ t $ 
\end{tabular}}
[NP 
[
{\begin{tabular}{c}
John
\\ $ \lambda P.P(john) $ \\
$ \langle \langle e, t \rangle t \rangle $ \end{tabular}}
]] 
[
{\begin{tabular}{c}
VP \\ 
$ \lambda z. \exists x [book(x) \land \exists y [ boy(y) \land has(x)(y) \land (hits(y)(z))]] $ \\
$ \langle e, t \rangle $
\end{tabular}}
[
{\begin{tabular}{c}
hits \\
$ \lambda A.\lambda x.A(\lambda y(hits(y)(x))) $ \\
$ \langle \langle \langle e, t \rangle , t \rangle , \langle e, t \rangle \rangle $ 
\end{tabular}}
] 
[
{\begin{tabular}{c}
NP \\
$ \lambda P.\exists x [book(x) \land \exists y [ boy(y) \land has(x)(y) \land P(y)]] $ \\
$ \langle \langle e, t \rangle , t \rangle $
\end{tabular}}
[
{\begin{tabular}{c}
NP \\
$ \lambda Q \exists x (boy(x) \land Qx) $ \\
$ \langle \langle e, t \rangle t \rangle $ 
\end{tabular}}
[
{\begin{tabular}{c}
a
\\ $ \lambda P \lambda Q \exists x (Px \land Qx) $ \\ 
$ \langle \langle e, t \rangle , \langle \langle e, t \rangle , t \rangle \rangle $ \end{tabular}}]
[
{\begin{tabular}{c}
boy \\
$ boy $ \\
$ \langle e, t \rangle $
\end{tabular}}
]] 
[
{\begin{tabular}{c}
PP \\
$ \lambda B.\lambda P.\exists x(book(x) \land B(\lambda y.has(x)(y) \land P(y))) $ \\ 
$ \langle \langle \langle e, t \rangle , t \rangle , \langle \langle e, t \rangle , t \rangle \rangle $ % NP -> NP
\end{tabular}}
[
{\begin{tabular}{c}
with \\
$ \lambda A.\lambda B.\lambda P.A(\lambda x.B(\lambda y.has(x)(y) \land P(y))) $ \\
$ \langle \langle \langle e, t \rangle , t \rangle , \langle \langle \langle e, t \rangle , t \rangle , \langle \langle e, t \rangle , t \rangle \rangle \rangle $ % NP -> NP -> NP
\end{tabular}}
] 
[
{\begin{tabular}{c}
NP \\
$ \lambda Q \exists x (book(x) \land Qx)$ \\
$ \langle \langle e, t \rangle , t \rangle $ 
\end{tabular}}
[{\begin{tabular}{c}
a
\\ $ \lambda P \lambda Q \exists x (Px \land Qx) $ \\ 
$ \langle \langle e, t \rangle , \langle \langle e, t \rangle , t \rangle \rangle $ \end{tabular}}]
[
{\begin{tabular}{c}
book \\
$ book $ \\
$ \langle e, t \rangle $
\end{tabular}}
]]]]]]

\pagebreak
\subsection*{Exercise 5}
%vp ellipsis
More lexicon:

smokes : $ smokes $ 

and : $ \lambda P \lambda A \lambda y.A(\lambda x (P(x) \land P(y))) $

Bill : $ \lambda P.P(bill) $

does : $ \lambda A.A $

too : $ \lambda D.D $

where $ D $ is of type $ \langle \langle \langle e, t \rangle , t \rangle , \langle \langle e, t \rangle , t \rangle \rangle $


%\synttree[{\begin{tabular}{c}S \\$ smokes(john) \land smokes(bill) $ \\$ t $\end{tabular}} [S [NP [John]] [VP [VP [smokes]]]] [SCON [CON [and]] [S [NP [Bill]] [VP [does] [too]]]]]

Apologies for the unorthodox phrase structure, but this is what my semantic
intuitions told me.

\synttree[{
\begin{tabular}{c}S \\
$ smokes(john) \land smokes(bill) $ \\
$ t $\end{tabular}}
[
{\begin{tabular}{c}
VP \\
$ \lambda y.(smokes(john) \land smokes(y)) $ \\
$ \langle e, t\rangle $ \end{tabular}}
[
{\begin{tabular}{c}
NP \\
$ \lambda P.P(john) $ \\
$ \langle \langle e, t \rangle , t \rangle $ \end{tabular}}
[John]] 
[
{\begin{tabular}{c}
VP \\
$ \lambda A.\lambda y.A(\lambda x (smokes(x) \land smokes(y))) $ \\ 
$ \langle \langle \langle e,t \rangle ,t\rangle , \langle e, t \rangle \rangle$ 
\end{tabular}}
[
{\begin{tabular}{c}
smokes \\
$ smokes $ \\
$ \langle e, t \rangle $ \end{tabular}}
] [
{\begin{tabular}{c}
CON \\
$ \lambda P \lambda A \lambda y.A(\lambda x.(Px \land Py)) $ \\
$ \langle \langle e, t \rangle , \langle \langle \langle e,t \rangle ,t\rangle , \langle e, t \rangle \rangle \rangle $ \end{tabular}}
[and]]]]
[
{\begin{tabular}{c}
S \\
$ \lambda P P(bill) $ \\ 
$ \langle \langle e, t \rangle , t \rangle $ \end{tabular}}
[
{\begin{tabular}{c}
NP \\
$ \lambda P.P(bill) $ \\
$ \langle \langle e, t \rangle , t \rangle $ \end{tabular}}
[Bill]] 
[
{\begin{tabular}{c}
VP \\
$ \lambda A.A $ \\
$ \langle \langle \langle e, t \rangle , t \rangle , \langle \langle e, t \rangle , t \rangle \rangle $ 
\end{tabular}}
[
{\begin{tabular}{c}
does \\
$ \lambda A.A$ \\
$ \langle \langle \langle e, t \rangle , t \rangle , \langle \langle e, t \rangle , t \rangle \rangle $
\end{tabular}}
] 
[
{\begin{tabular}{c}
too \\
$ \lambda D.D$ \\
$ \langle \langle \langle \langle e, t \rangle , t \rangle , \langle \langle e, t \rangle , t \rangle \rangle , \langle \langle \langle e, t \rangle , t \rangle , \langle \langle e, t \rangle , t \rangle \rangle \rangle $
\end{tabular}}
]
]]]

\end{document}