Processing math: 99%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

9.1: Finite Sets

( \newcommand{\kernel}{\mathrm{null}\,}\)

Preview Activity 9.1.1: Equivalent Sets, Part 1
  1. Let A and B be sets and let f be a function from A to B. (f:AB). Carefully complete each of the following using appropriate quantifiers: (If necessary, review the material in Section 6.3.)
    1. The function f is an injection provided that...
    2. The function f is not an injection provided that...
    3. The function f is a surjection provided that...
    4. The function f is not a surjection provided that...
    5. The function f is a bijection provided that...
Definitions: equivalent Sets and one-to-one correspondence

Let A and B be sets.

  • The set A is equivalent to the set B provided that there exists a bijection from the set A onto the set B. In this case, we write AB.
  • When AB, we also say that the set A is in one-to-one correspondence with the set B and that the set A has the same cardinality as the set B.

Note: When A is not equivalent to B, we write AB.

  1. For each of the following, use the definition of equivalent sets to determine if the first set is equivalent to the second set.
    1. A={1,2,3} and B={a,b,c}
    2. C={1,2} and B={a,b,c}
    3. X={1,2,3,...,10} and Y={57,58,59,...,66}
  2. Let D+ be the set of all odd natural numbers. Prove that the function f:ND+ defined by f(x)=2x1, for all xN, is a bijection and hence that ND+.
  3. Let R+ be the set of all positive real numbers. Prove that the function g:RR+ defined by g(x)=ex, for all xR is a bijection and hence, that RR+.
Preview Activity 9.1.2: Equivalent Sets, Part 2
  1. Review Theorem 6.20 in Section 6.4, Theorem 6.26 in Section 6.5, and Exercise (9) in Section 6.5.
  2. Prove each part of the following theorem.
Theorem 9.1.

Let A, B, and C be sets.

  1. For each set A, AA.
  2. For all sets A and B, if AB, then BA.
  3. For all sets A, B and C, if AB and BC, then AC.

Equivalent Sets

In Preview Activity 9.1.1, we introduced the concept of equivalent sets. The motivation for this definition was to have a formal method for determining whether or not two sets “have the same number of elements.” This idea was described in terms of a one-to-one correspondence (a bijection) from one set onto the other set. This idea may seem simple for finite sets, but as we will see, this idea has surprising consequences when we deal with infinite sets. (We will soon provide precise definitions for finite and infinite sets.)

Technical Note

The three properties we proved in Theorem 9.1 in Preview Activity 9.1.2 are very similar to the concepts of reflexive, symmetric, and transitive relations. However, we do not consider equivalence of sets to be an equivalence relation on a set U since an equivalence relation requires an underlying (universal) set U. In this case, our elements would be the sets A, B, and C, and these would then have to subsets of some universal set W (elements of the power set of W). For equivalence of sets, we are not requiring that the sets A, B, and C be subsets of the same universal set. So we do not use the term relation in regards to the equivalence of sets. However, if A and B are sets and AB, then we often say that A and B are equivalent sets.

Progress Check 9.2: Examples of Equivalent Sets

We will use the definition of equivalent sets from in Preview Activity 9.1.1 in all parts of this progress check. It is no longer sufficient to say that two sets are equivalent by simply saying that the two sets have the same number of elements.

  1. Let A={1,2,3,...,99,100} and let B={351,352,353,...,449,450}. Define f:AB by f(x)=x+350, for each x in A. Prove that f is a bijection from the set A to the set B and hence, AB.
  2. Let E be the set of all even integers and let D be the set of all odd integers.
    Prove that ED by proving that F:ED, where F(x)=x+1, for all xE, is a bijection.
  3. Let (0, 1) be the open interval of real numbers between 0 and 1. Similarly, if bR with b>0, let 0,b be the open interval of real numbers between 0 and b.
    Prove that the function f:(0,1)(0,b) by f(x)=bx, for all x(0,1), is a bijection and hence (0,1)(0,b).
Answer

Add texts here. Do not delete this text first.

In Part (3) of Progress Check 9.2, notice that if b>1, then (0, 1) is a proper subset of (0, b) and (0,1)(0,b). Also, in Part (3) of Preview Activity 9.1.1, we proved that the set D of all odd natural numbers is equivalent to N, and we know that D is a proper subset of N.

These results may seem a bit strange, but they are logical consequences of the definition of equivalent sets. Although we have not defined the terms yet, we will see that one thing that will distinguish an infinite set from a finite set is that an infinite set can be equivalent to one of its proper subsets, whereas a finite set cannot be equivalent to one of its proper subsets.

Finite Sets

In Section 5.1, we defined the cardinality of a finite set A, denoted by card(A), to be the number of elements in the set A. Now that we know about functions and bijections, we can define this concept more formally and more rigorously. First, for each kN, we define Nk to be the set of all natural numbers between 1 and k, inclusive. That is,

Nk={1,2,...,k}.

We will use the concept of equivalent sets introduced in Preview Activity 9.1.1 to define a finite set.

Definition: finite and infinite sets
  • A set A is a finite set provided that A= or there exists a natural number k such that ANk.
  • A set is an infinite set provided that it is not a finite set.
  • If ANk, we say that the set A has cardinality k (or cardinal number k), and we write card(A) =k.

In addition, we say that the empty set has cardinality 0 (or cardinal number 0), and we write card()=0.

Notice that by this definition, the empty set is a finite set. In addition, for each kN, the identity function on Nk is a bijection and hence, by definition, the set Nk is a finite set with cardinality k.

Theorem 9.3

Any set equivalent to a finite nonempty set A is a finite set and has the same cardinality as A.

Proof

Suppose that A is a finite nonempty set, B is a set, and AB. Since A is a finite set, there exists a kN such that ANk. We also have assumed that AB and so by part (b) of Theorem 9.1 (in Preview Activity 9.1.2), we can conclude that BA. Since ANk, we can use part (c) of Theorem 9.1 to conclude that BNk. Thus, B is finite and has the same cardinality as A.

It may seem that we have done a lot of work to prove an “obvious” result in Theorem 9.3. The same may be true of the remaining results in this section, which give further results about finite sets. One of the goals is to make sure that the concept of cardinality for a finite set corresponds to our intuitive notion of the number of elements in the set. Another important goal is to lay the groundwork for a more rigorous and mathematical treatment of infinite sets than we have encountered before. Along the way, we will see the mathematical distinction between finite and infinite sets.

The following two lemmas will be used to prove the theorem that states that every subset of a finite set is finite.

Lemma 9.4

If A is a finite set and xA, then A{x} is a finite set and card(A{x})=card(A)+1.

Proof

Let A is a finite set and assume that card(A)=k, where k=0 or kN. Assume xA.

If A=, then card(A)=0 and A{x}={x}, which is equivalent to N1. Thus, A{x} is a finite set with cardinality 1, which equals card(A) + 1.

If A, then ANk, for some kN. This means that card(A)=k, and there exists a bijection f:ANk. We will now use this bijection to define a function g:A{x}Nk+1 and then prove that the function g is a bijection. We define g:A{x}Nk+1 as follows: For each tA{x},

g(t)={f(t) if tAk+1 if t=x.

To prove that g is an injection, we let x1,x2A{x} and assume x1x2.

  • If x1,x2A, then since f is a bijection, f(x1)f(x2), and this implies that g(x1)g(x2).
  • If x1=x, then since x2x1, we conclude that x2x and hence x2A. So g(x1)=k+1, and since f(x2)Nk and g(x2)=f(x2), we can conclude that g(x1)g(x2).

This proves that the function g is an injection. The proof that g is a surjection is Exercise (1). Since g is a bijection, we conclude that A{x}Nk+1, and

card(A{x})=k+1.

Since card(A)=k, we have proved that card(A{x})=card(A)+1.

Lemma 9.5

For each natural number m, if ANm, then A is a finite set and card(A)m.

Proof

We will use a proof using induction on m. For each mN, let P(m) be, "If ANm, then A is finite and card(A)m".

We first prove that P(1) is true. If AN1, then A= or A={1}, both of which are finite and have cardinality less than or equal to the cardinality of N1. This proves that P(1) is true.

For the inductive step, let kN and assume that P(k) is true. That is, assume that if BNk, then B is a finite set and card(B)k. We need to prove that P(k+1) is true.

So assume that A is a subset of Nk+1. Then A{k+1} is a subset of Nk. Since P(k) is true, A{k+1} is a finite set and

card(A{k+1})k.

There are two cases to consider: Either k+1A or k+1A.

If k+1A, then A=A{k+1}. Hence, A is finite and

card(A)k<k+1.

If k+1A, then A=(A{k+1}){k+1}. Hence, by Lemma 9.4, A is a finite set and

card(A)=card(A{k+1} + 1\).

Since card(A{k+1})k, we can conclude that card(A)k+1.

This means that we have proved the inductive step. Hence, by mathematical induction, for each mN, if ANm, then A is finite and card(A)m.

The preceding two lemmas were proved to aid in the proof of the following theorem.

Theorem 9.6.

If S is a finite set and A is a subset of S, then A is a finite set and card(A)card(S).

Proof

Let S be a finite set and assume that A is a subset of S. If A=, then A is a finite set and card(A)card(S). So we assume that A.

Since S is finite, there exists a bijection f:SNk for some kN. In this case, card(S)=k. We need to show that A is equivalent to a finite set. To do this, we define g:Af(A) by

g(x)=f(x) for each xA.

Since f is an injection, we conclude that g is an injection. Now let yf(A). Then there exists an aA such that f(a)=y. But by the definition of g, this means that g(a)=y, and hence g is a surjection. This proves that g is a bijection.

Hence, we have proved that Af(A). Since f(A) is a subset of Nk, we use Lemma 9.5 to conclude that f(A) is finite and card(f(A))k. In addition, by Theorem 9.3, A is a finite set and card(A)=card(f(A)). This proves that A is a finite set and card(A)card(S).

Lemma 9.4 implies that adding one element to a finite set increases its cardinality by 1. It is also true that removing one element from a finite nonempty set reduces the cardinality by 1. The proof of Corollary 9.7 is Exercise (4).

corollary 9.7

If A is a finite set and xA, then A{x} is a finite set and card(A{x})=card(A)1

The next corollary will be used in the next section to provide a mathematical distinction between finite and infinite sets.

Corollary 9.8

A finite set is not equivalent to any of its proper subsets.

Proof

Let B be a finite set and assume that A is a proper subset of B. Since A is a proper subset of B, there exists an element x in BA. This means that A is a subset of B{x}. Hence, by Theorem 9.6,

card(A)card(B{x}).

Also, by Corollary 9.7

card(B{x})=card(B)1.

Hence, we may conclude that card(A)card(B)1 and that

card(A)<card(B).

Theorem 9.3 implies that BA. This proves that a finite set is not equivalent to any of its proper subsets.

The Pigeonhole Principle

The last property of finite sets that we will consider in this section is often called the Pigeonhole Principle. The “pigeonhole” version of this property says, “If m pigeons go into r pigeonholes and m>r, then at least one pigeonhole has more than one pigeon.”

In this situation, we can think of the set of pigeons as being equivalent to a set P with cardinality m and the set of pigeonholes as being equivalent to a set H with cardinality r. We can then define a function f:PH that maps each pigeon to its pigeonhole. The Pigeonhole Principle states that this function is not an injection. (It is not one-to-one since there are at least two pigeons “mapped” to the same pigeonhole.)

Theorem 9.9: The Pigeonhole Principle

Let A and B be finite sets. If card(A)>card(B), then any function f:AB is not an injection.

Proof

Let A and B be finite sets. We will prove the contrapositive o the theorem, which is, if there exists a function f:AB that is an injection, then card(A)card(B).

So assume that f:AB is an injection. As in Theorem 9.6, we define a function g:Af(A) by

g(x)=f(x) for each xA.

As we saw in Theorem 9.6, the function g is a bijection. But then Af(A) and f(A)B. Hence,

card(A)=card(f(x)) and cardf((A))card(B).

Hence, cardf((A))card(B), and this proves the contrapositive. Hence, if card(A)>card(B), then any function f:AB is not an injection.

The Pigeonhole Principle has many applications in the branch of mathematics called “combinatorics.” Some of these will be explored in the exercises.

Exercises 9.1
  1. Prove that the function g:A{x}Nk+1 in Lemma 9.4 is a surjection.
  2. Let A be a subset of some universal set U. Prove that if xU, then A×{x}A.
  3. Let E+ be the set of all even natural numbers. Prove that NE+.
  4. Prove Corollary 9.7.
    If A is a finite set and xA, then A{x} is a finite set and card(A{x})=card(A)1
    Hint: One approch is to use the fact that A=(A{x}){x}.
  5. Let A and B be sets. Prove that

    (a) If A is a finite set, then AB is a finite set.
    (b) If AB is a finite set, then A and B are finite set.
    (c) If AB is an infinite set, then A is an infinite set.
    (d) If A is an infinite set or B is an infinite set, then AB is an infinite set.
  6. There are over 7 million people living in New York City. It is also known that the maximum number of hairs on a human head is less than 200,000. Use the Pigeonhole Principle to prove that there are at least two people in the city of New York with the same number of hairs on their heads.
  7. Prove the following proposiitons:

    (a) If A, B, C, and D are sets with AB and CD, then A×CB×D.
    (b) If A, B, C, and D are sets with AB and CD and if A and C are disjoint and B and D are disjoint, then ACBD.

    Hint: Since AB and CD, there exist bijections f:AB and g:CD. To prove that A×CB×D, prove that h:A×CB×D is a bijection, where h(a,c)=(f(a),g(c)), for all (a,c)A×C.
    If AC= and BD=, then to prove that ACBD, prove that the following function is a bijection: k:ACBD, where
    k(x)={f(x) if tAg(x) if xC.
  8. Let A={a,b,c}.

    (a) Construct a function f:N5A such that f is a surjection.
    (b) Use the function f to construct a function g:AN5 so that fg=IA, where IA is the identity function on the set A. Is the function g an injection? Explain.
  9. This exercise is a generalization of Exercise (8). Let m be a natural number, let A be a set, and assume that f:NmA is a surjection. Define g:ANm asfollows:
    For each xA, g(x)=j, where j is the least natural number in f1({x}).
    Prove that fg=IA, where IA is the identity function on the set A and prove that g is an injection.
  10. Let B be a finite, nonempty set and assume that f:BA is a surjection. Prove that there exists a function h:AB such that fh=IA and h is an injection.
    Hint: Since B is finite, there exists a natural number m such that NmB. This means there exists a bijection k:NmB. Now let h=kg, where g is the function constructed in Exercise (9).

    Explorations and Activities
  11. Using the Pigeonhole Principle. For this activity, we will consider subsets of N30 that contain eight elements.

    (a) One such set is A={3,5,11,17,21,24,26,29}. Notice that
    {3,21,24,26}Aand3+21+24+26=74{3,5,11,26,29}Aand3+5+11+26+29=74
    Use this information to find two disjoint subsets of A whose elements have the same sum.
    (b) Let B={3,5,9,12,15,18,21,24}. Find two disjoint subsets of B whose elements have the same sum. Note: By convention, if T={a}, where aN, then the sum of the elements in T is equal to a.
    (c) Now let C be any subset of N30 that contains eight elements.
    i. How many subsets does C have?
    ii. The sum of the elements of the empty set is 0. What is the maximum sum for any subset of N30 that contains eight elements.? Let M be this maximum sum.
    iii. Now define a function f:P(C)NM so that for each XP, f(X) is equal to the sum of the elements in X.
    Use the Pigeonhole Principle to prove that there exist two subsets of C whose elements have the same sum.
    (d) If the two subsets in part (11(c)iii) are not disjoint, use the idea presented in part (11a) to prove that there exist two disjoint subsets of C whose elements have the same sum.
    (e) Let S be a subset of \mathbb{N}_{99} that contains 10 elements. Use the Pigeonhole Principle to prove that there exist two disjoint subsets of S whose elements have the same sum.
Answer

Add texts here. Do not delete this text first.


This page titled 9.1: Finite Sets is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Ted Sundstrom (ScholarWorks @Grand Valley State University) via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?