Home » Sets » Page 2

Tag: Sets

Prove distributive laws for unions and intersections of sets

Prove that A \cap (B \cup C) = (A \cap B) \cup (A \cap C) and A \cup (B \cap C) = (A \cup B) \cap (A \cup C).


Proof (A \cap (B \cup C) = (A \cap B) \cup (A \cap C)). Let x be an arbitrary element of A \cap (B \cup C). This means that x \in A and x \in (B \cup C). Further, since x \in (B \cup C) we know x \in B or x \in C. But then, this implies x \in (A \cap B) or x \in (A \cap C) depending on whether x \in B or x \in C, respectively. Then, since x \in (A \cap B) or x \in (A \cap C), we have x \in (A \cap B) \cup (A \cap C). Thus, A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C).
For the opposite inclusion, we let x be an arbitrary element of (A \cap B) \cup (A \cap C). This means that x \in (A \cap B) or x \in (A \cap C). If x \in (A \cap B) then x \in A and x \in B, while if x \in (A \cap C) we have x \in A and x \in C. Thus, we have x \in A no matter what, and either x \in B or x \in C. Since x \in B or x \in C, we know x \in (B \cup C). Since we already had that x \in A no matter what, we now have x \in A \cap (B \cup C). Therefore, (A \cap B) \cup (A \cap C) \subseteq A \cap (B \cup C).
Hence, A \cap (B \cup C) = (A \cap B) \cup (A \cap C).∎

Proof (A \cup (B \cap C) = (A \cup B) \cap (A \cup C)). Let x be an arbitrary element of A \cup (B \cap C). This means x \in A or x \in (B \cap C). If x \in A then x \in A \cup B and x \in A \cup C. Hence, x \in (A \cup B) \cap (A \cup C). Otherwise, if x \in (B \cap C) then x \in B and c \in C. Hence, x \in A \cup B and x \in A \cup C; therefore, x \in (A \cup B) \cap (A \cup C). Therefore, A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C).
For the reverse inclusion, let x be an arbitrary element of (A \cup B) \cap (A \cup C). This means x \in (A \cup B) and x \in (A \cup C). This implies that x \in A or x \in B and x \in C (since if x \notin A then the fact that x \in A \cup B and x \in A \cup C means x must be in both B and C). If x \in A, then x \in A \cup (B \cap C). On the other hand, if x \in B and x \in C, then x \in B \cap C. Hence, x \in A \cup (B \cap C). Therefore, (A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C).
Therefore, A \cup (B \cap C) = (A \cup B) \cap (A \cup C).∎

Prove the associative laws for union and intersections of sets

Prove that A \cup (B \cup C) = (A \cup B) \cup C and that A \cap (B \cap C) = (A \cap B) \cap C.


Proof (Associativity of unions). First, let x be any element in A \cup (B \cup C). This means that x \in A or x \in (B \cup C). If x \in A then x \in (A \cup B); hence, x \in (A \cup B) \cup C. On the other hand, if x \notin A, then x \in (B \cup C). This means x \in B or x \in C. If x\in B, then x \in (A \cup B) \implies x \in (A \cup B) \cup C. If x \in C, then x \in (A \cup B) \cup C. Hence, A \cup (B \cup C) \subseteq (A \cup B) \cup C.
For the reverse inclusion, let x be any element of (A \cup B) \cup C. Then, x \in (A \cup B) or x \in C. If x \in (A \cup B), we know x \in A or x \in B. If x \in A, then x \in A \cup (B \cup C). If x \in B, then x \in (B \cup C); hence, x \in A \cup (B \cup C). On the other hand, if x \in C, then x \in (B \cup C), and so, x \in A \cup (B \cup C). Therefore, (A \cup B) \cup C \subseteq A \cup (B \cup C).
Thus, A \cup (B \cup C) = (A \cup B) \cup C.∎

Proof (Associativity of intersections). To expedite matters, will prove both inclusions at once: x is in A \cap (B \cap C) if and only if x \in A and x \in (B \cap C), further, x \in (B \cap C) if and only if x \in B and x \in C. Similarly, x \in (A \cap B) \cap C if and only if x \in A and x \in B and x \in C. Thus, A \cap (B \cap C) and (A \cap B) \cap C have exactly the same elements (since x \in A \cap (B \cap C) if and only if x \in A and x \in B and x \in C if and only if x \in (A \cap B) \cap C).
Thus, A \cap (B \cap C) = (A \cap B) \cap C.∎

Prove the commutative laws of union and intersection

Prove A \cup B  = B \cup A and A \cap B = B \cap A.


Proof (A \cup B = B \cup A). If x is any element in A \cup B then, by definition of union, we have x \in A or x \in B. But, if x is in A or B, then it is in B or A, and by definition of union, this means x \in B \cup A. Therefore, A \cup B \subseteq B \cup A.
The other inclusion is identical: if x is any element of B \cup A, then we know x \in B or x \in A. But, x \in B or x \in A implies that x is in A or B; and hence, x \in A \cup B. Therefore, B\ \cup A \subseteq A \cup B.
Hence, A \cup B = B \cup A.∎

Proof (A \cap B = B \cap A). If x is any element in A \cap B, then we know by definition of intersection that x \in A and x \in B. Hence, x \in B and x \in A, and so, x \in B \cap A. Therefore, A \cap B \subseteq B \cap A.
The reverse inclusion is again identical: if x is any element of B \cap A, then we know x \in B and x \in A. Hence, x \in A and x \in B. This implies x \in A \cap B. Hence, B \cap A \subseteq A \cap B.
So, A \cap B = B \cap A.∎

Prove properties of set equality

Prove the following.

  1. \{ a,a \} = \{ a \}.
  2. \{ a,b \} = \{ b,a \}.
  3. \{ a \} = \{ b,c \} if and only if a=b=c.

  1. Proof. To show two sets are equal, we want to show that each is a subset of the other (i.e., we want to show that \{ a,a \} \subseteq \{ a \} and \{ a \} \subseteq \{ a, a \}).
    First, \{ a \} \subseteq \{ a,a \} since the only element of \{ a \} is a, and we have a \in \{ a,a \}.
    Second, the only element of \{ a, a \} is a, and we have a \in \{ a \}. Hence, \{ a,a \} \subseteq \{ a \}. Thus, \{ a,a \} = \{ a \}. ∎
  2. Proof. Again, we want to show \{ a,b \} \subseteq \{b,a \} and \{ b,a \} \subseteq \{ a,b \}.
    First, \{ a,b \} \subseteq \{ b,a \} since the elements of \{ a,b \} are a and b, and a, b \in \{ b, a \}.
    Second, the elements of \{ b,a \} are a and b. Since a,b \in \{a, b\} we have every element of \{ b, a \} is in \{ a,b \}; thus, \{ b,a \} \subseteq \{a,b \}.
    Therefore, \{ a,b \} = \{ b,a \}. ∎
  3. Proof. (\Rightarrow) Assume \{ a \} = \{ b,c \}. Since \{ b,c \} = \{ a \}, we must have \{ b,c \} \subseteq \{ a \}; hence, every element of \{ b,c \} must be contained in \{ a \}. This means that both b and c are in \{ a \}. Since a is the only element of \{ a \}, we must have a = b = c.
    (\Leftarrow) Conversely, assume a = b =c. Then \{ b,c \} = \{ a,a \} and from part (a) we know \{ a \} = \{ a,a \}; hence \{a \} = \{ b,c \}.∎

Proving some relations between given sets

Let

    \[A=\{1,2\}, \quad B=\{\{1\},\{2\}\}, \quad C=\{\{1\},\{1,2\}\}, \quad D=\{\{1\},\{2\},\{1,2\}\}.\]

Prove or disprove the following.

  1. A = B.
  2. A \subseteq B.
  3. A \subset C.
  4. A \in C.
  5. A \subset D.
  6. B \subset C.
  7. B \subset D.
  8. B \in D.
  9. A \in D.

  1. False.
    These sets are not equal since they do not contain the same elements (since 1 \neq \{ 1 \} and 2 \neq \{ 2 \}).
  2. False.
    Since A contains an element (e.g. 1) that is not contained in B, we have A \nsubseteq B. (Again, this is asking us to observe that 1 \neq \{ 1 \}.)
  3. False.
    Again, 1 \in A but 1 \notin C; hence, A \nsubseteq C.
  4. True.
    Proof. By definition of C we have \{ 1,2 \} \in C. Since A = \{1,2\}, we have A \in C.∎
  5. False.
    Since 1 \in A, but 1 \notin D, we have A \not\subset D.
  6. False.
    The element \{ 2 \} is in B, but is not in C. Hence, B \not\subset C.
  7. True.
    Proof. To show B \subset D, we must show that every element in B is also in D, and that B \neq D (so that B is a proper subset). First, the only two elements of B are the sets \{ 1 \} and \{ 2 \}. Since each of these sets is contained in D by definition of D, we have B \subseteq D. Finally, since the set \{ 1,2 \} \in D, but \{ 1,2 \} \notin B, we see that the inclusion is proper. Hence, B \subset D. ∎
  8. False.
    Again, the problem is emphasizing the difference between an element and the set that contains that element. In this case B = \{ \{1\},\{2\}\} and \{\{1\}, \{2\}\} is not an element of D (even though \{1\} and \{2\} are elements of D, the set containing the sets \{1\} and \{2\} is not).
  9. True.
    Proof. By the definition of D we have \{ 1 ,2 \} \in D. Since A = \{ 1,2 \}, we have A \in D. ∎

More proofs of set relations

Let A = \{ 1 \} and B = \{ \{ 1 \}, 1 \}. Prove or disprove the following.

  1. A \subset B.
  2. A \subseteq B.
  3. A \in B.
  4. 1 \in A.
  5. 1 \subseteq A.
  6. 1 \subset A.

  1. True.
    Proof. Since 1 is the only element in A, and 1 \in B, we have that every element of A is contained in B. Hence, A \subseteq B. Further, since \{ 1 \} \in B, but is not in A, we see that B \nsubseteq A. Therefore, A \subset B. ∎
  2. True.
    Proof. Again, since A \subset B \implies A \subseteq B, we have A \subseteq B by part (a). ∎
  3. True.
    Proof. By the definition of B we have that \{ 1 \} \in B. Since A = \{ 1 \}, we have A \in B. ∎
  4. True.
    Proof. By definition A = \{ 1 \}; hence, 1 \in A.∎
  5. False.
    Since 1 is not a set, we cannot have 1 \subseteq A.
  6. False.
    Since 1 is still not a set, we cannot have 1 \subset A.

Prove or disprove some set relations

If A = \{ 1 \} and B = \{ 1,2 \} prove or disprove the following:

  1. A \subset B.
  2. A \subseteq B.
  3. A \in B.
  4. 1 \in A.
  5. 1 \subseteq A.
  6. 1 \subset B.

  1. True Proof. To show A \subset B we must show that every element in A is also in B. Further (since Apostol seems to distinguish between \subset and \subseteq) we want to show that A \neq B.

    First, since 1 is the only element of A, and 1 \in B, we see that every element of A is indeed contained in B. Hence, A \subseteq B.

    Then, since 2 \in B, but 2 \notin A, we see that B \nsubseteq A. Hence A \neq B, so A is a proper subset of B, or A \subset B. ∎

  2. True
    Proof. This follows immediately from part (a) since A \subset B \implies A \subseteq B. ∎
  3. Not True
    This is not true since A = \{ 1 \} and the set \{ 1 \} is not an element of B (since 1 \neq \{ 1 \}).
  4. True
    Proof. There is really nothing to prove here. By definition, A is the set containing 1, so 1 is in A. ∎
  5. Not true
    This is not true since 1 is not a set, so is not a subset of A.
  6. Not true
    Again, 1 is not a set, so cannot be a subset of B.