Set Identities

Solved Problems

Solution.

1. We show that the left-hand side of the identity is a subset of the right side. Let's take an arbitrary element \(x \in {A \backslash B}.\) By the set difference identity, we have \(x \in A \cap {B^c}.\) If \(x \in {B^c},\) then \(x \in {A^c} \cup {B^c}.\) Using De Morgan's law, this means that \(x \in {\left( {A \cap B} \right)^c}.\) Thus, \(x \in A\) and \(x \in {\left( {A \cap B} \right)^c}.\) By the definition of set intersection, we have \(x \in A \cap {\left( {A \cap B} \right)^c}.\) Applying the set difference identity, we conclude that \(x \in A\backslash \left( {A \cap B} \right) = RHS.\)
2. Consider now the right-hand side and show that it is a subset of the left side. Let \(x \in A\backslash \left( {A \cap B} \right).\) Using the set difference identity, we can write that \(x \in A \cap {\left( {A \cap B} \right)^c}.\) By De Morgan's law, \({\left( {A \cap B} \right)^c} = {A^c} \cup {B^c}.\) Hence, \(x \in A \cap \left( {{A^c} \cup {B^c}} \right).\) Apply the distribution law: \(x \in \left( {A \cap {A^c}} \right) \cup \left( {A \cap {B^c}} \right).\) Here, \(A \cap {A^c} = \varnothing,\) by the complement law. Next, \(\varnothing \cup \left( {A \cap {B^c}} \right) = A \cap {B^c},\) by the commutative and identity laws. So, we see that \(x \in A \cap {B^c}.\) By the set difference identity, this means that \(x \in A\backslash B = LHS.\)

This proves that \(A\backslash B = A\backslash \left( {A \cap B} \right).\)

Solution.

1. First we show that the left-hand side of the identity is a subset of the right side. Take an arbitrary element \(x \in \left( {A \backslash B} \right) \cap C.\) By definition of set intersection, \(x \in \left( {A \backslash B} \right)\) and \(x \in C.\) Using the definition of set difference, we conclude that \(x \in A,\) \(x \notin B,\) and \(x \in C.\) If \(x \in A\) and \(x \in C,\) then \(x \in \left( {A \cap C} \right)\) by definition of set intersection. If \(x \notin B,\) then \(x \in B^c,\) by definition of set complement. Using the definition of set union, we can extend the last statement and rewrite it as \(x \in \left({{B^c} \cup {C^c}}\right).\) Now we apply De Morgan's law, which states that \(x \in \left({B \cap C}\right)^c.\) So, we have that \(x \in \left( {A \cap C} \right)\) and \(x \in \left({B \cap C}\right)^c.\) By definition of set intersection, we can write \(x \in \left( {A \cap C} \right) \cap {\left( {B \cap C} \right)^c}.\) Finally, using the set difference identity, we get \(x \in \left( {A \cap C} \right)\backslash \left( {B \cap C} \right),\) or \(x \in RHS.\)
2. Similarly we prove that the right-hand side is a subset of the left side. Suppose that \(x \in \left( {A \cap C} \right) \backslash \left( {B \cap C} \right).\) Using the set difference identity we can write this as \(x \in \left( {A \cap C} \right) \cap {\left( {B \cap C} \right)^c}.\) Apply De Morgan's law \({\left( {B \cap C} \right)^c} = {B^c} \cup {C^c}.\) This gives: \(x \in \left( {A \cap C} \right) \cap \left( {{B^c} \cup {C^c}} \right).\) By the distributive law, \(x \in \left( {\left( {A \cap C} \right) \cap {B^c}} \right)\) \(\cup \left( {\left( {A \cap C} \right) \cap {C^c}} \right).\) By the associative and commutative laws, \(x \in \left( {\left( {A \cap {B^c}} \right) \cap C} \right) \) \(\cup \left( {A \cap \left( {C \cap {C^c}} \right)} \right).\) Here \(C \cap {C^c} = \varnothing\) by the complement law, and \(A \cap \varnothing = \varnothing\) by the domination law. Hence, \(x \in \left( {\left( {A \cap {B^c}} \right) \cap C} \right) \cup \varnothing.\) So, \(x \in \left( {A \cap {B^c}} \right) \cap C\) (by the identity law). Using the set difference identity, we have \(x \in \left( {A\backslash B} \right) \cap C,\) or \(x \in LHS.\)

This shows that \(\left( {A\backslash B} \right) \cap C = \left( {A \cap C} \right)\backslash \left( {B \cap C} \right).\)

Solution.

We prove algebraically that the left hand side \(\left({LHS}\right)\) is equal to the right-hand side \(\left({RHS}\right).\)

By distributive laws,

Now we apply the complement law \({A \cap {A^c} = \varnothing.}\) This yields:

Finally, we use the commutative law \(A \cup B = B \cup A\) and the identity law \({A \cup \varnothing = A}.\)

Solution.

We prove this identity using the algebraic method. Consider the left-hand side \(\left({LHS}\right).\) By the set difference law, we can write it in the form

By De Morgan's law, \({\left( {B \cup C} \right)^c} = {B^c} \cap {C^c}.\) Given that \(A = A \cap A\) (the idempotent law), and using the associative and commutative rules, we obtain

Finally, applying the set difference law, we have

Solution.

We prove algebraically that the left hand side \(\left({LHS}\right)\) of the identity is equal to the right-hand side \(\left({RHS}\right).\)

Using the distribution law

we can write

Recall that by complement laws,

Hence,

Finally, using the identity law \(A \cap U = A,\) we conclude that

Solution.

We prove this identity algebraically - using the basic laws of set theory.

The symmetric difference in the left-hand side \(\left({LHS}\right)\) can be written as

Apply the set difference law:

By De Morgan's law, \({\left( {A \cap B} \right)^c} = {A^c} \cup {B^c}.\)

Using the commutative and associative laws, we have

By the complement law, \({{A^c} \cap A} = \varnothing\), and by the domination and commutative laws, \(\varnothing \cap B = B \cap \varnothing = \varnothing.\) Hence, \(\left( {A \cap B} \right) \cap {A^c} = \varnothing.\) Applying the identity law, we represent the left-hand side in the form

Using the distributive law, we get

Obviously that \({A \cap {A^c}} = \varnothing\), by the complement law. This yields:

Now we use again the commutative and identity laws:

By the set difference law, we conclude that

Solution.

We build a membership table for the sets \(A \cap \left( {B\backslash A} \right)\) and \(\varnothing.\) The number \(1\) represents membership in a set and \(0\) represents nonmembership. We consider all possible membership combinations in the original sets \(A\) and \(B\) and calculate the membership values for the sets in the left and right side of the identity. The results are shown in the following table:

Since the last two columns have the same values, the set identity holds.

Solution.

We construct a table which shows the membership relations for the sets in the left-hand side and the right-hand side of the identity. The number \(1\) indicates that an element is in a set, and \(0\) means that an element is not in a set. The table contains each combination of sets \(A\) and \(B\) that an element can belong to.

Since the answers in the last two columns are the same, the identity is proved.

Solution.

We represent the left-hand side in set builder notation:

Rewrite the statement \({x \notin A}\) with the negation operation:

By the distributive law,

The disjunction of \({x \in A}\) and \({\neg \left( {x \in A} \right)}\) is a true statement:

So, by the identity law,

Returning back to algebraic form, we conclude that

Solution.

The left-hand side of the identity is represented in set builder notation as follows:

The negation of the "element of" statement is written as

Using again the definition of set difference, we have

Replace \(x \notin B\) with \(\neg \left( {x \in B} \right):\)

Apply De Morgan's law:

By the distributive law,

Note that the conjunction of \({x \in A}\) and \({\neg \left( {x \in A} \right)}\) is a false statement:

Hence, by the commutative and identity laws,

Converting back from set builder notation to algebraic form, we get