# Cardinality

[https://math.libretexts.org/Bookshelves/Combinatorics\_and\_Discrete\_Mathematics/Supplemental\_Modules\_for\_Discrete\_Math/Additional\_Discrete\_Topics\_(Dean)/Infinite\_Sets\_and\_Cardinality](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Supplemental_Modules_for_Discrete_Math/Additional_Discrete_Topics_\(Dean\)/Infinite_Sets_and_Cardinality)

[https://primes.utm.edu/glossary/page.php?sort=Infinite](https://primes.utm.edu/glossary/page.php?sort=Infinite)

[https://www.britannica.com/science/set-theory/Operations-on-sets](https://www.britannica.com/science/set-theory/Operations-on-sets)

[https://www.probabilitycourse.com/chapter1/1\_2\_2\_set\_operations.php](https://www.probabilitycourse.com/chapter1/1_2_2_set_operations.php)

[https://www.cs.sfu.ca/\~ggbaker/zju/math/set-oper.html](https://www.cs.sfu.ca/~ggbaker/zju/math/set-oper.html)

* **Cardinality** is the number of elements in a set
* finite sets: cardinality is denoted by a normal cardinal number
* infinite sets: cardinality is denoted a transcendetal cardinal number
* instead of a single infinity, set theory has discovered infinity of infinities, through the work of Georg Cantor, forever linking set theory as the field of mathematics that deals with infinities.
* to obtain the cardinality of an infinite set S, we search for an injective function, i.e. a 1-to-1 mapping between S and ℕ; if we find such correspondance, then the infinity of S is enumerable (countably infinite set).

Finite sets

* cardinality of a finite set is established by enumerating its elements
* enumerating a set means putting it in a 1-to-1 correspondance with ℕ
* this often means finding a suitable bijective function
* to count means to mentally label (enumerate) elements

Infinite sets

* with infinite sets, notion of cardinality goes beyond some concrete quantity, towards the notion of the size of the particular _kind of infinity_ of a set.
* it is more about finding an appropriate bijective function for enumeration
* **Equinumerousity** is a property that two sets with equal cardinality have
* there are 2 kinds of infinity: countable and uncountable
* **Countable set** can be put in a bijection with ℕ
* **Uncountable set** cannot be put in a bijection with ℕ
* the smallest infinity is that of natural numbers, denoted by ℵ₀ (read "aleph naught"); this number is a cardinal number, $$\mathfrak{c}$$
* Two sets are equal iff they contain the same elements.
* Two sets are equivalent iff they have the same cardinality.
* Singleton or unit set is a set containing a single element.
* Unordered pair is a set containing two elements.
* Cardinality of a power set of a set $$X$$ is $$2^{|X|}$$.
* Cardinality of a power set of an empty set is: $$\mathcal{P}(\varnothing)=1$$.
* Cardinality of a set $$X$$ is equivalent to $$\mathbb{N}$$ if there is a bijective function, $$f:\mathbb{N} \mapsto X$$, mapping elements in $$\mathbb{N}$$ to the elements in $$X$$

## Cardinalities

| $$n$$ | $$\mathcal{P}: 2^n$$ | $$\mathcal{C}: n^2$$ | $$\mathcal{R}: 2^{(n^2)}$$ |
| ----- | -------------------- | -------------------- | -------------------------- |
| 0     | $$2^0$$ = 1          | $$0^2$$ = 0          | $$2^0$$ = 1                |
| 1     | $$2^1$$ = 2          | $$1^2$$ = 1          | $$2^1$$ = 2                |
| 2     | $$2^2$$ = 4          | $$2^2$$ = 4          | $$2^4$$ = 16               |
| 3     | $$2^3$$ = 8          | $$3^2$$ = 9          | $$2^9$$ = 512              |
| 4     | $$2^4$$ = 16         | $$4^2$$ = 16         | $$2^{16}$$ = 65,536        |
| 5     | $$2^5$$ = 32         | $$5^2$$ = 25         | $$2^{25}$$                 |
| 6     | $$2^6$$ = 64         | $$6^2$$ = 36         | $$2^{36}$$                 |
| 7     | $$2^7$$ = 128        | $$7^2$$ = 49         | $$2^{49}$$                 |
| 8     | $$2^8$$ = 256        | $$8^2$$ = 64         | $$2^{64}$$                 |
| 9     | $$2^9$$ = 512        | $$9^2$$ = 81         | $$2^{81}$$                 |

This table shows:

* the first column shows the cardinality of a n-element set.
* the second column shows the cardinality of the powersets of an n-element set&#x20;
* the third column shows the cardinality of the Cartesian product of an n-element set with itself.
* the fourth column shows the number of ditinct relations of an n-element set

## Cardinality

Cardinality of a set S, denoted by |S|, is the number of elements of the set. The number is also referred as the cardinal number. If a set has an infinite number of elements, its cardinality is ∞. |{1,2,3,4,5,…}| = ∞

|X|=|Y| denotes two sets X and Y having same cardinality. It occurs when the number of elements in X is exactly equal to the number of elements in Y. In this case, there exists a **bijective** function `f` from X to Y.

|X|≤|Y| denotes that set X's cardinality is less than or equal to set Y's cardinality. It occurs when number of elements in X is less than or equal to that of Y. Here, there exists an **injective** function 'f' from X to Y.

|X|<|Y| denotes that set X's cardinality is less than set Y's cardinality. It occurs when number of elements in X is less than that of Y. Here, the function 'f' from X to Y is _injective function but not bijective_.

If |X|≤|Y| and |X|≥|Y| then |X|=|Y|. The sets X and Y are commonly referred as _equivalent_ sets.
