Last updated 27jan15 and added to 1feb15.

Review of Math Logic from MA347 Prerequisite
\textit{ $\C$ 2015, Prof. George K. Francis, Mathematics Department, University of Illinois}

\begin{document}
\section{Introduction}

This lesson reviews what is needed in this course, whether you learned it
in the prerequisite MA347 at U Illinois, Urbana, or elsewhere. If you have
never seen this material, you can still profit from these pages and master
the content well enough to get by.

This page collects diverse links to source you will need to study for this
course. This page will fill in addtional material and well as elaborate
visit it.

Here is the briefest link to Advice
Some Logic and
Lots of Symbols  to get you started.

Here is the review of the
propositional calculus,
Lesson on Logic and Truthtables .

If you prefer to watch two video segments on the same material, here
is

5 minute Introduction  and a 20 minute elaboration of the above .pdf:

Propositional Calculus .

There remains a review of the Predicate Calclus which you may have learned
in a more casual way in MA347 or other math courses. We prefer to revie/teach
this material as part of new lessons on Euclidean Geometry.

\section{Predicate Calculus Review}

Suffice it mention here is that most mathematical propositions are assertions
about all members in a particular class of objects, for instance, all real
numbers. Others assert only there is at least one instance
for which the predicate is true. The former are called
\textit{universally quantified predicates} and the latter are called
\textit{existentially quantified predicates}. We use functional notations,
like $P(x)$ for sentences that say something about a \textit{dummy variable}
$t$. As soon as we stick a quantifier in front of them, they become propositions, because they are either true or false.

You are familiar, from the calculus, with
$(\forall \epsilon > 0) (\exists \delta > 0) ( 0 < |x-a| < \delta \Rightarrow |f(x) - f(a)|) < \epsilon$.
for the definition of
the continuity of the function $f$ at the point $a$. You see that continuity,
$cont(f,a)$, is already quite a complicated proposition about $f,a$. Do you remember how
to assert that $f$ is \textbf{continuous} at $a$? Possibly not. But there is
a nice mechanical way of figuring this out using the predicate calculus.
See below

First, suppose $P(t)$ is a proposition but with a subject $t$ which is not
specified. To assert that it is universally the case, we write
$(\forall t)P(t)$, and to say it holds only for some cases, we write
$(\exists t)P(t)$. Note that the negation for the universal statement is
an existential one, and vice versa:

\begin{eqnarray*}
\neg (\forall t)P(t) & \equiv  (\exists t)(\neg P(t)) \\
\neg (\exists t)Q(t) & \equiv  (\forall t)(\neg Q(t)) \\
\end{eqnarray*}

It is important to note the role of qualified quantifications, namely
those that also specify attributes of the dummy variables, as in our
example on continuity. Suppose $A(t)$ is some restriction, such as
$\epsilon$ is a positive real number, $\epsilon >0$. Then, recall

\begin{eqnarray*}
(\forall A(t))P(t) & \mbox{ really means } (\forall t)(A(t)\implies P(t))\\
(\exists B(t))Q(t) & \mbox{ really means } (\exists t)(B(t) \and  P(t))\\
\end{eqnarray*}

But there is little harm in using the informal, restricted quantifiers in
mathematics. In other areas, like law, one should be more careful. The
big question is whether we have similar rules for for negations with
restricted quantifiers, and here is a proof:

\begin{eqnarray*}
\neg(\forall A(t)P(t) &\equiv& \neg(\forall t)(A(t) \implies P(t)) \\
&\equiv& (\exists t)(\neg( A(t) \implies P(t))) \\
&\equiv& (\exists t)(\neg( \neg A(t) \or \negP(t))) \\
&\equiv& (\exists t)( A(t) \and \neg P(t))) \\
&\equiv& (\exists A(t)(\neg P(t)) \\
\end{eqnarray*}

Filecard L1 (TBA) Can you also compute the negation of a restricted existential
proposition the same way?

We are now ready to discover what a discontinuity at $f(a)$ means quite
mechanically.

$\neg (\forall \epsilon > 0) (\exists \delta > 0) ( 0 < |x-a| < \delta \implies |f(x) - f(a)|)$
$\equiv$
$(\exists \epsilon > 0) (\forall \delta > 0) ( \exists 0 < |x-a| < \delta )(|f(x) - f(a)| \ge \epsilon)$

Filecard L2 (TBA) Can you supply the intermediate steps in this proof?

Note. Put solutions into your Journal for the duration until a filecard
for this lesson is constructed.

\section{Syllogisms}
What you learned about the mathematical use of logic above, the propositional
and the predicate calculus, dates back only to about 1900, even though the
Greeks also invented logic, the Romans applied it to law, and the medieval
scholastics applied it to philosophy. Here are some ancient concepts, originally applied to \textit{syllogisms}. We remind you, or expand your vocabulary
to include the concepts of \textit{theorem, hypothesis, conclusion, converse,
inverse, contrapositive, and negation} as we will need them. A table summarizes
the ideas,
with the name of the implication and an equivalent form using only negation,
conjunction and disjunction. We use $H$ for the \textit{hypothesis} and
$C$ for the \textit{conclusion} of the theorem.

\begin{eqnarray*}
\mbox{theorem:           } H \Rightarrow C  &\equiv & \neg H \vee C \\
\mbox{its converse:      } C \Rightarrow H  &\equiv & \neg C \vee H \\
\mbox{its inverse:       } \neg  H \Rightarrow  \neg C  &\equiv &  H \vee \neg C \\
\mbox{its contrapositive:} \neg C \Rightarrow \neg H  &\equiv & C \vee \neg H \\
\mbox{its negation:      } \neg (H \Rightarrow C)  &\equiv &  H \wedge \neg C \\
\end{eqnarray*}

From this, it is immediately seen that the theorem and its contrapositive are
equivalent. When we say we are proving a theorem by contradition" we
really mean that we are proving its contrapositive. Similarly,
the converse and the inverse of a theorem are logically equivallent.

But the converse of a theorem is not the same as the theorem. This is the most
common logical mistake uneducated people make. Of course sometimes, both
theorem and converse are true (or false) together. In that case we say they
are equavalent, but we use a different symbol for it: $\iff$ instead
of the meta symbol $\equiv$. In common language, these two things say the same thing. In logic we make the distinction. But you'll have to take a course in logic to learn why. Note that the LaTeX name of $\iff$ is iff", which you are
used in the sentence "P if and only if".
You will get used to this vocabulary as we use it in subsequent lessons. But youshould remember to find it here for a quick reference.

Filecard L3: Prove that the inverse of the contrapositive of a theorem is the theorem again.

Filecard L4: What is the negation of the converse of a theorem?

Filecard L5: We often say that $P$ is necessary but not sufficient for $Q$.
What does that mean?

Filecard L6: In an implication $A \Rightarrow B$, which is the necessary and which is the sufficient condition?

Filecard L7: Find a case where $A \Rightarrow (B \Rightarrow C) \mbox{ not} \equiv (A \Rightarrow B) \Rightarrow C$ .
Hint: Try some truth values for $A,B,C$ which makes left and right hand sides
have different values.