Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Finite set

From Wikipedia, the free encyclopedia
Finite collection of distinct objects

A finite set of polygons in anEuler diagram

Inmathematics, afinite set is a collection of finitely many different things; the things are calledelements ormembers of the set and are typicallymathematical objects, such as numbers, symbols, points in space, lines, othergeometric shapes, variables, or other sets.

Informally, a finite set is a set which one could in principle count and finish counting. For example,{2,4,6,8,10}{\displaystyle \{2,4,6,8,10\}}is a finite set with five elements. The number of elements of a finite set is anatural number (possibly zero) and is called thecardinality (or thecardinal number) of the set. A set that is not a finite set is called aninfinite set. For example, the set{1,2,3,…}{\displaystyle \{1,2,3,\ldots \}}of all positive integers is infinite.

Finite sets are particularly important incombinatorics, the mathematical study ofcounting. Many arguments involving finite sets rely on thepigeonhole principle, which states that there cannot exist aninjectivefunction from a larger finite set to a smaller finite set.

Definition and terminology

[edit]

Thenatural numbers are defined abstractly by thePeano axioms, and can be constructed set-theoretically (for example, by theVon Neumann ordinals). Then, formally, a setS{\displaystyle S} is calledfinite if there exists abijectionf:S→{1,2,⋯,n}{\displaystyle f\colon S\to \{1,2,\cdots ,n\}}for some natural numbern{\displaystyle n}, analogous tocounting its elements. IfS{\displaystyle S} isempty, this isvacuously satisfied forn=0{\displaystyle n=0} with theempty function. The numbern{\displaystyle n} is the set's cardinality, denoted as|S|{\displaystyle |S|}.

If a nonempty set is finite, its elements may be written in asequence:x1,x2,…,xn(xi∈S, 1≤i≤n).{\displaystyle x_{1},x_{2},\ldots ,x_{n}\quad (x_{i}\in S,\ 1\leq i\leq n).}Ifn ≥ 2, then there are multiple such sequences.Incombinatorics, a finite set withn{\displaystyle n} elements is sometimes called ann{\displaystyle n}-set and asubset withk{\displaystyle k} elements is called ak{\displaystyle k}-subset. For example, the set{5,6,7}{\displaystyle \{5,6,7\}} is a 3-set – a finite set with three elements – and{6,7}{\displaystyle \{6,7\}} is a 2-subset of it.

This notation{1,⋯,n}{\displaystyle \{1,\cdots ,n\}} may bedefined recursively as

{1,⋯,n}={∅ (the empty set)ifn=0{1,⋯,n−1}∪{n}ifn≥1{\displaystyle \{1,\cdots ,n\}=\left\{{\begin{array}{lll}\varnothing {\text{ (the empty set)}}&{\text{if}}&n=0\\\{1,\cdots ,n-1\}\cup \{n\}&{\text{if}}&n\geq 1\\\end{array}}\right.}

Basic properties

[edit]

Anyproper subset of a finite setS{\displaystyle S} is finite and has fewer elements thanS itself. As a consequence, there cannot exist abijection between a finite setS and a proper subset ofS. Any set with this property is calledDedekind-finite. Using the standardZFC axioms forset theory, every Dedekind-finite set is also finite, but this implication cannot beproved in ZF (Zermelo–Fraenkel axioms without theaxiom of choice) alone.Theaxiom of countable choice, a weak version of the axiom of choice, is sufficient to prove this equivalence.

Any injective function between two finite sets of the same cardinality is also asurjective function (a surjection). Similarly, any surjection between two finite sets of the same cardinality is also an injection.

Theunion of two finite sets is finite, with|S∪T|≤|S|+|T|.{\displaystyle |S\cup T|\leq |S|+|T|.}

In fact, by theinclusion–exclusion principle:|S∪T|=|S|+|T|−|S∩T|.{\displaystyle |S\cup T|=|S|+|T|-|S\cap T|.}More generally, the union of any finite number of finite sets is finite. TheCartesian product of finite sets is also finite, with:|S×T|=|S|×|T|.{\displaystyle |S\times T|=|S|\times |T|.}Similarly, the Cartesian product of finitely many finite sets is finite. A finite set withn{\displaystyle n} elements has2n{\displaystyle 2^{n}} distinct subsets. That is, thepower set℘(S){\displaystyle \wp (S)} of a finite setS is finite, with cardinality2|S|{\displaystyle 2^{|S|}}.

Any subset of a finite set is finite. The set of values of a function when applied to elements of a finite set is finite.

All finite sets arecountable, but not all countable sets are finite. (Some authors, however, use "countable" to mean "countably infinite", so do not consider finite sets to be countable.)

Thefree semilattice over a finite set is the set of its non-empty subsets, with thejoin operation being given by set union.

Necessary and sufficient conditions for finiteness

[edit]

InZermelo–Fraenkel set theory without the axiom of choice (ZF), the following conditions are all equivalent:[1]

  1. S{\displaystyle S} is a finite set. That is,S{\displaystyle S} can be placed into a one-to-one correspondence with the set of those natural numbers less than some specific natural number.
  2. (Kazimierz Kuratowski)S{\displaystyle S} has all properties which can be proved by mathematical induction beginning with the empty set and adding one new element at a time.
  3. (Paul Stäckel)S{\displaystyle S} can be given atotal ordering which iswell-ordered both forwards and backwards. That is, every non-empty subset ofS{\displaystyle S} has both a least and a greatest element in the subset.
  4. Every one-to-one function from℘(℘(S)){\displaystyle \wp {\bigl (}\wp (S){\bigr )}} into itself isonto. That is, thepowerset of the powerset ofS{\displaystyle S} is Dedekind-finite (see below).[2]
  5. Every surjective function from℘(℘(S)){\displaystyle \wp {\bigl (}\wp (S){\bigr )}} onto itself is one-to-one.
  6. (Alfred Tarski) Every non-empty family of subsets ofS{\displaystyle S} has aminimal element with respect to inclusion.[3] (Equivalently, every non-empty family of subsets ofS{\displaystyle S} has amaximal element with respect to inclusion.)
  7. S{\displaystyle S} can be well-ordered and any two well-orderings on it areorder isomorphic. In other words, the well-orderings onS{\displaystyle S} have exactly oneorder type.

If theaxiom of choice is also assumed (theaxiom of countable choice is sufficient),[4] then the following conditions are all equivalent:

  1. S{\displaystyle S} is a finite set.
  2. (Richard Dedekind) Every one-to-one function fromS{\displaystyle S} into itself is onto. A set with this property is calledDedekind-finite.
  3. Every surjective function fromS{\displaystyle S} onto itself is one-to-one.
  4. S{\displaystyle S} is empty or everypartial ordering ofS{\displaystyle S} contains amaximal element.

Other concepts of finiteness

[edit]

In ZF set theory without theaxiom of choice, the following concepts of finiteness for a setS{\displaystyle S} are distinct. They are arranged in strictly decreasing order of strength, i.e. if a setS{\displaystyle S} meets a criterion in the list then it meets all of the following criteria. In the absence of the axiom of choice the reverse implications are all unprovable, but if the axiom of choice is assumed then all of these concepts are equivalent.[5] (Note that none of these definitions need the set of finiteordinal numbers to be defined first; they are all pure "set-theoretic" definitions in terms of the equality and membership relations, not involving ω.)

The forward implications (from strong to weak) are theorems within ZF. Counter-examples to the reverse implications (from weak to strong) in ZF withurelements are found usingmodel theory.[7]

Most of these finiteness definitions and their names are attributed toTarski 1954 byHoward & Rubin 1998, p. 278. However, definitions I, II, III, IV and V were presented inTarski 1924, pp. 49, 93, together with proofs (or references to proofs) for the forward implications. At that time, model theory was not sufficiently advanced to find the counter-examples.

Each of the properties I-finite thru IV-finite is a notion of smallness in the sense that any subset of a set with such a property will also have the property. This is not true for V-finite thru VII-finite because they may have countably infinite subsets.

Uniqueness of cardinality

[edit]

An important property of finite sets is that, for example, if a set has cardinality 4, then it cannot also have cardinality 5. Intuitively meaning that a set cannot have both exactly 4 elements and exactly 5 elements. However, it is not so obviously proven. The following proof is adapted fromAnalysis I byTerence Tao.[8]

Lemma: If a setX{\displaystyle X} has cardinalityn≥1,{\displaystyle n\geq 1,} andx0∈X,{\displaystyle x_{0}\in X,} then the setX−{x0}{\displaystyle X-\{x_{0}\}} (i.e.X{\displaystyle X} with the elementx0{\displaystyle x_{0}} removed) has cardinalityn−1.{\displaystyle n-1.}

Proof: GivenX{\displaystyle X} as above, sinceX{\displaystyle X} has cardinalityn,{\displaystyle n,} there is a bijectionf{\displaystyle f} fromX{\displaystyle X} to{1,2,…,n}.{\displaystyle \{1,\,2,\,\dots ,\,n\}.} Then, sincex0∈X,{\displaystyle x_{0}\in X,} there must be some numberf(x0){\displaystyle f(x_{0})} in{1,2,…,n}.{\displaystyle \{1,\,2,\,\dots ,\,n\}.} We need to find a bijection fromX−{x0}{\displaystyle X-\{x_{0}\}} to{1,…n−1}{\displaystyle \{1,\dots n-1\}} (which may be empty). Define a functiong{\displaystyle g} such thatg(x)=f(x0){\displaystyle g(x)=f(x_{0})} iff(x)=n{\displaystyle f(x)=n}, andg(x)=f(x){\displaystyle g(x)=f(x)} otherwise. Theng{\displaystyle g} is a bijection fromX−{x0}{\displaystyle X-\{x_{0}\}} to{1,…n−1}.{\displaystyle \{1,\dots n-1\}.}

Theorem: If a setX{\displaystyle X} has cardinalityn,{\displaystyle n,} then it cannot have any other cardinality. That is,X{\displaystyle X} cannot also have cardinalitym≠n.{\displaystyle m\neq n.}

Proof: IfX{\displaystyle X} is empty (has cardinality 0), then there cannot exist a bijection fromX{\displaystyle X} to any nonempty setY,{\displaystyle Y,} since,vacuously, nothing can map toy0∈Y.{\displaystyle y_{0}\in Y.} Assume, byinduction that the result has been proven up to some cardinalityn.{\displaystyle n.} IfX,{\displaystyle X,} has cardinalityn+1,{\displaystyle n+1,} assume it also has cardinalitym.{\displaystyle m.} We want to show thatm=n+1.{\displaystyle m=n+1.} By the lemma above,X−{x0}{\displaystyle X-\{x_{0}\}} must have cardinalityn{\displaystyle n} andm−1.{\displaystyle m-1.} Since, by induction, cardinality is unique for sets with cardinalityn,{\displaystyle n,} it must be thatm−1=n,{\displaystyle m-1=n,} and thusm=n+1.{\displaystyle m=n+1.}

See also

[edit]

Notes

[edit]
  1. ^"Art of Problem Solving",artofproblemsolving.com, retrieved2022-09-07
  2. ^The equivalence of the standard numerical definition of finite sets to the Dedekind-finiteness of the power set of the power set was shown in 1912 byWhitehead & Russell 2009, p. 288. This Whitehead/Russell theorem is described in more modern language byTarski 1924, pp. 73–74.
  3. ^Tarski 1924, pp. 48–58, demonstrated that his definition (which is also known as I-finite) is equivalent to Kuratowski's set-theoretical definition, which he then noted is equivalent to the standard numerical definition via the proof byKuratowski 1920, pp. 130–131.
  4. ^Herrlich, Horst (2006), "Proposition 4.13",Axiom of Choice, Lecture Notes in Mathematics, vol. 1876, Springer, p. 48,doi:10.1007/11601562,ISBN 3-540-30989-6, retrieved18 July 2023
  5. ^This list of 8 finiteness concepts is presented with this numbering scheme by bothHoward & Rubin 1998, pp. 278–280, andLévy 1958, pp. 2–3, although the details of the presentation of the definitions differ in some respects which do not affect the meanings of the concepts.
  6. ^de la Cruz, Dzhafarov & Hall (2006, p. 8)
  7. ^Lévy 1958 found counter-examples to each of the reverse implications in Mostowski models. Lévy attributes most of the results to earlier papers by Mostowski and Lindenbaum.
  8. ^Tao 2022, p. 59.

References

[edit]

External links

[edit]
General
Theorems
(list),
paradoxes
Logics
Traditional
Propositional
Predicate
Set theory
Types
ofsets
Maps,
cardinality
Theories
Formal
systems
(list),
language,
syntax
Example
axiomatic
systems
(list)
Proof theory
Model theory
Computability
theory
Related
Overview
Venn diagram of set intersection
Axioms
Operations
  • Concepts
  • Methods
Set types
Theories
Set theorists
Retrieved from "https://en.wikipedia.org/w/index.php?title=Finite_set&oldid=1335373488"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2026 Movatter.jp