% \documentclass tells what type of document you are preparing.
% ''article'' is the most generic type and works for anything you'll be doing
\documentclass{article}
% \usepackage imports packages with new symbols
% There are LOTS of possible packages, but the ones below cover most everything
% you'll need for math and graphics.
\usepackage{amsmath,amsthm,amssymb,latexsym,graphicx}
% \newtheorem lets you name a few different kinds of theorem environments
% The first argument is what you want the command to be named.
% The second argument is the word that should actually appear in the document.
% The optional third argument tells them all to use the same numbering scheme.
% It will make more sense when you see it in use later in the document.
\newtheorem*{thm}{Theorem}
\newtheorem*{prop}{Proposition}
\newtheorem*{defn}{Definition}
\newtheorem*{lem}{Lemma}
\newtheorem*{cor}{Corollary}
\newtheorem*{conj}{Conjecture}
% Put your title, author, and date information BEFORE \begin{document},
% then call the \maketitle command immediately after \begin{document}
\title{Proof Portfolio \# 7}
\author{Austin Mohr}
\date{\today} % You can specify a date, or just use \today to use today's date.
% \begin{document} and \end{document} mark the beginning and end of the
% part of the document you actually want to be typeset
\begin{document}
\maketitle
\begin{prop}
For any natural number $n$, there are as many subsets of $[n]$ as there are binary strings of length $n$.
\end{prop}
\begin{proof}
Let $n \in \mathbb{N}$ be given and let $A_n$ denote the collection of all binary strings of length $n$. Define a function $f: \mathcal{P}([n]) \rightarrow A_n$ in the following way: Given a subset $S$ of $[n]$, define $f(S)$ to be the binary string whose $k^\text{th}$ digit is 1 if $k \in S$ and 0 if $k \notin S$ (for $1 \leq k \leq n$). We claim that $f$ is a bijection.
To show that $f$ is injective, begin by assuming that $S_1 \neq S_2$, where $S_1$ and $S_2$ are subsets of $[n]$. We want to show that $f(S_1) \neq f(S_2)$. \textbf{(Your assumption is that the two sets differ, so one of $S_1$ or $S_2$ has an element that the other does not. Use this to conclude that the associated binary strings also differ.)}
To show that $f$ is surjective, let us be given a binary string $a$ of length $n$. We want to show that there is a subset $S$ of $[n]$ such that $f(S) = a$. \textbf{(Show that there is a set $S$ such that $f(S) = a$ by describing how to reconstruct $S$ from its binary string representation.)}
\end{proof}
% Here's the end of the document
\end{document}