Subsets, proper subsets and equal sets
Every member of one set is also in another. Is the second set bigger, or are the two really one set described in different words?
Where you are 15 in Sets
Why this exists
Once there are sets, the first thing to ask about two of them is how they sit against each other. The simplest question is whether one lies inside the other: is every member of this set also a member of that one? Every student in the chess club is a student at the school. Every multiple of 6 is a multiple of 3. Every counting number is an integer. The word for this is subset, and it is the relation that the rest of the language of sets is built on.
The word subset is generous, though. The statement “A is a subset of B” is true when A is a small part of B, and it is just as true when A and B are the same set. So on its own it cannot tell you whether B has anything extra. Often the extra is the whole point: the integers have negative numbers that the counting numbers never reach. To say that two sets are nested and not the same, mathematics needs a stricter word, proper subset.
The other end of the question is just as common. Sets are named in many ways. One description lists the members, another gives a rule, and a third builds the set from two others with unions and intersections. Sooner or later two descriptions turn up that look nothing alike, and the question is whether they name one set or two. Listing both and comparing works when the lists are short. It fails for a set such as “the integers that are multiples of both 2 and 3”, which has infinitely many members, so no list is ever finished. What is needed is a test that never lists anything: a way to settle equality by an argument about one typical member. That test is one of the most used moves in mathematics. Two sets are equal exactly when each is a subset of the other.
The three relations stand to each other the way \le, < and = do for numbers. A subset may be the whole set, a proper subset may not, and two sets that are each a subset of the other are equal.
Definition
Subset
Let A and B be sets. A is a subset of B when every member of A is also a member of B. We write
and read it “A is a subset of B” or “A is contained in B”. In symbols, A \subseteq B means that for every object x, if x \in A then x \in B. The same statement turned round is B \supseteq A, read “B is a superset of A” or “B contains A”.
A subset claim says something about every member of A, so it fails as soon as one member fails. We write A \nsubseteq B, “A is not a subset of B”, when there is at least one member of A that is not a member of B. One such member is enough, and it is called a witness.
A few cases show how the definition works.
- \{2, 3\} \subseteq \{1, 2, 3, 4\}, because both 2 and 3 are members of the larger set.
- \{1, 5\} \nsubseteq \{1, 2, 3, 4\}, because 5 is a member of the left set and not the right. The member 1 does belong to both, but that does not help: one failure is enough.
- Every set is a subset of itself: every member of A is a member of A.
- The empty set \varnothing, the set with no members, is a subset of every set. For \varnothing \subseteq A to fail there would have to be a member of \varnothing outside A, and \varnothing has no members at all. A statement of the form “if this, then that” is true when “this” never happens, and we say it is true vacuously.
Being a subset is not the same as being a member. 1 \in \{1, 2\} links a number to a set. \{1\} \subseteq \{1, 2\} links two sets: the only member of \{1\} is 1, which is in \{1, 2\}. But \{1\} \in \{1, 2\} is false, because the members of \{1, 2\} are the numbers 1 and 2, and neither of them is the set \{1\} (elements and membership).
Equal sets
A set is decided by its members and by nothing else. Two sets are equal when they have exactly the same members: every member of the first is a member of the second, and every member of the second is a member of the first. We write A = B, and A \neq B when they differ.
In symbols, A = B means that for every object x,
where \iff is read “if and only if”. Three things follow straight away.
- Order does not matter: \{2, 7\} = \{7, 2\}.
- Repeats do not matter: \{7, 7\} = \{7\}, and \{1, 2, 3, 2, 1\} = \{1, 2, 3\}.
- The description does not matter, only who is in the set. \{1, 2, 3\} and “the positive whole numbers less than 4” are one set.
Compare the two definitions. A \subseteq B is one half of A = B: it says “if x \in A then x \in B”, and equality asks for that and the reverse as well.
Proper subset
A is a proper subset of B when two things are both true:
- every member of A is a member of B, and
- A and B are not the same set.
Since a set is settled completely by its members, the second condition has an equivalent and more useful form: some member of B is not a member of A. Such a member is again called a witness, because it witnesses that B is strictly larger in content.
We write
and read it “A is a proper subset of B”. The same statement turned round is B \supsetneq A, read “B properly contains A”. Plain A \subseteq B is the weaker claim that allows A = B.
Two small cases show the difference. \{1, 2\} \subsetneq \{1, 2, 3\}, because both members of the left set are in the right set and 3 is in the right set but not the left. But \{1, 2, 3\} is not a proper subset of \{3, 2, 1\}: order does not matter, so these are the same set, and nothing in the right one is missing from the left.
Which symbol
Symbols vary between books. Levin writes \subset for a proper subset and \subseteq for “subset or equal”. Hefferon does the same, and points out that some authors use \subset for any kind of subset, proper or not. This lesson writes \subseteq for “subset, possibly equal” and \subsetneq for a proper subset, which can each mean only one thing.
In the first picture of Figure 1, A \subseteq B holds but B \subseteq A does not, because some members of B lie outside A; so A is a proper subset of B. In the second, neither inclusion holds. The third has a single circle, because when A = B there is only one set, with two names, and one outline is all it gets.
Intuition
Inside. Draw B as a region and A as a region. A \subseteq B says that the region A nowhere pokes out of B. To check it, you walk round the members of A only and ask of each one “is it in B?”. The members of B that are not in A are never looked at, which is why a subset claim cannot tell you whether B has extra members.
Equal. Numbers have a version of the next idea. If a \le b and b \le a, then a = b: neither is bigger, so they are the same number. For sets, \subseteq plays the part of \le, and “neither set has a member the other lacks” plays the part of “neither is bigger”.
Here is the picture behind it. Suppose A \subseteq B. Then the members of B fall into two groups, those that are in A and those that are not. In Figure 2 the second group is the shaded ring.
A \subseteq B alone allows the ring to have members. Adding B \subseteq A says that no member of B lies outside A, which is exactly the statement that the ring is empty. With the ring gone, B has nothing that A lacks, and A had nothing that B lacks from the start. The two sets coincide. This also shows why one inclusion is never enough. The first picture of Figure 1 satisfies A \subseteq B perfectly well, and the two sets are not equal.
Proper. If A is the whole of B, the two outlines lie on top of each other, and there is no difference to speak of: A \subseteq B holds and A \subsetneq B does not. If A leaves even a sliver of B uncovered, that sliver is the proper-subset gap, and any point in it is a witness.
So showing that A \subsetneq B is always two jobs. First check that every member of A is in B. Then name one member of B that A does not have. The second job is an existence claim, and the way to settle an existence claim is to produce the thing, which is exactly what a counterexample does to the statement “every member of B is in A”.
The picture says nothing about counting, so it works just as well for sets that never run out.
Each set is a proper subset of the next one out, and the marked numbers are the witnesses that prove it.
Where the comparison with numbers stops. Any two numbers can be compared: one of a < b, a = b, a > b always holds. Two sets cannot always be compared. \{1, 2\} and \{2, 3\} are each missing a member the other has, so neither is a subset of the other, proper or otherwise. That is the middle picture of Figure 1.
Results
Subsets
Every set is a subset of itself. A \subseteq A.
The empty set is inside everything. \varnothing \subseteq A for every set A.
Inclusions chain. If A \subseteq B and B \subseteq C, then A \subseteq C.
A witness shows a subset claim fails. A \nsubseteq B exactly when some x has x \in A and x \notin B.
Between the intersection and the union. For any sets A and B,
Equal sets
Equality of sets. A = B if and only if, for every object x, x \in A \iff x \in B.
Double inclusion. Two sets are equal if and only if each is a subset of the other.
A witness shows difference. To show A \neq B it is enough to find one object that belongs to one of the sets and not to the other.
Equality behaves like equality. A = A; if A = B then B = A; if A = B and B = C then A = C. Each holds because the same holds for “if and only if” about every object x.
A closed loop of inclusions. If a loop of inclusions closes up, such as A \subseteq B \subseteq C \subseteq A, every set on the loop is equal to every other (Exercise 48).
Proper subsets
Witness test. A \subsetneq B exactly when A \subseteq B and there is some x with x \in B and x \notin A.
Mutual inclusion. A \subsetneq B exactly when A \subseteq B and B \nsubseteq A.
Counting. If B is finite and A \subsetneq B, then
Turned round: if A \subseteq B and the two finite sets have the same number of members, then A = B.
Three laws. For any sets A, B, C:
- A \subsetneq A is never true.
- If A \subsetneq B, then B \subsetneq A is false.
- If A \subsetneq B and B \subsetneq C, then A \subsetneq C.
One strict link is enough. If A \subsetneq B and B \subseteq C, then A \subsetneq C. Likewise if A \subseteq B and B \subsetneq C, then A \subsetneq C.
The empty set. \varnothing \subsetneq B exactly when B has at least one member. So the empty set is a proper subset of every set except itself.
Counting all of them. A finite set with n members has 2^n subsets. Of these, 2^n - 1 are proper. When n \ge 1, exactly 2^n - 2 are both nonempty and proper.
Chains. If A_1 \subsetneq A_2 \subsetneq \cdots \subsetneq A_k are subsets of a finite set with n members, then k \le n + 1, and k = n + 1 can be reached.
Counting, Counting all of them and Chains are about finite sets only. For infinite sets all three fail, as the Boundaries section shows. The other results hold for every set.
Why it is true
Subsets
Itself. A \subseteq A asks that every member of A be a member of A, which says nothing at all.
The empty set. \varnothing \subseteq A asks that every member of \varnothing be a member of A. There is no member of \varnothing to test, so the condition can never fail. It is true vacuously.
Chaining. Let x \in A. Since A \subseteq B, x \in B. Since B \subseteq C, x \in C. That holds for every member of A, so A \subseteq C.
The witness. “A \subseteq B” says that every member of A passes the test “is in B”. A statement about every member is false exactly when at least one member fails it, and a member that fails is an x with x \in A and x \notin B.
Between the intersection and the union. If x \in A \cap B, then x is in both sets, so in particular x \in A. If x \in A, then x is in at least one of A and B, which is what x \in A \cup B means.
Every one of these arguments has the same shape: let x be any member of the left set, and show it is in the right set. Nothing special is assumed about x, so the argument covers every member at once, however many there are.
Equal sets
The definition of equality says that for every x, x \in A and x \in B stand or fall together. Double inclusion is that one sentence cut into its two halves.
Suppose first that A = B. If x \in A, then x \in B, since they have the same members. That is A \subseteq B. If x \in B, then x \in A in the same way. That is B \subseteq A.
Now suppose A \subseteq B and B \subseteq A, and let x be any object at all.
- If x \in A, then x \in B, because A \subseteq B.
- If x \in B, then x \in A, because B \subseteq A.
So x \in A exactly when x \in B. Since x was any object, that is the definition of A = B.
The witness rule is the same argument read backwards. If x \in A but x \notin B, the statement “every member of A is in B” has a failure, so A \subseteq B is false, and the sets cannot be equal.
This is the ordinary pattern for proving “P if and only if Q”: prove P \Rightarrow Q, then prove Q \Rightarrow P (proving an if and only if). Here P is “x \in A” and Q is “x \in B”. Notice also that x is never chosen to be special. That is why the argument covers sets of every size, finite or infinite, without listing a thing.
Proper subsets
The witness test. Suppose A \subseteq B and A \ne B. Two sets that are not equal must differ in some member: some object is in one of them and not the other. It cannot be in A and not in B, because A \subseteq B. So it is in B and not in A. Conversely, if A \subseteq B and some x is in B but not in A, the two sets disagree about x, so they are not equal.
Mutual inclusion. By double inclusion, two sets are equal exactly when each is a subset of the other. So, given A \subseteq B, the two sets are equal exactly when B \subseteq A as well, and they are different exactly when B \nsubseteq A.
Counting. Let x be a witness. Split the members of B into those that are in A and those that are not. Every member of A is in B, so the first group is all of A, and since B is finite, so is A, with \lvert A\rvert members. The second group contains x, so it has at least one member. Therefore
The turned-round form is the same statement read backwards: if the counts were equal, A could not be a proper subset, so A = B.
The three laws. The first: A \subsetneq A would need A \ne A, and a set is the same set as itself. The second: if A \subsetneq B there is a witness z \in B with z \notin A, so not every member of B is in A, which means B \nsubseteq A, so B \subsetneq A fails. The third is a short two-column proof.
| Statements | Reasons |
|---|---|
| A \subseteq B, B \subseteq C | parts of the two givens |
| x \in A gives x \in C | first into B, then into C |
| some z in C, not in B | a witness for B \subsetneq C |
| z \notin A | else z \in B |
| A \subsetneq C | A \subseteq C, and z is a witness |
One strict link is enough. The table used only A \subseteq B from the first link, never its strictness, so it already proves the second form. The first form takes its witness from the first link instead, and Example 16 writes it out.
The empty set. \varnothing \subseteq B always, as shown above. By the witness test, \varnothing \subsetneq B then holds exactly when B has a member, since that member is a witness. When B has none, B = \varnothing and the two sets are equal.
Counting all of them. To build a subset of a finite set with n members, go through the members one at a time and decide for each: in or out. Each decision has two outcomes and the decisions do not affect each other, so there are 2 \times 2 \times \cdots \times 2 = 2^n ways. Different choices give different subsets, and every subset arises from some choice. Exactly one choice, every member in, gives the set itself, and that is the only subset that is not proper. That leaves 2^n - 1. The choice “every member out” gives \varnothing. When n \ge 1 it differs from “every member in”, so removing it too leaves 2^n - 2.
Chains. Every set in the chain is a subset of the finite set, so it is finite. Along the chain the sizes then strictly increase, by the counting result, and every size is a whole number from 0 to n. A strictly increasing list drawn from n + 1 possible values has at most n + 1 entries. The bound is reached by starting at \varnothing and adding one member at a time.
Worked examples
Reading a pair of sets
For each pair, say whether the first set is a proper subset of the second, is a subset that is not proper, or is not a subset at all.
(a) \{2, 4\} and \{1, 2, 3, 4\}
(b) \{1, 2, 3\} and \{3, 2, 1, 1\}
(c) \{1, 5\} and \{1, 2, 3, 4\}
(d) \varnothing and \{7\}
(e) \varnothing and \varnothing
Solution(a) Both 2 and 4 are members of the right set, so the left set is a subset. Also 1 is a member of the right set and not of the left, so it is a witness. The left set is a proper subset.
(b) Repeats collapse, so \{3, 2, 1, 1\} is the set \{1, 2, 3\} written in a clumsy way. The two sets are equal. The left set is a subset, but not proper: no witness exists.
(c) The member 5 of the left set is not a member of the right set. So the left set is not a subset at all, and the question of properness never arises.
(d) The empty set has no member that could fail to be in \{7\}, so \varnothing \subseteq \{7\}. And 7 is in \{7\} but not in \varnothing. A proper subset.
(e) \varnothing \subseteq \varnothing is true, but the two sets are the same set. There is no witness. A subset, not proper.
Proving a subset with an arbitrary member
Let A = \{x \in \mathbb{R} : x^2 < 1\} and B = \{x \in \mathbb{R} : x < 1\}, where \mathbb{R} is the set of all real numbers. Show that A \subseteq B and that B \nsubseteq A.
SolutionA has infinitely many members, so the subset half cannot be done by checking them one by one. It is done by taking one member with nothing special about it.
Let x \in A, so x^2 < 1. Since x^2 = \lvert x\rvert^2, this says \lvert x\rvert^2 < 1. Now \lvert x\rvert is never negative, and if it were 1 or more its square would be 1 or more too. So \lvert x\rvert < 1, which means -1 < x < 1, and in particular x < 1. That puts x in B. Since x was any member of A, every member of A is in B: A \subseteq B.
For B \nsubseteq A one witness is enough. Take x = -2. It is a real number with -2 < 1, so -2 \in B. But (-2)^2 = 4, which is not less than 1, so -2 \notin A.
The two halves have different shapes. The inclusion needed an argument about an arbitrary member; the failure needed a single number. Together they show that A \subsetneq B: A is the stretch of numbers strictly between -1 and 1, and B also holds -1 and every number below it.
Members versus subsets
The set T = \{1, \{1\}, \{2, 3\}\} has exactly three members: the number 1, the set \{1\}, and the set \{2, 3\}. Decide which of these are true.
(a) \{1\} \in T
(b) \{1\} \subsetneq T
(c) \{2, 3\} \in T
(d) \{2, 3\} \subsetneq T
(e) \{\{2, 3\}\} \subsetneq T
SolutionTo test a subset claim, take each member of the left set and look for it in the list of members of T. Do not look inside those members.
(a) True. \{1\} is one of the three members of T.
(b) True. The only member of \{1\} is 1, and 1 is a member of T, so \{1\} \subseteq T. And T has a member, \{2, 3\}, that is not in \{1\}. So \{1\} is both a member of T and a proper subset of T, which are two different claims that happen to both hold.
(c) True. \{2, 3\} is one of the three members.
(d) False. The member 2 of \{2, 3\} is not one of the three members of T, since those are 1, \{1\} and \{2, 3\}. So \{2, 3\} is not even a subset of T.
(e) True. The only member of \{\{2, 3\}\} is the set \{2, 3\}, which is a member of T by (c). So it is a subset, and 1 \in T is a witness because 1 is not the set \{2, 3\}.
A subset survives intersection and union
Suppose A \subseteq B, and let C be any set. Show that A \cap C \subseteq B \cap C and A \cup C \subseteq B \cup C. Then decide whether A \subsetneq B forces A \cap C \subsetneq B \cap C.
SolutionA \cap C \subseteq B \cap C. Let x \in A \cap C, so x \in A and x \in C. Because A \subseteq B, the first gives x \in B. So x \in B and x \in C, which is x \in B \cap C.
A \cup C \subseteq B \cup C. Let x \in A \cup C, so x \in A or x \in C. If x \in A, then x \in B because A \subseteq B, and so x \in B \cup C. If x \in C, then x \in B \cup C straight away, since a union holds everything in either part.
Properness does not survive. Take A = \{1\}, B = \{1, 2\} and C = \{1\}. Then A \subsetneq B, with 2 as the witness. But
so the two intersections are equal and neither is a proper subset of the other. Intersecting with C threw away the witness 2. The same happens to unions with C = \{2\}: both A \cup C and B \cup C are \{1, 2\}. An inclusion is carried through, but a witness need not be.
Same members, different descriptions
Which of these sets are equal? Here \mathbb{Z} is the set of all integers.
Equality looks at members only. B lists the members of A in the opposite order, and order does not matter, so A = B. C repeats 4 and 8, and repeats collapse, so C = A too.
For D, the even whole numbers strictly between 0 and 10 are 2, 4, 6, 8, exactly the members of A. So D = A, even though it is written as a rule (this is set-builder notation).
E has a member A lacks: 10 \in E and 10 \notin A. That one witness settles it, so E \neq A. In fact A \subsetneq E, with 10 as the witness.
So A, B, C and D are all the same set, and E is a different one.
A solution set
Show that \{x \in \mathbb{R} : x^2 - 5x + 6 = 0\} = \{2, 3\}.
SolutionCall the left set S and the right set T. Two inclusions are needed.
S \subseteq T. Let x \in S, so x^2 - 5x + 6 = 0. The left side factors as (x - 2)(x - 3) = 0. A product of two numbers is zero only when one of them is zero, so x = 2 or x = 3. Either way x \in T.
T \subseteq S. Both members of T must satisfy the equation. For x = 2: 4 - 10 + 6 = 0. For x = 3: 9 - 15 + 6 = 0. So both are in S.
The first inclusion is where we learn that there are no other solutions. The second is where we learn that these two really are solutions. Each half does a different job, and neither could be skipped.
Reading a chain of steps as two inclusions
Show that \{x \in \mathbb{R} : |x - 1| < 2\} = \{x \in \mathbb{R} : -1 < x < 3\}.
SolutionLet x be a real number. Then
The first step holds because |u| < 2 says that u is less than 2 away from 0, which means -2 < u < 2. The second step adds 1 to all three parts, and adding 1 can be undone by subtracting 1.
Every step is an “if and only if”, so the chain can be read left to right or right to left. Read left to right, it shows every member of the first set is in the second. Read right to left, it shows the reverse. Both inclusions come from one chain, which works only because no step loses information. A single step that goes one way only, such as squaring both sides, would break the chain.
Two conditions at once
For a whole number k, let M_k be the set of integers that are multiples of k, so M_k = \{n \in \mathbb{Z} : n = km \text{ for some integer } m\}. Show that M_6 = M_2 \cap M_3.
SolutionM_6 \subseteq M_2 \cap M_3. Let n \in M_6, so n = 6m for some integer m. Then n = 2(3m), so n \in M_2, and n = 3(2m), so n \in M_3. Being in both, n is in the intersection.
M_2 \cap M_3 \subseteq M_6. Let n be in both sets. Since n \in M_3, write n = 3k for an integer k. Since n \in M_2, n is even. If k were odd, 3k would be odd, because an odd number times an odd number is odd, and then n would not be even. So k is even, k = 2j for an integer j, and n = 3(2j) = 6j. That puts n in M_6.
The second inclusion needed a real idea, about odd and even numbers. The first was a matter of rewriting 6m in two ways.
A set identity
Show that A \cup (A \cap B) = A for any sets A and B.
Figure 5 suggests the answer, but a picture of one arrangement is not a proof. Here is the argument with a member.
A \cup (A \cap B) \subseteq A. Let x be in the union. Then x \in A or x \in A \cap B. If x \in A there is nothing to show. If x \in A \cap B, then x is in both sets, so in particular x \in A.
A \subseteq A \cup (A \cap B). Let x \in A. A union contains everything in either part, so x \in A \cup (A \cap B).
Nothing about A and B was assumed, so the identity holds for all sets.
When only one inclusion holds
Is A \cap (B \cup C) = (A \cap B) \cup C true for all sets A, B and C?
SolutionTest the two inclusions separately.
A \cap (B \cup C) \subseteq (A \cap B) \cup C holds. Let x \in A with x \in B or x \in C. If x \in B, then x \in A \cap B, which is part of the right side. If x \in C, then x is in the right side because C is part of the union.
The reverse fails. Take A = \{1\}, B = \{1\} and C = \{2\}. Then
The object 2 is in the right side and not the left, so the two sides are not equal.
The answer is no. An identity has to hold for every choice of sets, so one choice that breaks it ends the matter. Here the left side is always inside the right side, but not the other way round.
There is only one empty set
Suppose E_1 and E_2 are both sets with no members at all. Show that E_1 = E_2.
SolutionBy double inclusion it is enough to show E_1 \subseteq E_2 and E_2 \subseteq E_1.
E_1 \subseteq E_2 says: for every x, if x \in E_1 then x \in E_2. There is no x with x \in E_1, so the condition is never tested and can never fail. It is true vacuously, exactly as \varnothing \subseteq A was in the definition of a subset.
The same argument with the names swapped gives E_2 \subseteq E_1.
So E_1 = E_2. Any two sets with no members are equal, so there is only one, and that is why it can have a name of its own, the empty set \varnothing, and why “\varnothing \subseteq A for every set A” is a statement about a single set. See the empty set.
Listing and counting
List every proper subset of \{a, b, c\}, and say how many there are and how many of them are nonempty.
Sort the subsets by size. There is one with no members, \varnothing. There are three with one member, \{a\}, \{b\} and \{c\}. There are three with two members, \{a, b\}, \{a, c\} and \{b, c\}. There is one with three members, \{a, b, c\}. That is eight subsets in all, as Figure 6 shows.
The last one is the set itself, the one subset with no witness. Each of the other seven is a subset with a member of \{a, b, c\} missing, and that missing member is its witness. So there are 7 = 2^3 - 1 proper subsets.
Of those seven, one is \varnothing. Removing it leaves 6 = 2^3 - 2 nonempty proper subsets.
Check. A set with 4 members has 2^4 - 1 = 15 proper subsets, and 15 is what listing by size gives: 1 + 4 + 6 + 4, which is every subset except the whole set.
A proper subset given by conditions
Let A be the set of integers x with x^2 \le 4, and let B be the set of integers x with \lvert x\rvert \le 3. In set-builder form (set-builder notation),
Show that A \subsetneq B.
SolutionFirst the subset half. Take any x \in A. Then x^2 \le 4. Because x^2 = \lvert x\rvert^2, this says \lvert x\rvert^2 \le 4, so \lvert x\rvert \le 2. And 2 \le 3, so \lvert x\rvert \le 3, and x \in B. Every member of A is a member of B.
Now a witness. Try x = 3. It is an integer with \lvert 3\rvert \le 3, so 3 \in B. But 3^2 = 9, which is not at most 4, so 3 \notin A. That one integer settles it: A \subsetneq B. (-3 would serve as well.)
Check. Listing the members gives
The 5 members of A all appear in B, which has 7, so \lvert A\rvert < \lvert B\rvert as the counting result requires.
An unknown inside a set
For which numbers k is \{1, 2, k\} \subsetneq \{1, 2, 3\}?
SolutionThere are two conditions, and each removes candidates.
For the subset condition, 1 and 2 are already members of \{1, 2, 3\}, so the only question is whether k is. It must be, so k \in \{1, 2, 3\}.
For the properness condition, the two sets must not be equal. If k = 3 then \{1, 2, k\} = \{1, 2, 3\}, which is equal, so k = 3 is out. If k = 1 the left set is \{1, 2, 1\} = \{1, 2\}, and if k = 2 it is \{1, 2, 2\} = \{1, 2\}. In both cases 3 is a witness.
So k = 1 or k = 2.
Check. k = 3 gives a subset that is not proper, and any other number, say k = 4, gives a set with a member outside \{1, 2, 3\}, which is not a subset. Only 1 and 2 survive both tests.
How small can the smallest set be?
Three sets satisfy A \subsetneq B \subsetneq C, and C has 5 members. Which values can \lvert A\rvert take?
SolutionThe counting result applies to each link, so
Sizes are whole numbers, so \lvert B\rvert \le 4, and then \lvert A\rvert \le \lvert B\rvert - 1 \le 3. Also \lvert A\rvert \ge 0. So \lvert A\rvert is one of 0, 1, 2, 3.
Each of these actually occurs. Take {C = \{1, 2, 3, 4, 5\}} and {B = \{1, 2, 3, 4\}}, and let A be \varnothing, \{1\}, \{1, 2\} or \{1, 2, 3\}. Each is a subset of B with fewer members than B, so each is a proper subset of B, and B \subsetneq C because 5 is a witness.
So \lvert A\rvert \in \{0, 1, 2, 3\}. Each strict link costs at least one member, which is why the largest value is 5 - 2.
One strict link is enough
Suppose A \subsetneq B and B \subseteq C. Show that A \subsetneq C.
SolutionThere are two parts to show, following the definition.
Every member of A is a member of C: if x \in A then x \in B, because A \subseteq B, and then x \in C, because B \subseteq C.
Next a witness. Because A \subsetneq B there is some z \in B with z \notin A. Because B \subseteq C, that same z is in C. So z \in C and z \notin A.
By the witness test, A \subsetneq C.
Notice that B \subseteq C may be an equality, and the argument does not care. The strictness came entirely from the first link and was carried along by the witness. This is why a long chain of \subseteq signs with a single \subsetneq somewhere in it proves a strict result from end to end.
Boundaries
The symbols differ between books. \subset means “proper subset” in some books and “any subset” in others. When the symbol is not defined, read the surrounding text, and in your own writing use \subsetneq or \subseteq, which are never ambiguous.
Member and subset are different relations. \in links an object to a set. \subseteq and \subsetneq link two sets. In Example 3, \{1\} is a member of T and also a proper subset of T, but 2 is a member of the member \{2, 3\} without being a member of T at all. Always ask which relation you are being asked about.
Equality looks at members, not at members of members. \{1, 2\} has two members, the numbers 1 and 2. \{\{1, 2\}\} has one member, the set \{1, 2\}. They are not equal. In the same way \varnothing \neq \{\varnothing\}, because the second set has a member and the first has none.
Both inclusions are needed for equality. A \subseteq B alone does not say A = B, as the first picture in Figure 1 shows. The second inclusion is a separate claim that needs its own argument.
Counting works only for finite sets. If A \subseteq B and B is finite, then A = B exactly when the two sets have the same number of members, and a proper subset has fewer. Equal counts alone prove nothing without the inclusion: \{1, 2\} and \{3, 4\} both have two members. For infinite sets the counting results fail even after the inclusion. The even whole numbers \{0, 2, 4, \dots\} are a proper subset of the whole numbers \{0, 1, 2, \dots\}, since 1 is a witness. Yet the rule n \mapsto 2n pairs every whole number with exactly one even number and leaves no even number unpaired, so in the sense of matching two sets one to one the two sets are the same size. In the same way the multiples of 10 sit inside \mathbb{Z} and n \mapsto 10n matches the integers one to one with them, yet 1 is an integer that is not a multiple of 10. An infinite set has infinitely many proper subsets, so no formula like 2^n - 1 applies, and a chain of proper subsets inside it need not stop: \{1\} \subsetneq \{1, 2\} \subsetneq \{1, 2, 3\} \subsetneq \cdots runs on for ever inside the whole numbers (Exercise 55). For infinite sets an argument about an arbitrary member is the only route to equality. The contrast is taken up in the lesson on infinite sets.
Properness belongs to the sets, not to how they are written. \{1, 2, 3\} and \{3, 2, 1, 1\} are the same set, so neither is a proper subset of the other. Write a set in any way you like, and the answer does not change.
Not every pair of sets is comparable. Two numbers always satisfy one of <, =, >, but two sets may satisfy none of the three set relations. \{1, 2\} and \{2, 3\} are such a pair, drawn in the middle picture of Figure 1.
The empty set is a proper subset here. It is a proper subset of every nonempty set, and it is counted in 2^n - 1. To leave it out as well, a text says “nonempty proper subset”, as in Exercise 22. Nothing is a proper subset of \varnothing, which agrees with 2^0 - 1 = 0.
A complement depends on the universe. The complement A^{c} is taken inside a universal set U that holds every object under discussion. With A = \{1\}, the complement is \{2, 3\} when U = \{1, 2, 3\} and \{2\} when U = \{1, 2\}. So an equation between complements only makes sense once U is fixed. See complements.
Order matters for lists and pairs, not for sets. \{1, 2\} = \{2, 1\}, but the ordered pair (1, 2) is not the same as (2, 1), because in a pair order is part of the object. Equality of sets is a separate notion, and it ignores order.
Where this goes next
Double inclusion is the working method of proving a set identity: to show two expressions built from unions, intersections and complements describe one set, follow an arbitrary member through the definitions in each direction. It is how the rules collected in set identities are established, among them De Morgan’s laws for sets and the distributive laws.
The subsets of a set, collected together, form the power set, a set whose members are sets, and two such sets are equal in exactly the same way. Its proper subsets are all of its subsets but the set itself, so the count 2^n - 1 is the count of all subsets of a set with that one set subtracted. A function drawn as a set of pairs is equal to another function when the two sets of pairs are equal. A Venn diagram can suggest that one set lies inside another or that two expressions describe the same set, and an argument with an arbitrary member is how that suggestion gets proved.
Nested number sets such as those in Figure 4 are the chain of proper subsets in how the number sets nest, each step justified by a witness. And the finite-versus-infinite contrast in the Boundaries section runs through infinite sets and countable sets. A finite set can never be matched one to one with a proper subset of itself, while the whole numbers can, and that difference is one way to see what “infinite” means.
Beyond sets, double inclusion is one case of a general pattern for any claim of the form “if and only if”: see the biconditional and direct proof, which supplies each one-way half.
Exercises
Is it a subset?
- Is \{1, 4, 9\} \subseteq \{n^2 : n \in \mathbb{Z}\}?
- Is \{1, 4, 8\} \subseteq \{n^2 : n \in \mathbb{Z}\}?
- Is \mathbb{Z} \subseteq \mathbb{Q}, where \mathbb{Q} is the set of rational numbers, the numbers \tfrac{p}{q} with p and q integers and q \neq 0?
- Which of \varnothing \subseteq \{\varnothing\} and \varnothing \in \{\varnothing\} are true?
Proper subset or not?
- Is \{2, 4, 6\} a proper subset of \{1, 2, 3, 4, 5, 6\}?
- Is \{1, 2, 3\} a proper subset of \{3, 2, 1\}?
- Is \{a, c\} a proper subset of \{a, b\}?
- Is \varnothing a proper subset of \{0\}?
- Is \varnothing a proper subset of \varnothing?
- Let S = \{1, \{2\}, \{1, 2\}\}. True or false: (a) {\{2\} \in S} (b) {\{2\} \subsetneq S} (c) {\{1\} \subsetneq S} (d) {\{\{2\}\} \subsetneq S} (e) {\{1, 2\} \in S} (f) {\{1, 2\} \subsetneq S}
Same set or different?
For each pair, say whether the two sets are equal. If they are not, name one object that belongs to one and not the other.
- \{a, b, c\} and \{c, a, b\}
- \{1, 2, 2, 3, 3, 3\} and \{1, 2, 3\}
- \{0, 1\} and \{x \in \mathbb{R} : x^2 = x\}
- \{1, 2, 3\} and \{n \in \mathbb{Z} : n > 0,\ n^2 < 10\}
- \{1, 2\} and \{\{1\}, \{2\}\}
- \{x \in \mathbb{R} : x^2 < 0\} and \varnothing
- \varnothing and \{\varnothing\}
Listing and counting
- List every proper subset of \{x, y\}.
- List every proper subset of \{1, 2, 3, 4\} that contains both 1 and 2.
- How many proper subsets does \{1, 2, 3, 4, 5, 6\} have?
- A set has 255 proper subsets. How many members does it have?
- How many nonempty proper subsets does a set with 7 members have?
- A set has exactly one proper subset. How many members does it have?
- What is the largest k for which there are subsets {A_1 \subsetneq A_2 \subsetneq \cdots \subsetneq A_k} of \{1, 2, 3, 4, 5, 6\}?
Proving inclusions and equalities
- Let A = \{x \in \mathbb{R} : x > 2\} and B = \{x \in \mathbb{R} : x^2 > 4\}. Prove that A \subseteq B, and show that B \subseteq A fails.
In Exercises 26 to 31, prove the equality by showing both inclusions, or decide as asked.
- \{x \in \mathbb{R} : x^2 = 9\} = \{-3, 3\}
- \{x \in \mathbb{R} : x^2 - 7x + 10 = 0\} = \{2, 5\}
- \{x \in \mathbb{R} : |x| \le 3\} = \{x \in \mathbb{R} : -3 \le x \le 3\}
- \{x \in \mathbb{R} : 2x + 1 > 7\} = \{x \in \mathbb{R} : x > 3\}
- With M_k as in Example 8, M_{10} = M_2 \cap M_5.
- With M_k as in Example 8, is M_4 = M_2 \cap M_6? Decide, and if not, say which of the two inclusions fail.
Conditions, unknowns and sizes
- For which numbers k is \{1, 3, k\} \subsetneq \{1, 2, 3, 4\}?
- Let A be the set of solutions of {x^2 - 3x + 2 = 0} and B the set of solutions of {(x + 1)(x - 1)(x - 2) = 0}. Show that A \subsetneq B.
- Let M_6 be the set of positive whole numbers that are multiples of 6, and M_3 the set of positive whole numbers that are multiples of 3. Show that M_6 \subsetneq M_3.
- Let M_4 and M_6 be the sets of positive whole numbers that are multiples of 4 and of 6. Is either a proper subset of the other?
- Let A = \{x \in \mathbb{R} : 2 \le x < 5\} and B = \{x \in \mathbb{R} : 2 \le x \le 5\}. Is A \subsetneq B? Is B \subsetneq A?
- A \subsetneq B and B has 9 members. Which values can \lvert A\rvert take?
Set identities and inclusions
In Exercises 38 to 46, A, B and C are any sets inside a universal set U, and A^{c} is the set of members of U not in A.
- Prove A \cap (A \cup B) = A.
- Prove A \cap (B \cup C) = (A \cap B) \cup (A \cap C).
- Prove that if A \subseteq B, then A \cup B = B.
- Prove (A^{c})^{c} = A.
- Is A \cup (B \cap C) = (A \cup B) \cap C true for all sets? Prove it or give an example where it fails, and say whether either inclusion holds in general.
- Prove that A \subseteq B if and only if A \cap B^{c} = \varnothing.
- Prove that if A \subseteq C and B \subseteq C, then A \cup B \subseteq C.
- Prove that if C \subseteq A and C \subseteq B, then C \subseteq A \cap B.
- Prove that if A \subseteq B, then B^{c} \subseteq A^{c}.
Reasoning
- \{1, 2\} \subseteq \{1, 2, 3\} is true. What must be shown in addition to conclude that the two sets are equal, and can it be shown here?
- Suppose A \subseteq B, B \subseteq C and C \subseteq A. Show that A = B = C.
- Prove that A \cup B = A \cap B if and only if A = B.
- Prove that A \subseteq B if and only if A \cap B = A.
- Figure 5 suggests that A \cup (A \cap B) = A. What does a picture of one arrangement leave unsaid, and why does the argument with an arbitrary member not have that gap?
- Explain why no set is a proper subset of itself.
- Prove that if A \subsetneq B, then B \nsubseteq A.
- Prove that if A \subsetneq B and B \subsetneq C, then C has at least two different members that are not in A. Does this need the sets to be finite?
- For each positive whole number k let A_k = \{1, 2, \dots, k\}. Show that {A_1 \subsetneq A_2 \subsetneq A_3 \subsetneq \cdots} is a chain of proper subsets of the whole numbers with no last set. Which hypothesis of the chain result does this chain not meet?
- Show that the even whole numbers are a proper subset of the whole numbers, and that {n \mapsto 2n} matches each whole number with exactly one even number and uses every even number. Then explain why no finite set can be matched one to one with a proper subset of itself.
Answers
- Yes. 1 = 1^2, 4 = 2^2 and 9 = 3^2, so each of the three members is the square of an integer.
- No, and 8 is a witness. The squares of integers are 0, 1, 4, 9, 16, \dots, since (-n)^2 = n^2, and 8 lies strictly between 2^2 = 4 and 3^2 = 9, so no integer has square 8.
- Yes. Every integer n can be written as the fraction \tfrac{n}{1}, so it is rational.
- Both are true. \varnothing \subseteq \{\varnothing\} because the empty set is a subset of every set. \varnothing \in \{\varnothing\} because the only member of \{\varnothing\} is \varnothing itself.
- Yes. Every member of \{2, 4, 6\} is in \{1, 2, 3, 4, 5, 6\}, and 1 is in the larger set but not the smaller, so 1 is a witness.
- No. The two sets have the same members, so they are the same set. The first is a subset of the second but not a proper one.
- No. c is a member of \{a, c\} but not of \{a, b\}, so it is not even a subset.
- Yes. \varnothing has no member that could fail to be in \{0\}, so it is a subset, and 0 is a member of \{0\} that \varnothing lacks.
- No. \varnothing \subseteq \varnothing, but the two are the same set, so there is no witness.
- (a) true, (b) false, (c) true, (d) true, (e) true, (f) false. The members of S are 1, \{2\} and \{1, 2\}. (a) and (e) are listed. (b) fails because the only member of \{2\} is 2, which is not listed. (c) holds because 1 is listed and S has other members. (d) holds because the only member of \{\{2\}\} is \{2\}, which is listed, and 1 is a witness. (f) fails because 2 is a member of \{1, 2\} but not of S.
- Equal. Order does not matter, and both sets have the members a, b and c.
- Equal. Repeats collapse, so the left set has the members 1, 2 and 3 and no others.
- Equal. A real number satisfies x^2 = x when x(x - 1) = 0, so x = 0 or x = 1, and both of those work.
- Equal. 1^2 = 1, 2^2 = 4 and 3^2 = 9 are less than 10, while every larger whole number has a square of at least 16, so the rule picks out exactly 1, 2 and 3.
- Not equal. 1 belongs to the first set but not to the second, whose only members are the sets \{1\} and \{2\}.
- Equal. No real number has a negative square, so the left set has no members, and a set with no members is \varnothing.
- Not equal. \{\varnothing\} has one member, namely \varnothing, and \varnothing has none. So \varnothing belongs to \{\varnothing\} and not to \varnothing.
- \varnothing, \{x\} and \{y\}. The four subsets of \{x, y\} are these three and \{x, y\} itself, which is not proper.
- \{1, 2\}, \{1, 2, 3\} and \{1, 2, 4\}. A subset containing 1 and 2 is settled by whether it also has 3 and whether it also has 4, which gives four sets, and the one with both is \{1, 2, 3, 4\}, not proper.
- 63. A set with 6 members has 2^6 = 64 subsets, and one of them is the set itself, so 2^6 - 1 = 63.
- 8. From 2^n - 1 = 255 we get 2^n = 256 = 2^8, so n = 8.
- 126. There are 2^7 = 128 subsets, and two of them are not wanted, the empty set and the set itself, so 2^7 - 2 = 126.
- 1. From 2^n - 1 = 1 we get 2^n = 2, so n = 1. The set \{a\} has only \varnothing as a proper subset.
- 7. Sizes strictly increase along a chain and lie between 0 and 6, which allows at most 7 sets. The chain that starts at \varnothing and adds the members 1, 2, and so on in turn reaches 7: it is \varnothing, \{1\}, \{1, 2\}, and so on up to \{1, 2, 3, 4, 5, 6\}.
- Let x \in A, so x > 2. Then x is positive, so multiplying x > 2 by x gives x^2 > 2x, and 2x > 4 because x > 2. So x^2 > 4 and x \in B. For the failure, -3 is a witness: (-3)^2 = 9 > 4, so -3 \in B, but -3 is not greater than 2, so -3 \notin A. Together these show A \subsetneq B.
- Let S be the left set. If x \in S, then x^2 - 9 = 0, so (x - 3)(x + 3) = 0, and x = 3 or x = -3. Conversely 3^2 = 9 and (-3)^2 = 9, so both 3 and -3 are in S.
- If x^2 - 7x + 10 = 0, then (x - 2)(x - 5) = 0, so x = 2 or x = 5. Conversely 4 - 14 + 10 = 0 and 25 - 35 + 10 = 0, so 2 and 5 are in the set.
- For real x, |x| \le 3 \iff -3 \le x \le 3, because |x| \le 3 says x is at most 3 away from 0. Every step reverses, so each set lies inside the other.
- For real x, 2x + 1 > 7 \iff 2x > 6 \iff x > 3. Subtracting 1 and dividing by 2 can both be undone, so the chain runs both ways and gives both inclusions.
- M_{10} \subseteq M_2 \cap M_5: if n = 10m, then n = 2(5m) = 5(2m). For the reverse, let n = 5k and let n be even. If k were odd, 5k would be odd, so k is even, k = 2j, and n = 10j, which is in M_{10}.
- Not equal, and neither inclusion holds. 4 \in M_4, but 4 is not a multiple of 6, so 4 \notin M_2 \cap M_6 and M_4 \subseteq M_2 \cap M_6 fails. 6 \in M_2 \cap M_6, but 6 is not a multiple of 4, so M_2 \cap M_6 \subseteq M_4 fails.
- k \in \{1, 2, 3, 4\}. For a subset, k must be one of 1, 2, 3, 4. Then \{1, 3, k\} has at most 3 members while \{1, 2, 3, 4\} has 4, so the two can never be equal and every such k works.
- A = \{1, 2\}, because x^2 - 3x + 2 = (x - 1)(x - 2). B = \{-1, 1, 2\}, since a product is zero only when a factor is. Both members of A are in B, and -1 \in B is not in A, so A \subsetneq B.
- A multiple of 6 has the form 6m = 3(2m), which is a multiple of 3, so M_6 \subseteq M_3. The number 3 is a multiple of 3 but not of 6 (it is smaller than 6 and positive), so 3 is a witness.
- Neither. 4 is in M_4 but not in M_6, so M_4 \nsubseteq M_6. 6 is in M_6 but not in M_4, since 6 is not a whole number of fours, so M_6 \nsubseteq M_4.
- A \subsetneq B is true, and B \subsetneq A is false. Every x with 2 \le x < 5 also has 2 \le x \le 5, so A \subseteq B. And 5 \in B but 5 \notin A, so 5 is a witness. That same 5 shows B \nsubseteq A, so B \subsetneq A fails.
- 0, 1, 2, 3, 4, 5, 6, 7, 8, which is nine values. The counting result gives \lvert A\rvert < 9, and any whole number from 0 to 8 occurs: take A to be any part of B with that many members.
- If x \in A \cap (A \cup B), then x \in A, so the left side is inside A. If x \in A, then x \in A \cup B, and so x \in A \cap (A \cup B). Both inclusions hold.
- Left inside right: let x \in A with x \in B or x \in C. If x \in B then x \in A \cap B, and if x \in C then x \in A \cap C, so x is in the union. Right inside left: if x \in A \cap B then x \in A and x \in B, so x \in B \cup C; if x \in A \cap C the same works with C. Either way x \in A \cap (B \cup C).
- Suppose A \subseteq B. Every member of B is in A \cup B, so B \subseteq A \cup B. For the reverse, let x \in A \cup B. If x \in B, done. If x \in A, then x \in B because A \subseteq B. So A \cup B \subseteq B.
- If x \in A, then x \in U and x \notin A^{c}, so x \in (A^{c})^{c}. Conversely, if x \in (A^{c})^{c}, then x \in U and x \notin A^{c}. A member of U that is not in A^{c} must be in A, since otherwise it would be in A^{c}.
- No. Take A = \{1\} and B = C = \varnothing. The left side is \{1\} \cup \varnothing = \{1\}, and the right side is \{1\} \cap \varnothing = \varnothing, so the inclusion of the left side in the right fails in general. The other inclusion (A \cup B) \cap C \subseteq A \cup (B \cap C) does hold: if x \in C and x \in A or x \in B, then either x \in A, or x \in B \cap C.
- Suppose A \subseteq B. A member of A \cap B^{c} would be in A, hence in B, and also in B^{c}, hence not in B, which is impossible. So A \cap B^{c} has no members: A \cap B^{c} = \varnothing. Conversely, suppose A \cap B^{c} = \varnothing and let x \in A. Then x \in U. If x were not in B it would be in B^{c}, and so in A \cap B^{c}, which has no members. So x \in B, and A \subseteq B.
- Let x \in A \cup B. If x \in A, then x \in C because A \subseteq C. If x \in B, then x \in C because B \subseteq C. Either way x \in C, so A \cup B \subseteq C.
- Let x \in C. Then x \in A because C \subseteq A, and x \in B because C \subseteq B. So x \in A \cap B, and C \subseteq A \cap B.
- Let x \in B^{c}, so x \in U and x \notin B. If x were in A, then x would be in B, because A \subseteq B, and it is not. So x \notin A, and since x \in U, x \in A^{c}. That shows B^{c} \subseteq A^{c}: taking complements turns an inclusion round.
- The other inclusion, \{1, 2, 3\} \subseteq \{1, 2\}, which says every member of the larger set is in the smaller. It cannot be shown, because 3 is in the larger set and not in the smaller. So the sets are not equal.
- A \subseteq B and B \subseteq C give A \subseteq C: if x \in A then x \in B, and so x \in C. Together with C \subseteq A this gives A = C. Also B \subseteq C \subseteq A gives B \subseteq A, and with A \subseteq B this gives A = B. So all three are equal.
- If A = B, then A \cup B = A \cup A = A and A \cap B = A \cap A = A, so the two sides agree. Conversely, suppose A \cup B = A \cap B and let x \in A. Then x \in A \cup B, which is the set A \cap B, so x \in B. That shows A \subseteq B, and the same argument with the names swapped shows B \subseteq A. So A = B by double inclusion.
- Suppose A \subseteq B. Always A \cap B \subseteq A. For the reverse, let x \in A; then x \in B since A \subseteq B, so x \in A \cap B. So A \cap B = A. Conversely, suppose A \cap B = A and let x \in A. Then x \in A \cap B, so x \in B, which shows A \subseteq B.
- The picture shows circles that overlap in a particular way. It does not by itself cover sets that do not overlap at all, or where one sits inside the other, so each such case would need looking at separately. The argument starts from “let x be a member of” one side and assumes nothing about how A and B relate, so it covers every case at once.
- A proper subset must be a different set from the one it sits inside, and no set differs from itself. A \subseteq A is true, but A = A, so there is no member of A outside A to serve as a witness.
- Suppose A \subsetneq B. By the witness test there is a z \in B with z \notin A. Then not every member of B is in A, which says B \nsubseteq A. In particular B \subsetneq A is impossible, since it would need B \subseteq A.
- Since A \subsetneq B there is a y \in B with y \notin A, and y \in C because B \subseteq C. Since B \subsetneq C there is a z \in C with z \notin B, and z \notin A, since otherwise A \subseteq B would put it in B. Finally y \ne z, because y \in B and z \notin B. So y and z are two different members of C outside A. Finiteness was never used, so this holds for all sets. For finite sets it gives \lvert A\rvert \le \lvert C\rvert - 2, as in Example 15.
- Every member of A_k is at most k, so it is at most k + 1 and lies in A_{k + 1}, and k + 1 is a witness, since it is in A_{k + 1} and bigger than every member of A_k. So A_k \subsetneq A_{k + 1}. Every A_k is a set of whole numbers, and after any A_k comes A_{k + 1}, so there is no last set. The chain result assumes the sets lie inside a finite set with n members. The whole numbers are not finite, so there is no n, and no bound on the length.
- Every even whole number is a whole number, and 1 is a whole number that is not even, so it is a witness. The rule n \mapsto 2n gives each n one even number. Different n give different results, since 2n = 2n' forces n = n', so no even number is used twice. Every even number m is 2n for the whole number n = m/2, so none is left out. For a finite set, matching one to one means the two sets have the same number of members. A proper subset of a finite set has fewer members by the counting result, so such a matching is impossible.