Math Is Fun Forum

cxc001

Member

Registered: 2010-04-09

Posts: 17

Cardinality Problem: Prove |A| < |N|

Prove cardinality of every finite nonempty set A is less then cardinality of natural number N
|A|<|N|

set A is nonempty finite set
natural number N is denumerable (infinite countable set)

|A|<|N| if there exist a injective (one-to-one) function f: A->N, but NO bijective function, which means NO surjective (onto) function

How to prove it in detail???

Help please!!!

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Cardinality Problem: Prove |A| < |N|

It depends on which how you define “finite set”. The two most commonly used definitions are:

(1) A set is said to be infinite iff there is a bijection from itself to a proper subset of itself. It is said to be finite iff it is not infinite (i.e. there is no bijection from itself to a proper subset of itself).

(2) A set S is said to be finite iff it is empty or there is a bijection from S to the set {1,2,…,n} for some natural number n.

From the first definition, we see that ℕ is infinite (e.g. there is a bijection from itself to the set of all even natural numbers). From the second definition, the fact that ℕ is not finite can be proved by induction on n.

Let’s do the proof of the problem using both definitions.

(1) Using this definition, it is more straightforward to prove the contrapositive statement: If |ℕ| ≤ |A| then A is infinite. |ℕ| ≤ |A| means there is an injective function f from ℕ into A. Since ℕ is infinite, so is f(ℕ). And since A has an infinite subset, it must itself be infinite.

(2) For this, we use contradiction and the axiom of choice. It may be that you can do it without the axiom of choice (ask Ricky ) but since the axiom of choice simplifies life a great deal, I don’t see why I shouldn’t be justified in using it.

The fact that there is an injective function from A into ℕ is a simple consequence of the definition of finiteness. Suppose there is a surjective function f from A onto ℕ. By the axiom of choice, there is a bijection f* from a subset A* of A to ℕ (i.e. define the equivalence relation ~ on A by x ~ y iff f(x) = f(y), then select a unique element from each equivalence class to form A* and take f* to be the restriction of f to A*). As A is finite, so is A*. Let g be a bijection from A* to {1,2,…,n} for some natural number n. Then g∘f*[sup]−1[/sup] is a bijection from ℕ to {1,2,…,n}, implying that ℕ is finite – a contradiction.

Last edited by JaneFairfax (2010-04-11 11:10:59)

cxc001

Member

Registered: 2010-04-09

Posts: 17

Re: Cardinality Problem: Prove |A| < |N|

Thanks a lot JaneFairfax!!!