Tag: Sets

Prove the given sets are measurable and have zero area

by RoRi

July 15, 2015

Prove measurability and establish that the area is zero for each of the following.

Any set consisting of a single point.
Any set consisting of finitely many points in the plane.
The finite union of line segments in the plane.

Proof. Since all rectangles are measurable with area equal to $hk$ where $h$ and $k$ are the lengths of the edges of the rectangle, a single point is measurable with area 0, since a point is rectangle with $h=k=0. \qquad \blacksquare$
Proof. We prove by induction on $n$ , the number of points. For the case $n=1$ , the statement is true by part (a). Now, assume it is true for some $n=k \in \mathbb{Z}_{>0}$ . Then, we have a set $S \in \mathcal{M}$ of $k$ points in the plane and $a(S) = 0$ . Let $T$ be a point in the plane. By part (a), $T \in \mathcal{M}$ and $a(T) = 0$ . Thus,

$S \cup T \in \mathcal{M} \qquad \text{and} \qquad a(S \cup T) = a(S) + a(T) - a(S \cap T).$

But, $S \cap T \subseteq S$ , so

$a(S \cap T) \leq a(S) \quad \implies \quad a(S \cap T) \leq 0 \quad \implies \quad a(S \cap T) = 0.$

(Where Axiom 1 of area guarantees us that $a(S \cap T)$ cannot be negative.) Thus, $a(S \cup T) =0$ . Hence, the statement is true for $k+1$ points in a plane, and thus for all $n \in \mathbb{Z}_{>0}. \qquad \blacksquare$
Proof. We again use induction, now on $n$ , the number of lines in a plane. For $n=1$ , we let $S$ be a set with one line in a plane. Since a line is rectangle and all rectangles are measurable, we have $S \in \mathcal{M}$ . Further, $a(S) = 0$ since a line is a rectangle with either $h= 0$ or $k =0$ , and so in either case, $hk = 0$ . Thus, the statement is true for a single line in the plane, the case $n=1$ .
Assume then that it is true for $n=k \in \mathbb{Z}_{>0}$ . Let $S$ be a set of $k$ lines in the plane. Then by the induction hypothesis, $S \in \mathcal{M}$ and $a(S) = 0$ . Let $T$ be a single line in the plane. By the case $n=1$ above, $T \in \mathcal{M}$ and $a(T) = 0$ . Thus, $S \cup T \in \mathcal{M}$ and $a(S \cup T) = 0$ (since $a(S) = a(T) = a(S \cap T) = 0$ ). Hence, the statement is true for $k+1$ lines in a plane, and so for all $n \in \mathbb{Z}_{>0}. \qquad \blacksquare$

One correct and one incorrect formula for set complements

by RoRi

June 22, 2015

Given the two formulas:
$\begin{align*} A - (B - C) &= (A - B) \cup C \\ A - (B \cup C) &= (A-B)-C. \end{align*}$

Identify which one is always correct and which one is sometimes wrong, and prove the result.
Give an additional condition for the incorrect formula to be always true.

The formula $A \smallsetminus (B \smallsetminus C) = (A \smallsetminus B) \cup C$ is false in general.

Proof. Let

$A = \{ 1,2 \}, \quad B = \{ 1 \}, \quad C = \{ 1,2,3 \}.$

Then,

$A \smallsetminus (B \smallsetminus C) = \{ 1,2 \}, \quad \text{but} \quad (A \smallsetminus B) \cup C = \{ 1,2,3 \}.$

Thus, the formula does not hold in this counterexample.∎

The formula $A \smallsetminus (B \cup C) = (A \smallsetminus B) \smallsetminus C$ is correct.
Proof. Let $x$ be any element of $A \smallsetminus (B \cup C)$ . This means $x \in A$ and $x \notin (B \cup C)$ , which in turn means $x \notin B$ and $x \notin C$ . Since $x \in A$ and $x \notin B$ we have $x \in (A \smallsetminus B)$ . Then, since $x \notin C$ , we have $x \in (A \smallsetminus B) \smallsetminus C$ . Thus, $A \smallsetminus (B \cup C) \subseteq (A \smallsetminus B) \smallsetminus C$ .
For the reverse inclusion, let $x$ be any element of $(A \smallsetminus B) \smallsetminus C$ . This gives us $x \in (A \smallsetminus B)$ and $x \notin C$ . The first part in turn gives us $x \in A$ and $x \notin B$ . But then we have $x$ in neither $B$ nor $C$ ; hence, $x \notin (B \cup C)$ . Since $x \in A$ , we then have $x \in A \smallsetminus (B \cup C)$ . Therefore, $(A \smallsetminus B) \smallsetminus C \subseteq A \smallsetminus (B \cup C)$ .
Therefore, $A \smallsetminus (B \cup C) = (A \smallsetminus B) \smallsetminus C$ .∎

To make the first formula in part (a) always correct, we add the condition that $C \subseteq A$ . The claim is then:
If $C \subseteq A$ , then $A \smallsetminus (B \smallsetminus C) = (A \smallsetminus B) \cup C$ .
Proof. Let $x$ be any element in $A \smallsetminus (B \smallsetminus C)$ , then $x \in A$ and $x \notin (B \smallsetminus C)$ . But, $x \notin (B \smallsetminus C)$ means that $x \notin B$ or $x \in C$ (since this is the negation of $x \in (B \smallsetminus)$ which means $x \in B$ and $x \notin C$ , so its negation is $x \notin B$ or $x \in C$ ). So, if $x \notin B$ , then $x \in (A \smallsetminus B)$ and hence $x \in (A \smallsetminus B) \cup C$ . On the other hand, if $x \in C$ , then $x \in (A \smallsetminus B) \cup C$ as well. Hence, $A \smallsetminus (B \cup C) \subseteq (A \smallsetminus B) \cup C$ .
For the reverse inclusion, let $x \in (A \smallsetminus B) \cup C$ . Then $x \in (A \smallsetminus B)$ or $x \in C$ . If $x \in (A \smallsetminus B)$ , then $x \in A$ and $x \notin B$ . Since, $x \notin B$ , then we know $x \notin (B \smallsetminus C)$ (since every $x \in (B \smallsetminus C)$ must be in $B$ ). Therefore, $x \in A \smallsetminus (B \smallsetminus C)$ . On the other hand, if $x \in C$ , then since $C \subseteq A$ (by our additional hypothesis) we know $x \in A$ . Further, since $x \in C$ , we know $x \notin (B \smallsetminus C)$ . Therefore, $x \in A \smallsetminus (B \smallsetminus C)$ . So, $(A \smallsetminus B) \cup C \subseteq A \smallsetminus (B \smallsetminus C)$ .
Therefore, indeed, $A \smallsetminus (B \smallsetminus C) = (A \smallsetminus B) \cup C$ .∎

Prove relationships between complements, unions and intersections for classes of sets

by RoRi

June 22, 2015

Prove that for a class of sets $\mathcal{F}$ we have,

$B \smallsetminus \bigcup_{A \in \mathcal{F}} A = \bigcap_{A \in \mathcal{F}} (B \smallsetminus A) \qquad \text{and} \qquad B \smallsetminus \bigcap_{A \in \mathcal{F}} A = \bigcup_{A \in \mathcal{F}} (B \smallsetminus A).$

Proof. Let $x$ be an arbitrary element of $B \smallsetminus \bigcup_{A \in \mathcal{F}} A$ . This means that $x \in B$ and $x \notin \bigcup_{A \in \mathcal{F}} A$ , which means that $x$ is not in $A$ for any $A$ in the class $\mathcal{F}$ . Hence, for every $A \in \mathcal{F}$ we have $x \in (B \smallsetminus A)$ (since $x$ is in $B$ no matter what, and $x$ is not in $A$ for any $A$ that we choose, so it must be in $B \smallsetminus A$ ). But, $x \in (B \smallsetminus A)$ for all $A \in \mathcal{F}$ means that $x$ is in the intersection $\bigcap_{A \in \mathcal{F}} (B \smallsetminus A)$ ; and hence, $B \smallsetminus \bigcup_{A \in \mathcal{F}} A \subseteq \bigcap_{A \in \mathcal{F}} (B \smallsetminus A)$ .
For the reverse inclusion, let $x$ be any element in $\bigcap_{A \in \mathcal{F}} (B \smallsetminus A)$ . This means that $x \in (B \smallsetminus A)$ for every $A \in \mathcal{F}$ , i.e., $x \in B$ and $x \notin A$ for every $A \in \mathcal{F}$ . Since $x \notin A$ for every $A$ , we then have $x \notin \bigcup_{A \in \mathcal{F}}$ . Hence, $x \in B \smallsetminus \bigcup_{A \in \mathcal{F}}$ . Therefore, $\bigcap_{A \in \mathcal{F}} (B \smallsetminus A) \subseteq B \smallsetminus \bigcup_{A \in \mathcal{F}} A$ .
Hence, $B \smallsetminus \bigcup_{A \in \mathcal{F}} A = \bigcap_{A \in \mathcal{F}} (B \smallsetminus A)$ . ∎

Proof. Let $x$ be any element of $B \smallsetminus \bigcap_{A \in \mathcal{F}} A$ . This means that $x \in B$ and $x \notin \bigcap_{A \in \mathcal{F}} A$ . Further, $x$ not in the intersection of the sets $A \in \mathcal{F}$ means that there is at least one $A \in \mathcal{F}$ , say $A'$ , such that $x \notin A'$ . Since $x \notin A'$ and $x \in B$ , we know $x \in (B \smallsetminus A')$ . Then we can conclude $x \in \bigcup_{A \in \mathcal{F}} (B \smallsetminus A)$ . Thus, $B \smallsetminus \bigcap_{A \in \mathcal{F}} \subseteq \bigcup_{A \in \mathcal{F}} (B \smallsetminus A)$ .
For the reverse inclusion, we let $x$ be any element in $\bigcup_{A \in \mathcal{F}} (B \smallsetminus A)$ . This means there is at least one $A \in \mathcal{F}$ , say $A'$ , such that $x \in (B \smallsetminus A')$ , which means $x \in B$ and $x \notin A'$ . Since $x \notin A'$ , we know $x \notin \bigcap_{A \in \mathcal{F}} A$ ; therefore, $x \in B \smallsetminus \bigcap_{A \in \mathcal{F}} A$ . Hence, $\bigcup_{A \in \mathcal{F}} (B \smallsetminus A) \subseteq B \smallsetminus \bigcap_{A \in \mathcal{F}} A$ .
Therefore, $B \smallsetminus \bigcap_{A \in \mathcal{F}} A = \bigcup_{A \in \mathcal{F}} (B \smallsetminus A).$ ∎

Prove that the complement of an intersection is the union of the complements

by RoRi

June 22, 2015

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

Proof. First, let $x$ be any element in $A \smallsetminus (B \cap C)$ . By definition of complement, this means that $x \in A$ and $x \notin (B \cap C)$ . Since $x \notin (B \cap C)$ we have either $x \notin B$ or $x \notin C$ which implies, coupled with the fact that $x$ is in $A$ , means $x \in (A \smallsetminus B)$ or $x \in (A \smallsetminus C)$ , respectively. Since $x$ is in at least one of these, $x$ is in the union $(A \smallsetminus B) \cup (A \smallsetminus C)$ . Therefore, $A \smallsetminus (B \cap C) \subseteq (A \smallsetminus B) \cup (A \smallsetminus C)$ .
For the reverse inclusion, let $x$ be an arbitrary element of $(A \smallsetminus B) \cup (A \smallsetminus C)$ . Then, either $x \in (A \smallsetminus B)$ or $x \in (A \smallsetminus C)$ .
If $x \in (A \smallsetminus B)$ , then $x \in A$ and $x \notin B$ ; hence, $x \notin (B \cap C)$ . Therefore, $x$ is in $A \smallsetminus (B \cap C)$ . On the other hand, if $x \in (A \smallsetminus C)$ , then $x \in A$ and $X \notin C$ ; hence, $x \notin (B \cap C)$ . This again implies $x$ is in $A \smallsetminus (B \cap C)$ . Therefore, $(A \smallsetminus B) \cup (A \smallsetminus C) \subseteq A \smallsetminus (B \cap C)$ .
Hence, $A \smallsetminus (B \cap C) = (A \smallsetminus B) \cup (A \smallsetminus C)$ .∎

Prove some more statements about sets and subsets

by RoRi

June 21, 2015

Prove that if $A \subset B$ and $B \subset C$ , then $A \subset C$ .
Prove that if $A \subseteq B$ and $B \subseteq C$ , then $A \subseteq C$ .
If $A \subset B$ and $B \subseteq C$ then we claim $A \subset C$ .
If $x \in A$ and $A \subseteq B$ , then $x \in B$ .
What can you say if $x \in A$ and $A \in B$ ?

Proof. Let $x$ be any element in $A$ . Then, $x \in B$ since $A \subset B$ . Further, there is some $y \in B$ such that $y \notin A$ (since $A \subset B$ means that $A$ is a proper subset of $B$ ). Then, since $B \subset C$ we have both $x, y \in C$ . Hence, $A \subset C$ (since every element of $A$ is in $C$ , and there is at least one element of $C$ not in $A$ , so $A \neq C$ ).∎
Proof. Let $x$ be any element of $A$ . Then, $x \in B$ since $A \subseteq B$ . Further, $x \in B$ implies $x \in C$ since $B \subseteq C$ . Thus, $A \subseteq C$ .∎
Proof. This was established in part (a) since we didn’t need $B \neq C$ in that proof. (Since $A$ a proper subset of $B$ guaranteed there was some $y$ in $B$ that wasn’t in $A$ , and since $B$ is a subset, proper or otherwise, of $C$ , this $y$ is in $C$ ; hence, $A$ is a proper subset of $C$ .)∎
Proof. Since $A \subseteq B$ we know every element of $A$ is in $B$ . Hence, if $x \in A$ , then $x \in B$ .∎
If $x \in A$ and $A \in B$ , then we cannot conclude that $x \in B$ . For example, let $A = \{ 1 \}$ and $B = \{ \{ 1 \} \}$ . Then, $A \in B$ (since $A$ is the set $\{ 1 \}$ and $B$ contains this set). However, $1 \in A$ , but $1 \notin B$ (since $B$ contains the set which contains 1, but does not contain the element 1).

If C is a subset of A and B, then it is a subset of their intersection

by RoRi

June 20, 2015

Prove that if $C \subseteq A$ and $C \subseteq B$ , then $C \subseteq A \cap B$ .

Proof. Let $x$ be any element in $C$ . Then, $x \in A$ since $C \subseteq A$ , and $x \in B$ since $B \subseteq C$ . Therefore, $x \in A \cap B$ . Hence, $C \subseteq A \cap B$ .∎

Prove that if A and B are subsets of C, then so is their union

by RoRi

June 20, 2015

Prove that if $A \subseteq C$ and $B \subseteq C$ , then $A \cup B \subseteq C$ .

Proof. Let $x$ be any element in $A \cup B$ . Then, by definition of union, we have $x \in A$ or $x \in B$ . If $x \in A$ , then $x \in C$ since $A \subseteq C$ . On the other hand, if $x \in B$ , then $x \in C$ as well since $B \subseteq C$ . Hence, $A \cup B \subseteq C$ .∎

Yet more proofs on intersections and unions of sets

by RoRi

June 20, 2015

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

Proof. First, it is clear that $A \subseteq A \cup (A \cap B)$ (see Exercise 12 of Section I.2.5, or simply note that $x \in A$ implies $x \in A \cup (A \cap B)$ since $x$ is in $A$ ).
For the reverse inclusion, if $x$ is any element of $A \cup (A \cap B)$ then $x \in A$ or $x \in (A \cap B)$ . But $x \in A \cap B$ implies $x \in A$ (and $x \in B$ ). So, in either case $x \in A$ ; hence, $A \cup (A \cap B) \subseteq A$ .
Therefore, $A \cup (A \cap B) = A$ .∎

Proof. From Exericse 12 (Section I.2.5) we know that $A \cap C \subseteq A$ for any set $C$ ; hence, $A \cap (A \cup B) \subseteq A$ .
For the reverse inclusion, if $x$ is any element in $A$ , then $x \in A$ and $x \in A \cup B$ ; hence, $x \in A \cap (A \cup B)$ . Therefore, $A \cap (A \cup B) \subseteq A$ .
Hence, $A \cap (A \cup B) = A$ .∎

Union and intersection of a set with the empty set

by RoRi

June 20, 2015

Prove that $A \cup \varnothing = A$ and that $A \cap \varnothing = \varnothing$ .

Proof. If $x \in A \cup \varnothing$ , then $x \in A$ or $x \in \varnothing$ by definition of union. Since $x \notin \varnothing$ (by definition of $\varnothing$ ), we must have $x \in A$ . Hence, $A \cup \varnothing \subseteq A$ .
On the other hand, if $x \in A$ , then $x \in A \cup \varnothing$ by definition of union, so $A \subseteq A \cup \varnothing$ .
Therefore, $A \cup \varnothing = A$ .∎

Proof. If $x \in A \cap \varnothing$ , then by definition of intersection $x \in A$ and $x \in \varnothing$ . But, by definition of $\varnothing$ , there is no $x$ such that $x \in \varnothing$ . Hence, $A \cap \varnothing$ must be empty. By uniqueness of the empty set then, we have $A \cap \varnothing = \varnothing$ .∎

Prove some more relations between sets

by RoRi

June 20, 2015

Prove that $A \subseteq A \cup B$ and that $A \cap B \subseteq A$ .

Proof. If $x$ is any element of $A$ , then by definition of $A \cup B$ , we have $x \in A \cup B$ (since $A \cup B$ is the set of elements in either $A$ or $B$ ). Thus, $A \subseteq A \cup B$ . ∎

Proof. If $x$ is any element of $A \cap B$ , then $x \in A$ since $A \cap B$ is defined to be the set of elements that are in both $A$ and $B$ . Therefore, $A \cap B \subseteq A$ . ∎