\documentclass{article} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage{amsfonts} %TCIDATA{OutputFilter=LATEX.DLL} %TCIDATA{Version=5.50.0.2953} %TCIDATA{} %TCIDATA{BibliographyScheme=Manual} %TCIDATA{Created=Monday, July 19, 2004 16:06:22} %TCIDATA{LastRevised=Wednesday, May 09, 2012 17:29:02} %TCIDATA{} %TCIDATA{} %TCIDATA{Language=American English} %TCIDATA{CSTFile=Math.cst} %TCIDATA{PageSetup=72,72,72,72,0} %TCIDATA{AllPages= %F=36,\PARA{038

\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 $xx).$ 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\ (x0\}=% %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)=bf: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}