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 questions arising in your study. Be sure your update this page whenever you 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.