\documentclass{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsfonts}

%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=5.50.0.2953}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Created=Monday, July 19, 2004 16:06:22}
%TCIDATA{LastRevised=Wednesday, May 09, 2012 17:29:02}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="General\Blank with Theorem Tags">}
%TCIDATA{Language=American English}
%TCIDATA{CSTFile=Math.cst}
%TCIDATA{PageSetup=72,72,72,72,0}
%TCIDATA{AllPages=
%F=36,\PARA{038<p type="texpara" tag="Body Text" >\hfill \thepage}
%}


\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\input{tcilatex}
\begin{document}


\section{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \protect\vspace{1pt}Problems and Comments on the Foundations:
Logic and Proofs, Sets and Functions \newline
}

\section{ Chapter 1 and Chapter 2}

\subsection{\textbf{Section 1.1, Problems 1,3,17,25}}

\textbf{Comments. }You should\textbf{\ }pay special attention to implication 
$p~\rightarrow q,$ read \textit{"If p then q"}. The formula $p\rightarrow q$
is considered as false only if $p$ is true and $q$ is false. The conjunction
of $p\rightarrow q$ and $q\rightarrow p$ is called \textbf{equivalence}, $%
p\longleftrightarrow q$ and read "$p$ if and only if $q$". Notice that

"\textit{p if q" is actually }$q\rightarrow p$ and \textit{"p only if q" is
the same as }$p\rightarrow q.$

The expression $\lnot q\rightarrow \lnot p~$\ is called the \textbf{%
contrapositive }of $p\rightarrow q$ while $q\rightarrow p$ is called the 
\textbf{converse} of $p\rightarrow q.$The expression $\lnot p\rightarrow
\lnot q$ is called the \textbf{inverse }of \ $p\rightarrow q.$

The implication $p\rightarrow q$ has the same meaning as its contrapositive $%
\lnot q\rightarrow \lnot p.$

\textbf{Problem:} (a) What is the converse of the inverse?\textbf{\ }(b)%
\textbf{\ }What is the inverse of the converse?

\textbf{Answer: }(a)\textbf{\ }$p\rightarrow q$ given. Inverse: $\lnot
p\rightarrow \lnot q,$ converse of inverse: $\lnot q\rightarrow \lnot p$
which is the contrapositive of $p\rightarrow q.$ (b) $p\rightarrow q$ given.
Converse: $q\rightarrow p$, inverse of converse: $\lnot q\rightarrow \lnot
p. $Which is again the contrapositive.

\subsection{\textbf{Section 1.3, } Problems: 16, 23, 24, 25 \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ }

\textbf{Comments. }Let $P(p_{1},\ldots ,p_{n})~$be a formula in
propositional variables $p_{1},\ldots ,p_{n}.$ Like $P(p_{1},p_{2})=p_{1}%
\vee \lnot p_{2}$. We say that $P(p_{1},\ldots ,p_{n})$ and $Q(p_{1},\ldots
,p_{n})$ are \textit{equivalent }if they have for any truth valuation of the 
$p_{i~}$the same truth tables. For this we write $P\equiv Q$. For example $%
p_{1}\rightarrow p_{2}\equiv \lnot p_{1}\vee p_{2}$.

A formula $P(p_{1},\ldots ,p_{n})$ is called a \textbf{tautology}\textit{\ }%
if $P(p_{1},\ldots ,p_{n})$ has always truth value $\mathbf{T.}$

\begin{proposition}
$P\equiv Q$ if and only if $P\leftrightarrow Q$ is a tautology.
\end{proposition}

\begin{proof}
$P\leftrightarrow Q$ has truth value $\mathbf{F}$ iff $(P\rightarrow
Q)\wedge (Q\rightarrow P)$ is false. That is, $(P\rightarrow Q)$ is false or 
$(Q\rightarrow P)$ is false. Now, $(P\rightarrow Q)$ is false iff ($P$ is%
\textbf{\ }$\mathbf{T)}$ and ($Q$ is $\mathbf{F)}$ or ($Q$ is $\mathbf{T)}$
and ($P$ is $\mathbf{F)}$. Thus $P\leftrightarrow Q$ has truth value $%
\mathbf{T}$ iff $P$ and $Q$ have he same truth values. Hence $%
P\leftrightarrow Q$ has always truth value $\mathbf{T~}$if $P$ and $Q$ have
always the same truth values.
\end{proof}

\vspace{1pt} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 

\begin{example}
\textbf{\ }$p\rightarrow q\equiv $ $\lnot q\rightarrow \lnot p$. Hence an
implication is equivalent to its contrapositive. Thus $q\rightarrow p$ is
equivalent to $\lnot p\rightarrow \lnot q$ , the converse of an implication
is equivalent to the inverse.
\end{example}

\subsection{Section 1.4, Problems: 16, 43, 45, 46, 47}

\textbf{Comments. }A formula like $x<y$ does not have a fixed truth value.
If we interpret $<$ as the ordinary ordering in $%
%TCIMACRO{\U{211d} }%
%BeginExpansion
\mathbb{R}
%EndExpansion
,$ then $2<3$ has truth value $\mathbf{T}$ while $3<2$ has truth value $%
\mathbf{F}$. We say that $x<y$~is a \textit{predicate }or \textit{%
propositional function} \textit{\ }in variables $x$ and $y.$ A propositional
function $P(x_{1,}\ldots x_{n})$ takes on a certain truth value if the
variables have been specified by elements $x_{1}=a_{1},\ldots ,x_{n}=a_{n}.$
The elements $a_{i}$ are taken from a fixed domain $D$\ that is associated
with $P(x_{1,}\ldots x_{n}).$

\textbf{First order formulas} are defined inductively by the following three
rules. We start with a certain set of \textbf{basic} predicates, like $%
P(a,y) $ etc. and say that

\begin{enumerate}
\item All basic predicates are formulas. They are called the \textbf{atomic }%
formulas.

\item If $\alpha $ and $\beta $ are formulas then $(\alpha \wedge \beta
),(\alpha \vee \beta ),(\alpha \rightarrow \beta ),(\alpha \leftrightarrow
\beta ),\lnot a$ are formulas. That is, propositional combinations of
formulas are formulas.

\item If $\alpha $ is a formula and $x$any variable then $\forall x\alpha $
and $\exists x\alpha $ are formulas. We assume that we have an infinite set
of variables which designate elements from a fixed domain $D$.$~$\ 
\end{enumerate}

Formulas are derived by finitely many applications of the rules 1-3. It is
assumed that equality $E(x,y)\equiv x=y$ is amongst the basic predicates. In
rule 3. we say that $\alpha $ is the scope of the quantifier $\forall x$ or $%
\exists x$, respectively. An occurrence of a variable $x$ is called \textit{%
free} in the formula $\alpha $ if it is not in the scope of any quantifier.
Otherwise this occurrence is called \textit{bound}. A formula without free
variables is called a sentence.

\begin{example}
The first occurrence (read from left to right) of the variable $x$ in the
formula $(\forall x\exists y\ P(x,y)\vee \lnot Q(x,y,z))$ is bound, the
other occurrence is free. The only occurrence of $z$ is free.
\end{example}

Given a formula $\alpha (x_{1},\ldots x_{n})$ and elements $a_{1},\ldots
a_{n}$ from the domain $D$, then $\alpha (a_{1},\ldots ,a_{n})$ takes on a
certain truth value. This can be proven proven inductively and is anyway
quite obvious. For example, if we know already the truth value of $\alpha
(a) $ for every $a\in D$, then the truth value of $\forall x\alpha (x)$ is $%
\mathbf{T}$ in case that the truth value of $\alpha (a)$ is $\mathbf{T}$ for
every $a\in D.$

\begin{example}
Let $D=%
%TCIMACRO{\U{2115} }%
%BeginExpansion
\mathbb{N}
%EndExpansion
$ be the set of natural numbers. Find the truth value of $\forall x\exists
y\ (y>x).$ This formula does not contain any free variable, it is a
sentence. Thus it is either true or false. Let $n$ be any natural number.
then we need to know the truth value of\ $\exists y\ (y>n).$ But $n+1>n,$
and for the chosen $n$ we see that $y=n+1$ makes $\exists y\ (y>n)$ true.
Because this works for every $n$ the sentence $\forall x\exists y\ (y>x)$ is
true in $%
%TCIMACRO{\U{2115} }%
%BeginExpansion
\mathbb{N}
%EndExpansion
.$
\end{example}

\subsection{\protect\vspace{1pt}Section 1.5, Problems: 9, 19}

\textbf{Comments. }It is important to observe the order of quantifiers. If$%
L(x,y)$ stands for ``$\mathit{x}$\textit{\ likes to buy }$\mathit{y}$\textit{%
'' where }$x$ stands for persons and $y$ stands for expensive cars then the
sentence $\forall x\exists y\ L(x,y)$ says that every person likes to buy an
expensive car. While $\exists y\forall x\ L(x,y)$ says something different.
Namely, there is some expensive car everybody would like to buy. A more
mathematical example is $\forall x\exists y\ (x<y)$ which is true for the
set of real numbers but $\exists y\forall x\ x<y$ is false for real numbers.

\subsection{Section 1.6, Problems: 3, 7}

\vspace{1pt}This section gives a short but complete description of first
order logic. Table 1 and Table 2 list all the necessary rules. Many proofs
are \textit{indirect}: Instead of proving directly the implication $%
p\rightarrow q,$ one shows $\lnot q\rightarrow \lnot p$. This is then called
an \textit{Indirect Proof}.

That $p\rightarrow q$ is true can also be shown by demonstrating that $%
p\wedge \lnot q$ is false. This is called a \textit{Proof by Contradiction}.

\begin{proof}
$p\rightarrow q\equiv \mathbf{T\;}$iff$\;p\wedge \lnot q\equiv \mathbf{F}$
iff $\lnot (p\wedge \lnot q)\equiv \mathbf{T}$ iff $\lnot p\vee q\equiv 
\mathbf{T}$ iff p$\rightarrow q\equiv \mathbf{T.}$
\end{proof}

\vspace{1pt}

While reading this section you should keep in mind that you can learn how to
prove mathematical facts essentially only by doing proofs and not so much by
studying the concept of formal proofs and logic.

\subsection{Section 2.1, Problems: 1, 2, 3, 21, 23}

Definition 1 is somewhat circular. In order to understand ``A \textit{set }%
is an unordered \textit{collection} of objects'', you have to understand
what a collection is. We will later treat sets as undefined objects\ $%
x,y,\ldots $ that are subject to certain axioms concerning the membership
relation $"\in " $.

One of the axioms will be \textit{Leibnitz's Extensionality Axiom}. It is
treated in the book as a definition: \textit{Two sets are equal if and only
if they have the same elements.}

The practical aspect here is that if a set is given by listing its elements,
there might be repetitions. The elements of the set $%
%TCIMACRO{\U{2115} }%
%BeginExpansion
\mathbb{N}
%EndExpansion
\ $of natural numbers can be listed as: $1,2,3,\ldots $ or $%
1,2,2,3,3,3,\ldots $ or $1,2,4,3,5,6,8,7\ldots .$As long as any natural
numbers appears in the list, we are given as underlying set of the list, the
set of natural numbers. We will later learn in the axiomatic approach how to
define the set of natural numbers precisely.

Given a set $A,$ we can define its subsets, and its set of subsets, the
powerset $\mathbf{P(A).}$ If $A$ is finite and has $n$ elements, then the
powerset of $A$ has $2^{n}$ elements.

If $A~$and $B$ are sets, then the set of all \textit{ordered pairs} $%
(a,b),a\in A,b\in B$ is called the Cartesian product $A\times B.$If $A$ and $%
B$ are finite with $n$ and $m$ elements, respectively, then $A\times B$ has $%
n\cdot m$ many elements. We will later give a precise definition of what an
ordered pair is.

We stipulate the existence of a set with no element. This is called the 
\textit{empty} set. It must be unique and its notation is $\emptyset .$

\subsection{Section 2.2, Problems: 20, 46, 47, 59}

The complement of a set $A$ can be defined only relative to a set that
contains $A.$ Such a set is often called the \textit{universe }$U.$ Then $%
\overline{A}$ is the set of elements that belong to $U$ but not to $A.$
Union and intersection can be defined for any collection of sets. For
example, let $D_{r}=\{P|\ |P|<r\}$ be the set of all points in the plane
whose distance to the origin $O$ is less than $r.$ Then

\[
\bigcup \{D_{r}|\ r>0\}=%
%TCIMACRO{\U{211d} }%
%BeginExpansion
\mathbb{R}
%EndExpansion
^{2},\bigcap \{D_{r}|\ r>0\}=O 
\]

Table 1 and Table 2 relate logical identities to set identities. The logical
equivalence $p\vee q\equiv q\vee p$ corresponds to the set theoretical
identity $A\cup B=B\cup A.$This becomes obvious if we let: $p=(x$ \textit{%
belongs to }$A),$ $q=(x$ \textit{belongs to }$B\mathit{)}$.

\subsection{Section 2.3, Problems:1, 10, 12, 14, 16, 40}

It is important to note that for a function $f:A\rightarrow B$ one has that
for \textbf{every }$a\in A$ one has \textbf{exactly }one $b\in B$ assigned
as function value. In lower level courses, this is called the \textit{%
vertical line} test for the graph of functions from real numbers to real
numbers.

An incorrect but often used notation for a function is $y=f(x).$ A correct
notation must specify the \textit{domain} $A$ and the co-domain $B.$ A
function $f$ can be described by a formula, like $f(x)=x^{2},$ or by a
recipe that allows us to calculate for any argument its value. Here is such
a recipe: $f(0)=0,\ f(1)=1~$and $~f(n)=f(n-1)+f(n-2).$ This gives $%
f(2)=f(1)+f(0)=1+0=1,\ f(3)=f(2)+f(1)=1+1=2, f(4)=f(3)+f(2)=2+1=3.\ldots$

The point is that one can calculate for every natural number $n$ the value $%
~f(n).$

A function $f:A\rightarrow B$ is \textit{one-one} or \textit{injective }if $%
x\neq y\rightarrow f(x)\neq f(y).$This is logically equivalent to $%
f(x)=f(y)\rightarrow x=y.$ Notice that $x=y\rightarrow f(x)=f(y)$ is always
true, it doesn't say anything about $f.$ The function $f:%
%TCIMACRO{\U{211d} }%
%BeginExpansion
\mathbb{R}
%EndExpansion
\rightarrow 
%TCIMACRO{\U{211d} }%
%BeginExpansion
\mathbb{R}
%EndExpansion
,x\mapsto x^{2}$ is not injective, because we have $f(-1)=f(1).$ However, $%
%TCIMACRO{\U{211d} }%
%BeginExpansion
\mathbb{R}
%EndExpansion
^{+}\rightarrow 
%TCIMACRO{\U{211d} }%
%BeginExpansion
\mathbb{R}
%EndExpansion
^{+},x\mapsto x^{2}$ is injective.

In lower level classes, a function is called injective if it passes the 
\textit{horizontal line} test. A function from a set of real numbers to the
set of real numbers is injective if every horizontal line intersects the
graph of the function in at most one point. By the way, we can define the
graph of any function as a subset of the Cartesian product of domain and
co-domain:%
\[
f:A\rightarrow B,\text{has }graph(f)=\{(a,f(a))|\ a\in A\} 
\]

One must distinguish between \textit{image} and codomain. The image of a
function is the set of all images:

\[
f:A\rightarrow B\text{ has }im(f)=\{f(a)|\ a\in A\} 
\]

A function $f:A\rightarrow B$ is\textit{\ onto } or \textit{surjective }if $%
im(f)=B.$ A function which is injective as well as surjective is called 
\textit{bijective}. You should note the following:

$f:A\rightarrow B$\textit{is \textbf{injective} if and only if for every} $%
b\in B$ \textit{there is \textbf{at most} \textbf{one} }$a\in A$ \text{ 
\textit{such that} }$f(a)=b$

$f:A\rightarrow B~\text{\textit{is \textbf{surjective} if there is for every}
}b\in B~\text{\textbf{at}\textit{\ }\textbf{least one} }a\in A\text{ \textit{%
such that} }f(a)=b $

$f:A\rightarrow B$ \textit{is \textbf{bijective} if for every} $b\in B$\text{
\textit{there is }\textbf{exactly one}} $a\in A$ \text{\textit{such that}}$%
f(a)=b$

Bijective functions are also called \textit{one-to-one correspondences}. If $%
f:A\rightarrow B~$is bijecive, then one has a function which is called the 
\textit{inverse} $f^{-1}~$of $f:$ 
\[
f^{-1}:B\rightarrow A,b\mapsto a\text{ where }f(a)=b 
\]

If $f:A\rightarrow B$~and $g:B\rightarrow C$ are functions, then the\textit{%
\ composition} of $g$ and $f$ is the function $h:A\rightarrow C,a\mapsto
g(f(a))$ and one writes $h=g\circ f$, read $g$~\textit{after} $f.$

For every set $A$ one has the identity function $id_{A}:A\rightarrow
A,a\mapsto a.$ We now have: 
\[
f^{-1}\circ f=id_{A},~f\circ f^{-1}=id_{B} 
\]

\begin{theorem}
A function $f:A\rightarrow B$ is surjective if and only if there is a
function $g:B\rightarrow A$ such that $f\circ g=id_{B}.$ That is, $f$ has a
right inverse $g.$ The function $f:A\rightarrow B$ is injective if and only
if there is a function $h:B\rightarrow A$ such that $h\circ f=id_{A}.$ `That
is,$~f$ has a left inverse. The function $f$ is bijective if and only if it
has a left as well a right inverse both of which have to be equal to the
inverse $f^{-1}$ of $f.$

\begin{proof}
A right inverse $g:B\rightarrow A$ calculates the counter image $a$ for the
element $b:g(b)=a$ where $f(a)=b$ \ If $f$ is surjective then there is for
every $b\in B$ some $a\in A$ such that $f(a)=b.$ Thus we may pick for every $%
b\in B~$any such $a$ in order to define a right inverse $g$ for $f.$ This
process requires the Axiom of Choice. We will discuss this axiom later.

If $f$ has a left inverse $h:B\rightarrow A$ then $f(a_{1})=f(a_{2})$ yields 
$h(f(a_{1})=h(f(a_{2})),~$that is $a_{1}=a_{2.}$ If $f$ is injective then in
order to define a left inverse, we pick for every $b\in im(f)$ the unique $%
a\in A$ such that $f(a)=b.$ For any $b\notin im(f)$ we may choose some $a\in
A $ arbitrarily. This defines a left inverse $h:B\rightarrow A$ for $f.$

If $f$ has a left inverse $h:B\rightarrow A~$as well as a right inverse then 
$g:B\rightarrow A,$ then $g=h=f^{-1}.$ Indeed,

$\text{If }f\circ g=id_{B},$ \text{ and }$h\circ f=id_{A}$ \text{ then }$%
h\circ (f\circ g)=h\circ id_{B}=h$ \text{ and }$(h\circ f)\circ
g=id_{A}\circ g=g $

However, composition of functions is associative, that is $h\circ (f\circ
g)=(h\circ f)\circ g.$

\begin{example}
The function $f:%
%TCIMACRO{\U{2115} }%
%BeginExpansion
\mathbb{N}
%EndExpansion
\rightarrow 
%TCIMACRO{\U{2115} }%
%BeginExpansion
\mathbb{N}
%EndExpansion
,n\mapsto 2n,$ is injective. For any left inverse $h:%
%TCIMACRO{\U{2115} }%
%BeginExpansion
\mathbb{N}
%EndExpansion
\rightarrow 
%TCIMACRO{\U{2115} }%
%BeginExpansion
\mathbb{N}
%EndExpansion
,$ we must have $h(2n)=n$ but it doesn't matter how any such $h$ is defined
on the odd numbers in order to have that $h(f(n))=h(2n)=n.$

The function $f:%
%TCIMACRO{\U{2115} }%
%BeginExpansion
\mathbb{N}
%EndExpansion
\rightarrow 
%TCIMACRO{\U{2115} }%
%BeginExpansion
\mathbb{N}
%EndExpansion
,0\mapsto 0,1\mapsto 0,n\mapsto n-1$ for $n\geq 2$ is surjective. We can
define a right inverse $g$ by $g(n)=n+1.$But we could also have defined $%
g(0)=0$ and $g(n)=n+1$ for $n\geq 1,$in order to have $f(g(n))=n.$
\end{example}
\end{proof}
\end{theorem}

\end{document}