Exercise 9.1.14

Question

% Custom definitions (IntroToSetTheory)
% Source section: sec_9_1.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}}

% Section-local definitions
% Macros useful for this section
\def\uni{\bigcup_{i \in I}}
\def\sumi{\sum_{i \in I}}
\def\prodi{\prod_{i \in I}}
\def\prodj{\prod_{j \in J}}

ewcommand\unaj[1]{\bigcup_{j \in J_{#1}} A_j}
Evaluate the cardinality of $\prod_{0 < \a < \w_1} \a$.
    [Answer: $2^{\al_1}$.]

Dan Whitman · Accepted Answer

% Custom definitions (IntroToSetTheory)
% Source section: sec_9_1.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}}

% Section-local definitions
% Macros useful for this section
\def\uni{\bigcup_{i \in I}}
\def\sumi{\sum_{i \in I}}
\def\prodi{\prod_{i \in I}}
\def\prodj{\prod_{j \in J}}

ewcommand\unaj[1]{\bigcup_{j \in J_{#1}} A_j}
\begin{lem} \label{lem:cardar:al2}
    If $\a$ and $\b$ are ordinals and $\a \leq \b$, then $\al_\a^{\al_\b} = 2^{\al_\b}$.
  \end{lem}
  \qproof{
    First we have that
    \gath{
      2^{\al_\b} \leq \al_\a^{\al_\b}
    }
    by property (n) after Lemma~5.6.1 since clearly $2 \leq \al_\a$.
    We also have
    \ali{
      \al_\a^{\al_\b} &\leq \parens{2^{\al_\a}}^{\al_\b} & 	ext{(again by property (n), and Theorems~5.1.8 and 5.1.9)} \
      &= 2^{\al_\a \cdot \al_\b} & 	ext{(by Theorem~5.1.7b)} \
      &= 2^{\al_\b}. & 	ext{(by Corollary~7.2.2 since $\a \leq \b$)}
    }
    Hence it follows from the \cbthrm{} that $\al_\a^{\al_\b} = 2^{\al_\b}$ as desired.
  }

\mainprob

We claim that $\abs{\prod_{0 < \a < \w_1} \a} = 2^{\al_1}$.
  \qproof{
    First, let $I = \braces{\a \where 0 < \a < \w_1}$ so that clearly $\prod_{0 < \a < \w_1} \a = \prodI \a$.
    It is trivial to show that the mapping
    \gath{
      f(\a) = \begin{cases}
        \a+1 & 0 \leq \a < \w_0    \
        \a   & \w_0 \leq \a < \w_1
      \end{cases}
    }
    for $\a \in \w_1$ is a bijection from $\w_1$ to $I$, and hence $\abs{I} = \abs{\w_1} = \al_1$.
    Also, since $\a < \w_1$ for any $\a \in I$, it follows from Lemma~ef{lem:aleph:alephadd:alephlt} that $\abs{\a} \leq \al_0$.
    Therefore, we first have
    \ali{
      \abs{\prodI \a} &= \prodI \abs{\a} & 	ext{(by the definition of the cardinal product)} \
      &\leq \prodI \al_0 & 	ext{(by Exercise~9.1.8 since $\abs{\a} \leq \al_0$ for all $\a \in I$)} \
      &= \al_0^{\abs{I}} & 	ext{(by Exercise~9.1.10)} \
      &= \al_0^{\al_1} & 	ext{(since we have shown that $\abs{I} = \al_1$)} \
      &= 2^{\al_1}. & 	ext{(by Lemma~ef{lem:cardar:al2})}
    }
    Now, let $J = \braces{\a \where 1 < \a < \w_1}$.
    For any $a = \angles{a_2, a_3, \ldots, a_\w, a_{\w+1},\ldots} = \angles{a_\a \where \a \in J} \in \prodJ \a$, it is easy to show that the function that maps this to $b = \angles{0, a_2, a_3, \ldots, a_\w, a_{\w+1}, \ldots} \in \prodI \a$ is bijective so that $\abs{\prodJ \a} = \abs{\prodI \a}$.
    It should also be clear that $\abs{J} = \abs{I} = \al_1$.
    Lastly, we clearly have $2 \leq \abs{a}$ for all $a \in J$ since $1 < \a$.
    We then have
    \ali{
      2^{\al_1} &= 2^{\abs{J}} & 	ext{(since $\abs{J} = \al_1$)} \
      &= \prodJ 2 & 	ext{(by Exercise~9.1.10)} \
      &\leq \prodJ \abs{\a} & 	ext{(by Exercise~9.1.8 since $2 \leq \abs{\a}$ for all $\a \in J$)} \
      &= \abs{\prodJ \a} & 	ext{(by the definition of the cardinal product)} \
      &= \abs{\prodI \a} & 	ext{(by what was shown above)}
    }
    It therefore follows from the \cbthrm{} that $\abs{\prod_{0 < \a < \w_1} \a} = \abs{\prodI \a} = 2^{\al_1}$ as desired.
  }

Exercise 9.1.14

Answers

Comments

Exercise 9.1.14

Answers

Comments

Add answer