Editing Set (mathematics) (section)

==Cardinality==
{{Main|Cardinality|Cardinal number}}

Informally, the cardinality of a set {{math|''S''}}, often denoted {{math|{{mabs|''S''}}}}, is the number of its members.<ref name="Moschovakis1994">{{cite book|author=Yiannis N. Moschovakis|title=Notes on Set Theory|url=https://books.google.com/books?id=ndx0_6VCypcC|year=1994|publisher=Springer Science & Business Media|isbn=978-3-540-94180-4}}</ref> This number is the [[natural number]] {{tmath|n}} when there is a [[bijection]] between the set that is considered and the set {{tmath|\{1,2,\ldots, n \} }} of the {{tmath|n}} first natural numbers. The cardinality of the empty set is {{tmath|0}}.<ref name="Smith2008">{{cite book|author=Karl J. Smith|title=Mathematics: Its Power and Utility|url=https://books.google.com/books?id=-0x2JszrkooC&pg=PA401|date=7 January 2008|publisher=Cengage Learning|isbn=978-0-495-38913-2|page=401}}</ref> A set with the cardinality of a natural number is called a [[finite set]] which is true for both cases. Otherwise, one has an [[infinite set]].<ref>{{Cite book |last=Biggs |first=Norman L. |title=Discrete Mathematics |publisher=Oxford University Press |year=1989 |isbn=0-19-853427-2 |edition=revised |location=New York |pages=39 |language=en |chapter=Functions and counting}}</ref>

The fact that natural numbers measure the cardinality of finite sets is the basis of the concept of natural number, and predates for several thousands years the concept of sets. A large part of [[combinatorics]] is devoted to the computation or estimation of the cardinality of finite sets. 

===Infinite cardinalities===
The cardinality of an infinite set is commonly represented by a [[cardinal number]], exactly as the number of elements of a finite set is represented by a natural numbers. The definition of cardinal numbers is too technical for this article; however, many properties of cardinalities can be dealt without referring to cardinal numbers, as follows.

Two sets {{tmath|S}} and {{tmath|T}} have the same cardinality if there exists a one-to-one correspondence ([[bijection]]) between them. This is denoted <math>|S|=|T|,</math> and would be an [[equivalence relation]] on sets, if a set of all sets would exist.

For example, the natural numbers and the even natural numbers have the same cardinality, since multiplication by two provides such a bijection. Similarly, the [[interval (mathematics)|interval]] {{tmath|(-1, 1)}} and the set of all real numbers have the same cardinality, a bijection being provided by the function {{tmath|x\mapsto \tan(\pi x/2)}}.

Having the same cardinality of a [[proper subset]] is a characteristic property of infinite sets: ''a set is infinite if and only if it has the same cardinality as one of its proper subsets.''
So, by the above example, the natural numbers form an infinite set.<ref name="Lucas1990"/>

Besides equality, there is a natural inequality between cardinalities: a set {{tmath|S}} has a cardinality smaller than or equal to the cardinality of another set {{tmath|T}} if there is an [[injection (mathematics)|injection]] frome {{tmath|S}} to {{tmath|T}}. This is denoted <math>|S|\le |T|.</math>

[[Schröder–Bernstein theorem]] implies that <math>|S|\le |T|</math> and <math>|T|\le |S|</math> imply <math>|S|= |T|.</math> Also, one has <math>|S|\le |T|,</math> if and only if there is a surjection from {{tmath|T}} to {{tmath|S}}. For every two sets {{tmath|S}} and {{tmath|T}}, one has either <math>|S|\le |T|</math> or <math>|T|\le |S|.</math>{{efn|This property is equivalent to the [[axiom of choice]].}} So, inequality of cardinalities is a [[total order]].

The cardinality of the set {{tmath|\N}} of the natural numbers, denoted <math>|\N|=\aleph_0,</math> is the smallest infinite cardinality. This means that if {{tmath|S}} is a set of natural numbers, then either {{tmath|S}} is finite or <math>|S|=|\N|.</math>

Sets with cardinality less than or equal to <math>|\N|=\aleph_0</math> are called ''[[countable set]]s''; these are either finite sets or ''[[countably infinite set]]s'' (sets of cardinality <math>\aleph_0</math>); some authors use "countable" to mean "countably infinite". Sets with cardinality strictly greater than <math>\aleph_0</math> are called ''[[uncountable set]]s''.

[[Cantor's diagonal argument]] shows that, for every set {{tmath|S}}, its power set (the set of its subsets) {{tmath|2^S}} has a greater cardinality:
<math display=block>|S|<\left|2^S \right|.</math>
This implies that there is no greatest cardinality.

===Cardinality of the real numbers===

The cardinality of set of the [[real numbers]] is called the [[cardinality of the continuum]] and denoted {{tmath|\mathfrak c}}. (The term "[[continuum (set theory)|continuum]]" referred to the [[real line]] before the 20th century, when the real line was not commonly viewed as a set of numbers.)

Since, as seen above, the real line {{tmath|\R}} has the same cardinality of an [[open interval]], every subset of {{tmath|\R}} that contains a nonempty [[open interval]] has also the cardinality {{tmath|\mathfrak c}}.

One has 
<math display=block>\mathfrak c = 2^{\aleph_0},</math>
meaning that the cardinality of the real numbers equals the cardinality of the [[power set]] of the natural numbers. In particular,<ref name="Stillwell2013">{{cite book|author=John Stillwell|title=The Real Numbers: An Introduction to Set Theory and Analysis|url=https://books.google.com/books?id=VPe8BAAAQBAJ|date=16 October 2013|publisher=Springer Science & Business Media|isbn=978-3-319-01577-4}}</ref>   
<math display=block>\mathfrak c > \aleph_0.</math>

When published in 1878 by [[Georg Cantor]],<ref name = "Cantor1878" /> this result was so astonishing that it was refused by mathematicians, and several tens years were needed before its common acceptance.

It can be shown that {{tmath|\mathfrak c}} is also the cardinality of the entire [[plane (mathematics)|plane]], and of any [[dimension (mathematics)|finite-dimensional]] [[Euclidean space]].<ref name="Tall2006">{{cite book|author=David Tall|title=Advanced Mathematical Thinking|url=https://books.google.com/books?id=czKqBgAAQBAJ&pg=PA212|date=11 April 2006|publisher=Springer Science & Business Media|isbn=978-0-306-47203-9|pages=211}}</ref>

The [[continuum hypothesis]], was a conjecture formulated by Georg Cantor in 1878 that there is no set with cardinality strictly between {{tmath|\aleph_0}} and {{tmath|\mathfrak c}}.<ref name = "Cantor1878">{{Cite journal
 | first = Georg | last = Cantor
 | title = Ein Beitrag zur Mannigfaltigkeitslehre
 | journal = [[Journal für die Reine und Angewandte Mathematik]]
 | volume = 1878 | issue = 84
 | year = 1878 | pages=242–258
 | url = http://www.digizeitschriften.de/dms/img/?PPN=PPN243919689_0084&DMDID=dmdlog15 | doi=10.1515/crll.1878.84.242| doi-broken-date = 1 November 2024
 }}</ref> In 1963, [[Paul Cohen]] proved that the continuum hypothesis is [[independence (mathematical logic)|independent]] of the [[axiom]]s of [[Zermelo–Fraenkel set theory]] with the [[axiom of choice]].<ref name = "Cohen1963a">
{{Cite journal
 | first = Paul J. | last = Cohen
 | title = The Independence of the Continuum Hypothesis
 | journal = Proceedings of the National Academy of Sciences of the United States of America
 | volume = 50 | issue = 6 | date = December 15, 1963a | pages = 1143–1148
 | doi = 10.1073/pnas.50.6.1143
 | pmid = 16578557
 | pmc = 221287 | jstor=71858
 | bibcode = 1963PNAS...50.1143C| doi-access = free
 }}
</ref> 
This means that if the most widely used [[set theory]] is [[consistency|consistent]] (that is not self-contradictory),{{efn|The consistency of set theory cannot proved from within itself.}} then the same is true for both the set theory with the continuum hypothesis added as a further axiom, and the set theory with the negation of the continuum hypothesis added.