Subsets

Learning Objectives

After completing this section, you should be able to:

1. Represent subsets and proper subsets symbolically.
2. Compute the number of subsets of a set.
3. Apply concepts of subsets and equivalent sets to finite and infinite sets.

Exponential Notation

So far, we have figured out how many subsets exist in a finite set by listing them. Recall that in , when we listed all the subsets of the three-element set \(L=\{newspaper, magazine, book\}\) we saw that there are eight subsets. In Your Turn 1.11, we discovered that there are four subsets of the two-element subset, \(S=\{heads, tails\}\). A one-element set has two subsets, the empty set and itself. The only subset of the empty set is the empty set itself. But how can we easily figure out the number of subsets in a very large finite set? It turns out that the number of subsets can be found by raising 2 to the number of elements in the set, using exponential notation to represent repeated multiplication. For example, the number of subsets of the set \(L=\{newspaper, magazine, book\}\) is equal to \({2}^{3}=2⋅2⋅2=8\). Exponential notation is used to represent repeated multiplication, \({b}^{n}=b⋅b⋅b⋅\ldots ⋅b\), where \(b\) appears as a factor \(n\) times.

Computing the Number of Subsets of a Set

Try it.

Find the number of subsets of each of the following sets.

1. The set of top five scorers of all time in the NBA: \(S=\{LeBron James, Kareem Abdul-Jabbar, Karl Malone, Kobe Bryant, Michael Jordan\}\text{.}\)
2. The set of the top four bestselling albums of all time: \(A=\{Thriller, Hotel California, The Beatles White Album, Led Zepplin IV\}\).
3. \(R=\{Snap, Crackle, Pop\}\).

Solution

1. \(n(S)=5\). So, the total number of subsets of \(S\ \text{is}\ {2}^{5}=2⋅2⋅2⋅2⋅2=32\).
2. \(n(A)=4\). Therefore, the total number of subsets of \(A\ \text{is}\ {2}^{4}=16\).
3. \(n(R)=3\). So, the total number of subsets of \(R\ \text{is}\ {2}^{3}=8\).

Equivalent Subsets

In the early 17th century, the famous astronomer Galileo Galilei found that the set of natural numbers and the subset of the natural numbers consisting of the set of square numbers, \({n}^{2}\), are equivalent. Upon making this discovery, he conjectured that the concepts of less than, greater than, and equal to did not apply to infinite sets.

Sequences and series are defined as infinite subsets of the set of natural numbers by forming a relationship between the sequence or series in terms of a natural number, \(n\). For example, the set of even numbers can be defined using set builder notation as \(\{a|a=2n\ \text{where}\ n\ \text{is a natural number}\}\). The formula in this case replaces every natural number with two times the number, resulting in the set of even numbers, \(\{2,4,6,\ldots \}\). The set of even numbers is also equivalent to the set of natural numbers.

Subsets

• Every member of a subset of a set is also a member of the set containing it. \(A⊆B\)
• A proper subset of a set does not contain all the members of the set containing it. There is a least one member of set \(B\) that is not a member of set \(A\). \(A⊂B\)
• The number subsets of a finite set \(A\) with \(n(A)\) members is equal to 2 raised to the \(n(A)\) power.
• The empty set is a subset of every set and must be included when listing all the subsets of a set.
• Understand how to create and distinguish between equivalent subsets of finite and infinite sets that are not equal to the original set.

Formulas

The number of subsets of a finite set \(A\) is equal to 2 raised to the power of \(n(A)\), where \(n(A)\) is the number of elements in set \(A\): Number of Subsets of Set \(A={2}^{n(A)}\).

À vous Aucune calculatrice ne tranche celle-ci, mais ses éléments sont calculables. Essayez-en un ci-dessous, ou tapez le vôtre.

⌨ Saisir ✎ Dessine-le

Ton problème de maths

π Résolvez

Exercices (7)

Essayez chacun d'abord sur papier. Révélez la réponse pour vérifier; les vérifiés peuvent être ouverts dans le solveur pour chaque étape.

1. Set \(L\) is a set of reading materials available in a shop at the airport, \(L=\{\text{newspaper, magazine, book}\}\). List all the subsets of set \(L\).

   Résolvez-le étape par étape Indice

   Révèle la réponse

   Step 1: It is best to begin with the set itself, as every set is a subset of itself. In our example, the cardinality of set \(L\) is \(n(L)=3\). There is only one subset of set \(L\) that has the same number of elements of set \(L:\{\text{newspaper},\text{magazine},\text{book}\}\).

   Step 2: Next, list all the proper subsets of the set containing \(n(L)-1\) elements. In this case, \(3-1=2\). There are three subsets that each contain two elements: \(\{\text{newspaper},\text{magazine}\}\), \(\{\text{newspaper},\text{book}\}\), and \(\{\text{magazine},\text{book}\}\).

   Step 3: Continue this process by listing all the proper subsets of the set containing \(n(L)-2\) elements. In this case, \(3-2=1\). There are three subsets that contain one element: \(\{\text{newspaper}\}\), \(\{\text{magazine}\}\), and \(\{\text{book}\}\).

   Step 4: Finally, list the subset containing 0 elements, or the empty set: \(\{\ \}\).

2. Consider the set of common political parties in the United States, \(P=\{Democratic, Green, Libertarian, Republican\}\). Determine if the following sets are proper subsets of \(P\).

   1. \(M=\{Democratic, Republican\}\)
   2. \(G=\{\text{Green}\}\)
   3. \(V=\{Republican, Libertarian, Green, Democratic\}\)
   Résolvez-le étape par étape Indice

   Révèle la réponse

   1. \(M\) is a proper subset of \(P\), written symbolically as \(M⊂P\) because every member of \(M\) is a member of set \(P\), but \(P\) also contains at least one element that is not in \(M\).
   2. \(G\) is a single member proper subset of \(P\), written symbolically as \(G⊂P,\) because Green is a member of set \(P\), but \(P\) also contains other members (such as Democratic) that are not in \(G\).
   3. \(V\) is subset of \(P\) because every member of \(V\) is also a member of \(P\), but it is not a proper subset of \(P\) because there are no members of \(V\) that are not also in set \(P\). We can represent the relationship symbolically as \(V⊆P,\) or more precisely, set \(V\) is equal to set \(P\), \(V=P.\)

3. Consider the subsets of a standard deck of cards: \(S=\{spades, hearts, diamonds, clubs\}\); \(R=\{hearts, diamonds\}\); \(B=\{spades, clubs\}\); and \(C=\{\text{clubs}\}\).

   Express the relationship between the following sets symbolically.

   1. Set \(S\) and set \(B\).
   2. Set \(C\) and set \(B\).
   3. Set \(R\) and \(R\).
   Résolvez-le étape par étape Indice

   Révèle la réponse

   1. \(B⊂S\). \(B\) is a proper subset of set \(S\).
   2. \(C⊂B\). \(C\) is a proper subset of set \(B\).
   3. \(R⊆R\ \text{or}\ R=R\). \(R\) is subset of itself, but not a proper subset of itself because \(R\) is equal to itself.

4. Find the number of subsets of each of the following sets.

   1. The set of top five scorers of all time in the NBA: \(S=\{LeBron James, Kareem Abdul-Jabbar, Karl Malone, Kobe Bryant, Michael Jordan\}\text{.}\)
   2. The set of the top four bestselling albums of all time: \(A=\{Thriller, Hotel California, The Beatles White Album, Led Zepplin IV\}\).
   3. \(R=\{Snap, Crackle, Pop\}\).
   Résolvez-le étape par étape Indice

   Révèle la réponse

   1. \(n(S)=5\). So, the total number of subsets of \(S\ \text{is}\ {2}^{5}=2⋅2⋅2⋅2⋅2=32\).
   2. \(n(A)=4\). Therefore, the total number of subsets of \(A\ \text{is}\ {2}^{4}=16\).
   3. \(n(R)=3\). So, the total number of subsets of \(R\ \text{is}\ {2}^{3}=8\).

5. Using natural numbers, multiples of 3 are given by the sequence \(\{3, 6, 9, \ldots \}\). Write this set using set builder notation by expressing each multiple of 3 using a formula in terms of a natural number, \(n\).

   Résolvez-le étape par étape Indice

   Révèle la réponse

   \(\{m|m=3n\ \text{where}\ n\ is a natural number\}\) or \(\{m|m=3n\ \text{where}\ n\in N\}\). In this example, \(m\) is a multiple of 3 and \(n\) is a natural number. The symbol \(\in\) is read as “is a member or element of.” Because there is a one-to-one correspondence between the set of multiples of 3 and the natural numbers, the set of multiples of 3 is an equivalent subset of the natural numbers.

6. A fast-food restaurant offers a deal where you can select two options from the following set of four menu items for $6: a chicken sandwich, a fish sandwich, a cheeseburger, or 10 chicken nuggets. Javier and his friend Michael are each purchasing lunch using this deal. Create two equivalent, but not equal, subsets that Javier and Michael could choose to have for lunch.

   Résolvez-le étape par étape Indice

   Révèle la réponse

   The possible two-element subsets are: {chicken sandwich, fish sandwich}, {chicken sandwich, cheeseburger}, {chicken sandwich, chicken nuggets}, {fish sandwich, cheeseburger}, {fish sandwich, chicken nuggets}, and {cheeseburger, chicken nuggets}. One possible solution is that Javier picked the set {chicken sandwich, chicken nuggets}, while Michael chose the {cheeseburger, chicken nuggets}. Because Javier and Michael both picked two items, but not exactly the same two items, these sets are equivalent, but not equal.

7. A high school volleyball team at a small school consists of the following players: {Angie, Brenda, Colleen, Estella, Maya, Maria, Penny, Shantelle}. Create two possible equivalent starting line-ups of six players that the coach could select for the next game.

   Résolvez-le étape par étape Indice

   Révèle la réponse

   There are actually 28 possible ways that the coach could choose his starting line-up. Two such equivalent subsets are {Angie, Brenda, Maya, Maria, Penny, Shantelle} and {Angie, Brenda, Colleen, Estella, Maria, Shantelle}. Each subset has six members, but they are not identical, so the two sets are equivalent but not equal.

Conservez votre propre travail

Un compte gratuit ajoute des notes sur chaque leçon, un enregistrement de ce que vous avez terminé, vos problèmes résolus en un seul endroit, et un tuteur que vous pouvez demander sur cette page. Les maths eux-mêmes sont ouverts à tout le monde, signé ou non.

Inscription Connexion

Symboles utilisés ici

Appuyez sur n'importe quel symbole pour la définition complète, une image et ce que signifie chaque lettre.

\neqnot equal
The two sides are different.\inftyinfinity
Not a number: "grows without bound" in limits and intervals.\mathbb{N}number sets
Naturals, integers, rationals, reals, complex numbers.x \in Aelement of, subset
x belongs to A; every element of A is in B.A \cup Bunion, intersection, difference
In either; in both; in A but not B.\emptysetempty set, cardinality
The set with no elements; the number of elements of A.\forallfor all, there exists
Quantifiers: every x; at least one x.\negnot, and, or, implies, iff
Logical connectives.\blacksquare\ \text{or}\ \squareend of proof (halmos)
Marks the point where the statement has been established.

Comment faire: Subsets

1. Represent subsets and proper subsets symbolically.
2. Compute the number of subsets of a set.
3. Apply concepts of subsets and equivalent sets to finite and infinite sets.
4. Set
5. Set
6. Set
7. The set of top five scorers of all time in the NBA:
8. The set of the top four bestselling albums of all time:

Questions posées par les gens

Are some infinities bigger than others?

Yes. The integers and the rationals can be listed; the real numbers cannot (Cantor's diagonal argument), so there are strictly more reals than integers.

What is the difference between a relation and a function?

A relation pairs inputs with outputs freely; a function is a relation in which every input gets exactly one output.

Certaines parties de cette page sont adaptées de OpenStax Contemporary Mathematics (CC BY-NC-SA 4.0). Condensés et réexpliqués ici ; les erreurs sont les nôtres. Comme sa source est autorisée à des fins non commerciales, cette leçon est gratuite, ne vend rien et est partagée avec la même licence.

Plus en Set Theory & Logic

Sets and operationsRelations, functions and equivalenceCardinality and infinityLogic and methods of proof