Editing Cardinality (section)

=== Countable sets ===
{{Main|Countable set}}
A set is called ''[[countable]]'' if it is [[Finite set|finite]] or has a bijection with the set of [[natural number]]s <math>(\N),</math> in which case it is called ''countably infinite''. The term ''[[denumerable]]'' is also sometimes used for countably infinite sets. For example, the set of all even natural numbers is countable, and therefore has the same cardinality as the whole set of natural numbers, even though it is a [[proper subset]]. Similarly, the set of [[square numbers]] is countable, which was considered paradoxical for hundreds of years before modern set theory (see: ''{{section link||Pre-Cantorian Set theory}}''). However, several other examples have historically been considered surprising or initially unintuitive since the rise of set theory.

{{Multiple image
| direction         = horizontal
| image1            = Diagonal argument.svg
| image2            = Straight counter-clockwise spiral path in square grid.png
| total_width       = 330
| footer            = Two images of a visual depiction of a function from <math>\N</math> to <math>\Q.</math> On the left, a version for the positive rational numbers. On the right, a spiral for all pairs of integers <math>p/q.</math>
}}

The [[rational numbers]] <math>(\Q)</math> are those which can be expressed as the [[quotient]] or [[Fraction (mathematics)|fraction]] {{tmath|\tfrac p q}} of two [[integer]]s. The rational numbers can be shown to be countable by considering the set of fractions as the set of all [[ordered pairs]] of integers, denoted <math>\Z\times\Z,</math> which can be visualized as the set of all [[Integer lattice|integer points]] on a grid. Then, an intuitive function can be described by drawing a line in a repeating pattern, or spiral, which eventually goes through each point in the grid. For example, going through each diagonal on the grid for positive fractions, or through a lattice spiral for all integer pairs. These technically over cover the rationals, since, for example, the rational number <math display="inline">\frac{1}{2}</math> gets mapped to by all the fractions <math display="inline">\frac{2}{4},\, \frac{3}{6}, \, \frac{4}{8}, \, \dots ,</math> as the grid method treats these all as distinct ordered pairs. So this function shows <math>|\Q| \leq |\N|</math> not <math>|\Q| = |\N|.</math> This can be corrected by "skipping over" these numbers in the grid, or by designing a function which does this naturally, but these menthods are usually more complicated.
[[File:Algebraicszoom.png|thumb|273x273px|Algebraic numbers on the [[complex plane]], colored by degree]]
A number is called [[Algebraic number|algebraic]] if it is a solution of some [[polynomial]] equation (with integer [[coefficient]]s). For example, the [[square root of two]] <math>\sqrt2</math> is a solution to <math>x^2 - 2 = 0,</math> and the rational number <math>p/q</math> is the solution to <math>qx - p = 0.</math> Conversely, a number which cannot be the root of any polynomial is called [[Transcendental number|transcendental]]. Two examples include [[Euler's number]] (''{{mvar|e}}'') and [[Pi|pi ({{pi}})]]. In general, proving a number is trancendental is considered to be very difficult, and only a few classes of transcendental numbers are known. However, it can be shown that the set of algebraic numbers is countable (for example, see ''{{slink|Cantor's first set theory article|The proofs}}''). Since the set of algebraic numbers is countable while the real numbers are uncountable (shown in the following section), the transcendental numbers must form the vast majority of real numbers, even though they are individually much harder to identify. That is to say, [[almost all]] real numbers are transcendental.