Countable set: Difference between revisions

In more technical terms, assuming the [[axiom of countable choice]], a set is ''countable'' if its [[cardinality]] (the number of elements of the set) is not greater than that of the natural numbers. A countable set that is not finite is said to be '''countably infinite'''.

A set is ''[[uncountable]]'' if it is not countable, i.e. its cardinality is greater than <math>\aleph_0</math>.<ref name=Yaqub>{{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>

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, \dots, 100\}</math> presumably denotes the set of [[integer]]s from 1 to 100. Even in this case, however, it is still ''possible'' to list all the elements, because the number of elements in the set is finite. If we number the elements of the set 1, 2, and so on, up to <math>n</math>, this gives us the usual definition of "sets of size <math>n</math>".

[[Georg Cantor]] showed that not all infinite sets are countably infinite. For example, the real numbers cannot be put into one-to-one correspondence with the natural numbers (non-negative integers). The set of real numbers has a greater cardinality than the set of natural numbers and is said to be uncountable.

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.

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 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>

}}}}

{{math theorem | math_statement = <math>\Z</math> (the set of all integers) and <math>\Q</math> (the set of all rational numbers) are countable.{{efn|'''Proof:''' The integers <math>\Z</math> are countable because the function <math>f:\Z\to\N</math> given by <math>f(n)=2^n</math> if <math>n</math> is non-negative and <math>f(n)=3^{-n}</math> if <math>n</math> is negative, is an injective function. The rational numbers <math>\Q</math> are countable because the function <math>g:\Z\times\N\to\Q</math> given by <math>g(m,n)=m/(n+1)</math> is a surjection from the countable set <math>\Z\times\N</math> to the rationals <math>\Q</math>.}}}}

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>i</math> there is a surjective function <math>g_i:\N\to A_i</math> and hence the function

}}}}

{{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.}}}}

{{math theorem | math_statement = The set of all finite-length [[sequence]]s of natural numbers is countable.}}

{{math theorem | math_statement = The set of all finite [[subset]]s of the natural numbers is countable.}}

{{math theorem | math_statement = Let <math>S</math> and <math>T</math> be sets.

# If the function <math>g:S\to T</math> is surjective and <math>S</math> is countable then <math>T</math> is countable.}}

{{math theorem | name = Proposition | math_statement = The set <math>\mathcal{P}(\N)</math> is not countable; i.e. it is [[uncountable]].}}