Exercise 6.5.14

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}}
(a) If $\a \leq \b$ then $\a^\g \leq \b^\g$.

(b) If $\a > 1$ and if $\b < \g$, then $\a^\b < \a^\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}}
% BEGIN INPUT shared/lem_ord_expin_sups
\begin{lem}\label{lem:ord:expin:sups}
  Suppose that $\g$ is a nonzero limit ordinal and $\braces{\a_
}$ and $\braces{\b_
}$ for $
 < \g$ are two transfinite sequences.
  Also suppose that $\a_
 \leq \b_
$ for every $
 < \g$.
  Then
  $$
    \sup_{
 < \g} \a_
 \leq \sup_{
 < \g} \b_
.
  $$
\end{lem}
\qproof{
  First let $A = \braces{\a_
 \where 
 < \g}$ and $B = \braces{\b_
 \where 
 < \g}$ be the ranges of the sequences so that we must show that $\sup{A} \leq \sup{B}$.
  Now consider any $\a \in A$ so that $\a = \a_
$ for some $
 < \g$.
  We then have that
  $$
    \a = \a_
 \leq \b_
 \leq \sup{B}
  $$
  so that $\sup{B}$ is an upper bound of $A$ since $\a$ was arbitrary.
  It then follows from the least upper bound property that $\sup{A} \leq \sup{B}$ as desired.
}
% END INPUT shared/lem_ord_expin_sups

\mainprob

(a)
  \qproof{
    We show this by transfinite induction on $\g$.
    So first suppose that $\a \leq \b$.
    Then for $\g = 0$ we clearly have
    $$
      \a^\g = \a^0 = 1 = \b^0 = \b^\g,
    $$
    where we have used Definition~6.5.9a twice.
    Then $\a^\g \leq \b^\g$ clearly holds.

Now suppose that $\a^\g \leq \b^\g$ so that we have
    \ali{
      \a^{\g+1} &= \a^\g \cdot \a & 	ext{(by Definition~6.5.9b}) \
      &\leq \b^\g \cdot \a & 	ext{(follows from Exercise~6.5.8b and the induction hypothesis)} \
      &\leq \b^\g \cdot \b & 	ext{(follows from Exercise~6.5.7 since $\a \leq \b$)} \
      &= \b^{\g + 1}. & 	ext{(by Definition~6.5.9b)}
    }
    Lastly suppose that $\g$ is a nonzero limit ordinal and that $\a^\d \leq \b^\d$ for all $\d < \g$.
    We then have
    \ali{
      \a^\g &= \sup_{\d < \g} a^\d & 	ext{(by Definition~6.5.9c)} \
      &\leq \sup_{\d < \g} \b^\d & 	ext{(by Lemma~ef{lem:ord:expin:sups} and the induction hypothesis)} \
      &= \b^\g\,, & 	ext{(by Definition~6.5.9c again)}
    }
    which completes the transfinite induction.
  }

(b)
  \qproof{
    Suppose that $\a > 1$.
    We then show the result by transfinite induction on $\g$ similarly to the proof of Exercise~6.5.7a.
    Suppose that $\b < \d$ implies that $\a^\b < \a^\d$ for all $\d < \g$ and that $\b < \g$.

Case: $\g$ is a successor ordinal.
    Then $\g = \d + 1$ for an ordinal $\d$ and $\b \leq \d$ since $\b < \g = \d + 1$.
    We then have
    \ali{
      \a^\b &\leq \a^\d & 	ext{(by the induction hypothesis if $\b < \d$ and trivially if $\b = \d$)} \
      &= \a^\d \cdot 1 \
      &< \a^\d \cdot \a & 	ext{(by Exercise~6.5.7a since $1 < \a$ and $\a^\d 
eq 0$)} \
      &= \a^{\d+1} & 	ext{(by Definition~6.5.9b)} \
      &= \a^\g.
    }
    Case: $\g$ is a limit ordinal.
    Here we have that $\b+1 < \g$ as well since $\b < \g$.
    We then have
    \ali{
      \a^\b &< \a^{\b+1} & 	ext{(by the induction hypothesis since $\b < \b+1 < \g$)} \
      &\leq \sup_{\d < \g} \a^\d & 	ext{(since the supremum is an upper bound)} \
      &= \a^\g. & 	ext{(by Definition~6.5.9c)}
    }
    Thus in either case $\a^\b < \a^\g$, thereby completing the transfinite induction.
  }

Exercise 6.5.14

Answers

Comments

Exercise 6.5.14

Answers

Comments

Add answer