Exercise 6.5.8

Question

% Custom definitions (IntroToSetTheory)
% Source section: sec_6_5.tex

% Common sets
\def
ats{{\boldsymbol{N}}}
\def\ints{{\boldsymbol{Z}}}
\defats{{\boldsymbol{Q}}}
\def\prats{ats^+}
\defeals{{\boldsymbol{R}}}
\def\es{\varnothing}

% Common variables/symbols
\def\vphi{\varphi}
\def\a{\alpha}
\def\b{\beta}
\def\g{\gamma}
\def\d{\delta}
\def\e{\varepsilon}
\def\z{\zeta}
\def\k{\kappa}
\def\l{\lambda}
\def
{
u}
\def{ho}
\def\s{\sigma}
\def	{	au}
\def\x{\xi}
\def\w{\omega}
\def\W{\Omega}
\def\al{\aleph}

% Logic
\def\bic{\leftrightarrow}

ewcommand{\propP}[1]{\prop{P}(#1)}
\def\lxor{\veebar}

% For set-buider notation
\def\where{\mid}

% Other stuff
\def\dom{\mathrm{dom}\,}
\defan{\mathrm{ran}\,}

% Cardinality shortcuts
\def\cnats{{\al_0}}
\def\ccont{{2^\cnats}}

% Equivalence classes

ewcommand\eclass[2]{\squares{#1}_{#2}}

% Shortcuts that make writing easier

ewcommand\parens[1]{\left( #1 ight)}

ewcommand\squares[1]{\left[ #1 ight]}

ewcommand\braces[1]{\left\{ #1 ight\}}

ewcommand\angles[1]{\left\langle #1 ightangle}

ewcommand\ceil[1]{\left\lceil #1 ightceil}

ewcommand\floor[1]{\left\lfloor #1 ightfloor}

ewcommand\abs[1]{\left| #1 ight|}

ewcommand\dabs[1]{\left\| #1 ight\|}

ewcommand\vect[1]{\mathrm{\mathbf{#1}}}

ewcommand\conj[1]{\overline{#1}}

ewcommand\pset[1]{\mathcal{P}\left(#1ight)}

ewcommand\inv[1]{#1^{-1}}

ewcommand\prop[1]{\mathbf{#1}}
\defest{estriction}

ewcommand	et[2]{{^{#1}#2}}

% Families of set
\def\famF{\mathcal{F}}

% These are needed so that half-open intervals do not cause auto-indentation issues due to unmatched brackets

ewcommand\clop[1]{[#1)}

ewcommand\ilab[1]{#1)}

% Other miscellaneous stuff
\def\ss{\subseteq}
\def\pss{\subset}
\def\Seq{\mathrm{Seq}}
\def\prece{\preccurlyeq}
\def\sd{\bigtriangleup}

% Environment shortcuts

ewcommand\gath[1]{\begin{gather*} #1 \end{gather*}}

ewcommand\ali[1]{\begin{align*} #1 \end{align*}}

ewcommand\qproof[1]{\begin{proof} #1 \end{proof}}

ewcommand\bicproof[2]{
  $(	o)$ #1

$(\leftarrow)$ #2
}

ewcommand\seteqproof[2]{
  $(\ss)$ #1

$(\supseteq)$ #2
}

% Environment for indenting nested paragraphs (useful in case trees)

ewenvironment{indpar}
{
  \begin{adjustwidth}{1cm}{}
    }{
  \end{adjustwidth}
}

% Exercise, Theorem, and solution shortcuts

ewcommand\exercise[2]{{
      enewcommand\label[1]{} % Needed to suppress multiply-defined label warning since the same question numbers are used in different sections
      \setcounter{subsubsection}{#1-1} % Subsubsections are used to that lemmas have the full nested numbering
      \stepcounter{subsubsection} % Need to increment this so that the lemma counter gets reset
      \setcounter{question}{#1-1} % Manually set the question number since we always know the exercise number
      \question{#2} % The actual exam class question
    }}

ewcommand\exerciseapp[3]{
  \setqf{#2}
  \exercise{#1}{#3}
  \setqf{}
}

ewcommand	heorem[2]{{
      enewcommand\label[1]{} % Needed to suppress multiply-defined label warning since the same question numbers are used in different sections
      \setcounter{subsubsection}{#1-1} % Subsubsections are used to that lemmas have the full nested numbering
      \stepcounter{subsubsection} % Need to increment this so that the lemma counter gets reset
      \setcounter{question}{#1-1} % Manually set the question number since we always know the theorem number
      \question{#2} % The actual exam class question
    }}

ewcommand	heoremapp[3]{
  \setqf{#2}
  	heorem{#1}{#3}
  \setqf{}
}

ewcommand\sol[1]{
  \begin{solution}

#1
  \end{solution}
}

% Main problem and theorem labels
\def\mainprob{	extbf{Main Problem.}}
\def\mainthrm{	extbf{Main Theorem.}}

% Saves some typing
\def\cbthrm{Cantor-Bernstein Theorem}

% Book title
\def\booktitle{
  Introduction to Set Theory \
  Third Edition, Revised and Expanded \
  by Karel Hrbacek and Thomas Jech
}

% Environment aliases used in the source sections

ewenvironment{lem}{\begin{lemma}}{\end{lemma}}

ewenvironment{defin}{\begin{definition}}{\end{definition}}

ewenvironment{cor}{\begin{corollary}}{\end{corollary}}

ewenvironment{thrm}{\begin{theorem}}{\end{theorem}}

% Override indpar to avoid changepage/adjustwidth dependency
enewenvironment{indpar}{\begin{quote}}{\end{quote}}
Let $\a$, $\b$, and $\g$ be ordinals, and let $\a < \b$.
  Then

(a) $\a + \g \leq \b + \g$

(b) $\a \cdot \g \leq \b \cdot \g$.

Dan Whitman · Accepted Answer

% Custom definitions (IntroToSetTheory) % Source section: sec_6_5.tex % Common sets \def ats{{\boldsymbol{N}}} \def\ints{{\boldsymbol{Z}}} \def ats{{\boldsymbol{Q}}} \def\prats{ ats^+} \def eals{{\boldsymbol{R}}} \def\es{\varnothing} % Common variables/symbols \def\vphi{\varphi} \def\a{\alpha} \def\b{\beta} \def\g{\gamma} \def\d{\delta} \def\e{\varepsilon} \def\z{\zeta} \def\k{\kappa} \def\l{\lambda} \def { u} \def { ho} \def\s{\sigma} \def { au} \def\x{\xi} \def\w{\omega} \def\W{\Omega} \def\al{\aleph} % Logic \def\bic{\leftrightarrow} ewcommand{\propP}[1]{\prop{P}(#1)} \def\lxor{\veebar} % For set-buider notation \def\where{\mid} % Other stuff \def\dom{\mathrm{dom}\,} \def an{\mathrm{ran}\,} % Cardinality shortcuts \def\cnats{{\al_0}} \def\ccont{{2^\cnats}} % Equivalence classes ewcommand\eclass[2]{\squares{#1}_{#2}} % Shortcuts that make writing easier ewcommand\parens[1]{\left( #1 ight)} ewcommand\squares[1]{\left[ #1 ight]} ewcommand\braces[1]{\left\{ #1 ight\}} ewcommand\angles[1]{\left\langle #1 ight angle} ewcommand\ceil[1]{\left\lceil #1 ight ceil} ewcommand\floor[1]{\left\lfloor #1 ight floor} ewcommand\abs[1]{\left| #1 ight|} ewcommand\dabs[1]{\left\| #1 ight\|} ewcommand\vect[1]{\mathrm{\mathbf{#1}}} ewcommand\conj[1]{\overline{#1}} ewcommand\pset[1]{\mathcal{P}\left(#1 ight)} ewcommand\inv[1]{#1^{-1}} ewcommand\prop[1]{\mathbf{#1}} \def est{ estriction} ewcommand et[2]{{^{#1}#2}} % Families of set \def\famF{\mathcal{F}} % These are needed so that half-open intervals do not cause auto-indentation issues due to unmatched brackets ewcommand\clop[1]{[#1)} ewcommand\ilab[1]{#1)} % Other miscellaneous stuff \def\ss{\subseteq} \def\pss{\subset} \def\Seq{\mathrm{Seq}} \def\prece{\preccurlyeq} \def\sd{\bigtriangleup} % Environment shortcuts ewcommand\gath[1]{\begin{gather*} #1 \end{gather*}} ewcommand\ali[1]{\begin{align*} #1 \end{align*}} ewcommand\qproof[1]{\begin{proof} #1 \end{proof}} ewcommand\bicproof[2]{ $( o)$ #1 $(\leftarrow)$ #2 } ewcommand\seteqproof[2]{ $(\ss)$ #1 $(\supseteq)$ #2 } % Environment for indenting nested paragraphs (useful in case trees) ewenvironment{indpar} { \begin{adjustwidth}{1cm}{} }{ \end{adjustwidth} } % Exercise, Theorem, and solution shortcuts ewcommand\exercise[2]{{ enewcommand\label[1]{} % Needed to suppress multiply-defined label warning since the same question numbers are used in different sections \setcounter{subsubsection}{#1-1} % Subsubsections are used to that lemmas have the full nested numbering \stepcounter{subsubsection} % Need to increment this so that the lemma counter gets reset \setcounter{question}{#1-1} % Manually set the question number since we always know the exercise number \question{#2} % The actual exam class question }} ewcommand\exerciseapp[3]{ \setqf{#2} \exercise{#1}{#3} \setqf{} } ewcommand heorem[2]{{ enewcommand\label[1]{} % Needed to suppress multiply-defined label warning since the same question numbers are used in different sections \setcounter{subsubsection}{#1-1} % Subsubsections are used to that lemmas have the full nested numbering \stepcounter{subsubsection} % Need to increment this so that the lemma counter gets reset \setcounter{question}{#1-1} % Manually set the question number since we always know the theorem number \question{#2} % The actual exam class question }} ewcommand heoremapp[3]{ \setqf{#2} heorem{#1}{#3} \setqf{} } ewcommand\sol[1]{ \begin{solution} #1 \end{solution} } % Main problem and theorem labels \def\mainprob{ extbf{Main Problem.}} \def\mainthrm{ extbf{Main Theorem.}} % Saves some typing \def\cbthrm{Cantor-Bernstein Theorem} % Book title \def\booktitle{ Introduction to Set Theory \ Third Edition, Revised and Expanded \ by Karel Hrbacek and Thomas Jech } % Environment aliases used in the source sections ewenvironment{lem}{\begin{lemma}}{\end{lemma}} ewenvironment{defin}{\begin{definition}}{\end{definition}} ewenvironment{cor}{\begin{corollary}}{\end{corollary}} ewenvironment{thrm}{\begin{theorem}}{\end{theorem}} % Override indpar to avoid changepage/adjustwidth dependency enewenvironment{indpar}{\begin{quote}}{\end{quote}} (a) \qproof{ We show this by transfinite induction on $\g$. For $\g = 0$ we clearly have $$ \a + \g = \a + 0 = \a < \b = \b + 0 = \b + \g $$ so that $\a + \g \leq \b + \g$ is true. Now suppose that $\a + \g \leq \b + \g$ so that we have $$ \a + (\g + 1) = (\a + \g) + 1 \leq (\b + \g) + 1 = \b + (\g + 1) $$ by Lemma~ ef{lem:ord:natlt} and Corollary~ ef{cor:ord:nateq} since $\a + \g \leq \b + \g$ (induction hypothesis) and $1$ is a natural number. Lastly, suppose that $\g$ is a nonzero limit ordinal and that $\a + \d \leq \b + \d$ for all $\d < \g$. Let $A = \braces{\a + \d \where \d < \g}$ and tentatively suppose that $\a + \g > \b + \g$. Then $\b + \g < \a + \g = \sup{A}$ so that $\b + \g$ is not an upper bound of $A$. Hence there is a $\d < \g$ such that $\b + \g < \a + \d$. We then have that $$ \b + \d \leq \sup\braces{\b + \e \where \e < \g} = \b + \g < \a + \d, $$ but this contradicts the induction hypothesis since $\d < \g$. So it has to be that $\a + \g \leq \b + \g$ as desired. This completes the inductive proof. Furthermore we give an example that shows that the $\leq$ cannot be replaced with $<$ in the conclusion. Let $\a = 1$, $\b = 2$, and $\g = \w$. Then clearly $\a = 1 < 2 = \b$ but we also have $$ \a + \g = 1 + \w = \w = 2 + \w = \b + \g $$ so that clearly $\a + \g < \b + \g$ is not true since they are equal. Note also that clearly if $\a = \b$ then $\a + \g = \b + \g$ so that $\a + \g \leq \b + \g$ is still true. Hence the conclusion is also true in the slightly more general case of $\a \leq \b$. } (b) \qproof{ We also show this by transfinite induction on $\g$. For $\g = 0$ we clearly have $$ \a \cdot \g = \a \cdot 0 = 0 = \b \cdot 0 = \b \cdot \g $$ so that $\a \cdot \g \leq \b \cdot \g$ is true. Now suppose that $\a \cdot \g \leq \b \cdot \g$ so that we have \ali{ \a \cdot (\g + 1) &= \a \cdot \g + \a & ext{(by Definition~6.5.6b)} \ &< \a \cdot \g + \b & ext{(by Lemma~6.5.4 since $\a < \b$)} \ &\leq \b \cdot \g + \b & ext{(by part (a) and the induction hypothesis)} \ &= \b \cdot (\g + 1) & ext{(by Definition~6.5.6b again)}. } Lastly, suppose that $\g$ is a nonzero limit ordinal and that $\a \cdot \d < \b \cdot \d$ for all $\d < \g$. The argument is analogous to that in part (a). Let $A = \braces{\a \cdot \d \where \d < \g}$ and tentatively suppose that $\a \cdot \g > \b \cdot \g$. Then $\b \cdot \g < \a \cdot \g = \sup{A}$ so that $\b \cdot \g$ is not an upper bound of $A$. Hence there is a $\d < \g$ such that $\b \cdot \g < \a \cdot \d$. We then have that $$ \b \cdot \d \leq \sup\braces{\b \cdot \e \where \e < \g} = \b \cdot \g < \a \cdot \d, $$ but this contradicts the induction hypothesis since $\d < \g$. So it has to be that $\a \cdot \g \leq \b \cdot \g$ as desired. This completes the inductive proof. } A case in which $\a < \b$ but $\a \cdot \g = \b \cdot \g$ is clearly provided when $\g = 0$ so that $\leq$ in the conclusion cannot be replaced with $<$. Similarly here if $\a = \b$ then $\a \cdot \g = \b \cdot \g$ so that $\a \cdot \g \leq \b \cdot \g$ is still true. Hence the conclusion is also true in the slightly more general case of $\a \leq \b$.

Exercise 6.5.8

Answers

Comments

Exercise 6.5.8

Answers

Comments

Add answer