Every subset of a finite set is finite

  • Thread starter Simpl0S
  • Start date
  • #1
14
0

Homework Statement



Proposition. Every subset of a finite set is finite.

2. Relevant definitions

Definition. Two sets ##X## and ##Y## have the same cardinality iff there is a bijection between ##X## and ##Y##.
A set ##X## is finite iff there is a bijection between ##X## and ##\{1, ... , n\}## for ##n \in \mathbb{N} = \{0, 1, ...\}##. In this case, we write ##\#(X) = n##.

The Attempt at a Solution



I have one question regarding the definition. Does it matter whether one uses the bijection ##f : X \to \{1, ..., n\}## or ##f : \{1, ... , n\} \to X##? I would say no, since I have proven that a function is bijective if and only if its inverse is bijective.
Are there any benefits to using ##f : X \to \{1, ..., n\}## or ##f : \{1, ... , n\} \to X##?

Proof. Induction on ##n##. For ##n = 0## we have ##\#(X) = 0## and hence ##X = \emptyset##. Thus, the only subset ##A \subseteq X## is ##A = \emptyset##. Hence ##A## is finite. This proves the base case.

Suppose inductively that ##X## is finite and ##A \subseteq X## implies ##A## is finite. By definition this means that there is a bijection ##f : \{1, ... , n \} \to X## and there is a bijection ##g : \{1, ... , m \} \to A## such that ##m \leq n##.

We wish to show that the proposition is true for ##n + 1##. That is, if ##\#(X') = n + 1## - in other words if ##X' := X \cup \{x\}## with ##x \notin X## - and ##A' \subseteq X'## implies that ##A'## is finite. This means that there is a bijection ##f' : \{1, ... , n + 1 \} \to X'## and we must find a bijection ##g' : \{1, ... , m' \} \to A'## with ##m' \leq n + 1##.

We can assume that ##A'## is a proper subset ##A' \subset X'## since if ##A' = X'##, then we are done.

Now for the case where ##A' \subset X'## we have ##m' < n + 1##, i.e. ##m = n##. Aren't we done now by the induction hypothesis?

This is all I have for now.
 

Answers and Replies

  • #2
member 587159
No, it doesn't matter for the reason you told. The existence of a bijection ##X \to \{1, \dots, n\}## is equivalent with the existence of a bijection ##\{1, \dots, n\} \to X## (the inverse function indeed does the job, as you greatly explained). So both these definitions are equivalent. There isn't really an advantage.

As for the proposition "Every subset of a finite subset is finite", I really don't see the need for an induction proof (I didn't read your proof attempt).

Here is a proof sketch, and I leave the details for you.

Let ##X## be finite, and ##A \subseteq X##

(1) Show that it is sufficient to find an injection ##A \to \{1, \dots n\}## for some ##n \in \mathbb{N}## (HINT: if you have an injection ##A \to \{1, \dots n\}## for some ##n \in \mathbb{N}##, you also have a bijection ##A \to \{1, \dots k\}## for some ##k \in \mathbb{N}##. Can you see the obvious bijection?)

(2) By assumption, there exist ##m \in \mathbb{N}## and a bijection ##f: X \to \{1, \dots, m\}##. Consider the map ##g: A \to X: a \mapsto a##. What can you say about ##f \circ g?##
 
Last edited by a moderator:

Related Threads on Every subset of a finite set is finite

Replies
17
Views
6K
Replies
16
Views
2K
Replies
3
Views
401
Replies
4
Views
1K
Replies
4
Views
5K
Replies
3
Views
5K
Replies
6
Views
535
  • Last Post
Replies
5
Views
3K
Replies
0
Views
2K
Top