Editing Cardinality (section)

===Equinumerosity===
{{Main|Equinumerosity}}
The intuitive property of two sets having the "same size" is that their objects can be paired one-to-one. For example, in [[Cardinality#top|the image above]], a set of apples is paired with a set of oranges, proving the sets are the same size without referring to these sets' "number of elements" at all. A one-to-one pairing between two sets defines a bijective function between them by mapping each object to its pair. Similarly, a bijection between two sets defines a pairing of their elements by pairing each object with the one it maps to. Therefore, these notions of "pairing" and "bijection" are intuitively equivalent. In fact, it is often the case that functions are defined literally as this set of pairings (see ''{{slink|Function (mathematics)|Formal definition}}''). Thus, the following definition is given:

Two sets <math>A</math> and <math>B</math> are said to have the ''same cardinality'' if their elements can be paired one-to-one. That is, if there exists a function <math>f:A \mapsto B</math> which is bijective. This is written as <math>A \sim B,</math> <math>A \approx B,</math> <math>A \equiv B,</math> and eventually <math> |A| = |B| ,  </math> once <math>|A|</math> has been defined. Alternatively, these sets, <math>A </math> and <math> B,</math> may be said to be ''similar'', [[Equinumerous|''equinumerous'']], or ''equipotent''. For example, the set <math>E = \{0, 2, 4, 6, \text{...}\}</math> of non-negative [[even number]]s has the same cardinality as the set <math>\N = \{0, 1, 2, 3, \text{...}\}</math> of [[natural numbers]], since the function <math>f(n) = 2n</math> is a bijection from {{tmath|\N}} to {{tmath|E}} (see picture above).

For finite sets {{tmath|A}} and {{tmath|B}}, if ''some'' bijection exists from {{tmath|A}} to {{tmath|B}}, then ''each'' injective or surjective function from {{tmath|A}} to {{tmath|B}} is a bijection. This property is no longer true for infinite {{tmath|A}} and {{tmath|B}}. For example, the function {{tmath|g}} from {{tmath|\N}} to {{tmath|E}}, defined by <math>g(n) = 4n</math> is injective, but not surjective since 2, for instance, is not mapped to, and {{tmath|h}} from {{tmath|\N}} to {{tmath|E}}, defined by <math>h(n) = 2 \operatorname{floor}(n/2)</math> (see: ''[[floor function]]'') is surjective, but not injective, since 0 and 1 for instance both map to 0. Neither {{tmath|g}} nor {{tmath|h}} can challenge <math>|E| = |\N|,</math> which was established by the existence of {{tmath|f}}.

==== Equivalence ====
[[File:Example for a composition of two functions.svg|thumb|Example for a composition of two functions.|282x282px]]
A fundamental result necessary in developing a theory of cardinality is showing it is an [[equivalence relation]]. A binary [[Relation (mathematics)|relation]] is an equivalence relation if it satisfies the three basic properties of equality: [[Reflexive relation|reflexivity]], [[Symmetric relation|symmetry]], and [[Transitive relation|transitivity]]. A relation <math>R</math> is reflexive if, for any <math>a,</math> <math>aRa</math> (read: <math>a</math> is <math>R</math>-related to <math>a</math>); symmetric if, for any <math>a</math> and <math>b,</math> if <math>aRb,</math> then <math>bRa</math> (read: if <math>a</math> is related to <math>b,</math> then <math>b</math> is related to <math>a</math>); and transitive if, for any <math>a,</math> <math>b,</math> and <math>c,</math> if <math>aRb</math> and <math>bRc,</math> then <math>aRc.</math>

Given any set <math>A,</math> there is a bijection from <math>A</math> to itself by the [[identity function]], therefore cardinality is reflexive. Given any sets <math>A</math> and <math>B,</math> such that there is a bijection <math>f</math> from <math>A</math> to <math>B,</math> then there is an [[inverse function]] <math>f^{-1}</math> from <math>B</math> to <math>A,</math> which is also bijective, therefore cardinality is symmetric. Finally, given any sets <math>A,</math> <math>B,</math> and <math>C</math> such that there is a bijection <math>f</math>  from <math>A</math> to <math>B,</math> and <math>g</math> from <math>B</math> to <math>C,</math> then their [[Function composition|composition]] <math>g \circ f</math> (read: <math>g</math> after <math>f</math>) is a bijection from <math>A</math> to <math>C,</math> and so cardinality is transitive. Thus, cardinality forms an equivalence relation. This means that cardinality [[Partition of a set|partitions sets]] into [[equivalence classes]], and one may assign a representative to denote this class. This motivates the notion of a [[Cardinality#Cardinal numbers|cardinal number]].

Somewhat more formally, a relation must be a certain set of [[ordered pairs]]. Since there is no [[set of all sets]] in standard set theory (see: ''{{section link||Cantor's paradox}}''), cardinality is not a relation in the usual sense, but a [[Predicate (logic)|predicate]] or a relation over [[Class (set theory)|classes]].