请输入您要查询的字词:

 

单词 UniquenessOfCardinality
释义

uniqueness of cardinality


Theorem.

The cardinality of a set is unique.

Proof.

We will verify the result for finite setsMathworldPlanetmath only.Suppose A is a finite set with cardinality A=n and A=m. Then there exist bijections f:nA and g:mA. Since g is a bijection, it is invertiblePlanetmathPlanetmathPlanetmath, and g-1:Am is a bijection. Then the compositionMathworldPlanetmathPlanetmath g-1f is a bijection from n to m. We will show by inductionMathworldPlanetmath on n that m=n. In the case n=1 we have n=1={1}, and it must be that m={1} as well, whence m=1=n. Now let n1, and suppose that, for all m, the existence of a bijection f:nm implies n=m. Let m and suppose h:n+1m is a bijection. Let k=h(n+1), and notice that 1km. Since h is onto there exists some jn+1 such that f(j)=m. There are two cases to consider. If j=n+1, then we may define ϕ:nm-1 by ϕ(i)=h(i) for all in, which is clearly a bijection, so by the inductive hypothesis n=m-1, and thus n+1=m. Now suppose jn+1, and define ϕ:nm-1 by

ϕ(i)={h(i)if ijkif i=j.

We first show that ϕ is one-to-one. Let i1,i2n, where i1i2. First consider the case where neither i1 nor i2 is equal to j. Then, since h is one-to-one, we have

ϕ(i1)=h(i1)h(i2)=ϕ(i2).

In the case i1=j, again because h is one-to-one, we have

ϕ(i1)=k=h(n+1)h(i2)=ϕ(i2).

Similarly it can be shown that, if i2=j, ϕ(i1)ϕ(i2), so ϕ is one-to-one. We now show that ϕ is onto. Let lm-1. If l=k, then we may take i=j to have ϕ(i)=ϕ(j)=k=l. If lk, then, because h is onto, there exists some in such that h(i)=l, so g(i)=h(i)=l. Thus g is onto, and our inductive hypothesis again gives n=m-1, hence n+1=m. So by the principle of induction, the result holds for all n. Returning now to our set A and our bijection g-1f:nm, we may conclude that m=n, and consequently that the cardinality of A is unique, as desired.∎

Corollary.

There does not exist a bijection from a finite set to a proper subsetMathworldPlanetmathPlanetmath of itself.

Proof.

Without a loss of generality we may assume the proper subset is nonempty, for if the set is empty then the corollary holds vacuously. So let A be as above with cardinality n, B a proper subset of A with cardinality m<n, and suppose f:AB is a bijection. By hypothesisMathworldPlanetmathPlanetmath there exist bijections g:nA and h:mB; but then h-1(fg) is a bijection from n to m, whence by the preceding result n=m, contrary to assumptionPlanetmathPlanetmath.∎

The corollary is also known more popularly as the pigeonhole principleMathworldPlanetmath.

Titleuniqueness of cardinality
Canonical nameUniquenessOfCardinality
Date of creation2013-03-22 16:26:52
Last modified on2013-03-22 16:26:52
Ownermathcam (2727)
Last modified bymathcam (2727)
Numerical id27
Authormathcam (2727)
Entry typeTheorem
Classificationmsc 03E10
Related topiccardinality
Related topicbijection
Related topicfunction
Related topicset
Related topicsubset
Related topicSubset
Related topicBijection
Related topicSet
Related topicPigeonholePrinciple
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 21:16:23