Concept
Countable set
Overview
A mathematical set is countable if either it is finite or it can be put in one to one correspondence with the set of natural numbers. Equivalently, a set is countable if there exists an injective function from it into the natural numbers; this means that each element in the set may be associated to a unique natural number, or that the elements of the set can be counted one at a time, although the counting may never finish due to an infinite number of elements.
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; for example the set of all natural numbers
N
{\displaystyle \mathbb {N} }
or all rational numbers
Q
{\displaystyle \mathbb {Q} }
.
The concept is attributed to Georg Cantor, who proved the existence of uncountable sets, that is, sets that are not countable; for example the set of the real numbers
R
{\displaystyle \mathbb {R} }
.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
The notion of continuity depends upon that of _order_, since continuity is merely a particular type of order. Mathematics has, in modern times, brought order into greater and greater prominence. In former days, it was supposed (and philosophers are still apt to suppose) that quantity was the fundamental notion of mathematics. But nowadays, quantity is banished altogether, except from one little corner of Geometry…
Bertrand Russell, Mysticism and Logic and Other Essays
States what Countable set is.
Thus there arises a classification of modes of formation, or in the language commonly used by mathematicians, a classification of Functions. Any number, considered as formed from any other number, is called a function of it; and there are as many kinds of functions as there are modes of formation. The simple functions are by no means numerous, most functions being formed by the combination of several of the…
John Stuart Mill, A System of Logic, Ratiocinative and Inductive
States what Countable set is.
Propositions, therefore, concerning numbers, have the remarkable peculiarity that they are propositions concerning all things whatever; all objects, all existences of every kind, known to our experience. All things possess quantity; consist of parts which can be numbered; and in that character possess all the properties which are called properties of numbers. That half of four is two, must be true whatever the word…
John Stuart Mill, A System of Logic
States what Countable set is.
Related ideas
- Finite set
- Georg Cantor
- Tuple
- Skolem's paradox
- Infinite set
- Integer
- Function (mathematics)
- Mathematical logic
- Rational number
- Real number
- Natural number
- Ordered pair
- Reductio ad absurdum
- Power set
- Recursion
- Set (mathematics)
- Total order
- Uncountable set
- Cantor's theorem
- Löwenheim–Skolem theorem
- Bijection
- Union (set theory)
- Cantor's diagonal argument
- Map (mathematics)
Place in the tradition
Part of First-order logic.