Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

πŸ”—

Section 9.3 Subsets and equality of sets

πŸ”—
πŸ”—
Often we want to distinguish a collection of certain β€œspecial” elements within a larger set of elements.
subset
πŸ”—
a set whose elements are all members of another set
AβŠ†B
πŸ”—
set A is a subset of or is contained in set B
A Venn diagram demonstrating a subset relationship
πŸ”—
Figure 9.3.1. A Venn diagram demonstrating a subset relationship.
πŸ”—

Warning 9.3.2.

πŸ”—
We also sometimes use the phrase β€œcontained in” to mean an object is an element of a set.
πŸ”—

Example 9.3.4. Basic examples involving familiar sets of numbers.

πŸ”—
  • πŸ”—
    Every natural number is an integer, so NβŠ†Z. To emphasize this, we could write N={m∈Z∣mβ‰₯0}.
  • πŸ”—
    Every integer can be considered to be a rational number, since for every m∈Z we can write m=ab with a=m and b=1. Thus ZβŠ†Q.
  • πŸ”—
    Every rational number can be considered to be a real number if we identify fractions with their decimal expansions via long division. Thus QβŠ†R.
πŸ”—

Example 9.3.5. Candidate-condition notation always defines subsets.

πŸ”—
When we define a set by Candidate-condition notation, we first specify a pool of candidate elements, and then a condition or collection of conditions that those candidates must satisfy in order to actually be included in the set. But then every element in the set we are defining must first be from the set of candidate elements, so our defined set must be a subset of the candidate set.
πŸ”—
For example, in Example 9.3.4, we provided a definition for the set N in candidate-condition form where the pool of candidates is the set Z. This definition makes it explicit that NβŠ†Z.
πŸ”—

Worked Example 9.3.6.

πŸ”—
πŸ”—
Prove that AβŠ†B for
A={3m+1|m∈Z},B={x∈R|sin⁑(Ο€(xβˆ’1)3)=0}.
Solution.
There are an infinite number of elements of A, so we cannot check that all elements of A are also elements of B one-by-one. Instead, we let a variable x represent an arbitrary but unspecified element of A. Since all elements of A have the form 3m+1 for some m∈Z, we have x=3m+1 for some m∈Z. Check the condition for being an element of B by calculating
sin⁑(Ο€(xβˆ’1)3)=sin⁑(Ο€((3m+1)βˆ’1)3)=sin⁑(mΟ€)=0.
Therefore, x∈B. Since the above calculation works for every m∈Z, all elements of A are elements of B.
πŸ”—

A look ahead.

πŸ”—
We will study abstract notions of relation and the transitive property in Chapter 17.
πŸ”—
set equality
πŸ”—
write A=B if both sets consist of precisely the same elements
πŸ”—

Remark 9.3.9.

πŸ”—
πŸ”—
One could combine both applications of the Subset Test described in the Test for Set Equality above into one biconditional: A=B is true if
(βˆ€x)(x∈A⇔x∈B)
πŸ”—
is true. If the logic of x∈Aβ‡’x∈B is easily reversed, then it makes sense to argue x∈A⇔x∈B instead of separately arguing x∈Aβ‡’x∈B and x∈Bβ‡’x∈A. However, in most cases separate arguments of these logical implications is preferred.
πŸ”—

Worked Example 9.3.10.

πŸ”—
Let A and B be as in Worked Example 9.3.6. Prove that A=B.
Solution.

Show BβŠ†A.

Let x represent an arbitrary element of B. This means that
sin⁑(Ο€(xβˆ’1)3)=0.
However, we know from trigonometry that sin⁑θ=0 if and only if ΞΈ is an integer multiple of Ο€; i.e. ΞΈ=mΟ€ for some m∈Z. If we set
Ο€(xβˆ’1)3=mΟ€
and solve for x, we get x=3m+1∈A.
πŸ”—
proper subset
πŸ”—
a set contained in but not equal to another set
Aβ«‹B
πŸ”—
set A is a proper subset of set B
πŸ”—

Note 9.3.11.

πŸ”—
Some people exclude βˆ… from the definition of proper subset.
πŸ”—

Example 9.3.13. Proper subsets of number sets.

πŸ”—
πŸ”—
We already know that NβŠ†ZβŠ†QβŠ†R, but we have
  1. πŸ”—
    Nβ«‹Z, since, for example, βˆ’1∈Z but βˆ’1βˆ‰N;
  2. πŸ”—
    Zβ«‹Q, since, for example, 12∈Q but 12βˆ‰Z; and
  3. πŸ”—
    Qβ«‹R, since, for example, 2∈R but 2βˆ‰Q.
πŸ”—

Remark 9.3.14.

πŸ”—
To show the Aβ‰ B part of Aβ«‹B, you only need to exhibit one example element of B which is not in A; i.e. you need to find a counterexample for the logical implication x∈Bβ‡’x∈A.
<Prev^TopNext>