\documentclass[12pt]{article}
\usepackage{amsmath,amsthm,amsfonts,amssymb,latexsym, hyperref}

\begin{document}

\begin{center}
\textbf{Predicate Logic / First Order Logic}
\end{center}

\

The predicate logic system, also called first order logic, subsumes the logical rules that we have already considered (the `propositional logic').  It adds quantifiers, free variables and relations.

\

Quantifiers. There are two quantifiers $\forall, \exists$:
\begin{eqnarray*}
\forall & \mbox{means} & \mbox{`for all'} \\
\exists & \mbox{means} & \mbox{`there exists'}.
\end{eqnarray*}

\

The letters, $x, y, z$ are typically used for free variables.

\

Follow are some examples of relations I've made up.

\begin{eqnarray*}
H(x) & \mbox{means} & x \mbox{ is human} \\
M(x) & \mbox{means} & x \mbox{ is mortal}.
\end{eqnarray*}
So the statement $H(\mbox{Socrates})$ is true (if we don't worry about the time factor or change the ``is'' to ``was''); and the statement $H(\mbox{Mickey Mouse})$ is not true.  So I can use a quantifier to tell us that there is such a thing as `Socrates' and that Socrates is human:
$$\exists x(x = \mbox{Socrates})(H(x)).$$
We would read this as, `There exists an $x$ such that $x$ is \textit{Socrates} so that $x$ is human.
And I can say that humans are mortal:
$$\forall x(H(x) \Rightarrow M(x)).$$
The standard syllogism about Socrates can be written,
$$[(\forall x (H(x) \Rightarrow M(x))) \wedge (\exists x(x=\mbox{Socrates})(H(x)))] \Rightarrow M(\mbox{Socrates}).$$
Notice that the following statement is also true,
$$[(\forall x (H(x) \Rightarrow M(x))) \wedge (\exists x(x=\mbox{Mickey Mouse})(H(x)))] \Rightarrow M(\mbox{Mickey Mouse}).$$

For another example, consider the familiar arithmetic relation $R(x,y)$ which means $x$ is less than $y$ and which may be abbreviated $x < y$.  So we can state the tri-part axiom (assume that the variables $x$ and $y$ are numbers; this avoids leading off with the relation stating $\forall x (x \mbox{ is a number}))$:
$$\forall x (\forall y ((x<y)\vee (y<x) \vee (x=y))).$$

\

Exercise 1a. Convert each of the following statements into an English sentence without using the predicate symbols and determine whether or not the statements are true.  For each of the statements assume that the universe $U$ is the set of real numbers.  So that the statement $(x\in R) \wedge (x<2)$ can be rewritten as $(x<2)$.

\

\noindent
I.  Assume $r=5$:

\begin{eqnarray*}
\mbox{a.)} &  & \exists x (x^2 < r) \\
\mbox{b.)} &  & \forall x (x^2 < r) \\
\mbox{c.)} &  & \exists x (x^2 > r) \\
\mbox{d.)} &  & \forall x (x^2 > r) \\
\mbox{e.)} &  & \sim \exists x (x^2 < r) \\
\mbox{f.)} &  & \sim \forall x (x^2 < r) \\
\mbox{g.)} &  & \sim \exists x (x^2 > r) \\
\mbox{h.)} &  & \sim \forall x (x^2 > r) \\
\mbox{i.)} &  & \exists x (\sim (x^2 < r)) \\
\mbox{j.)} &  & \forall x (\sim (x^2 < r)) \\
\mbox{k.)} &  & \exists x (\sim (x^2 > r)) \\
\mbox{l.)} &  & \forall x (\sim (x^2 > r)).
\end{eqnarray*}

Note that some of the third group of four are equivalent to some of the second group of four.  Also note that, for example, that $\sim (x^2 < r)$ is mathematically equivalent to $(x^2 \ge r)$.

\

\noindent
II.  Assume $r=0$: repeat exercises a-l for $r=0$.

\

\noindent
III.  Let $P_r(x)$ be the statement $x^2<r$ and let $Q_r(x)$ be the statement $x^2>r$.
\begin{eqnarray*}
\mbox{a.)} &  & \exists r \exists x P_r(x) \\
\mbox{b.)} &  & \forall r \exists x P_r(x) \\
\mbox{c.)} &  & \exists r \forall x P_r(x) \\
\mbox{d.)} &  & \forall r \forall x P_r(x) \\
\mbox{e.)} &  & \sim \exists r \exists x P_r(x) \\
\mbox{f.)} &  & \sim \forall r \exists x P_r(x) \\
\mbox{g.}  &  & \sim \exists r \forall x P_r(x) \\
\mbox{h.)} &  & \sim \forall r \forall x P_r(x) \\
\mbox{a.)} &  & \exists r \exists x (\sim P_r(x)) \\
\mbox{b.)} &  & \forall r \exists x (\sim P_r(x)) \\
\mbox{c.)} &  & \exists r \forall x (\sim P_r(x)) \\
\mbox{d.)} &  & \forall r \forall x (\sim P_r(x)).
\end{eqnarray*}

Again note that some of the third group of four are equivalent to some of the second group of four.

\

Exercise 1b.  Convert each of the following statements into a symbolic representation in the predicate logic.  Assume that $R(x,y)$ is some arbitrary relation.

    a.) For some pair $x,y$ the relation $R(x,y)$ is true.

    b.) For some pair $x,y$ the relation $R(x,y)$ is false.

    c.) The relation $R(x,y)$ is always true.

    d.) The relation $R(x,y)$ is always false.

    e.) For some value of $x$ the relation $R(x,y)$ is always true.

    f.) For some value of $x$ the relation $R(x,y)$ is always false.

    g.) For each $y$ there is an $x$ so that $R(x,y)$ true.

    h.) There is an $x$ so that for each $y$, $R(x,y)$ true.

    i.) If $x \in U$ then there is a $y \in U$ so that $R(x,y)$.

\

Exercise 2.  Translate the following logical statement into words, assume that all free variables are numbers and that the relations $<, +, -, \times, \ldots$ take on the values we're used to. Assume that $0, 1, 3, 3.56,$ etc. are the fixed constants with their traditional values.  Determine which logical statements are true and find counter examples for those that are not true.  Assume that $R(x,y)$ is some arbitrary relation.
$$
\begin{array}{ll}
 \mbox{a.} & \forall x \forall y (x+y = y + x) \\
 \mbox{b.} & \forall x \forall y (x-y = y - x) \\
 \mbox{c.} & \forall x \exists y (x+y = y + x) \\
 \mbox{d.} & \forall x \exists y (x-y = y - x) \\
 \mbox{e.} & \forall x \exists y (x < y) \\
 \mbox{f.} & \exists y \forall x (x < y) \\
 \mbox{g.} & \forall x ((0<x) \Rightarrow \exists y ((y<x)\wedge (0<y))) \\
 \mbox{h.} & \sim(\exists y \forall x (x<y)) \\
 \mbox{i.} & \forall y \exists x (\sim(x<y))\\
 \mbox{j.} & \sim(\exists y \forall x R(x,y))  \Leftrightarrow \forall y \exists x (\sim R(x,y))\\
 \mbox{k.} & \sim(\exists y \forall x R(x,y))  \Leftrightarrow \exists y \forall x (\sim R(x,y)).
\end{array}$$

\

\begin{center}
\textbf{Examples}
\end{center}

\

For these examples we assume our universe $U$ is the set of real numbers.  So for a number $x$, $H(x)$ is a statement about $x$.  For example let $H(x)$ be the statement $x^2>4$.  I'll use the notation $H(x): x^2>4$ to indicate this.  In this case $H(1.5)$ is false and the statement $H(3)$ is true.  The statement $\exists x ( H(x))$ is true because there exists an $x$ such that $H(x)$, namely $x=3$.  And the statement $\forall x (H(x))$ is false because $H(x)$ is not true for all $x$.  Therefore I can write, for this meaning of $H(x)$:
\begin{eqnarray*}
\exists x(H(x)) & \mbox{equivalently} & \exists x (x^2>4) \ \ \mbox{ is true}; \\
\forall x(H(x)) & \mbox{equivalently}  & \forall x (x^2>4) \ \ \mbox{ is false}.  \\
\end{eqnarray*}

\

Exercise 3.  For an arbitrary relation $D(x)$, justify the following :
\begin{eqnarray*}
\sim (\exists x D(x))  & = & \forall x (\sim D(x));\\
\sim (\forall x D(x))  & = & \exists x (\sim D(x)).
\end{eqnarray*}

\

When there are two variables it gets more complicated.  Suppose $B(x,y)$ is the statement $x < y^2$.  The statement
$$\forall x \exists y B(x,y)$$
should be parsed as follows:
$$\forall x (\exists y (B(x,y))).$$
So in order for this statement to be true, we need to have that for all possible $x$ values, the statement $\exists y( B(x,y))$ must be true.
We can interpret this in English as

``For all $x$ there is a $y$ so that $B(x,y)$.''

\noindent
Equivalently:

``If $x$ is a number, there is a $y$ so that $B(x,y)$.''

\noindent
or

``If $x$ is a number, there is a $y$ so that $x < y^2$.''

\noindent
This statement is true, in fact any $y$ such that $y> \sqrt{|x|}$ should work.  If this is correct, this says that the statement
$$\forall x(B(x, \sqrt{|x|} +1))$$
is true.

However the statement
$$\exists y \forall x  B(x,y)$$
is not true because there is no (fixed) number $y$ so that $x < y^2$ is always true; in fact we can always pick $x= y^2 + 1$ so make the statement false.

\noindent
Here are how the other possibilities go:

\begin{eqnarray*}
\exists x \forall y (x<y^2)  &   \mbox{is true}; \\
\forall y \exists x (x<y^2)  &   \mbox{is true}.
\end{eqnarray*}

\

Problem:  Is the following true for an arbitrary relation $R(x,y)$:
\begin{eqnarray*}
\exists x \forall y (R(x,y))  & \Rightarrow &\forall y  \exists x (R(x,y)).
\end{eqnarray*}








\end{document}