Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Finite set
Summary
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
is a finite set with five elements. The number of elements of a finite set is a natural number (possibly zero) and is called the cardinality (or the cardinal number) of the set. A set that is not a finite set is called an infinite set. For example, the set of all positive integers is infinite:
Finite sets are particularly important in combinatorics, the mathematical study of counting. Many arguments involving finite sets rely on the pigeonhole principle, which states that there cannot exist an injective function from a larger finite set to a smaller finite set.
Formally, a set S is called finite if there exists a bijection
for some natural number n. The number n is the set's cardinality, denoted as S. The empty set or ∅ is considered finite, with cardinality zero.
If a set is finite, its elements may be written — in many ways — in a sequence:
In combinatorics, a finite set with n elements is sometimes called an n-set and a subset with k elements is called a k-subset. For example, the set is a 3-set – a finite set with three elements – and is a 2-subset of it.
(Those familiar with the definition of the natural numbers themselves as conventional in set theory, the so-called von Neumann construction, may prefer to use the existence of the bijection , which is equivalent.)
Any proper subset of a finite set S is finite and has fewer elements than S itself. As a consequence, there cannot exist a bijection between a finite set S and a proper subset of S. Any set with this property is called Dedekind-finite. Using the standard ZFC axioms for set theory, every Dedekind-finite set is also finite, but this implication cannot be proved in ZF (Zermelo–Fraenkel axioms without the axiom of choice) alone.
The axiom of countable choice, a weak version of the axiom of choice, is sufficient to prove this equivalence.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.