2.1
Basic Operations of Sets

2.1.1 Sets and Membership

Sets are (arguably) the most fundamental of all mathematical objects. Quite simply, a set is

a collection things, the things belonging to the set are called members

or elements of the set.1 Other synonyms for the word “set,” are collection, class, family, and ensemble. We refer to a collection of people, family of functions, an ensemble of voters, and so on. We even consider sets whose members themselves are sets, such as the set of classes at a university, where each class consists of students. In mathematics, we might consider the set of all open intervals on the real line or the set of solutions of an equation.

If a set does not contain too many members, we can specify the set by simply writing down the members of the inside a pair of brackets, such as {3, 7, 31}, which denotes the first three Mersenne primes.2 Sometimes sets contain an infinite number of elements, like the natural numbers, where we might specify them by {1, 2, 3, …}, where the three dots after the 3 signify “and so on.”

We generally denote sets by capital letters such as A, B, C, … and members of sets by small letters, like a, b, c, …. If a is a member of a set A, we denote this by writing a ∈ A, and we say “a is a member of A” or “a belongs to A.” If an element does not belong to a set, we denote this by a ∉ A.

One can also specify a set by specifying defining properties of the member of the set, such as illustrated in Figure 2.1.which we read as “the set of all x in a set A that satisfies the proposition P(x).” The set of even integers could be denoted by

equation
Set notation {x ∈ A:P(x)} with arrows marking All x ∈ A, Such that, and P(x) holds.

Figure 2.1 Set notation.

Some common sets in mathematics are listed in Table 2.1.

Table 2.1 Some common sets.

Common sets in mathematics
images

The half‐open intervals (a, b] and [a, b) are defined similarly.

Some examples illustrating membership and nonmembership in sets are the following.

equation

2.1.2 Universe, Subset, Equality, Complement, Empty Set

  • Universe: The universe U is the set consisting of the totality of elements under consideration. A common universe in number theory is the natural numbers ℕ, whereas in calculus, a common universe is the real numbers ℝ, or intervals of real numbers such as [0, 1] or [0, ∞).
  • Subset: One is often interested in a set A which is part of a larger set B. We say that a set A is a subset of a set B if every member of A is also a member of B. Symbolically, we write this as A ⊆ B and is read “A is contained in B.” If A ⊆ B but A ≠ B, we say that A is a proper subset of a set B and denote this by A ⊂ B.

    Sets are often illustrated visually by Venn diagrams, where sets are represented by circles or ovals and elements of a set as points inside the circle. Figure 2.2 shows a Venn diagram that might ring a bell for most students and illustrates A ⊆ B. The diagram also illustrates that A is not a subset of C.

  • Equality of Sets: Two sets A and B are equal if they consist of the same members. In other words,
    equation
  • Complement of a Set: If a set A belongs to a universe U, the complement of A, written images consists of all members of U that do not belong to A. In other words,
    equation
  • Empty Set: The set that does not contain any members is called the empty set3(or null set) and plays an important role in set theory. It is denoted by the Greek letter Ø or by the empty bracket { }.

    The empty set is not is not nothing, it is something, it is just that it contains nothing. You might think of the empty set as a bag that has nothing in it. In this regard, it might be better to denote the empty set by { } rather than Ø. For example

    equation

    which may seem a bit strange, but it makes a point. There is only one empty set regardless of how differently it is expressed.

  • Power Set: For every set A, the collection of all subsets of A is called the power set of A and denoted by P(A) or sometimes 2A. For example the power set of the set A = {a, b, c} consists of the following set (or collection) of eight subsets of A:
    equation

    A few power sets of some other sets are given in Table 2.2

Venn diagram displaying a circle labeled B for Things studied enclosed by a bigger circle labeled A for Things in the course overlapping to another circle labeled C for Things on the exam.

Figure 2.2 Venn diagram you may be familiar.

Table 2.2 Typical power sets.

Set Power set
Ø {Ø}
{a} {Ø, {a}}
{a, b} {Ø, {a}, {b}, {a, b}}
{a, {b}} {Ø, {a}, {{b}}, {a, {b}}}

Later, we will prove that for any set of n elements, the power set contains 2n elements, which we will prove by induction.4

Venn diagram illustrating subsets displaying boxes enclosing another smaller boxes with labels A, B, and C.

Figure 2.3 Venn diagram illustrating subsets.

2.1.3 Union, Intersection, and Difference of Sets

In arithmetic, we have the binary operations + and ×, whereas in logic, we have analogous binary operations of ∨ and ∧, and now for sets, we have the binary operations of union ∪ and intersection ∩.

Diagram displaying a rectangle labeled U enclosing two overlapping solid circles labeled A and B illustrating a union.

Figure 2.4 Set union.

Diagram displaying a rectangle labeled U enclosing two overlapping circles labeled A and B with shaded overlapped portion illustrating an intersection.

Figure 2.5 Set intersection.

2.1.4 Venn Diagrams of Various Sets

Venn diagrams for subsets A, B of a universe U are shown in Figure 2.6. The universe is represented by the rectangle containing the sets.

Six Venn diagrams displaying two overlapping ellipses labeled A and B with shaded portions illustrating A ∪ B, A ∩ B, Ā, A – B, etc. inside boxes labeled U.

Figure 2.6 Venn diagrams for two sets.

Figure 2.7 illustrates Venn diagrams for three subsets of a universe U.

Six Venn diagrams displaying three overlapping circles labeled A and B with shaded portions illustrating A ∩ B ∩ C, A ∪ B ∪ C, etc. inside boxes labeled U.

Figure 2.7 Venn diagrams for three sets.

2.1.5 Relation Between Sets and Logic

The properties of “∪” and “∩” in set theory have their counterparts in the properties of “∨” and “∧” in sentential logic. Table 2.3 illustrates these counterparts.

Table 2.3 Equivalence between some laws of logic and laws of sets.

Tautology Set equivalence
P ∨ Q ≡ Q ∨ P A ∪ B = B ∪ A
P ∧ Q ≡ Q ∧ P A ∩ B = B ∩ A
P ∨ (Q ∨ R) ≡ (P ∨ Q) ∨ R A ∪ (B ∪ C) = (A ∪ B) ∪ C
P ∧ (Q ∧ R) ≡ (P ∧ Q) ∧ R A ∩ (B ∩ C) = (A ∩ B) ∩ C
P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
P ∧ P ≡ P A ∩ A = A
P ∨ P ≡ P A ∪ A = A

2.1.6 De Morgan's Laws for Sets

In sentential logic, we were introduced to the important tautologies

equation

called De Morgan's laws. We now prove the set versions of these laws.

The second De Morgan law is left to the reader. See Problem 21.

2.1.7 Sets, Logic, and Arithmetic

We compare the set operations of union and intersection with the logical operations of “and” and “or,” and the arithmetic operations of + and + and × in Table 2.4.

Table 2.4 Sets, logic, and arithmetic.

Sets Sentences Arithmetic
+
×
images P
= =
Ø F 0
U T 1

Problems

  1. Set Notation

    Write the following sets in notation {x : P(x)}.

    1. The real numbers between 0 and 1.
    2. The natural numbers between 2 and 5.
    3. The set of prime numbers.
    4. {1, 2, 3, …}
    5. {5, 6, 7}
    6. The solutions of the equation x2 − 1 = 0.
  2. True or False

    If A = {{a}, {b, c}, {d, e, f}}, tell if the following are true or false:

    1. a ∈ A
    2. a ⊆ A
    3. c ∈ A
    4. {b, c} ∈ A
    5. Ø ∈ A
    6. Ø ⊆ A
  3. Checking Subsets: True or False
    1. ℤ ⊆ ℝ
    2. ℝ ⊆ ℂ
    3. (0, 1) ⊆ [0, 1]
    4. (0, 1) ⊆ ℝ
    5. (2, 5) ⊆ ℚ
    6. ℚ ⊆ (2, 5)
    7. [1, 3] ⊆ {1, 3}
    8. {1, 3} ⊆ [1, 3]
    9. {3, 15} ⊆ {3, 5, 7, 15}
  4. The Empty Set: True or False
    1. Ø = {Ø}
    2. Ø ∈ {Ø}
    3. Ø ⊆ {Ø}
    4. A ∪  Ø  = A
    5. {Ø} ⊆ Ø
    6. {Ø} ∈ {{Ø}}
    7. {{Ø}} ∈ {Ø, {Ø}}
  5. True or False
    1. A ∈ A
    2. If A ⊆ B and x ∉ B then x ∉ A
    3. A ⊆ B then A ∈ B.
    4. A ∈ B then A ⊆ B
    5. A ∈ B and B ∈ C then A ∈ C
    6. A ∈ B and B ∈ C then A ⊆ C
  6. Sets, Members, and Subsets

    Which pair (∈, ⊆), images, (∉, ⊆), images of connectives describe the relationship between the quantity on the left with the set on the right. The answer to a) is images since a is a member of {c, a, t} but not a subset.

    1. a___{c, a, t} Ans: images
    2. a___{c, a, {a}, t} Ans: images
    3. {a, t}___{c, a, t} Ans: ∉, ⊆
    4. {a}___{c, {a}, t}
    5. {a, {t}}___{c, a, t, {t}}
    6. {a, {t}}___{c, a, t, {t}, {a, {t}}}
    7. {c, a, {t}}___{a, t, {t}}
    8. {a, {t}}___{c, a, t, {t}}
    9. Ø___Ø
    10. {Ø}___{Ø}
    11. {Ø}___{Ø, {Ø}}
    12. Ø___{Ø}
    13. {Ø}___Ø
  7. Power Sets

    Find the power set of the given sets.

    1. A = {4, 5, 6}
    2. A = {⊕, ⊙ , ⊗}
    3. A = {a, {b}}
    4. A = {a, {b, {c}}}
    5. A = {a, {a}}
    6. A = {Ø, {Ø}}
  8. Find the Set

    Let A = {a1, a2, …}, where an is the remainder when n is divided by 5. List the elements of the set A.

  9. Interesting

    If A = {a, b, c} are the following relations true or false?

    1. A ∈ P(A)
    2. A ⊆ P(A)
  10. Power Set as a Collection of Functions

    The power set of a set can be interpreted as the set of all functions7 defined on the set whose values are 0 and 1. For example the functions defined on the set A = {a, b} with values 0 and 1 are

    • f(a) = 0, f(b) = 0 corresponds to Ø
    • f(a) = 1, f(b) = 0  corresponds to {a}
    • f(a) = 0, f(b) = 1 corresponds to {b}
    • f(a) = 1, f(b) = 1 corresponds to {a, b}

    Show that the elements of the power set of A = {a, b, c} can be placed in this “one‐to‐one” correspondence with the functions on A whose values are either 0 or 1.

  11. Second Power Set

    The second power set of a set A is the set of subsets of the set, or P(P(A)). What is the second power set of A = {a}?

  12. Power Set of the Empty Set

    Prove P(Ø) = {Ø}

  13. Identities

    Let A, B, and C be arbitrary subsets of a universe U. Prove the following.

    1. A ⊆ A
    2. A ∪  Ø  = A
    3. A ∩  Ø  = Ø
    4. images
    5. A ∩ U = A
    6. images
    7. A ⊆ B ⇒ A ∪ B = B
    8. A ∪ A = A ∩ A
    9. images
  14. Difference Between Sets

    The formula images defines the difference between two sets in terms of the operations of intersection and complement. Can you find a formula for the union A ∪ B in terms of intersections and complements?

  15. NASC for Disjoint Sets

    Prove A ∩ B =  Ø  ⇔ A − B = A.

  16. Distributive Law

    Prove that if A, B, and C are sets, then “∪” distributes over “∩.” That is A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

  17. Set Identity

    Prove A ⊆ B ⇔ A ∪ B = B.

  18. Proving Set Relations with Truth Tables

    It is possible to prove identities of sets using truth tables. For example one of DeMorgan's laws

    equation

    is verified from Table 2.5, replacing the union by “or,” the intersection by “and,” and set complementation by “not.”

    Prove the following identities using truth tables.

    1. images
    2. images
    3. A ∪ (B ∪ C) = (A ∪ B) ∪ C
    4. A ∪ B = (A ∩ B) ∪ (A − B) ∪ (B − A)

    Table 2.5 Verifying set relations with truth tables.

    (1) (2) (3) (4) (5)
    x ∈ A x ∈ B A ∪ B images images images images
    T T T F F F F
    T F T F F T F
    F T T F T F F
    F F F T T T T
    A down bracket.
    Same truth values
  19. Sets and Their Power Sets

    Prove

    equation
  20. Computer Representation of Sets

    Finite sets can be represented by vectors of 0s and 1s. For the set U = {a1, a2, … , an}, we can represent a subset S of this set by a bit string, where the ith bit is 1 if ai ∈ S and 0 if ai ∉ S. The following problems relate to this representation of sets. Take as the universe, the set U = {0, 1, 2, 3, 4, 5, 6, 7}.

    1. If U = {3, 9, 2, 5, 6 }, what is S ⊆ U for the bit string 11001?
    2. If U = {1, 2, 3, 4, 5, 6 }, what is the bit string for A = {2, 6}?
    3. If U = {1, 2, 3, 4, 5, 6 } and S = {1, 4, 5}, T = {1, 2, 4, 6}, what is the bit string for S ∩ T?
    4. If U = {1, 2, 3, 4, 5, 6 }and S = {1, 4, 5}, T = {1, 2, 4, 6}, what is the bit string for S ∪ T?
    5. How would you represent the complement of a subset of U = {1, 2, 3, 4, 5, 6 }?
  21. De Morgan's Law

    Prove the De Morgan law images.

  22. Internet Research

    There is a wealth of information related to topics introduced in this section just waiting for curious minds. Try aiming your favorite search engine toward mathematical rigor, naive set theory, George Boole, power set of a set.

Notes

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
44.201.64.238