\documentclass[12pt,titlepage]{article} \usepackage{amsmath} \usepackage{mathrsfs} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} \usepackage{mathtools} \usepackage{graphicx} \usepackage{color} \usepackage{ucs} \usepackage[utf8x]{inputenc} \usepackage{xparse} \usepackage{hyperref} %----Macros---------- % % Unresolved issues: % % \righttoleftarrow % \lefttorightarrow % % \color{} with HTML colorspec % \bgcolor % \array with options (without options, it's equivalent to the matrix environment) % Of the standard HTML named colors, white, black, red, green, blue and yellow % are predefined in the color package. Here are the rest. \definecolor{aqua}{rgb}{0, 1.0, 1.0} \definecolor{fuschia}{rgb}{1.0, 0, 1.0} \definecolor{gray}{rgb}{0.502, 0.502, 0.502} \definecolor{lime}{rgb}{0, 1.0, 0} \definecolor{maroon}{rgb}{0.502, 0, 0} \definecolor{navy}{rgb}{0, 0, 0.502} \definecolor{olive}{rgb}{0.502, 0.502, 0} \definecolor{purple}{rgb}{0.502, 0, 0.502} \definecolor{silver}{rgb}{0.753, 0.753, 0.753} \definecolor{teal}{rgb}{0, 0.502, 0.502} % Because of conflicts, \space and \mathop are converted to % \itexspace and \operatorname during preprocessing. % itex: \space{ht}{dp}{wd} % % Height and baseline depth measurements are in units of tenths of an ex while % the width is measured in tenths of an em. \makeatletter \newdimen\itex@wd% \newdimen\itex@dp% \newdimen\itex@thd% \def\itexspace#1#2#3{\itex@wd=#3em% \itex@wd=0.1\itex@wd% \itex@dp=#2ex% \itex@dp=0.1\itex@dp% \itex@thd=#1ex% \itex@thd=0.1\itex@thd% \advance\itex@thd\the\itex@dp% \makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}} \makeatother % \tensor and \multiscript \makeatletter \newif\if@sup \newtoks\@sups \def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}% \def\reset@sup{\@supfalse\@sups={}}% \def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else% \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}% \else \append@sup#2 \@suptrue \fi% \expandafter\mk@scripts\fi} \def\tensor#1#2{\reset@sup#1\mk@scripts#2_/} \def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2% \reset@sup\mk@scripts#3_/} \makeatother % \slash \makeatletter \newbox\slashbox \setbox\slashbox=\hbox{$/$} \def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$} \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa \copy\slashbox \kern-\@tempdima \box\@tempboxa} \def\slash{\protect\itex@pslash} \makeatother % math-mode versions of \rlap, etc % from Alexander Perlis, "A complement to \smash, \llap, and lap" % http://math.arizona.edu/~aprl/publications/mathclap/ \def\clap#1{\hbox to 0pt{\hss#1\hss}} \def\mathllap{\mathpalette\mathllapinternal} \def\mathrlap{\mathpalette\mathrlapinternal} \def\mathclap{\mathpalette\mathclapinternal} \def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}} \def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}} \def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}} % Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2} \let\oldroot\root \def\root#1#2{\oldroot #1 \of{#2}} \renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}} % Manually declare the txfonts symbolsC font \DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n} \SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n} \DeclareFontSubstitution{U}{txsyc}{m}{n} % Manually declare the stmaryrd font \DeclareSymbolFont{stmry}{U}{stmry}{m}{n} \SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n} % Manually declare the MnSymbolE font \DeclareFontFamily{OMX}{MnSymbolE}{} \DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n} \SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n} \DeclareFontShape{OMX}{MnSymbolE}{m}{n}{ <-6> MnSymbolE5 <6-7> MnSymbolE6 <7-8> MnSymbolE7 <8-9> MnSymbolE8 <9-10> MnSymbolE9 <10-12> MnSymbolE10 <12-> MnSymbolE12}{} % Declare specific arrows from txfonts without loading the full package \makeatletter \def\re@DeclareMathSymbol#1#2#3#4{% \let#1=\undefined \DeclareMathSymbol{#1}{#2}{#3}{#4}} \re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46} \re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12} \re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64} \re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6} \re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77} \re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77} \makeatother % \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE \makeatletter \def\Decl@Mn@Delim#1#2#3#4{% \if\relax\noexpand#1% \let#1\undefined \fi \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}} \def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}} \def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}} \Decl@Mn@Open{\llangle}{mnomx}{'164} \Decl@Mn@Close{\rrangle}{mnomx}{'171} \Decl@Mn@Open{\lmoustache}{mnomx}{'245} \Decl@Mn@Close{\rmoustache}{mnomx}{'244} \makeatother % Widecheck \makeatletter \DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}} \def\@widecheck#1#2{% \setbox\z@\hbox{\m@th$#1#2$}% \setbox\tw@\hbox{\m@th$#1% \widehat{% \vrule\@width\z@\@height\ht\z@ \vrule\@height\z@\@width\wd\z@}$}% \dp\tw@-\ht\z@ \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@ \setbox\tw@\hbox{% \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box \tw@}}}% {\ooalign{\box\tw@ \cr \box\z@}}} \makeatother % \mathraisebox{voffset}[height][depth]{something} \makeatletter \NewDocumentCommand\mathraisebox{moom}{% \IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{% \IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}% }{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}% \mathpalette\@temp{#4}} \makeatletter % udots (taken from yhmath) \makeatletter \def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.} \mkern2mu\raise4\p@\hbox{.}\mkern1mu \raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}} \makeatother %% Fix array \newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}} %% \itexnum is a noop \newcommand{\itexnum}[1]{#1} %% Renaming existing commands \newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}} \newcommand{\widevec}{\overrightarrow} \newcommand{\darr}{\downarrow} \newcommand{\nearr}{\nearrow} \newcommand{\nwarr}{\nwarrow} \newcommand{\searr}{\searrow} \newcommand{\swarr}{\swarrow} \newcommand{\curvearrowbotright}{\curvearrowright} \newcommand{\uparr}{\uparrow} \newcommand{\downuparrow}{\updownarrow} \newcommand{\duparr}{\updownarrow} \newcommand{\updarr}{\updownarrow} \newcommand{\gt}{>} \newcommand{\lt}{<} \newcommand{\map}{\mapsto} \newcommand{\embedsin}{\hookrightarrow} \newcommand{\Alpha}{A} \newcommand{\Beta}{B} \newcommand{\Zeta}{Z} \newcommand{\Eta}{H} \newcommand{\Iota}{I} \newcommand{\Kappa}{K} \newcommand{\Mu}{M} \newcommand{\Nu}{N} \newcommand{\Rho}{P} \newcommand{\Tau}{T} \newcommand{\Upsi}{\Upsilon} \newcommand{\omicron}{o} \newcommand{\lang}{\langle} \newcommand{\rang}{\rangle} \newcommand{\Union}{\bigcup} \newcommand{\Intersection}{\bigcap} \newcommand{\Oplus}{\bigoplus} \newcommand{\Otimes}{\bigotimes} \newcommand{\Wedge}{\bigwedge} \newcommand{\Vee}{\bigvee} \newcommand{\coproduct}{\coprod} \newcommand{\product}{\prod} \newcommand{\closure}{\overline} \newcommand{\integral}{\int} \newcommand{\doubleintegral}{\iint} \newcommand{\tripleintegral}{\iiint} \newcommand{\quadrupleintegral}{\iiiint} \newcommand{\conint}{\oint} \newcommand{\contourintegral}{\oint} \newcommand{\infinity}{\infty} \newcommand{\bottom}{\bot} \newcommand{\minusb}{\boxminus} \newcommand{\plusb}{\boxplus} \newcommand{\timesb}{\boxtimes} \newcommand{\intersection}{\cap} \newcommand{\union}{\cup} \newcommand{\Del}{\nabla} \newcommand{\odash}{\circleddash} \newcommand{\negspace}{\!} \newcommand{\widebar}{\overline} \newcommand{\textsize}{\normalsize} \renewcommand{\scriptsize}{\scriptstyle} \newcommand{\scriptscriptsize}{\scriptscriptstyle} \newcommand{\mathfr}{\mathfrak} \newcommand{\statusline}[2]{#2} \newcommand{\tooltip}[2]{#2} \newcommand{\toggle}[2]{#2} % Theorem Environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{prop}{Proposition} \newtheorem{cor}{Corollary} \newtheorem*{utheorem}{Theorem} \newtheorem*{ulemma}{Lemma} \newtheorem*{uprop}{Proposition} \newtheorem*{ucor}{Corollary} \theoremstyle{definition} \newtheorem{defn}{Definition} \newtheorem{example}{Example} \newtheorem*{udefn}{Definition} \newtheorem*{uexample}{Example} \theoremstyle{remark} \newtheorem{remark}{Remark} \newtheorem{note}{Note} \newtheorem*{uremark}{Remark} \newtheorem*{unote}{Note} %------------------------------------------------------------------- \begin{document} %------------------------------------------------------------------- \section*{countable set} \hypertarget{context}{}\subsubsection*{{Context}}\label{context} \hypertarget{type_theory}{}\paragraph*{{Type theory}}\label{type_theory} [[!include type theory - contents]] \hypertarget{countable_sets}{}\section*{{Countable sets}}\label{countable_sets} \noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak \noindent\hyperlink{definitions}{Definitions}\dotfill \pageref*{definitions} \linebreak \noindent\hyperlink{examples_and_properties}{Examples and Properties}\dotfill \pageref*{examples_and_properties} \linebreak \noindent\hyperlink{history}{History}\dotfill \pageref*{history} \linebreak \noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak \noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak \hypertarget{idea}{}\subsection*{{Idea}}\label{idea} Let $S$ be any [[set]], and let $\mathbf{N}$ be the [[set]] of [[natural number]]s. Let $|S|$ be the [[cardinality]] of $S$, and let $\aleph_0$ be the cardinality of $\mathbf{N}$. Then $S$ is: \begin{itemize}% \item \textbf{denumerable} if ${|S|} = \aleph_0$, \item \textbf{countable} if ${|S|} \leq \aleph_0$, and \item \textbf{uncountable} if ${|S|} \gt \aleph_0$. \end{itemize} Note that the first two terms are not entirely standardised; some authors use them interchangeably for one or the other concept. \hypertarget{definitions}{}\subsection*{{Definitions}}\label{definitions} If you accept the [[axiom of choice]], then there is really nothing more to say than what was above. In weaker [[foundations]], more care may be needed. The following definitions should be more than enough for practical use in [[constructive mathematics]]: \begin{itemize}% \item A [[set]] $S$ is \textbf{denumerable} if there exists a [[bijection]] between $S$ and $\mathbf{N}$; or in other words if $S$ is the same as $\mathbf{N}$ [[up to isomorphism]] in [[Set]]. \item $S$ is \textbf{denumerably indexed} if there exists a [[surjection]] to $S$ from $\mathbf{N}$ (or equivalently any denumerable set); or in other words if $S$ a [[quotient set]] of a $\mathbf{N}$, up to isomorphism. \item $S$ is \textbf{countable} if there exists a bijection between $S$ and a [[detachable subset|detachable]] [[lower subset]] of $\mathbf{N}$. \item $S$ is \textbf{countably indexed} if there exists a [[surjection]] to $S$ from a countable set. \item $S$ is \textbf{subcountable} (or \emph{subdenumerable}) if there exists an [[injection]] from $S$ to a countable set, or equivalently to a denumerable set; or in other words if $S$ is a [[subset]] of $\mathbf{N}$, up to isomorphism. \item $S$ is \textbf{subcountably indexed} (or \emph{subdenumerably indexed}) if $S$ is a [[subquotient]] of $\mathbf{N}$, up to isomorphism. \item $S$ is \textbf{uncountable} if, given any [[function]] $f$ from a detachable subset of $\mathbf{N}$ to $S$, the function is strongly non-surjective in the sense that there exists an element of $S$ that is not in the [[image]] of $f$. \end{itemize} Of course, the terms are even less standardised here. Certainly it is common for `countable' to mean countably indexed, and yet it may also (as in classical mathematics) mean denumerable. In at least some contexts, `enumerable' (without the initial `d') means denumerably indexed. Not only does the difference between `denumerable' and `countable' disappear when we add the prefix `sub' (for obvious reasons), but it almost disappears when we add the suffix `ly indexed'! Specifically, a set is denumerably indexed if and only if it is both [[inhabited set|inhabited]] and countably indexed; and a set is countably indexed if and only if it is either [[empty set|empty]] or denumerably indexed. That countability involves \emph{lower} subsets of $\mathbb{N}$ is also almost irrelevant here; any \emph{inhabited} detachable subset of $\mathbb{N}$ is denumerably indexed regardless of its closure under order. On the other hand, it is key that countability involves \emph{detachable} subsets of $\mathbb{N}$, so that not every subcountable set is necessarily countable (or even countably indexed). Indeed, the set of [[computable numbers]] is subcountably indexed, while the set of [[real numbers]] is uncountable (and thus not countably indexed); yet in [[Russian constructivism]], these are the same set! One reason to focus on countably indexed sets is that this is about the most general concept that definitely does \emph{not} hold of the set of real numbers. There is a lot of freedom in defining uncountability. You can start with countable or countably indexed sets and require that any function from them to $S$ be non-surjective (in the strong sense used in the definition above). Or you can start with denumerable or denumerably indexed sets and require that any function from them to $S$ be non-surjective, then add the additional clause that $S$ must be [[inhabited set|inhabited]]. Or you can compromise, and start with a detachable subset of $\mathbb{N}$ without requiring it to be a lower subset, since this is enough to prove $S$ inhabited and make the order-closure irrelevant. All of these definitions are equivalent! Arguably, uncountability is really a property of a set [[equipped with]] an [[inequality relation]] $\#$. Then $S$ is \textbf{$\#$-uncountable}, or the pair $(S,\#)$ is \textbf{strongly uncountable} (or just \emph{uncountable} if context is clear) if, given any [[function]] $f$ from a detachable subset of $\mathbf{N}$ to $S$ (or equivalently any variation as in the previous paragraph), the function is $\#$-strongly non-surjective in the sense that there exists an element of $S$ that is $\#$-distinct from every element in the [[image]] of $f$. Then the mere set $S$ is uncountable if and only if it is uncountable when equipped with the [[denial inequality]]. \hypertarget{examples_and_properties}{}\subsection*{{Examples and Properties}}\label{examples_and_properties} The set of [[real numbers]] is uncountable. Even in constructive mathematics, this is true for pretty much any notion of real number, from [[regular Cauchy real numbers]] to [[MacNeille real numbers]], by any of the usual arguments. Every denumerable set is [[infinite set|infinite]], and hence so is every set with a denumerable subset. Classically (usng [[dependent choice]] $DC$), we have the converse: a set is infinite if and only if it has a denumerable subset. If a set has a denumerable subset, then its [[power set]] is uncountable. Even without $DC$, using [[excluded middle]] instead, the power set of an infinite set is uncountable. In contrast, the set of [[algebraic numbers]] is denumerable. Also, the set of [[computable numbers]] is subcountably indexed (and infinite, so denumerable in classical mathematics). Combined with the uncountability of the real numbers, this gives the existence of transcendental numbers (constructively) and uncomputable numbers (classically). Classically, every set is countable [[xor]] uncountable. Even constructively, a countably indexed set cannot be uncountable. In [[Russian constructivism]], however, there are subcountable sets that are also uncountable. In particular, the set of computable numbers is subcountably indexed, while the set of real numbers is uncountable, yet in Russian constructivism, these are the same set! In some formalisms of Russian constructivism, \emph{every} set is subcountably indexed. The [[empty set]] is countable, although not denumerably indexed. Conversely, any uncountable set must be [[inhabited set|inhabited]], as must be any denumerably indexed set. Even constructively, a countable set is empty xor inhabited. Every [[finite set]] is countable, every finitely indexed set is countably indexed, every subfinite set is subcountable, and every subfinitely indexed set is subcountably indexed. Conversely, every uncountable set is [[infinite set|infinite]]. Classically, a denumerable set is precisely an [[infinite set|infinite]] countable set; sometimes this is written as a \emph{countably infinite set}. Thus classically, a countable set is finite xor denumerable. Even constructively, a countable set is denumerable if and only if it is not finite. Classically (using [[countable choice]]), [[countable unions of countable sets are countable]]. \hypertarget{history}{}\subsection*{{History}}\label{history} Arguably, [[set theory]] as such begins with the 1873 correspondence between [[Georg Cantor]] and [[Richard Dedekind]] on countability. Although they tacitly used [[excluded middle]] throughout, generally speaking, their results were constructive if taken to be about countably indexed sets. They worked out the countability of the algebraic numbers and the uncountability of the real numbers, including both constructive and nonconstructive proofs of the existence of transcendental numbers. (This was the same year that [[Charles Hermite]] published a proof that $\mathrm{e}$ is transcendental, although [[Joseph Liouville]] had shown how to artificially construct transcendental numbers as early as 1851.) In subsequent correspondence with Cantor, [[Karl Weierstrass]] stressed the usefulness of the countability of the algebraic numbers but downplayed the notion of uncountability. Still, he urged Cantor to publish. Since Weierstrass and the [[finitism|finitist]] [[Leopold Kronecker]] were senior editors at Krelle's Journal, Cantor wrote his 1874 article carefully. He showed the denumerability of the algebraic numbers explicitly and titled the article as if that were the only subject. He then added a footnote in the proofreading stages, using an [[interval]]-based argument, showing how a transcendental number could be constructed from this denumeration. Cantor's argument was essentially a constructive proof that the set of real numbers is uncountable, as it could apply to any denumerably indexed subset. He tacitly used [[LLPO]], but it's straightforward to avoid this using binary [[meets]] and [[joins]] of real numbers, which are constructive. He also used a [[Dedekind cut]] to construct the final transcendental number, and it is this that Kronecker would have most likely objected to, since it is an irreducibly infinite procedure to construct a single number. However, the argument is acceptable to any non-finitist constructivist. In the correspondence with Dedekind, it was Cantor who first considered and proved the uncountability of the real numbers but Dedekind who first considered and proved the countability of the algebraic numbers, which was the ostensible subject of Cantor's article. Furthermore, it was Dedekind who first wrote the interval-based proof that Cantor used in his footnote that was the real point of the article. However, Cantor gave Dedekind no credit. This strained their relationship for a few years afterward. The [[diagonal argument]] also shows the uncountability of the real numbers (nonconstructively through [[Cantor's Theorem]] on the cardinality of power sets, constructively through a slight generalization), but Cantor did not publish this until 1891. Interpreted finitistically as an algorithm to construct, from a sequence of real numbers, an approximation of a hypothetical number not in the sequence, the diagonal argument is more efficient; pedagogically, it is easier to explain. However, it was not the first. \hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts} \begin{itemize}% \item [[countable ordinal]] \item [[countable cover]] \end{itemize} \hypertarget{references}{}\subsection*{{References}}\label{references} \begin{itemize}% \item \href{https://en.wikipedia.org/wiki/Georg_Cantor's_first_set_theory_article}{https\char58\char47\char47en\char46wikipedia\char46org\char47wiki\char47Georg\char95Cantor\char39s\char95first\char95set\char95theory\char95article} (which discusses both the origin of the 1874 article and the questions of constructivity that arose in its aftermath) \end{itemize} [[!redirects countable set]] [[!redirects countable sets]] [[!redirects countably infinite set]] [[!redirects countably infinite sets]] [[!redirects denumerable set]] [[!redirects denumerable sets]] [[!redirects uncountable set]] [[!redirects uncountable sets]] [[!redirects countable family]] [[!redirects countable families]] [[!redirects numerable]] [[!redirects numerable set]] [[!redirects numerable sets]] \end{document}