\documentclass[10pt]{article}
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{parskip}
\usepackage{titlesec}
\usepackage[section]{placeins}
\usepackage{xcolor}
\usepackage{breakcites}
\usepackage{lineno}
\usepackage{hyphenat}
\PassOptionsToPackage{hyphens}{url}
\usepackage[colorlinks = true,
linkcolor = blue,
urlcolor = blue,
citecolor = blue,
anchorcolor = blue]{hyperref}
\usepackage{etoolbox}
\makeatletter
\patchcmd\@combinedblfloats{\box\@outputbox}{\unvbox\@outputbox}{}{%
\errmessage{\noexpand\@combinedblfloats could not be patched}%
}%
\makeatother
\usepackage{natbib}
\renewenvironment{abstract}
{{\bfseries\noindent{\abstractname}\par\nobreak}\footnotesize}
{\bigskip}
\titlespacing{\section}{0pt}{*3}{*1}
\titlespacing{\subsection}{0pt}{*2}{*0.5}
\titlespacing{\subsubsection}{0pt}{*1.5}{0pt}
\usepackage{authblk}
\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\providecommand{\tightlist}{\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}%
\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}
\usepackage[utf8]{inputenc}
\usepackage[ngerman,english]{babel}
\begin{document}
\title{Logic, Set Theory, and Proofs}
\author[1]{James S. Wang}%
\affil[1]{Johns Hopkins University}%
\vspace{-1em}
\date{\today}
\begingroup
\let\center\flushleft
\let\endcenter\endflushleft
\maketitle
\endgroup
\sloppy
NoteUtil Parameters
Separator is '\textasciitilde{}
~~~~Heading character is `\textbar{}'
~~~~The 2 headings are `Units' and `Sub-units'~~~~
Extensions are:~~~~~~~~
~~~~~ ~ ~Additional Information \&\& \&\&~ ~ ~ ~~
~~~~~ ~ ~Example \%\% \%\%~~~~~~~~
~~~~~ ~ ~LaTeX \textbackslash{}{[} \textbackslash{}{]}
Categories are:~ ~
~~~~~ ~ ~! Important definition
\section*{Set Theory}\label{set-theory}
\textbf{Set} \textasciitilde{} This is a collection of objects. It is
customary to use capital letters to describe these. This can be
described by explicitly listing its elements between curly brackets
where the elements are separated by commas. \%\%X = \{1, 3, 5, \ldots{},
49\}\%\% \[\text{If } a \text{ is an element of the set } A \text{, then we write } a \in A\] \[\text{If } a \text{ does not belong to } A \text{, then we write } a \notin A\] \[\text{If } S \text{ satisfies some condition } p(x) \text{, we write } S = \{x: p(x)\}\]
\textbf{Elements/Members} \textasciitilde{} These are objects that make
up a set. It is customary to use lower case letters to describe these.
\%\%The elements of \{1, 2, 3\} are 1, 2, and 3.\%\%
\textbf{Empty/Null/Void Set} \textasciitilde{} This is a special set
that contains no elements. It is denoted by [?] = \{\}.
\textbf{Absolute Value} \textasciitilde{} This operation says that for
any number a, this equals a if a \textgreater{}= 0 and -a if a
\textless{}= 0. \%\%abs(-3) = 3 and abs(3) = 3.\%\%
\textbf{Counting/Natural Numbers} \textasciitilde{} These numbers are
denoted by its symbol \textbf{N}. They consist of 1, 2, 3, \ldots{}.
\&\&Although many properties do not apply to \textbf{N}, it is important
because of its relation to ``mathematical induction''.\&\& \&\&The
letter \textbf{N} comes from ``Natural''.\&\& \textbf{Integers}
\textasciitilde{} These numbers are denoted by its symbol \textbf{Z}.
They consist of \ldots{}, -2, -1, 0, 1, 2, \ldots{}. \&\&The letter
\textbf{Z} comes from the German word ``Zahl'' meaning number.\&\&
\textbf{Rational Numbers} \textasciitilde{} These numbers are denoted by
its symbol \textbf{Q}. They are formed by taking m/n of integers with n
!= 0. \&\&The letter \textbf{Q} comes from ``Quotients''.\&\&
\textbf{Irrational Numbers} \textasciitilde{} These numbers are denoted
by its symbol \textbf{I}. These numbers can be represented by infinite
decimals, such as pi and sqrt(2). Any number that is not rational is
this. \&\&The letter \textbf{I} comes from ``Irrational''.\&\&
\textbf{Real Numbers} \textasciitilde{} These numbers are denoted by its
symbol \textbf{R}. They consist of all of the rational numbers and also
include the irrational numbers. It can be denoted as the open interval
(-Inf, Inf). \&\&The letter \textbf{R} comes from ``Real''.\&\&
\textbf{Complex Numbers} \textasciitilde{} These numbers are denoted by
its symbol \textbf{C} and are numbers in the form a + bi, where a, b are
real numbers and i = sqrt(-1). One of these numbers where b = 0 is a
real number. Therefore, every real number is also this. The sum of two
of these (a + bi) and (c + di) is (a + c) + (b + d)i, whereas their
product is (ac - bd) + (ad + bc)i. \&\&The letter \textbf{C} comes from
``Complex''.\&\&
\begin{itemize}
\tightlist
\item
Summary of special sets: \[\begin{array}{ll} \textbf{symbol} & \textbf{for the set of} \\
\\N & \text{natural numbers (positive integers)}
\\Z & \text{integers}
\\Q & \text{rational numbers}
\\I & \text{irrational numbers}
\\R & \text{real numbers}
\\C & \text{complex numbers} \end{array}\]
\end{itemize}
\textbf{Cardinality} \textasciitilde{} This property is denoted by
\textbar{}S\textbar{} and represents the number of elements in the set
S. The \_\_\_ of the null set is 0. A set S is \textbf{finite} if this
equals n for some nonnegative integer n. A set S is \textbf{infinite} if
this is not finite. \%\%\textbar{}\{1, 3, 5, 7\}\textbar{} = 4\%\%
\textbf{Subset} \textasciitilde{} This is a set A if every element of A
also belongs to a set B. \&\&If A is a subset of B, and B is a subset of
C, then A is a subset of C.\&\& \&\&Every set is a subset of itself.\&\&
\&\&The null set is a subset of every set. If it were not, that would
imply that there is some element in the null set that is not in some set
A, but the null set has no elements, so it must be a subset of A.\&\&
\%\%If A = \{1, 2, 3\} and B = \{1, 2, 3\}, A is a subset of B.\%\%
\[\text{If } A \text{ is a subset of } B \text{, then } A \subseteq B\] \[\text{If } C \text{ is not a subset of } D \text{, then } C \not\subseteq D\]
\textbf{Universal Set} \textasciitilde{} In typical discussion of sets,
we are ordinarily concerned with subsets of some specified set U, called
this. This is the set where all sets being discussed are subsets of this
set. For example, when dealing with only integers, this is Z. When only
dealing with real numbers, this is R.
\textbf{Open Interval} \textasciitilde{} This is the set (a, b) = \{x in
R: a \textless{} x \textless{} b\}. \[\left(a, b\right) = \{x \in \textbf{R}: a < x < b\}\] \%\%5/2, sqrt(5),
3, pi all belong in the open interval (2, 5), but none of the numbers
sqrt(2), 1.99, 2, or 5 belong to (2, 5).\%\% \textbf{Closed Interval}
\textasciitilde{} This is the set {[}a, b{]} = \{x in R: a \textless{}=
x \textless{}= b\}. \[\left[a, b \right] = \{x \in \textbf{R}: a \leq x \leq b\}\] \%\%2, 3, 4, and 5 belong to the
closed interval {[}2, 5{]}, but 1 and 6 do not.\%\%
\textbf{Half-open/Half-closed Intervals} \textasciitilde{} This is a set
(a, b{]} or {[}a, b) = \{x in R: a \textless{} x \textless{}= b\} or \{x
in R: a \textless{}= x \textless{} b\} respectively. \[\left[a, b\right) = \{x \in \textbf{R}: a \leq x < b\} \text{ and } \left(a, b\right] = \{x \in \textbf{R}: a < x \leq b\}\]
\%\%The function sqrt(x) exists in the half-closed interval {[}0,
Inf).\%\% \textbf{Equality of Sets} \textasciitilde{} Two sets A and B
are said to have tihs property if they have exactly the same elements.
Another way of describing this is that every element of A is in B and
every element of B is in A. \[A \subseteq B \text{ and } B \subseteq A\] \%\%If A = \{1, 2\} and
B = \{2, 1\}, A = B\%\%
\textbf{Proper Subset} \textasciitilde{} A set A is a \_\_\_ of B if A
is a subset of B but A != B. \[\text{If } A \text{ is a proper subset of } B \text{, we write} A \subset B\] * It is often
convenient to represent sets by diagrams called \textbf{Venn diagrams}.
\%\%If A = \{1, 2\} and B = \{1, 2, 3\}, then A is a proper subset of
B.\%\%
\textbf{Power Set} \textasciitilde{} This is the set consisting of all
subsets of a given set A. It is denoted by P(A). The cardinality of this
set is equal to 2 to the power of the cardinality of A.
\[\lvert \mathcal{P}(A) \rvert = 2^{\lvert A \rvert}\] \%\%The power set of A = \{1, 3\} is P(A) = \{
\{1\}, \{3\}, \{1, 3\}, null set \}.\%\%
\textbf{Union} \textasciitilde{} This is an operation on two sets A and
B, denoted by A U B, and is the set of all elements belonging to A or B.
\%\%If A = \{1, 2\} and B = \{2, 3\}, their union is \{1, 2, 3\}.\%\%
\[A \cup B = \{x : x \in A \text{ or } x \in B\}\] \textbf{Intersection} \textasciitilde{} This is an
operation on two sets A and B, denoted by A [?] B, and is equal to the set
of all elements belonging to both A and B. \&\&For every two sets A and
B, it follows that A [?] B is a subset of A U B.\&\& \%\%If A = \{1, 2\}
and B = \{2, 3\}, then their intersection is \{2\}. \[A \cap B = \{x : x \in A \text{ and } x \in B\}\]
\textbf{Disjoint} \textasciitilde{} This is a property of two sets A and
B when they have no elements in common. Then A [?] B = the null set.
\%\%If A = \{1, 2\} and B = \{3, 4\}, then they are disjoint.\%\%
\textbf{Difference} \textasciitilde{} This is an operation on two sets A
and B, denoted by A - B or A \textbackslash{} B, and is equal to the set
of all elements in A, but not in B. \&\&Sometimes, this is also called
the \textbf{relative complement} of B in A.\&\& \%\%If A = \{1, 2, 3\}
and B = \{2, 3\}, A - B = \{1\} and B - A = null set\%\%
\[A - B = \{x: x \in A \text{ and } x \notin B\}\] \textbf{Complement} \textasciitilde{} This is an
operation on a certain universal set U and a set A, denoted by A-bar = U
- A, and is equal to the set of all elements belonging to U, but not A.
\%\%If the universal set is \{1, 2, \ldots{}, 10\} and A = \{1, 2, 3,
4\}, then the complement of set A is \{5, 6, 7, 8, 9, 10\}.\%\%
\[\bar{A} = U - A = \{x : x \in U \text{ and } x \notin A\}\]
\begin{itemize}
\tightlist
\item
Because it is often useful to consider the union of several sets,
additional notation is needed. The union of the n \textgreater{}= 2
sets A1, A2, \ldots{}, An is denoted by A1 U A2 U \ldots{} U An or
\(\cup_{i=1}^n A_i = \{x: x \in A_i \text{ for some } i, 1 \leq i \leq n\}\)
\item
The intersection of n \textgreater{}= 2 sets A1, A2, \ldots{}, An is
expressed as A1 [?] A2 [?] \ldots{} [?] An, or \(\cap_{i=1}^n A_i = \{x: x \in A_i \text{ for every } i, 1 \leq i \leq n\)
\item
\textbf{Index Set} \textasciitilde{} This is a set I that is used as a
mechanism for selecting the sets we want to consider. It takes certain
sets at an index alpha in this set I. Suppose that there is a set S\_a
for each a in I. We write an \textbf{Indexed Collection of Sets} as
\{S\_a\}\_(a in I) to describe the collection of all sets S\_a where a
in I. \%\%For n in N, define Sn = \{n, 2n\}. S1 = \{1, 2\}, S2 = \{2,
4\} and S4 = \{4, 8\}. Then S1 U S2 U S4 = \{1, 2, 4, 8\}. The index
set can be expressed as let I = \{1, 2, 4\} and U\_(alpha in I) of
S\_alpha.\%\% \[\{S_\alpha\}_{\alpha \in I}\]
\end{itemize}
\textbf{Pairwise Disjoint} \textasciitilde{} A collection S of subsets
of a set A are considered to have this property if every two distinct
subsets that belong to S are disjoint. \%\%If A = \{1, 2, \ldots{}, 7\},
B = \{1, 6\}, C = \{2, 5\}, D = \{4, 7\}, and S = \{B, C, D\}, then S is
pairwise disjoint because B [?] C = B [?] D = C [?] D = null set.\%\%
\textbf{Partition} \textasciitilde{} This is a collection S of nonempty
subsets of A such that every element of A belongs to exactly one subset
in S. It must satisfy the following three properties: (1) X != null set
for every set X in S. (2) For every two sets X, Y in S, either X = Y or
X [?] Y = null set. (3) U\_(X in S) of X is equal to A. \%\%If A = \{1, 2,
3, \ldots{}, 10\}, then a partition of A could be \{\{1, 2\}, \{9, 7\},
\{5, 6, 10\}, \{3, 4, 8\}\}.\%\%
\textbf{Ordered Pair} \textasciitilde{} This is a single element
consisting of a pair of elements in which x is the first element and y
is the second element. For two of these (x, y), (w, z) to be equal, we
must have x = w and y = z. This is because (x, y) != (y, x). \%\%(1, 2)
is an ordered pair.\%\% \textbf{Cartesian Product} \textasciitilde{}
This operation on two sets A and B denoted by A x B is the set
consisting of all ordered pairs whose first coordinate belongs to A and
whose second coordinate belongs to B. \&\&Note that if A or B = null
set, then the product is also null set. \&\& \&\&The Cartesian product R
x R is the set of all points in the Euclidean plane. The graph of the
straight line y = 2x + 3 is the set \{(x, y) in R x R: y = 2x + 3.\&\&
\&\&For all finite sets A and B, \textbar{}A x B\textbar{} =
\textbar{}A\textbar{} * \textbar{}B\textbar{}\&\& \%\%If A = \{1, 2\}
and B = \{4, 5\}, then their product is \{(1, 4), (1, 5), (2, 4), (2,
5)\}\%\% \[A \times B = \{(a, b) : a \in A \text{ and } b \in B\}\]
\textbf{Even} \textasciitilde{} An integer n is said to have this
property if n = 2k for some integer k. \textbf{Odd} \textasciitilde{} An
integer n is said to have this property if n = 2k + 1 for some integer
k.
\textbf{Parity} \textasciitilde{} Two integers x and y are said to share
this property if they are both even or odd, and have the opposite of
this property if one of x and y is even and the other is odd. \%\%5 and
13 have the same parity, but 8 and 11 do not.\%\%
\textbf{Divides} \textasciitilde{} For integers a and b with a != 0, we
say that a \_\_\_ b if there is an integer c such that b = ac. It is
denoted by a \textbar{} b. \&\&If a \textbar{} b, then we also say that
b is a \textbf{multiple} of a and that a is a \textbf{divisor} of b.\&\&
\&\&If a does not divide b, there is a dash crossing out the bar in the
notation.\&\& \&\&Note that while every integer can be expressed as 2k
or 2k + 1, every integer can also be expressed as n = 3k, n = 3k + 1, n
= 3k + 2, or n = 4k, n = 4k + 1, n = 4k + 2, n = 4k + 3\&\& \%\%4
\textbar{} 48 because 48 = 4 * 12 and -3 \textbar{} 57 because 57 =
(-3)(-19). On the other hand, 4 does not divide 66 because there is no
integer c such that 66 = 4c.\%\%
\textbf{Unique Element} \textasciitilde{} This is an element belonging
to some prescribed set A possessing a certain property that only it has.
In other words, this is \_\_\_ because it is the only element of A
having property P. Typically, to prove that only one element has
property P, we can proceed in one of the two ways: (1) (Direct) Assume
that a and b are elements of A possessing property P and show that a =
b. (2) (Contradiction) Assume that a and b are distinct elements of A
possessing property P and show that a = b.
\textbf{Least Element} \textasciitilde{} Let A be a nonempty set of real
nubers. A number m [?] A is called a \_\_\_ of A if x [?] m for every x [?] A.
Some nonempty sets of real numbers have these, others do not. \&\&If a
nonempty set A has a least element, then this element is necessarily
unique.\&\& \%\%The set N has a smallest element (1), while Z doesn't.
The closed interval {[}2, 5{]} has the minimum element 2, but the open
interval (2, 5) has no minimum element.\%\%
\textbf{Well-Ordered} \textasciitilde{} A nonempty set S of real numbers
is said to have this property if every nonempty subset of S has a least
element. \&\&Every nonempty finite set of real numbers is well-ordered.
Note that although the closed interval {[}0, 1{]} has the least element
0, it is not well-ordered because the open interval (0, 1) is a nonempty
subset of {[}0, 1{]}. \&\& \%\%Let S = \{-7, -1, 2\}. The nonempty
subsets of S are \{-7, -1, 2\}, \{-7, -1\}, \{-7, -2\}, \{-1, 2\},
\{-7\}, \{-1\}, and \{2\}. Since each of these subsets has a least
element, S is well-ordered.\%\%
\section*{Logic}\label{logic}
\textbf{Statement} \textasciitilde{} This is a declarative sentence or
assertion that is true or false (but not both). \&\&Every statement has
a \textbf{truth value}, namely \textbf{true} (denoted by T) and
\textbf{false} (denoted by F).\&\& \&\&We commonly use P, Q, and R to
denote statements, or P1, P2, \ldots{}, Pn if there are several
statements involved.\&\& \%\%The sentence: The integer 3 is odd is a
statement which is true.\%\% \textbf{Open Sentence} \textasciitilde{}
This is a declarative sentence that contains one or more variables, each
variable representing a value in some prescribed set, called the
\textbf{domain} of the variable, and which becomes a statement when
values from their respective domains are substituted for these
variables. \%\%The real number r is rational or 3x = 12 are both open
statements. For the latter, if the domain is the set of integers, then
the statement is only true when x = 4. We'd say that the latter is an
open sentence over the domain of all integers.\%\% \textbf{Truth Table}
\textasciitilde{} This is a list of the possible truth values of a
statement. \[\begin{array}{c|c} P & Q \\ \\ T & T \\ T & F \\ F & T \\ F & F \end{array}\] \textbf{Negation} \textasciitilde{} This
of a statement P is the statement not P, denoted by \selectlanguage{ngerman}¬P. Although ¬P
could always be expressed as ``It is not the case that P,'' there are
better ways. When applied to a true statement, it becomes false, and
when applied to a false statement, it becomes true. \%\%P1: The integer
3 is odd. ¬P1: The integer 3 is not odd, or even better, The integer 3
is even.\%\% \[\neg P\] \textbf{Disjunction} \textasciitilde{}
This is the statement P or Q and is denoted by P \selectlanguage{english}[?] Q. It is true if at
least one of P and Q is true, otherwise it is false. Therefore, it is
true if exactly one of P and Q is true or if both P and Q are true.
\%\%P1: the integer 3 is odd, P2: The integer 57 is prime. The
disjunction, P1 \selectlanguage{english}[?] P2: Either 3 is odd or 57 is a prime. Since P1 is
true, the statement is true.\%\% \[P \vee Q\]
\textbf{Conjunction} \textasciitilde{} This is the statement P and Q and
is denoted by P \selectlanguage{english}[?] Q. It is only true if both P and Q are true, otherwise
it is false. \%\%P1: the integer 3 is odd, P2: The integer 57 is prime.
The conjunction, P1 \selectlanguage{english}[?] P2: 3 is odd and 57 is prime. Since P2 is false,
the statement is false.\%\% \[P \wedge Q\]
\textbf{Conditional/Implication} \textasciitilde{} This is the statement
If P, then Q, denoted by P \selectlanguage{english}= Q. It can also be expressed as P implies Q.
It is only false when P is true and Q is false. This statement can be
expressed in several different ways, including: ``If P, then Q'', ``Q if
P'', ``P implies Q'', ``P only if Q'', ``P is sufficient for Q'', and
``Q is necessary for P.'' \&\&The statement !(P \selectlanguage{english}= Q) is logically
equivalent to P \selectlanguage{english}[?] !Q\&\& \&\&!(P \selectlanguage{english}= Q) is logically equivalent to P \selectlanguage{english}[?]
(!Q)\&\& \%\%P1: The integer 3 is odd, P2: The integer 57 is prime. The
implication P1 \selectlanguage{english}= P2: If 3 is an odd integer, then 57 is prime. Since P1
is true and P2 is false, the conditional is false. However, P2 \selectlanguage{english}= P1: If
57 is prime, then 3 is odd. Since P2 is false, the statement is true.
\[P \implies Q\]
\textbf{Hypothesis/Premise} \textasciitilde{} This is the statement or
open sentence P in the implication P \selectlanguage{english}= Q. \%\%If T is an equilateral
triangle, then T is isosceles. The first part, ``If T is an equilateral
triangle'' is our hypothesis.\%\% \textbf{Conclusion} \textasciitilde{}
This is the statement or open sentence Q in the implication P \selectlanguage{english}= Q.
\%\%If T is an equilateral triangle, then T is isosceles. The second
part, ``Then T is isosceles'' is our conclusion.\%\% \textbf{Converse}
\textasciitilde{} For statements or open sentences P and Q, this is the
implication Q \selectlanguage{english}= P. This statement is not logically equivalent to P \selectlanguage{english}= Q.
\%\%P1: 3 is an odd integer, P2: 57 is prime. The converse of the
implication P1 \selectlanguage{english}= P2 (If 3 is an odd integer, then 57 is prime) is the
implication P2 \selectlanguage{english}= P1: If 57 is prime, then 3 is an odd integer.\%\%
\[Q \implies P\] \textbf{Inverse} \textasciitilde{} For statements or
open sentences P and Q, this is the implication !P \selectlanguage{english}= !Q. This statement
is not logically equivalent to P \selectlanguage{english}= Q. \%\%P1: 3 is an odd integer, P2:
57 is a prime. The inverse of the implication P1 \selectlanguage{english}= P2 (If 3 is an odd
integer, then 57 is prime) is the implication !P \selectlanguage{english}= !Q: If 3 is an even
integer, then 57 is composite.\%\% \[\neg P \implies \neg Q\]
\textbf{Contrapositive} \textasciitilde{} For statements or open
sentences P and Q, this is the implication !Q \selectlanguage{english}= !P. This statement is
logically equivalent to P \selectlanguage{english}= Q. \%\%If P1: 3 is an odd integer, P2: 57 is
a prime. The contrapositive of the implication P1 \selectlanguage{english}= P2 (If 3 is an odd
integer, then 57 is prime) is the implication !Q \selectlanguage{english}= !P: If 57 is
composite, then 3 is an even integer.\%\% \[\neg Q \implies \neg P\]
\textbf{Biconditional} \textasciitilde{} This is the statement P if and
only if Q, P is equivalent to Q, or P is necessary and sufficient for Q,
denoted by P \selectlanguage{english}= Q. This is true whenever the statements P and Q are both
true or both false, and false otherwise. It is logically equivalent to
(P \selectlanguage{english}= Q) \selectlanguage{english}[?] (Q \selectlanguage{english}= P). \&\& !(P \selectlanguage{english}= Q) is logically equivalent to (P \selectlanguage{english}[?] (\selectlanguage{english}~ Q))
\selectlanguage{english}[?] (Q \selectlanguage{english}[?] (\selectlanguage{english}~ P)). \&\&\%\% The biconditional 3 is an odd integer if and
only if 57 is prime is false, while the biconditionals 100 is even if
and only if 101 is prime and 5 is even if and only if 4 is odd are both
true.\%\% \[P \iff Q\]
\textbf{Logical Connectives} \textasciitilde{} The symbols !, \selectlanguage{english}[?], \selectlanguage{english}[?], \selectlanguage{english}=,
and \selectlanguage{english}= are sometimes referred to as this. From given statements, we can
use these to form more intricate statements. Any statement composed of
one or more given statements (\textbf{component statements}) and at
lesat one logical connective is called a \textbf{compound statement}.
\%\% The statement (P \selectlanguage{english}[?] Q) \selectlanguage{english}[?] (P \selectlanguage{english}[?] R) is a statement formed from the
given statements P, Q and R and the logical connectives \selectlanguage{english}[?] and \selectlanguage{english}[?].\%\%
\textbf{Tautology} \textasciitilde{} A compound statement S is called
this if it is true for all possible combinations of truth values of the
componnet statements that comprise S. \%\%The statement (P \selectlanguage{english}[?] !P) is a
tautology because either P or !P will be true, preventing them from both
being false at the same time.\%\% \textbf{Contradiction}
\textasciitilde{} A compound statement S is called this if it is false
for all possible combinations of truth values of the component
statements that are used to form S. \%\%The statement (P \selectlanguage{english}[?] !P) is a
contradiction because either P or !P will be false, preventing both of
them from being true at the same time.\%\% \textbf{Logical Equivalence}
\textasciitilde{} Two compound statements R and S are said to have this
property if they both have the same truth values for all combinations of
truth values of their component statements. This is denoted by R \selectlanguage{english}[?] S.
This would mean that the biconditional R \selectlanguage{english}= S is true for all possible
combinations of truth values and hence R \selectlanguage{english}= S is a tautology. \%\%The
statements (P \selectlanguage{english}[?] Q) and (Q \selectlanguage{english}[?] P) are logically equivalent because they
have the same truth values for all combinations of truth values.\%\%
\[R \equiv S\]
\textbf{Commutative Laws} \textasciitilde{} These laws state that for
statements P, Q and R, (a) P \selectlanguage{english}[?] Q \selectlanguage{english}[?] Q \selectlanguage{english}[?] P. (b) P \selectlanguage{english}[?] Q \selectlanguage{english}[?] Q \selectlanguage{english}[?] P.
\textbf{Associative Laws} \textasciitilde{} These laws state that for
statements P, Q and R (a) P \selectlanguage{english}[?] (Q \selectlanguage{english}[?] R) \selectlanguage{english}[?] (P \selectlanguage{english}[?] Q) \selectlanguage{english}[?] R. (b) P \selectlanguage{english}[?] (Q \selectlanguage{english}[?] R) \selectlanguage{english}[?]
(P \selectlanguage{english}[?] Q) \selectlanguage{english}[?] R. \textbf{Distributive Laws} \textasciitilde{} These laws
state that for statements P, Q and R (a) P \selectlanguage{english}[?] (Q \selectlanguage{english}[?] R) \selectlanguage{english}[?] (P \selectlanguage{english}[?] Q) \selectlanguage{english}[?] (P \selectlanguage{english}[?]
R). (b) P \selectlanguage{english}[?] (Q \selectlanguage{english}[?] R) \selectlanguage{english}[?] (P \selectlanguage{english}[?] Q) \selectlanguage{english}[?] (P \selectlanguage{english}[?] R). \textbf{De Morgan's Laws}
\textasciitilde{} These laws state that for statements P, Q and R (a)
!(P \selectlanguage{english}[?] Q) \selectlanguage{english}[?] (!P) \selectlanguage{english}[?] (!Q). (b) !(P \selectlanguage{english}[?] Q) \selectlanguage{english}[?] (!P) \selectlanguage{english}[?] (!Q). \[\neg \left(P \vee Q\right) \equiv \neg P \wedge \neg Q\]
\[\neg\left(P \wedge Q\right) \equiv \neg P \vee \neg Q\]
\textbf{Universal Quantifier} \textasciitilde{} This is the phrase ``for
every'' applied to an open sentence P(x) over a domain S, denoted by the
symbol \selectlanguage{english}[?]. Other ways to express this are ``for each'' and ``for all.''
\%\%Let P(x) denote that ``x is even'' over the domain of all positive
multiples of 2. Then we can say that for every positive multiple of 2
(x), the multiple of 2 is even (P(x))\%\% \[\forall x \in S, P(x)\]
\textbf{Existential Quantifier} \textasciitilde{} This is the phrase
``there exists'', ``there is'', ``for some'', and ``for at least one''
applied to an open sentence P(x) over a domain S, denoted by the symbol
\selectlanguage{english}[?]. \%\%Let f(x) = (x - 3) = 0 and P(x) = ``x is the solution to f(x)
over the domain of all real numbers. Then we can say that there exists a
real number (x), such that the real number is a solution to f(x)
(P(x)).\%\% \[\exists x \in S, P(x)\]
\begin{itemize}
\tightlist
\item
Summary of all logical connectives: \[\begin{array}{ll}
\neg & \text{negation (not)}
\\\vee & \text{disjunction (or)}
\\\wedge & \text{conjunction (and)}
\\\implies & \text{implication (if, then)}
\\\iff & \text{biconditional (if and only if)}
\\\forall & \text{universal quantifier (for every)}
\\\exists & \text{existential quantifier (there exists)}
\end{array}\]
\end{itemize}
\textbf{Characterization} \textasciitilde{} Suppose that some concept or
object is expressed in an open sentence P(x) over a domain S and Q(x) is
another open sentence over the domain S concerning this concept. We say
that if [?]x [?] S, P(x) = Q(x) is a true statement, then it is a \_\_\_ of
this concept. Furthermore, we say that this concept has been \_\_\_-ed
by Q(x). \%\%A real number r is irrational if and only if r has a
nonrepeating decimal expansion. The characterization is that irrational
numbers are characterized by their nonrepeating decimal expansion.
Another example includes equilateral triangles being characterized by
three equal angles.
\section*{Proofs}\label{proofs}
\textbf{Axiom} \textasciitilde{} This is a mathematical statement whose
truth is accepted without proof. \%\%An axiom of Euclid in geometry
states that for every line l and point P not on l, there is a unique
line containing P that is parallel to l. \textbf{Theorem}
\textasciitilde{} This is a mathematical statement whose truth can be
verified. Mathematicians generally reserve this word for statements that
are especially significant or interesting. \textbf{Corollary}
\textasciitilde{} This is a mathematical result that can be deducted
from, and is thereby a consequence of some earlier result.
\textbf{Lemma} \textasciitilde{} This is a mathematical result that is
useful in establishing the truth of some other result.
\textbf{Trivial Proof} \textasciitilde{} This is a proof where we show
that Q(x) is true for all x in S regardless of the truth value of P(x).
Then according to the truth table for implications, the statement P(x) =
Q(x) will be true for all x in S. \%\%Let n be in all integers (Z), if
n\^{}3 \textgreater{} 0, then 3 is odd. This is a trivial proof because
3 is always an odd integer.\%\% \textbf{Vacuous Proof} \textasciitilde{}
This is a proof where we show that P(x) is a false statement for all x
in S regardless of the truth value of Q(x). Then according to the truth
table for implications, the statement P(x) = Q(x) will be true for all x
in S. \%\%Let x be in the set of all real numbers (R). If x\^{}2 -2x + 2
\textless{}= 0, then x\^{}3 \textgreater{}= 8. Notice that x\^{}2 -2x +
1 = (x - 1)\^{}2 \textgreater{}= 0. Then x\^{}2 - 2x + 2 = (x - 1)\^{}2
+ 1 \textgreater{}= 1 \textgreater{} 0. Thus x\^{}2 -2x + 2 \textless{}=
0 is fase for all x in R, and the implication is true.\%\%
\textbf{Direct Proof} \textasciitilde{} This is a proof where we
consider an arbitrary element x in S for which P(x) is true and show
that Q(x) is true as well for this element x. Then we can generalize
this to all elements of x in S, proving the mathematical statement P(x)
= Q(x) to be true. \%\%Prove that if n is an odd integer, then 3n + 7 is
an even integer. 1. Assume that n is an odd integer. 2. Since n is odd,
we can write n = 2k + 1 for some integer k. 3. Now, 3n + 7 = 3(2k + 1) +
7 = 6k + 3 + 7 = 6k + 10 = 2 (3k + 5). 4. Since 3k + 5 is an integer, 3n
+ 7 is even.\%\%
\textbf{Proof by Contrapositive} \textasciitilde{} This is a proof where
we consider an arbitrary element x in S for which we assume \selectlanguage{ngerman}¬Q(x) is
true and show that ¬P(x) is true as well. Then we can generalize this to
all elements x in S, proving the mathematical statement ¬Q(x) \selectlanguage{english}= !P(x),
which then proves P(x) \selectlanguage{english}= Q(x) is also true. \%\%Let x be in Z (all
integers). If 5x - 7 is even, then x is odd. Assume that x is even. Then
x = 2k for some integer k. Then 5x - 7 = 10k - 7 = 2 (5k - 4) + 1. Since
5a - 4 is an integer, the integer 5x - 7 is odd. Since we have shown
that if x is not odd, 5x - 7 is not even, that proves that if 5x - 7 is
even, then x is odd.\%
\textbf{Proof by Cases} \textasciitilde{} This is a proof where we
consider multiple parts or properties that an element x in set S may
possess or for each subset to which x may belong. This is because it is
sometimes useful to observe that x possesses one of two or more
properties. If we can verify the truth of the statement for each
property that x may have, then we have a proof of the statement. \&\&The
parts are divided into \textbf{cases}, which may be further divided into
\textbf{subcases}\&\& \%\%If we are considering Z (all integers) as our
universal subset and are trying to prove \selectlanguage{english}[?]n \selectlanguage{english}[?] Z, R(n) then possible
proof by cases could be: 1. Case 1: n is even. Case 2: n is odd. 2. Case
1: x = 0, Case 2: x \textless{} 0, Case 3: x \textgreater{} 0. Or if we
are considering N (all natural numbers), possible proof by cases could
be: 1. Case 1: n = 1, Case 2: n \textgreater{}= 2.\%\% \%\%If n is in Z,
then n\^{}2 + 3n + 5 is an odd integer. Proceed with the following two
cases: n is even and n is odd. If n is even, then n = 2x for some x in
Z. Thus n\^{}2 + 3n + 5 = (2x)\^{}2 + 3(2x) + 5 = 4x\^{}2 + 6x + 5 =
2(2x\^{}2 + 3x + 2) + 1. Since 2x\^{}2 + 3x + 2 is an integer, the
integer n\^{}2 + 3n + 5 is odd. If n is odd, then n = 2y + 1 for some y
in Z. Thus, n\^{}2 + 3n + 5 = (2y + 1)\^{}2 + 3(2y + 1) + 5 = 4y\^{}2 +
10y + 9 = 2(2y\^{}2 + 5y + 4) + 1. Because 2y\^{}2 + 5y + 4 is an
integer, the integer n\^{}2 + 3n + 5 is odd.\%\%
\textbf{Without Loss of Generality (WLOG)} \textasciitilde{} This phrase
is used to indicate that the proofs of the two situations are similar,
so the proof of only one is needed. \%\%Let a and b be integers. Prove
that ab is even if and only if a is even or b is even. (1) Assume that a
is even or b is even. Without loss of generality, let a be even. Then a
= 2x for some integer x. Thus ab = (2x)b = 2(xb). Since xb is an
integer, ab is even. (2) Assume that a is odd and b is odd. Then a = 2x
+ 1 and b = 2y + 1 for x, y in Z. Hence ab = (2x + 1)(2y + 1) = 4xy + 2x
+ 2y + 1 = 2(2xy + x + y) + 1. Since 2xy + x + y is an integer, ab is
odd. Thus the contrapositive is true.\%\%
\textbf{Counterexample} \textasciitilde{} This is an element x that
shows the falsehood of a statement \selectlanguage{english}[?]x \selectlanguage{english}[?] S, R(x). This is because \selectlanguage{english}~ (\selectlanguage{english}[?]x \selectlanguage{english}[?]
S, R(x)) \selectlanguage{english}[?] \selectlanguage{english}[?]x \selectlanguage{english}[?] S, \selectlanguage{english}~ R(x). A statement P is said to be
\textbf{disproved} if it is shown to be false in some manner.
\textbf{Proof by Contradiction} \textasciitilde{} This is a proof where
we assume R is a false statement and, from this assumption, we are able
to arrive at or deduce a statement that contradicts some assumption we
made in the proof or some known fact. If we denote the known fact as P,
then we have declared !P and have thus produced the contradiction C: P \selectlanguage{english}[?]
(! P). We have therefore established the truth of the implication (! R)
\selectlanguage{english}= C. However, because (! R) \selectlanguage{english}= C is a true statement, and C is false, it
follows that ! R is false, and so R is true, as desired. \%\%Prove that
there is no smallest positive real number. Assume, to the contrary, that
there is a smallest positive real number r. Since 0 \textless{} r/2
\textless{} r, it follows that r/2 is a positive real number smaller
than r. This, however, is a contradiction.\%\%
\textbf{Existence Theorem} \textasciitilde{} This is an assertion of the
existence of an object (or objects) possesing some specified porperty or
properties. Typically, this concerns an open sentence R(x) over a
domain. S can be expressed as a quantified statement: \selectlanguage{english}[?]x \selectlanguage{english}[?] S, R(x) :
There exists x \selectlanguage{english}[?] S such that R(x). \%\%There exists an integer whose
cube equals its square. (1)\%\%
\textbf{Existence Proof} \textasciitilde{} This is a proof where we
display or construct an example of an object that verifies that such an
object must exist without ever producing a single example of the desired
type. \%\%There is at least one student X in this class for whom the
following statement is true: No other student in the class has more
hairs on his head than X. Which student is it? That we shall never know,
but of his existence we can be absolutely certain.\%\% \%\%Prove that
there exists an integer whose cube equals its square. While one may spot
that 1 yields an easy solution, if you did not realize that, an
alternate proof starts with x\^{}3 = x\^{}2, then x\^{}3 - x\^{}2 = 0,
x\^{}2 (x - 1) = 0. This gives us two possible integers with this
property, namely 1 and 0.\%\%
\textbf{The Well-Ordering Principle} \textasciitilde{} This principle
states that the set N of natural numbers is well-ordered. \textbf{The
Principle of Mathematical Induction} \textasciitilde{} This principle
states that for each positive integer n, let P(n) be a statement. If 1.
P(1) is true. 2. The implication ``If P(k), then P(k + 1)'' is true for
every positive integer k, then P(n) is true for every positive integer
n. \&\&The Principle of Mathematical Induction is a consequence of The
Well-Ordering Principle.\&\& \textbf{The Strong Principle of
Mathematical Induction} \textasciitilde{} This principle states that for
each positive integer n, let P(n) be a statement. If (a) P(1) is true
and (b) the implication ``If P(i) for every integer i with 1
\textless{}= i \textless{}= k, then P(k + 1)'' is true for every
positive integer k, then P(n) is true for every positive integer n.
\textbf{Proof by Induction} \textasciitilde{} This is a proof where we
prove the quantified statement \selectlanguage{english}[?]n \selectlanguage{english}[?] N, P(n) to be true if (1) we show
that the statement P(1) is true and (2) we can establish the truth of
the implication ``If P(k), then P(k + 1)'' for an arbitrary positive
integer k. Often we use a direct proof to verify \selectlanguage{english}[?]k \selectlanguage{english}[?] N, P(k) \selectlanguage{english}= P(k +
1), but any proof technique is acceptable. If we use the strong
principle of mathematical induction, we must prove that the implication
``If P(i) for every integer i with 1 \textless{}= i \textless{}= k, then
P(k + 1)'' is true for every positive integer k. \&\&The verification of
P(1) in an induction proof is called the \textbf{base step}\&\& \&\&The
statement P(k) is called the \textbf{inductive/induction
hypothesis.}\&\& \&\&Establishing the truth of \selectlanguage{english}[?]k \selectlanguage{english}[?] N, P(k) \selectlanguage{english}= P(k + 1)
is called the \textbf{inductive step}. \%\%Let P(n): 1 + 2 + 3 +
\ldots{} + n = n (n + 1) / 2 where n \selectlanguage{english}[?] N. Prove that P(n) is true for
every positive integer n. 1. Start with the base step: P(1) = (1 * 2) /
2 = 1, which is true. 2. Assume that P(k) is true for an arbitrary
positive integer k, assume that 1 + 2 + 3 + \ldots{} + k = k (k + 1) /
2. 3. We show that P(k + 1) is true: prove that 1 + 2 + 3 + \ldots{} +
(k + 1) = (k + 1) (k + 2) / 2. Thus 1 + 2 + 3 + \ldots{} + (k + 1) = (1
+ 2 + 3 + \ldots{} + k) + (k + 1) = k (k + 1) / 2 + (k + 1) = (k (k + 1)
+ 2 (k + 1)) / 2 = ((k + 1) + (k + 2)) / 2. By The Principle of
Mathematical Induction, P(n) is true for every positive integer n.\%\%
\%\%A sequence is defined recursively by a1 = 1, a2 = 3, and a\_n =
2a\_(n - 1) - a\_(n - 2) for n \textgreater{}= 3. Prove that a\_n = 2n -
1 for all n in N. Since a1 = 2 * 1 - 1, the formula holds for n = 1.
Assume for an arbitrary positive integer k that a\_i = 2i - 1 for all
integers i with 1 \textless{}= i \textless{}= k. We show that a\_(k + 1)
= 2(k + 1) - 1 = 2k + 1.If k = 1, then a\_(k + 1) = a2 = 2 * 1 + 1 = 3.
Since a2 = 3, it follows that a\_(k + 1) = 2k + 1 when k = 1. Hence we
may assume tat k \textgreater{}= 2. Since k + 1 \textgreater{}= 3, it
follows that a\_(k + 1) = 2 a\_k - a\_(k - 1) = 2(2k - 1) - (2k - 3) =
2k + 1, which is the desired result. By the Strong Principle of
Mathematical Induction, a\_n = 2n - 1 for all n in N.\%\%
\textbf{Proof by Minimum Counterexample} \textasciitilde{} Suppose that
P(n) is a statement for each positive integer n. If we try to prove \selectlanguage{english}[?]n \selectlanguage{english}[?]
N, P(n) by contradiction, then in this proof, we start by assuming that
there exists positive integers n such that P(n) is false. By the
Well-Ordering Principle, there exists a smallest positive integer m such
that P(m) is a false statement. Therefore, for any integer k with 1
\textless{}= k \textless{} m, the statement P(k) is true. This will lead
to a contradiction and we have proven \selectlanguage{english}[?]n \selectlanguage{english}[?] N, P(n). \%\%For every
positive integer n, prove 6 \textbar{} (n\^{}3 - n). Assume, to the
contrary, that there are positive integers n such that 6 does not
\textbar{} (n\^{}3 - n). Then there is a smallest positive integer n
such that 6 does not \textbar{} (n\^{}3 - n). Let m be this integer. If
n = 1, then n\^{}3 - n = 0, while if n = 2, then n\^{}3 - n = 6. since 6
\textbar{} 0 and 6 \textbar{} 6, it follows that 6 \textbar{} (n\^{}3 -
n) for n = 1, 2. Therefore m \textgreater{}= 3 (this was chosen for
convenience because the proof would eventually fail if m \textgreater{}=
2). So we can write m = k + 2, where 1 \textless{}= k \textless{} m.
Observe that m\^{}3 - m = (k + 2)\^{}3 - (k + 2) = (k\^{}3 + 6k\^{}2 +
12k + 8) - (k + 2) = (k\^{}3 - k) + (6k\^{}2 + 12k + 6). Since k
\textless{} m, it follows that 6 \textbar{} (k\^{}3 - k) (this is
because m is the minimum counterexample, and everything less than m must
be true). Hence, k\^{}3 - k = 6x for some integer x. So we have m\^{}3 -
m = 6x + 6(k\^{}2 + 2k + 1) = 6 (x + k\^{}2 + 2k + 1). Since x + k\^{}2
+ 2k + 1 is an integer, 6 \textbar{} (m\^{}3 -m), which is a
contradiction.
\begin{itemize}
\tightlist
\item
Questions to ask yourself before attempting a proof:
\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\tightlist
\item
Do you have a clear understanding of the statement?
\item
Do you know the definition of all mathematical concepts mentioned in
the statement?
\item
What properties of these concepts and related results do you know?
\item
Is it clear what information you are permitted to use in an attempt
to verify the statement?
\item
Can I make the proof simpler? (Remove exponents, Factor)
\end{enumerate}
\end{itemize}
\section*{Theorems}\label{theorems}
\begin{itemize}
\tightlist
\item
Theorem 2.21 - Let P and Q be two statements. Then prove that P \selectlanguage{english}= Q
and (!P) \selectlanguage{english}[?] Q are logically equivalent.
\item
Theorem 2.22:
\begin{itemize}
\tightlist
\item
Commutative Laws - These laws state that for statements P, Q and R,
(a) P \selectlanguage{english}[?] Q \selectlanguage{english}[?] Q \selectlanguage{english}[?] P. (b) P \selectlanguage{english}[?] Q \selectlanguage{english}[?] Q \selectlanguage{english}[?] P.
\item
Associative Laws - These laws state that for statements P, Q and R
(a) P \selectlanguage{english}[?] (Q \selectlanguage{english}[?] R) \selectlanguage{english}[?] (P \selectlanguage{english}[?] Q) \selectlanguage{english}[?] R. (b) P \selectlanguage{english}[?] (Q \selectlanguage{english}[?] R) \selectlanguage{english}[?] (P \selectlanguage{english}[?] Q) \selectlanguage{english}[?] R.
\item
Distributive Laws - These laws state that for statements P, Q and R
(a) P \selectlanguage{english}[?] (Q \selectlanguage{english}[?] R) \selectlanguage{english}[?] (P \selectlanguage{english}[?] Q) \selectlanguage{english}[?] (P \selectlanguage{english}[?] R). (b) P \selectlanguage{english}[?] (Q \selectlanguage{english}[?] R) \selectlanguage{english}[?] (P \selectlanguage{english}[?] Q) \selectlanguage{english}[?] (P
\selectlanguage{english}[?] R).
\item
De Morgan's Laws - These laws state that for statements P, Q and R
(a) !(P \selectlanguage{english}[?] Q) \selectlanguage{english}[?] (!P) \selectlanguage{english}[?] (!Q). (b) !(P \selectlanguage{english}[?] Q) \selectlanguage{english}[?] (!P) \selectlanguage{english}[?] (!Q).
\end{itemize}
\item
Theorem 2.25 - For statements P and Q:
\begin{itemize}
\tightlist
\item
! (P \selectlanguage{english}= Q) \selectlanguage{english}[?] P \selectlanguage{english}[?] (! Q).
\item
! (P \selectlanguage{english}= Q) \selectlanguage{english}[?] (P \selectlanguage{english}[?] (! Q)) \selectlanguage{english}[?] (Q \selectlanguage{english}[?] (! P))
\end{itemize}
\item
Theorem 3.9 - For every two statements P and Q, the implication P \selectlanguage{english}= Q
and its contrapositive are logically equivalent; P \selectlanguage{english}= Q \selectlanguage{english}[?] (! Q) \selectlanguage{english}= (!
P).
\item
Theorem 3.12 - Let x \selectlanguage{english}[?] Z. Then x is even if and only if x\^{}2 is
even. A corollary is x is odd if and only if x\^{}2 is odd.
\item
Theorem 3.16 - Let x, y \selectlanguage{english}[?] Z. Then x and y are of the same parity if
and only if x + y is even.
\item
Theorem 3.17 - Let a and b be integers. Then ab is even if and only if
a is even or b is even.
\item
Theorem 5.16 - The real number \selectlanguage{english}[?]2 is irrational.
\item
Theorem 6.1 - If a set A of real numbers has a least element, then A
has a unique least element.
\item
Theorem 6.7 - For each integer m, the set S = \{i \selectlanguage{english}[?] Z : i \selectlanguage{english}[?] m\} is
well-ordered.
\item
Theorem 6.8 - For a fixed integer m, let S = \{i \selectlanguage{english}[?] Z : i \selectlanguage{english}[?] m\}. For
each integer n \selectlanguage{english}[?] S, let P(n) be a statement. If P(m) is true and the
implication ``If P(k) then P(k+1)'' is true for every integer k \selectlanguage{english}[?] S,
then P(n) is true for every integer n \selectlanguage{english}[?] S.
\end{itemize}
\selectlanguage{english}
\FloatBarrier
\end{document}