Finite: Difference between revisions
OfficialURL (talk | contribs) No edit summary |
No edit summary |
||
| (4 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
A [[set]] is said to be '''finite''' if its elements can be labeled with the numbers from \(1\) to \(n\), for some natural number \(n\). A set that isn't finite is said to be [[infinite]]. |
A [[set]] is said to be '''finite''' if its elements can be labeled with the numbers from \(1\) to \(n\), for some natural number \(n\). A set that isn't finite is said to be [[infinite]]. |
||
More precisely, a set \(S\) is finite when there exists \(n\in \mathbb N\) and a [https://en.wikipedia.org/wiki/Bijection bijective function] \(f:S\to\{<n\}\), where \(\{<n\}\) denotes the set of naturals less than \(n\). The unique natural for which this holds is called its [[cardinality]], although this concept may be defined in greater generality. Perhaps the simplest finite set is the [[empty set]], whose cardinality is [[0]]. Any singleton set \(\{a\}\) is finite and has cardinality [[1]]. |
More precisely, a set \(S\) is finite when there exists \(n\in \mathbb N\) and a [https://en.wikipedia.org/wiki/Bijection bijective function] (a one-to-one correspondence) \(f:S\to\{<n\}\), where \(\{<n\}\) denotes the set of naturals less than \(n\). In terms of von Neumann ordinals, this is equivalent to there being some well-ordering on the set whose order-type is finite. The unique natural for which this holds is called its [[cardinality]], although this concept may be defined in greater generality. Perhaps the simplest finite set is the [[empty set]] \(\varnothing\), whose cardinality is [[0]]. Any singleton set \(\{a\}\) is finite and has cardinality [[1]]. |
||
An [[ordinal]] is called '''finite''' when it's the [[order type]] of a finite [[well-ordered set]]. It can be proven that these ordinals correspond precisely to the order types of the sets \(\{<n\}\). This allows for the identification of finite ordinals with natural numbers. |
An [[ordinal]] is called '''finite''' when it's the [[order type]] of a finite [[well-ordered set]]. It can be proven that these ordinals correspond precisely to the order types of the sets \(\{<n\}\). This allows for the identification of finite ordinals with natural numbers. |
||
Likewise, a [[cardinal]] is called '''finite''' when it's the cardinality of a finite set. Once again, finite cardinals can be identified with the natural numbers. |
|||
== Dedekind finiteness == |
|||
Dedekind has the following definition of finiteness that does not make reference to \(\mathbb N\): |
|||
: \(X\) is finite if there is no proper subset of \(X\) that has the same cardinality as \(X\). |
|||
Without the axiom of choice it cannot be proven that this is equivalent to the \(\mathbb N\)-based definition of finiteness.{{citation needed}} |
|||
== Properties == |
== Properties == |
||
| Line 9: | Line 16: | ||
* The powerset of a finite set is finite. |
* The powerset of a finite set is finite. |
||
* The union of two finite sets, and thus of finitely many finite sets, is finite. |
* The union of two finite sets, and thus of finitely many finite sets, is finite. |
||
* The [[ordinal sum|sum]], [[ordinal product|product]], or [[ordinal exponentiation|exponentiation]] of two finite ordinals is finite. |
|||
* The [[cardinal sum|sum]], [[cardinal product|product]], or [[cardinal exponentiation|exponentiation]] of two finite cardinals is finite. |
|||
== External links == |
== External links == |
||
| ⚫ | |||
* {{Mathworld|Finite Set|author=Barile, Margherita}} |
* {{Mathworld|Finite Set|author=Barile, Margherita}} |
||
| ⚫ | |||
Latest revision as of 23:37, 7 September 2023
A set is said to be finite if its elements can be labeled with the numbers from \(1\) to \(n\), for some natural number \(n\). A set that isn't finite is said to be infinite.
More precisely, a set \(S\) is finite when there exists \(n\in \mathbb N\) and a bijective function (a one-to-one correspondence) \(f:S\to\{<n\}\), where \(\{<n\}\) denotes the set of naturals less than \(n\). In terms of von Neumann ordinals, this is equivalent to there being some well-ordering on the set whose order-type is finite. The unique natural for which this holds is called its cardinality, although this concept may be defined in greater generality. Perhaps the simplest finite set is the empty set \(\varnothing\), whose cardinality is 0. Any singleton set \(\{a\}\) is finite and has cardinality 1.
An ordinal is called finite when it's the order type of a finite well-ordered set. It can be proven that these ordinals correspond precisely to the order types of the sets \(\{<n\}\). This allows for the identification of finite ordinals with natural numbers.
Likewise, a cardinal is called finite when it's the cardinality of a finite set. Once again, finite cardinals can be identified with the natural numbers.
Dedekind finiteness[edit | edit source]
Dedekind has the following definition of finiteness that does not make reference to \(\mathbb N\):
- \(X\) is finite if there is no proper subset of \(X\) that has the same cardinality as \(X\).
Without the axiom of choice it cannot be proven that this is equivalent to the \(\mathbb N\)-based definition of finiteness.[Citation needed]
Properties[edit | edit source]
- Any subset of a finite set is finite. In particular, the intersection of a finite set and any other set is finite.
- The powerset of a finite set is finite.
- The union of two finite sets, and thus of finitely many finite sets, is finite.
- The sum, product, or exponentiation of two finite ordinals is finite.
- The sum, product, or exponentiation of two finite cardinals is finite.
External links[edit | edit source]
- Barile, Margherita. "Finite Set" at MathWorld.
- Wikipedia Contributors. "Finite set".