Every subset of a finite set is finite

In summary: It follows that ##f \circ g## is an injection ##A \to \{1, \dots, m\}##, which concludes the proof. In summary, every subset of a finite set is finite.
  • #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.
 
Physics news on Phys.org
  • #2
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:

1. What is the definition of a finite set?

A finite set is a set that has a limited or definite number of elements. This means that the set can be counted or enumerated and there is an end to the number of elements in the set.

2. How is the concept of a finite set related to subsets?

A subset is a set that contains elements from a larger set. In the case of a finite set, all subsets of that set will also have a limited or definite number of elements, making them finite as well.

3. Why is it important to understand that every subset of a finite set is finite?

This concept is important in many areas of mathematics, such as set theory, combinatorics, and graph theory. It helps to establish the properties and limitations of finite sets and their subsets.

4. Can there be an infinite subset of a finite set?

No, by definition, a finite set cannot have an infinite subset. All subsets of a finite set must also be finite.

5. Are there any exceptions to the rule that every subset of a finite set is finite?

No, this rule holds true for all finite sets, regardless of their size or the number of elements in the set. It is a fundamental property of finite sets.

Suggested for: Every subset of a finite set is finite

Back
Top