Content deleted Content added
m Fixed a linguistic issue. |
→Formal overview: Fix grammar. |
||
| (23 intermediate revisions by 14 users not shown) | |||
Line 11:
==A note on terminology <span class="anchor" id="Terminology"></span>==
Although the terms "countable" and "countably infinite" as defined here are quite common, the terminology is not universal.<ref>{{cite book |last1=Manetti |first1=Marco |title=Topology |date=19 June 2015 |publisher=Springer |isbn=978-3-319-16958-3 |page=26 |url=https://books.google.com/books?id=89zyCQAAQBAJ&pg=PA26 |language=en}}</ref> An alternative style uses ''countable'' to mean what is here called countably infinite, and ''at most countable'' to mean what is here called countable.<ref name="Rudin">{{Harvard citation no brackets|Rudin|1976|loc=Chapter 2}}</ref><ref>{{harvnb|Tao|2016|p=181}}</ref>
The terms ''enumerable''<ref>{{Harvard citation no brackets|Kamke|1950|page=2}}</ref> and '''denumerable'''<ref name="Lang">{{Harvard citation no brackets|Lang|1993|loc=§2 of Chapter I}}</ref><ref name="Apostol">{{Harvard citation no brackets|Apostol|1969|loc=Chapter 1.14|p=23}}</ref> may also be used, e.g. referring to countable and countably infinite respectively,<ref>{{cite book |last1=Thierry |first1=Vialar |title=Handbook of Mathematics |date=4 April 2017 |publisher=BoD - Books on Demand |isbn=978-2-9551990-1-5 |page=24 |url=https://books.google.com/books?id=RkepDgAAQBAJ&pg=PA24 |language=en}}</ref>
==Definition==
The most concise definition is in terms of [[cardinality]]. A set <math>S</math> is ''countable'' if its cardinality <math>|S|</math> is less than or equal to <math>\aleph_0</math> ([[aleph-null]]), the cardinality of the set of [[natural numbers]] <math>\N = \{ 0, 1, 2, 3, \ldots \}</math>. A set <math>S</math> is ''countably [[infinite set|infinite]]'' if <math>|S| = \aleph_0</math>. A set is ''[[uncountable]]'' if it is not countable, i.e. its cardinality is greater than <math>\aleph_0</math>; the reader is referred to [[Uncountable set]] for further discussion.<ref>{{cite book |last1=Yaqub |first1=Aladdin M. |title=An Introduction to Metalogic |date=24 October 2014 |publisher=Broadview Press |isbn=978-1-4604-0244-3 |url=https://books.google.com/books?id=cyljCAAAQBAJ&pg=PT187 |language=en}}</ref>▼
* Its [[cardinality]] <math>|S|</math> is less than or equal to <math>\aleph_0</math> ([[aleph-null]]), the cardinality of the set of [[natural numbers]] <math>\N</math>.<ref name=Yaqub/>
* There exists an [[injective function]] from
▲* <math>S</math> is countable.<ref name="Lang"/>
▲* There exists an [[injective function]] from {{mvar|S}} to <math>\N</math>.<ref name=Singh>{{cite book |last1=Singh |first1=Tej Bahadur |title=Introduction to Topology |date=17 May 2019 |publisher=Springer |isbn=978-981-13-6954-4 |page=422 |url=https://books.google.com/books?id=UQiZDwAAQBAJ&pg=PA422 |language=en}}</ref><ref name=Katzourakis>{{cite book |last1=Katzourakis |first1=Nikolaos |last2=Varvaruca |first2=Eugen |title=An Illustrative Introduction to Modern Analysis |date=2 January 2018 |publisher=CRC Press |isbn=978-1-351-76532-9 |url=https://books.google.com/books?id=jBFFDwAAQBAJ&pg=PT15 |language=en}}</ref>
* <math>S</math> is empty or there exists a [[surjective function]] from <math>\N</math> to <math>S</math>.<ref name=Katzourakis/>
* There exists a [[bijective]] mapping between <math>S</math> and a subset of <math>\N</math>.<ref>{{harvnb|Halmos|1960|loc=p. 91}}</ref>
* <math>S</math> is either [[Finite set|finite]] (<math>|S|<\aleph_0</math>) or countably infinite.<ref
All of these definitions are equivalent.
A set <math>S</math> is ''countably [[infinite set|infinite]]'' if:
* Its cardinality <math>|S|</math> is
* There is an injective and surjective (and therefore [[bijection|bijective]]) mapping between <math>S</math> and <math>\N</math>.
* <math>S</math> has a [[One-one correspondence|one-to-one correspondence]] with <math>\N</math>.<ref>{{harvnb|Kamke|1950|loc=p. 2}}</ref>
* The elements of <math>S</math> can be arranged in an infinite sequence <math>a_0, a_1, a_2, \ldots</math>, where <math>a_i</math> is distinct from <math>a_j</math> for <math>i\neq j</math> and every element of <math>S</math> is listed.<ref>{{cite book |last1=Dlab |first1=Vlastimil |last2=Williams |first2=Kenneth S. |title=Invitation To Algebra: A Resource Compendium For Teachers, Advanced Undergraduate Students And Graduate Students In Mathematics |date=9 June 2020 |publisher=World Scientific |isbn=978-981-12-1999-3 |page=8 |url=https://books.google.com/books?id=l9rrDwAAQBAJ&pg=PA8 |language=en}}</ref><ref>{{harvnb|Tao|2016|p=182}}</ref>
▲
==History==
Line 36 ⟶ 37:
==Introduction==
A ''[[Set (mathematics)|set]]'' is a collection of ''elements'', and may be described in many ways. One way is simply to list all of its elements; for example, the set consisting of the integers 3, 4, and 5 may be denoted <math>\{3, 4, 5\}</math>, called roster form.<ref>{{Cite web|date=2021-05-09|title=What Are Sets and Roster Form?|url=https://www.expii.com/t/what-are-sets-and-roster-form-4300| url-status=live|website=expii|archive-url=https://web.archive.org/web/20200918224155/https://www.expii.com/t/what-are-sets-and-roster-form-4300 |archive-date=2020-09-18 }}</ref> This is only effective for small sets, however; for larger sets, this would be time-consuming and error-prone. Instead of listing every single element, sometimes an ellipsis ("...") is used to represent many elements between the starting element and the end element in a set, if the writer believes that the reader can easily guess what ... represents; for example, <math>\{1, 2, 3,
[[File:Aplicación 2 inyectiva sobreyectiva02.svg|thumb|x100px|Bijective mapping from integer to even numbers]]
Some sets are ''infinite''; these sets have more than <math>n</math> elements where <math>n</math> is any integer that can be specified. (No matter how large the specified integer <math>n</math> is, such as <math>n=10^{1000}</math>, infinite sets have more than <math>n</math> elements.) For example, the set of natural numbers, denotable by <math>\{0, 1, 2, 3, 4, 5,
<math display="block">\ldots \, -\! 2\! \rightarrow \! - \! 4, \, -\! 1\! \rightarrow \! - \! 2, \, 0\! \rightarrow \! 0, \, 1\! \rightarrow \! 2, \, 2\! \rightarrow \! 4 \, \cdots</math>
or, more generally, <math>n \rightarrow 2n</math> (see picture). What we have done here is arrange the integers and the even integers into a ''one-to-one correspondence'' (or ''[[bijection]]''), which is a [[function (mathematics)|function]] that maps between two sets such that each element of each set corresponds to a single element in the other set. This mathematical notion of "size", cardinality, is that two sets are of the same size if and only if there is a bijection between them. We call all sets that are in one-to-one correspondence with the integers ''countably infinite'' and say they have cardinality <math>\aleph_0</math>.
Line 48 ⟶ 49:
By definition, a set <math>S</math> is ''countable'' if there exists a [[bijection]] between <math>S</math> and a subset of the [[natural numbers]] <math>\N=\{0,1,2,\dots\}</math>. For example, define the correspondence
<math display=block>
a \leftrightarrow 1,\ b \leftrightarrow 2,\ c \leftrightarrow 3
Since every element of <math>S=\{a,b,c\}</math> is paired with ''precisely one'' element of <math>\{1,2,3\}</math>, ''and'' vice versa, this defines a bijection, and shows that <math>S</math> is countable. Similarly we can show all finite sets are countable.▼
</math>
▲Since every element of <math>S=\{a,b,c\}</math> is paired with ''precisely one'' element of <math>\{1,2,3\}</math>, ''and'' vice versa, this defines a bijection, and shows that <math>S</math> is countable. Similarly we can show all finite sets
As for the case of infinite sets, a set <math>S</math> is countably infinite if there is a [[bijection]] between <math>S</math> and all of <math>\N</math>. As examples, consider the sets <math>A=\{1,2,3,\dots\}</math>, the set of positive [[integer]]s, and <math>B=\{0,2,4,6,\dots\}</math>, the set of even integers. We can show these sets are countably infinite by exhibiting a bijection to the natural numbers. This can be achieved using the assignments ''n'' ↔ ''n+1'' and ''n'' ↔ 2''n'', so that▼
▲As for the case of infinite sets, a set <math>S</math> is countably infinite if there is a [[bijection]] between <math>S</math> and all of <math>\N</math>. As examples, consider the sets <math>A=\{1,2,3,\dots\}</math>, the set of positive [[integer]]s, and <math>B=\{0,2,4,6,\dots\}</math>, the set of even integers. We can show these sets are countably infinite by exhibiting a bijection to the natural numbers. This can be achieved using the assignments
<math display=block>\begin{matrix}
0 \leftrightarrow 1, & 1 \leftrightarrow 2, & 2 \leftrightarrow 3, & 3 \leftrightarrow 4, & 4 \leftrightarrow 5, & \ldots \\[6pt]
0 \leftrightarrow 0, & 1 \leftrightarrow 2, & 2 \leftrightarrow 4, & 3 \leftrightarrow 6, & 4 \leftrightarrow 8, & \ldots
\end{matrix}</math>
Every countably infinite set is countable, and every infinite countable set is countably infinite. Furthermore, any subset of the natural numbers is countable, and more generally:
{{math theorem | math_statement = A subset of a countable set is countable.<ref>{{harvnb|Halmos|1960|page=91}}</ref>}}
The set of all [[ordered pair]]s of natural numbers (the [[Cartesian product]] of two sets of natural numbers, <math>\N\times\N</math> is countably infinite, as can be seen by following a path like the one in the picture: [[File:Pairing natural.svg|thumb|300px|The [[Cantor pairing function]] assigns one natural number to each pair of natural numbers]] The resulting [[Map (mathematics)|mapping]] proceeds as follows:
<math display=block>
0 \leftrightarrow (0, 0), 1 \leftrightarrow (1, 0), 2 \leftrightarrow (0, 1), 3 \leftrightarrow (2, 0), 4 \leftrightarrow (1, 1), 5 \leftrightarrow (0, 2), 6 \leftrightarrow (3, 0), \ldots
</math>
This mapping covers all such ordered pairs.
This form of triangular mapping [[recursion|recursively]] generalizes to <math>n</math>-[[tuple]]s of natural numbers, i.e., <math>(a_1,a_2,a_3,\dots,a_n)</math> where <math>a_i</math> and <math>n</math> are natural numbers, by repeatedly mapping the first two elements of an <math>n</math>-tuple to a natural number. For example, <math>(0, 2, 3)</math> can be written as <math>((0, 2), 3)</math>. Then <math>(0, 2)</math> maps to 5 so <math>((0, 2), 3)</math> maps to <math>(5, 3)</math>, then <math>(5, 3)</math> maps to 39. Since a different 2-tuple, that is a pair such as <math>(
{{math theorem | math_statement = The [[Cartesian product]] of finitely many countable sets is countable.<ref>{{Harvard citation no brackets|Halmos|1960|page=92}}</ref>{{efn|'''Proof:''' Observe that <math>\N\times\N</math> is countable as a consequence of the definition because the function <math>f:\N\times\N\to\N</math> given by <math>f(m,n)=2^m\cdot3^n</math> is injective.<ref>{{Harvard citation no brackets|Avelsgaard|1990|page=182}}</ref> It then follows that the Cartesian product of any two countable sets is countable, because if <math>A</math> and <math>B</math> are two countable sets there are surjections <math>f:\N\to A</math> and <math>g:\N\to B</math>. So <math>f\times g:\N\times\N\to A\times B</math>
Line 76 ⟶ 82:
Sometimes more than one mapping is useful: a set <math>A</math> to be shown as countable is one-to-one mapped (injection) to another set <math>B</math>, then <math>A</math> is proved as countable if <math>B</math> is one-to-one mapped to the set of natural numbers. For example, the set of positive [[rational number]]s can easily be one-to-one mapped to the set of natural number pairs (2-tuples) because <math>p/q</math> maps to <math>(p,q)</math>. Since the set of natural number pairs is one-to-one mapped (actually one-to-one correspondence or bijection) to the set of natural numbers as shown above, the positive rational number set is proved as countable.
{{math theorem | math_statement = Any finite [[union (set theory)|union]] of countable sets is countable.<ref>{{Harvard citation no brackets|Avelsgaard|1990|page=180}}</ref><ref>{{Harvard citation no brackets|Fletcher|Patty|1988|page=187}}</ref>{{efn|1='''Proof:''' If <math>A_i</math> is a countable set for each <math>i</math> in <math>I=\{1,\dots,n\}</math>, then for each <math>
<math display="block">G : I \times \mathbf{N} \to \bigcup_{i \in I} A_i,</math>
given by <math>G(i,m)=g_i(m)</math> is a surjection. Since <math>I\times \N</math> is countable, the union <math display="inline">\bigcup_{i \in I} A_i</math> is countable.
}}}}
With the foresight of knowing that there are uncountable sets, we can wonder whether or not this last result can be pushed any further. The answer is "yes" and "no", we can extend it, but we need to assume a new axiom to do so.
{{math theorem | math_statement = (Assuming the [[axiom of countable choice]]) The union of countably many countable sets is countable.{{efn|1='''Proof''': As in the finite case, but <math>I=\N</math> and we use the [[axiom of countable choice]] to pick for each <math>i</math> in <math>\N</math> a surjection <math>g_i</math> from the non-empty collection of surjections from <math>\N</math> to <math>A_i</math>.<ref>{{cite book |last1=Hrbacek |first1=Karel |last2=Jech |first2=Thomas |title=Introduction to Set Theory, Third Edition, Revised and Expanded |date=22 June 1999 |publisher=CRC Press |isbn=978-0-8247-7915-3 |page=141 |url=https://books.google.com/books?id=Er1r0n7VoSEC&pg=PA141 |language=en}}</ref> Note that since we are considering the surjection <math>G : \mathbf{N} \times \mathbf{N} \to \bigcup_{i \in I} A_i</math>, rather than an injection, there is no requirement that the sets be disjoint.}}}}
[[File:Countablepath.svg|thumb|300px|Enumeration for countable number of countable sets]]
<math display=block>
\begin{array}{ c|c|c }
\text{Index} & \text{Tuple} & \text {Element} \\ \hline
0 & (0,0) & \textbf{a}_0 \\
1 & (0,1) & \textbf{a}_1 \\
2 & (1,0) & \textbf{b}_0 \\
3 & (0,2) & \textbf{a}_2 \\
4 & (1,1) & \textbf{b}_1 \\
5 & (2,0) & \textbf{c}_0 \\
6 & (0,3) & \textbf{a}_3 \\
7 & (1,2) & \textbf{b}_2 \\
8 & (2,1) & \textbf{c}_1 \\
9 & (3,0) & \textbf{d}_0 \\
10 & (0,4) & \textbf{a}_4 \\
\vdots & &
\end{array}
</math>
We need the [[axiom of countable choice]] to index ''all'' the sets <math>\textbf{a},\textbf{b},\textbf{c},\dots</math> simultaneously.
Line 109 ⟶ 115:
{{math theorem | math_statement = The set of all finite-length [[sequence]]s of natural numbers is countable.}}
This set is the union of the length-1 sequences, the length-2 sequences, the length-3 sequences, and so on, each of which is a countable set (finite Cartesian product).
{{math theorem | math_statement = The set of all finite [[subset]]s of the natural numbers is countable.}}
Line 135 ⟶ 141:
* subsets of ''M'', hence countable,
* but uncountable from the point of view of ''M'',
was seen as paradoxical in the early days of set theory
The minimal standard model includes all the [[algebraic number]]s and all effectively computable [[transcendental number]]s, as well as many other kinds of numbers.
Line 164 ⟶ 170:
==References==
* {{Citation | first1=Tom M. | last1=Apostol | author-link=Tom M. Apostol | title=Multi-Variable Calculus and Linear Algebra with Applications | ___location=New York | publisher=John Wiley + Sons | edition=2nd
* {{citation | first=Carol|last=Avelsgaard|title=Foundations for Advanced Mathematics|year=1990|publisher=Scott, Foresman and Company|isbn=0-673-38152-8}}
* {{Citation | first = Georg | last = Cantor | title = Ein Beitrag zur Mannigfaltigkeitslehre | url = http://www.digizeitschriften.de/dms/img/?PID=GDZPPN002156806 | volume = 1878 | issue = 84 | pages = 242–248 | journal = Journal für die Reine und Angewandte Mathematik | year = 1878 | doi = 10.1515/crelle-1878-18788413| s2cid = 123695365 }}
| |||