Exercise 6.5.7

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_1$, $\a_2$, and $\b$ are ordinals and $\b 
eq 0$, then $\a_1 < \a_2$ if and only if $\b \cdot \a_1 < \b \cdot \a_2$.

(b) For all ordinals $\a_1$, $\a_2$, and $\b 
eq 0$, $\b \cdot \a_1 = \b \cdot \a_2$ if and only if $\a_1 = \a_2$.

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{ ($ o$) We show this by transfinite induction on $\a_2$. So suppose and that $\a_1 < \d$ implies that $\b \cdot \a_1 < \b \cdot \d$ for all $\d < \a_2$ and that $\a_1 < \a_2$. If $\a_2$ is a successor ordinal then $\a_2 = \d + 1$ for some ordinal $\d$ where $\a_1 \leq \d$ since $\a_1 < \a_2$. Then we have \ali{ \b \cdot \a_1 &\leq \b \cdot \d & ext{(by the induction hypothesis if $\a_1 < \d$ and trivially if $\a_1 = \d$)} \ &< \b \cdot \d + \b & ext{(by Lemma~6.5.4a since $0 < \b$)} \ &= \b \cdot (\d + 1) & ext{(by Definition~6.5.6b)} \ &= \b \cdot \a_2. } On the other hand if $\a_2$ is a limit ordinal then $\a_1 + 1 < \a_2$ since $\a_1 < \a_2$. Then we have that \ali{ \b \cdot \a_1 &< \b \cdot (\a_1 + 1) & ext{(by the induction hypothesis since $\a_1 < \a_1 +1 < \a_2$)} \ &\leq \sup_{\d < \a_2} \b \cdot \d & ext{(since the supremum is an upper bound)} \ &= \b \cdot \a_2. & ext{(by Definition~6.5.6c)} } This completes the inductive proof. ($\leftarrow$) For this we assume that $\b \cdot \a_1 < \b \cdot \a_2$. If it were the case that $\a_1 > \a_2$ than it would follow by the implication already shown that $\b \cdot \a_1 > \b \cdot \a_2$, which is a contradiction. Similarly if $\a_1 = \a_2$ then $\b \cdot \a_1 = \b \cdot \a_2$, another contradiction. Hence by the linearity of the order $<$ it must be that $\a_1 < \a_2$ as desired. } (b) \qproof{ This follows from part (a) in the same way as the proof of Lemma~6.5.4b but is repeated for completeness. ($ o$) We prove this part by contrapositive, so suppose that $\a_1 eq \a_2$. Then either $\a_1 < \a_2$ or $\a_1 > \a_2$. In the former case then part (a) implies that $\b \cdot \a_1 < \b \cdot \a_2$ so that $\b \cdot \a_1 eq \b \cdot \a_2$. In the latter case part (a) similarly implies that $\b \cdot \a_1 > \b \cdot \a_2$ so that again $\b \cdot \a_1 eq \b \cdot \a_2$. ($\leftarrow$) If $\a_1 = \a_2$ then we trivially have $\b \cdot \a_1 = \b \cdot \a_2$. }

Exercise 6.5.7

Answers

Comments

Exercise 6.5.7

Answers

Comments

Add answer