0.4 Discrete structures set theory  (Page 6/6)

Proof for 6: By the definition of the equality of sets, we need to prove that ∀x [x ∈ A ∪ (B ∩ C)] if and only if x ∈ (A ∪ B) ∩ (A ∪ C).

For that, considering the Universal Generalization rule, we need to show that for an arbitrary element in the universe x, x ∈ A ∪ (B ∩ C) if and only if x ∈ (A ∪ B) ∩ (A ∪ C).

Here the only if part is going to be proven. The if part can be proven similarly.

x ∈ A ∪ (B ∩ C) ⇔ x ∈ A ∨ x ∈ (B ∩ C) by the definition of ∪

⇔ x ∈ A ∨ (x ∈ B ⋀ x ∈ C) by the definition of ∩

⇔ (x ∈ A ∨ x ∈ B) ⋀ (x ∈ A ∨ x ∈ C) by the distribution from the equivalences of propositional logic

⇔ x ∈ (A ∪ B) ⋀ x ∈ (A ∪ C) by the definition of ∪.

⇔ x ∈ (A ∪ B) ∩ (A ∪ C) by the definition of ∩.

Proof for 8: (a) If A⊆B then A ∪ B = B.

Let x be an arbitrary element in the universe.

Then x ∈ A ∪ B ⇔ x ∈ A ∨ x ∈ B.

Since A⊆B, x ∈ A → x ∈ B

Also x ∈ B → x ∈ B

Hence x ∈ A ∪ B → x ∈ B.

Hence A ∪ B ⊆ B

Since B ⊆ A ∪ B (use "addition" rule), A ∪ B = B follows.

(b) Similarly for A ∩ B = A.

Alternative proof:

These can also be proven using 8, 14, and 15. For example, (b) can be proven as follows:

First by 15, A ∩B ⊆A.

Then since A ⊆A, and A ⊆B, by 7 A ∩A ⊆A ∩B.

Since A ∩A = A by 3, A ⊆A ∩B.

Proof for 9: Let x be an arbitrary element in the universe.

Then [x ∈ A ∪ (B - A)] ⇔ [x ∈ A ∨ (x ∈ B ⋀ x ∉ A)]

⇔ [(x ∈ A ∨ x ∈ B) ⋀ (x ∈ A ∨ x ∉ A)]

⇔ [(x ∈ A ∨ x ∈ B) ⋀ True]

⇔ [x ∈ A ∨ x ∈ B]

Hence A ∪ (B - A) = A ∪ B.

Alternative proof

This can also proven using set properties as follows.

A ∪( B - A ) = A ∪( B ∩ $\overline{A}$ ) by the definition of ( B - A ) .

= ( A ∪B ) ∩( A ∪ $\overline{A}$ ) by the distribution.

= (A ∪B ) ∩U

= ( A ∪B ) by 1.

Proof for 10: Suppose A ∩ (B - A) ≠ ∅.

Then there is an element x that is in A ∩ (B - A), i.e.

x ∈ A ∩ (B - A) ⇔ x ∈ A ⋀ x ∈ B – A

⇔ x ∈ A ⋀ (x ∈ B ⋀ x ∉ A)

⇔ (x ∈ A ⋀ x ∉ A) ⋀ x ∈ B

⇔ False

Hence A ∩ (B - A) ≠ ∅ does not hold.

Hence A ∩ (B - A) = ∅.

This can also be proven in the similar manner to 9 above.

Proof for 11: Let x be an arbitrary element in the universe.

Then x ∈ A - (B ∪ C) ⇔ x ∈ A ⋀ x ∉ B ∪ C

⇔ x ∈ A ⋀ ¬(x ∈ B ⋁ x ∈C)

⇔ x ∈ A ⋀ (x ∉ B ⋀ x ∉C)

⇔ (x ∈ A ⋀ x ∉ B) ⋀ x ∉C

⇔ (x ∈ A ⋀ x ∉ B) ⋀ (x ∈ A ⋀ x ∉C)

⇔ x ∈ A - B ⋀ x ∈ A - C

⇔ x ∈ (A - B) ∩ (A - C)

Hence A - (B ∪ C) = (A – B) ∩ (A - C)

Proof for 12:

(a) A ∪ B = U ⋀ A ∩ B = ∅ ⇒ B = $\overline{A}$ ?

(b) Try to prove B ⊆ $\overline{A}$ and $\overline{A}$ ⊆ B.

Let x be an arbitrary element in the universe.

Then if x ∈ B, then x ∉A since A ∩ B = ∅. Hence x ∈ $\overline{A}$ .

Hence B ⊆ $\overline{A}$ .

If x ∈ $\overline{A}$ , then x ∉A. Since x ∈ A ∨ x ∈ B (from A ∪ B = U ), x ∈ B

must hold. Hence $\overline{A}$ ⊆ B.

Hence B = $\overline{A}$ . (c) B = $\overline{A}$ ⇒ A ∪ B = U ⋀ A ∩ B = ∅ ?

Since B = $\overline{A}$ , A ∪ B = A ∪ (U-A) = A ∪ U = U since A ⊆ U

Also A ∩ B = A ∩ (U - A) = ∅ by 10 above.

Proof for 13: Since $\overline{\overline{A}}$ ∪ $\overline{A}$ = $\overline{A}$ ∪ $\overline{\overline{A}}$ , $\overline{A}$ ∪ $\overline{\overline{A}}$ = U

Also since $\overline{\overline{A}}$ ∩ $\overline{A}$ = $\overline{A}$ ∩ $\overline{\overline{A}}$ , $\overline{A}$ ∩ $\overline{\overline{A}}$ = ∅.

Hence $\overline{\overline{A}}$ satisfies the conditions for the complement of $\overline{A}$ .

Hence $\overline{\overline{A}}=A$ .

Questions and exercises

• Determine whether each of the following pairs of sets is equal.
  • ∅ and {∅}
  • {a,b,c} and {a,b,c,c}
  • {1,2,3} and {{1},{2},{3}}
• Let S1={a,b,c}, S2={a,b}, S3={b,c} and S4={b,c,d}. Which of the followings is correct?
  • S2 ⊆ S1
  • S3 ⊂S1
  • S4 ⊆ S1
• Let A={a,b,c,d} and B={a,b,c,d,e,f}. Which of the followings is correct?
  • A ∪ B = {a,b,c,d,e,f}
  • A ∩ B = {a,b,c,d}
  • A – B = {e,f}
  • B – A = {e,f}
• List the members of the following sets.
  • { x | x is a real number such that x ²= 4}
  • { x | x is an integer such that x ² =2}
• Determine whether each of the following pairs of sets is equal.

• {1, 2, 1, 3, 1, 2}, {2, 3, 1}
• {{1}}, {1, {1}}
• ∅, {∅}
• For each of the following sets, determine whether 1 is an element of that set.

• { x ∈R | x is an integer greater than 1}
• { x ∈R | x is the square of an integer}
• {1, 2, {1}}
• {{1}, {{1}}}
• {{1, 2}, {1, {1}}}
• {{{1}}}
• Suppose that A , B , and C are sets such that A ⊆ B and B ⊆ C . Show that A ⊆ C .
• Find the power set of each of the following sets.

• {a}
• {a, {a}}
• {∅, {∅}}
• Let A be a set. Show that ∅x A = A x ∅= ∅.
• How many different elements does A x B have if A has m elements and B has n elements?
• Let A = {1, 2, 3, 4} and b = {0, 3, 5}. Find

• A ∪ B
• A ∩ B
• A - B
• B - A
• What can you say about the sets A and B if the following are true?

• A ∪ B
• A ∪ B = A
• A - B = A
• Let A and B be subsets of a universal set U . Show that A ⊆ B if and only if $\overline{B}$ ⊆ $\overline{A}$ .
• Let A and B be sets. Show that

• A ∪ B = B ∪ A.
• A ∩ B = B ∩ A .
• Show that if A and B are sets, then $\overline{(A\cup B)}$ = $\overline{A}$ ∩ $\overline{B}$ by showing each side is a subset of the other side.
• Let A , B , and C be sets. Show that A ∪( B ∪ C ) = ( A ∪ B ) ∪ C.