Numbers, Counting, Cardinality

Skip to main content

\(\DeclareMathOperator{\ann}{ann} \DeclareMathOperator{\Ass}{Ass} \DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\can}{can} \DeclareMathOperator{\Ch}{Ch} \DeclareMathOperator{\char}{char} \DeclareMathOperator{\cp}{CharPoly} \DeclareMathOperator{\codim}{codim} \DeclareMathOperator{\coker}{coker} \DeclareMathOperator{\colim}{colim} \DeclareMathOperator{\cone}{cone} \DeclareMathOperator{\cont}{cont} \DeclareMathOperator{\diam}{diam} \DeclareMathOperator{\dim}{dim} \DeclareMathOperator{\edim}{embdim} \DeclareMathOperator{\End}{End} \DeclareMathOperator{\eval}{eval} \DeclareMathOperator{\Ext}{Ext} \DeclareMathOperator{\Frac}{Frac} \DeclareMathOperator{\Fun}{Fun} \DeclareMathOperator{\Gal}{Gal} \DeclareMathOperator{\gcd}{gcd} \DeclareMathOperator{\GL}{GL} \DeclareMathOperator{\height}{height} \DeclareMathOperator{\Hom}{Hom} \DeclareMathOperator{\id}{id} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\Inn}{Inn} \DeclareMathOperator{\ker}{ker} \DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\Mat}{Mat} \DeclareMathOperator{\max}{max} \DeclareMathOperator{\Min}{Min} \DeclareMathOperator{\mp}{MinPoly} \DeclareMathOperator{\mSpec}{mSpec} \DeclareMathOperator{\Nul}{Nul} \DeclareMathOperator{\ns}{nullspace} \DeclareMathOperator{\opp}{opp} \DeclareMathOperator{\Orb}{Orb} \DeclareMathOperator{\Out}{Out} \DeclareMathOperator{\pdim}{pdim} \DeclareMathOperator{\Perm}{Perm} \DeclareMathOperator{\PtStab}{pStab} \DeclareMathOperator{\rad}{rad} \DeclareMathOperator{\range}{range} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\res}{res} \DeclareMathOperator{\sStab}{SetStab} \DeclareMathOperator{\sign}{sign} \DeclareMathOperator{\SL}{SL} \DeclareMathOperator{\Span}{Span} \DeclareMathOperator{\Spec}{Spec} \DeclareMathOperator{\Stab}{Stab} \DeclareMathOperator{\Supp}{Supp} \DeclareMathOperator{\Syl}{Syl} \DeclareMathOperator{\Tor}{Tor} \DeclareMathOperator{\trace}{trace} \DeclareMathOperator{\trdeg}{trdeg} \newcommand{\Ob}{\mathrm{Ob}} \newcommand{\Set}{\mathbf{Set}} \newcommand{\Grp}{\mathbf{Grp}} \newcommand{\Ab}{\mathbf{Ab}} \newcommand{\Sgrp}{\mathbf{Sgrp}} \newcommand{\Ring}{\mathbf{Ring}} \newcommand{\Fld}{\mathbf{Fld}} \newcommand{\cRing}{\mathbf{cRing}} \newcommand{\Mod}[1]{#1-\mathbf{Mod}} \newcommand{\Cx}[1]{#1-\mathbf{Comp}} \newcommand{\vs}[1]{#1-\mathbf{vect}} \newcommand{\Vs}[1]{#1-\mathbf{Vect}} \newcommand{\vsp}[1]{#1-\mathbf{vect}^+} \newcommand{\Top}{\mathbf{Top}} \newcommand{\Setp}{\mathbf{Set}_*} \newcommand{\Alg}[1]{#1-\mathbf{Alg}} \newcommand{\cAlg}[1]{#1-\mathbf{cAlg}} \newcommand{\PO}{\mathbf{PO}} \newcommand{\Cont}{\mathrm{Cont}} \newcommand{\MaT}[1]{\mathbf{Mat}_{#1}} \newcommand{\Rep}[2]{\mathbf{Rep}_{#1}(#2)} \def\l{\lambda} \def\a{\alpha} \def\b{\beta} \def\d{\delta} \def\e{\varepsilon} \def\g{\gamma} \def\t{\theta} \def\s{\sigma} \def\z{\zeta} \def\vp{\varphi} \newcommand{\A}{\mathbb{A}} \newcommand{\B}{\mathbb{B}} \newcommand{\C}{\mathbb{C}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathbb{E}} \newcommand{\F}{\mathbb{F}} \newcommand{\G}{\mathbb{G}} \newcommand{\H}{\mathbb{H}} \newcommand{\I}{\mathbb{I}} \newcommand{\J}{\mathbb{J}} \newcommand{\K}{\mathbb{K}} \newcommand{\L}{\mathbb{L}} \newcommand{\M}{\mathbb{M}} \newcommand{\N}{\mathbb{N}} \newcommand{\O}{\mathbb{O}} \newcommand{\P}{\mathbb{P}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\S}{\mathbb{S}} \newcommand{\T}{\mathbb{T}} \newcommand{\U}{\mathbb{U}} \newcommand{\V}{\mathbb{V}} \newcommand{\W}{\mathbb{W}} \newcommand{\X}{\mathbb{X}} \newcommand{\Y}{\mathbb{Y}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\ON}{\mathbb{ON}} \def\cA{\mathcal A} \def\cB{\mathcal B} \def\cC{\mathcal C} \def\cD{\mathcal D} \def\cE{\mathcal E} \def\cF{\mathcal F} \def\cG{\mathcal G} \def\cH{\mathcal H} \def\cI{\mathcal I} \def\cJ{\mathcal J} \def\cK{\mathcal K} \def\cL{\mathcal L} \def\cM{\mathcal M} \def\cN{\mathcal N} \def\cO{\mathcal O} \def\cP{\mathcal P} \def\cQ{\mathcal Q} \def\cR{\mathcal R} \def\cS{\mathcal S} \def\cT{\mathcal T} \def\cU{\mathcal U} \def\cV{\mathcal V} \def\cW{\mathcal W} \def\cX{\mathcal X} \def\cY{\mathcal Y} \def\cZ{\mathcal Z} \newcommand{\fa}{{\mathfrak a}} \newcommand{\fb}{{\mathfrak b}} \newcommand{\fc}{{\mathfrak c}} \newcommand{\fd}{{\mathfrak d}} \newcommand{\fe}{{\mathfrak e}} \newcommand{\ff}{{\mathfrak f}} \newcommand{\fg}{{\mathfrak g}} \newcommand{\fh}{{\mathfrak h}} \newcommand{\fi}{{\mathfrak i}} \newcommand{\fj}{{\mathfrak j}} \newcommand{\fk}{{\mathfrak k}} \newcommand{\fl}{{\mathfrak l}} \newcommand{\fm}{{\mathfrak m}} \newcommand{\fn}{{\mathfrak n}} \newcommand{\fo}{{\mathfrak o}} \newcommand{\fp}{{\mathfrak p}} \newcommand{\fq}{{\mathfrak q}} \newcommand{\fr}{{\mathfrak r}} \newcommand{\fs}{{\mathfrak s}} \newcommand{\ft}{{\mathfrak t}} \newcommand{\fu}{{\mathfrak u}} \newcommand{\fv}{{\mathfrak v}} \newcommand{\fw}{{\mathfrak w}} \newcommand{\fx}{{\mathfrak x}} \newcommand{\fy}{{\mathfrak y}} \newcommand{\fz}{{\mathfrak z}} \newcommand{\fK}{{\mathfrak K}} \newcommand{\fR}{{\mathfrak R}} \def\sA{\mathscr A} \def\sB{\mathscr B} \def\sC{\mathscr C} \def\sD{\mathscr D} \def\sE{\mathscr E} \def\sF{\mathscr F} \def\sG{\mathscr G} \def\sH{\mathscr H} \def\sI{\mathscr I} \def\sJ{\mathscr J} \def\sK{\mathscr K} \def\sL{\mathscr L} \def\sM{\mathscr M} \def\sN{\mathscr N} \def\sO{\mathscr O} \def\sP{\mathscr P} \def\sQ{\mathscr Q} \def\sR{\mathscr R} \def\sS{\mathscr S} \def\sT{\mathscr T} \def\sU{\mathscr U} \def\sV{\mathscr V} \def\sW{\mathscr W} \def\sX{\mathscr X} \def\sY{\mathscr Y} \def\sZ{\mathscr Z} \def\adots{a_1, \dots, a_n} \def\bdots{b_1, \dots, b_n} \def\ddots{d_1, \dots, d_n} \def\edots{e_1, \dots, e_n} \def\fdots{f_1, \dots, f_n} \def\gdots{g_1, \dots, g_n} \def\udots{u_1, \dots, u_n} \def\xdots{x_1, \dots, x_n} \def\tS{\tilde{S}} \def\sdp{\rtimes} \newcommand{\tensor}{\otimes} \newcommand{\igen}[1]{\langle #1 \rangle} \def\nsg{\unlhd} \def\kval{{k-\mathrm{valued}}} \def\kalg{{k-\mathrm{alg}}} \newcommand\GG[2]{\Gal(#1/#2)} \newcommand{\MF}[3]{\Mat_{#1\times #2}(#3)} \newcommand{\vectwo}[2]{\begin{bmatrix} #1 \\ #2 \end{bmatrix}} \newcommand{\vecthree}[3]{\begin{bmatrix} #1 \\ #2 \\ #3\end{bmatrix}} \def\ob{{\mathfrak{ob}} } \def\qed{\square} \def\sse{\subseteq} \def\ss{\subset} \def\ssne{\subsetneq} \def\sm{\setminus} \def\inv{^{-1}} \newcommand{\es}{\emptyset} \newcommand{\Zm}[1]{\Z/({#1})} \def\ov#1{\overline{#1}} \newcommand{\leg}[2]{\left(\frac{{#1}}{{#2}}\right)} \def\th{^{th}} \def\htpy{\simeq_{\mathrm{htpc}}} \def\textand{ \, \text{and} \, } \def\textor{ \, \text{or} \, } \def\textfor{ \, \text{for} \, } \def\textfa{ \, \text{for all} \, } \def\textst{ \, \text{such that} \, } \def\textin{ \, \text{in} \, } \def\fg{ \, \text{finitely generated} \, } \newcommand{\op}{\mathrm{op}} \newcommand{\xra}[1]{\xrightarrow{#1}} \newcommand{\xora}[1]{\xtwoheadrightarrow{#1}} \newcommand{\xira}[1]{\xhookrightarrow{#1}} \newcommand{\xla}[1]{\xleftarrow{#1}} \def\lra{\longrightarrow} \def\into{\hookrightarrow} \def\onto{\twoheadrightarrow} \newcommand{\vv}[1]{\mathbf{#1}} \newcommand{\lm}[2]{{#1}\,\l + {#2}\,\mu} \renewcommand{\v}{\vv{v}} \renewcommand{\u}{\vv{u}} \newcommand{\w}{\vv{w}} \newcommand{\x}{\vv{x}} \renewcommand{\k}{\vv{k}} \newcommand{\0}{\vv{0}} \newcommand{\1}{\vv{1}} \newcommand{\vecs}[2]{#1_1,#1_2,\dots,#1_{#2}} \newcommand{\us}[1][n]{\vecs{\u}{#1}} \newcommand{\vs}[1][n]{\vecs{\v}{#1}} \newcommand{\ws}[1][n]{\vecs{\w}{#1}} \newcommand{\vps}[1][n']{\vecs{\v'}{#1}} \newcommand{\ls}[1][n]{\vecs{\l}{#1}} \newcommand{\mus}[1][n]{\vecs{\mu}{#1}} \newcommand{\lps}[1][n]{\vecs{\l'}{#1}} \def\td{\tilde{\delta}} \def\oo{\overline{\omega}} \def\ctJ{\tilde{\mathcal J}} \def\tPhi{\tilde{\Phi}} \def\te{\tilde{e}} \def\M{\operatorname{M}} \newcommand{\homotopic}{\simeq} \newcommand{\homeq}{\cong} \newcommand{\iso}{\approx} \newcommand{\dual}{\vee} \DeclarePairedDelimiter{\abs}{|}{|} \newcommand{\bv}{{\bar{v}}} \newcommand{\bu}{{\bar{u}}} \newcommand{\bw}{{\bar{w}}} \newcommand{\by}{{\bar{y}}} \newcommand{\ba}{{\bar{a}}} \newcommand{\bb}{{\bar{b}}} \newcommand{\bx}{{\bar{x}}} \DeclarePairedDelimiterX\setof[2]{\{}{\}}{#1\,|\,#2} \newcommand{\vx}{\underline{x}} \renewcommand{mod}[1]{\text{(mod }{#1})} \newcommand{\Slv}[3]{\sum_{{#2}=1}^{{#3}} {#1}_{{#2}} \v_{{#2}}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)

Section A.2 Numbers, Counting, Cardinality

Subsection Number Theory

Definition A.34. Divisibility.

Let \(a\) and \(b\) be integers. The integer \(a\) divides the integer \(b\) if and only if there is some integer \(q\) such that \(aq = b\text{.}\) If \(a\) divides \(b\text{,}\) we write \(a|b\text{,}\) and we say that \(a\) is a factor of \(b\text{,}\) and that \(b\) is divisible by \(a\text{.}\)

Definition A.35. Prime.

Let \(p\) be an integer greater than \(1\text{.}\) The integer \(p\) is a prime number if and only if the only positive integers that divide \(p\) are \(1\) and \(p\text{.}\) The integer \(p\) is a composite number iff it is not a prime number.

Definition A.36. GCD, LCM (*).

Theorem A.37. Division Algorithm.

Let \(a\) and \(b\) be integers with \(b>0\text{.}\) Then there exist unique integers \(q\) and \(r\) such that

\begin{equation*} a=bq+r\quad\text{and}\quad 0\leq r<b \end{equation*}

Proof.

Coming soon!

Subsection Counting (*)

Definition A.38. Binomial Coefficient (*).

Theorem A.39. Binomial Theorem (*).

Subsection Cardinality

Definition A.40. Cardinality.

A set \(X\) is finite if there is a bijection \(X \to \{1,...,n\}\) for some natural number \(n\text{,}\) or \(X\) is empty. In this case the number \(n\) is called the cardinality of \(X\text{.}\)

A set \(X\) is infinite if \(X\) is not finite. A set \(X\) is countable if there is an injection \(X \hookrightarrow \N\text{.}\)

Theorem A.41.

Let \(X\) be a set.

The following are equivalent:
1. \(X\) is finite.
2. There is an onto function \(\{1,...,n\} \onto X\) for some \(n \in \N.\)
3. There is a one-to-one function \(X \hookrightarrow \{1,...,n\}\) for some \(n \in \N\text{.}\)
The following are equivalent:
1. \(X\) is infinite.
2. There is an onto function \(X \onto \N\) .
3. There is a one-to-one function \(\N \hookrightarrow X\text{.}\)
The following are equivalent:
1. \(X\) is countable.
2. There is an onto function \(\N \to X\text{.}\)
3. There is an injection \(X \hookrightarrow \N\) .

Theorem A.42.

The class of finite sets is closed under: subsets, intersections, finite unions, and finite products.
The class of countable sets is closed under: subsets, intersections, countable unions, and finite products.