\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage[margin=1in]{geometry}
\usepackage{microtype}
\usepackage[parfill]{parskip}

\usepackage{graphicx,grffile}
\graphicspath{ {./img/} }
\usepackage{xcolor}
\usepackage{pgf,tikz,pgfplots}
\pgfplotsset{compat=1.15}
\usetikzlibrary{cd}
\usepackage{caption}

\usepackage[hidelinks]{hyperref}

\usepackage{amsmath,amssymb,amsthm,mathtools,mathrsfs,esdiff,stmaryrd,mathabx,dsfont}

\usepackage[inline]{enumitem}
\setlist[enumerate]{label=(\alph*),ref=(\alph*)}

\usepackage{cleveref}

% \usepackage{suffix}
\usepackage{ragged2e}
\usepackage{framed}

\makeatletter

\newcommand*{\CC}{\mathbb{C}}
\newcommand*{\RR}{\mathbb{R}}
\newcommand*{\QQ}{\mathbb{Q}}
\newcommand*{\ZZ}{\mathbb{Z}}
\newcommand*{\NN}{\mathbb{N}}
\newcommand*{\FF}{\mathbb{F}}
\renewcommand*{\AA}{\mathbb{A}} % Replace Å
\newcommand*{\PP}{\mathbb{P}}
\newcommand*{\GG}{\mathbb{G}}
\renewcommand*{\SS}{\mathbb{S}}
\newcommand*{\TT}{\mathbb{T}}
\newcommand*{\VV}{\mathbb{V}}

\newcommand*{\kA}{\mathfrak{A}}
\newcommand*{\km}{\mathfrak{m}}
\newcommand*{\kp}{\mathfrak{p}}
\newcommand*{\kq}{\mathfrak{q}}

\newcommand*{\sA}{\mathscr{A}}
\newcommand*{\sC}{\mathscr{C}}
\newcommand*{\sE}{\mathscr{E}}
\newcommand*{\sF}{\mathscr{F}}
\newcommand*{\sG}{\mathscr{G}}
\newcommand*{\sH}{\mathscr{H}}
\newcommand*{\sI}{\mathscr{I}}
\newcommand*{\sK}{\mathscr{K}}
\newcommand*{\sO}{\mathscr{O}}
\newcommand*{\sP}{\mathscr{P}}
\newcommand*{\sQ}{\mathscr{Q}}
\newcommand*{\sX}{\mathscr{X}}

\newcommand*{\cM}{\mathcal{M}}
\newcommand*{\cP}{\mathcal{P}}

\newcommand*{\nth}{^{\mathrm{th}}}

\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}
\DeclarePairedDelimiterX\innerp[2]{\langle}{\rangle}{#1,#2}
\DeclarePairedDelimiter{\norm}{\lVert}{\rVert}
\DeclarePairedDelimiter{\abs}{\lvert}{\rvert}
\DeclarePairedDelimiter{\order}{\lvert}{\rvert}
\DeclarePairedDelimiter{\ps}{\llbracket}{\rrbracket}
\DeclarePairedDelimiter{\angles}{\langle}{\rangle}

\DeclareMathOperator{\coker}{coker}
\DeclareMathOperator{\Span}{Span}
\DeclareMathOperator{\rank}{rk}
\DeclareMathOperator{\nullity}{null}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\tr}{tr}
% \DeclareMathOperator{\degree}{deg}
\DeclareMathOperator{\fchar}{char}
\DeclareMathOperator{\trdeg}{tr.deg}
\DeclareMathOperator{\codim}{codim}
\DeclareMathOperator{\height}{ht}
\DeclareMathOperator{\pd}{pd}

\DeclareMathOperator{\Pl}{Pl}
\DeclareMathOperator{\Sec}{Sec}
\DeclareMathOperator{\Div}{Div}
\let\div\undefined
\DeclareMathOperator{\div}{div}
\DeclareMathOperator{\Cl}{Cl}
\DeclareMathOperator{\Spec}{Spec}

% \newcommand{\divides}{\mid}
% \newcommand{\notdivides}{\nmid}

\newcommand*{\close}{\overline}
\newcommand*{\interior}[1]{#1^\circ}
\newcommand*{\bound}[1]{\partial #1}

\newcommand*{\xto}[1]{\xrightarrow{#1}}
\newcommand*{\xfrom}[1]{\xleftarrow{#1}}
\newcommand*{\To}{\Rightarrow}
\newcommand*{\into}{\hookrightarrow}
\newcommand*{\onto}{\twoheadrightarrow}
\newcommand*{\isoto}{\xto{\sim}}

\newcommand*{\dirlim}{\lim\limits_{longrightarrow}}
\newcommand*{\dirlimarg}[1]{\lim\limits_{\substack{\longrightarrow\\#1}}}
\newcommand*{\invlim}{\lim\limits_{\longleftarrow}}
\newcommand*{\invlimarg}[1]{\lim\limits_{\substack{\longleftarrow\\#1}}}

\newcommand*{\wh}[1]{\widehat{#1}}
\newcommand*{\wt}[1]{\widetilde{#1}}
\newcommand*{\ol}[1]{\overline {#1}}
\newcommand*{\ul}[1]{\underline {#1}}

\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Syl}{Syl}
\DeclareMathOperator{\Gal}{Gal}
\DeclareMathOperator{\Frac}{Frac}
\DeclareMathOperator{\Ann}{Ann}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\Tor}{Tor}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\PGL}{PGL}
\DeclareMathOperator{\Mat}{Mat}
\DeclareMathOperator{\Gr}{Gr}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\lcm}{lcm}

\newcommand*{\sep}{\mathrm{sep}}

\newcommand{\present}[2]{\langle{{#1} \: |  \: {#2}}\rangle}
\newcommand{\cyclic}[1]{\langle{#1}\rangle}

\newcommand*{\residue}[1]{\mkern 1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern 1.5mu}
\newcommand*{\zmod}[1]{ \Z / #1 \Z }

\newcommand*{\lni}{\lim_{n \to \infty}}
\newcommand*{\lNi}{\lim_{N \to \infty}}
\newcommand*{\sni}{\sum_{n=1}^\infty}

\newcommand\restr[2]{{% we make the whole thing an ordinary symbol
  \left.\kern-\nulldelimiterspace % automatically resize the bar with \right
  #1 % the function
  \vphantom{\big|} % pretend it's a little taller at normal size
  \right|_{#2} % this is the delimiter
}}
\newcommand*{\st}{\ \vert\ }

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

\newcommand{\catname}[1]{{\mathsf{#1}}}
\newcommand{\Set}{\mathsf{Set}}
\newcommand{\Alg}[1]{#1\!-\!\mathsf{Alg}}
\newcommand{\Vect}[1]{#1\!-\!\mathsf{Vect}}
\newcommand{\Mod}[1]{#1\!-\!\mathsf{Mod}}
\renewcommand{\mod}[1]{#1\!-\!\mathsf{mod}}
\newcommand{\CommAlg}[1]{#1\!-\!\mathsf{CommAlg}}
\newcommand{\Ring}{\mathsf{Rings}}
\newcommand{\CommRing}{\mathsf{CommRings}}
\newcommand{\Grp}{\mathsf{Grp}}
\newcommand{\Ab}{\mathsf{Ab}}
\newcommand{\Fun}{\mathsf{Fun}}
\newcommand{\For}{\mathsf{For}}
\newcommand{\Fld}{\mathsf{Fld}}
\newcommand{\Open}{\mathsf{Open}}
\newcommand{\Aff}[1]{#1\!-\!\mathsf{Aff}}
\newcommand{\aA}{\mathsf{A}}
\newcommand{\aB}{\mathsf{B}}
\newcommand{\aC}{\mathsf{C}}
\newcommand{\aD}{\mathsf{D}}
\newcommand{\aG}{\mathsf{G}}
\newcommand{\aK}{\mathsf{K}}
\newcommand{\aP}{\mathsf{P}}

\newcommand{\op}{\textnormal{op}}
\newcommand{\fd}{\textnormal{fd}}
\DeclareMathOperator{\Ob}{Ob}
\newcommand{\id}{\mathrm{id}}

\newcommand*{\dir}[2]{(#1) \( \Rightarrow \) (#2)}

% -------------------
% Heading Commands
% -------------------
\newcommand{\class}{Math 294}
\newcommand{\term}{Fall 2024}
\newcommand{\instructor}{Theo Sandstrom}
\newcommand{\head}[2]{%
\thispagestyle{empty}
\vspace*{-0.5in}
\noindent\begin{tabular*}{\textwidth}{l @{\extracolsep{\fill}} r @{\extracolsep{6pt}} l}
	\textbf{#1} & \textbf{Name:} & \makebox[8cm]{\hrulefill} \\
	\textbf{#2} & & \\
	\textbf{\class:\; \term} & & \\
	\textbf{Instructor: \instructor}
\end{tabular*} \\
\rule[2ex]{\textwidth}{2pt} %
}


% -------------------
% Commands
% -------------------
\newcounter{problem}
\newenvironment{problem}
{
  \begin{leftbar}
  \begin{justify}
    \stepcounter{problem}%
    \textbf{Problem \theproblem. }
}
{
\end{justify}
\end{leftbar}
}
\newenvironment{problem*}[1]
{
  \begin{leftbar}
  \begin{justify}
    \stepcounter{problem}%
    \textbf{Problem \theproblem\ (#1). }
}
{
\end{justify}
\end{leftbar}
}


% -------------------
% Header & Footer
% -------------------
\usepackage{fancyhdr}

\fancypagestyle{pages}{
	%Headers
	\fancyhead[L]{}
	\fancyhead[C]{}
	\fancyhead[R]{}
\renewcommand{\headrulewidth}{0pt}
	%Footers
	\fancyfoot[L]{}
	\fancyfoot[C]{}
	\fancyfoot[R]{}
\renewcommand{\footrulewidth}{0.0pt}
}
\headheight=0pt
\footskip=14pt

\pagestyle{pages}

\makeatother

\begin{document}

\head{Worksheet 6}{Week 6: 2024-10-01}

Let's keep diving into sets! We'll start out with some practice on the notion of a ``power
set'', and then we'll get into some of the basic set-theoretic foundations for mathematics. This
stuff is pretty weird! As always, work together, and ask lots of questions, both of each other,
and of me! \vspace{5mm}

\begin{framed}
  \textit{``It matters little who first arrives at an idea, rather what is significant is how
    far that idea can go.''} ---Sophie Germain

  Sophie Germain (1776–1831) was a French mathematician, renowned for her pioneering contributions to elasticity theory. She developed a deep passion for mathematics by studying the works of Archimedes through Euler, which she encountered in her parents' library. To access more mathematical texts, she even taught herself foreign languages, including Latin and Greek.

Despite her enthusiasm, Germain faced opposition from her parents, who were deeply upset by her unconventional interests. At the time, it was far from acceptable for a woman to pursue such studies. As Lynn Osen notes in her book Women in Mathematics:

  \textit{``Her family firmly and stubbornly opposed her decision, but her determination was only
    strengthened by the vehemence of their opposition... They denied her light and heat for her
    bedroom and confiscated her clothing after she retired at night in order to force her to
    sleep... but after her parents were in bed, she would wrap herself in quilts, take out a
    store of hidden candles, and work at her books all night. After finding her asleep at her
    desk in the morning, the ink frozen in the ink horn and her slate covered with calculations,
    her parents finally [allowed] Sophie to study and use her genius as she wished... and
    Sophie, still without a tutor, spent the years of the Reign of Terror studying differential
    calculus.''}

  In 1804, under the pseudonym Monsieur Le Blanc, Germain wrote to Carl Friedrich Gauss, one of
  the most brilliant mathematicians of his time---and perhaps of all time. In her letter, she
  proposed a new approach to Fermat's Last Theorem, a significant and unsolved problem in number
  theory. Gauss, known for his pride and aloofness, was unexpectedly impressed by ``Le Blanc's''
  work. When an acquaintance of Germain revealed her true identity to Gauss, she wrote to him to
  express both her gratitude and an apology for the deception. In his response, Gauss wrote:

  \textit{``But how to describe to you my admiration and astonishment at seeing my esteemed
    correspondent Monsieur Le Blanc metamorphose himself into this illustrious personage who
    gives such a brilliant example of what I would find it difficult to believe. A taste for the
    abstract sciences in general and above all the mysteries of numbers is excessively rare: one
    is not astonished at it: the enchanting charms of this sublime science reveal only to those
    who have the courage to go deeply into it. But when a person of the sex which, according to
    our customs and prejudices, must encounter infinitely more difficulties than men to
    familiarize herself with these thorny researches, succeeds nevertheless in surmounting these
    obstacles and penetrating the most obscure parts of them, then without doubt she must have
    the noblest courage, quite extraordinary talents and superior genius. Indeed nothing could
    prove to me in so flattering and less equivocal manner that the attractions of this science,
    which has enriched my life with so many joys, are not chimerical, than the predilection with
    which you have honored it.''}

  \noindent\makebox[\textwidth][c]{
  \begin{minipage}[t]{0.5\linewidth}
    \vspace{-2ex}
    \centering
    \includegraphics[width=3cm]{germain}
  \end{minipage}}
\end{framed}

Given a set \( X \), the \textit{power set} of \( X \), denoted by \( \cP(X) \) is the set
containing all subsets of \( X \): that is, \( \cP(X) = \{ A \st A \subseteq X \}. \)

\begin{problem}
  Find the power sets of each of the following sets:
  \begin{enumerate}
  \item \( \{ 1, 2 \} \)
  \item \( \{ a, b, c \} \)
  \item \( \{ \varnothing \} \)
  \end{enumerate}
\end{problem}

\vspace{1cm}

\begin{problem}
  Supposing that \( \{ 1 \} \in \cP(X) \), is it necessarily the case that \( 1 \in X \)? That
  \( \{ 1 \} \in X \)?
\end{problem}

\vspace{4cm}

\begin{problem}
  Prove that, for any sets \( X \) and \( Y \),
  \( \cP(X) \cup \cP(Y) \subseteq \cP(X \cup Y) \). When can this containment be replaced with
  the \textit{equality} \( \cP(X) \cup \cP(Y) = \cP(X \cup Y) \)?
\end{problem}

\vspace{7cm}

\begin{problem}
  Is it true that for all sets \( X \) and \( Y \), \( \cP(X) \cap \cP(Y) = \cP(X \cap Y) \)?
  Justify your answer with proof.
\end{problem}

\vspace{7cm}

\begin{problem}
  Suppose that \( X \) is a finite set containing exactly \( n \) elements. How many elements
  does \( \cP(X) \) have? Justify your answer with proof.
\end{problem}

\pagebreak

The remaining problems are focused on outlining the basic definition of the natural numbers in
terms of set-theoretic foundations. The idea is that you are given a very limited set of
tools---say, the empty set, unions/intersections, and the ability to use brackets to write down
sets---and these are the only mathematical objects at your disposal. How can you build a theory
of numbers and arithmetic from scratch?

\vspace{0.2cm}

\begin{problem}
  How many elements does \( \varnothing \) have?
\end{problem}

\vspace{1cm}

\begin{problem}
  For any set \( X \) define the \textit{successor} of \( X \), which we denote by \( X^+ \), to
  be \( X^+ = X \cup \{ X \} \). How many elements does \( \varnothing^+ \) have? What about
  \( \varnothing^{++} \)?

  Denote by \( X^{+n} \) the result of applying the \( (-)^+ \) operation \( n \) times. How
  many elements does \( \varnothing^{+n} \) have? 
\end{problem}

\vspace{4cm}

\begin{problem}
  Let \( X \) be a set, whose elements are all sets. We call \( X \) \textit{transitive} if, for
  every \( A \in X \), it is also true that \( A \subseteq X \). (This is very strange!) Prove
  that if \( X \) is transitive, then \( X^+ \) is transitive.
\end{problem}

\vspace{4cm}

\begin{problem}
  Let \( \omega \) denote the set
  \( \{ \varnothing, \varnothing^+, \varnothing^{++}, \dots, \varnothing^{+n}, \dots \}. \) Prove
  that \( \omega \) is transitive.
\end{problem}

\end{document}