Set Theory

Prove the identities:

Prove that the following identities hold for the universal set $X$ and $A, B, C \subset X$.

Prove that the following identities hold for the universal set $X$ and $A, B, C \subset X$.

Prove that $A \backslash B \subset (A \backslash C) \cup (C \backslash B)$.

Prove that $A \triangle B \subset (A \triangle C) \cup (C \triangle B)$.

Prove that $A \backslash (B \cap C) \subset (A \backslash B) \cup ((A \cap B) \backslash C)$.

Prove that $A \backslash B=\left(A^{C} \cup B\right)^{C}$.

Prove that $A \cap \left(E_{1} \cup E_{2}\right)=\left(A \cap E_{1}\right) \cup \left(A \cap E_{2} \cap E_{1}^{C}\right)$.

Prove that $(A \cup B) \triangle (C \cup D) \subset (A \triangle C) \cup (B \triangle D)$.

Prove that $(A \triangle B)=A^{C} \triangle B^{C}$.

Prove that $(A \cap B) \triangle (C \cap D) \subset (A \triangle C) \cup (B \triangle D)$.

Suppose that $E \subset U \cup V$. Prove that $E \backslash (A \cup B) \subset (U \backslash A) \cup (V \backslash B)$.

Suppose that $A \cap B \subset C$. Prove that $A \backslash C \subset A \backslash B$.

Prove that $(A \triangle B) \triangle B=A$.

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

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

Suppose that $A \subset C$. Prove that $A^{C} \cap B^{C}=(B \cup C)^{C} \cup (C \backslash (A \cup B))$.

Prove that $\left[(A \cap S) \cup \left(B \cap S^{C}\right)\right]^{C}=\left(A^{C} \cap S\right) \cup \left(B^{C} \cap S^{C}\right)$.

Prove that $(A \backslash B) \triangle (C \backslash D) \subset (A \triangle C) \cup (B \triangle D)$.

Let $\left\{ A_{n}\right\}_{n=1}^{\infty }$ and $\left\{ B_{n}\right\}_{n=1}^{\infty }$ be arbitrary collections of sets and $A= \cup_{n=1}^{\infty } A_{n}, B=\cup_{n=1}^{\infty } B_{n}$. Prove that

Let $\left\{ A_{n}\right\}_{n=1}^{\infty }$ be an arbitrary collection of sets. Prove that

Let $\left\{ A_{n}\right\}_{n=1}^{\infty }$ and $\left\{ B_{n}\right\}_{n=1}^{\infty }$ be decreasing collections of sets (meaning that $A_{n} \supset A_{n+1}$ and $B_{n} \supset B_{n+1}$ for all $n \in \mathbb {N}$ ).

Let $A_{0}$ be a set and let $A_{n} \subset A_{0}$ for all $n \in \mathbb {N}$. Prove that

Let $X$ be a set and $\left\{ E_{n}\right\}_{n \in \mathbb {N}}$ subsets of $X$. Let $A_{1}=E_{1}$ and, for $k \geq 2, A_{k}=E_{k} \backslash \left(E_{1} \cup E_{2} \cup \cdots \cup E_{k-1}\right)$. Prove that $\left\{ A_{k}\right\}_{k=1}^{\infty }$ is a sequence of pairwise disjoint sets and that $\cup_{k=1}^{\infty } A_{k}=\cup_{k=1}^{\infty } E_{k}$.

Let $\left\{ E_{n}\right\}$ be subsets of $X$. Prove that

Let $\left\{ A_{n}\right\}_{n=1}^{\infty }$ and $\left\{ B_{n}\right\}_{n=1}^{\infty }$ be arbitrary collections of sets. Prove that:

Let $\left\{ A_{n}\right\}_{n=1}^{\infty }$ be an arbitrary collection of sets. Prove that:

Prove that $\limsup_{n \rightarrow \infty } E_{n}=\left\{ x: x \in E_{i} \text{ for infinitely many } i\right\}$.

Prove that $\liminf_{n \rightarrow \infty } E_{n}=\left\{ x: x \in E_{i} \text{ for all but finitely many } i\right\}$.

Calculate $\limsup E_{n}$ and $\liminf E_{n}$ if $E_{n}=(-1 / n, 1-1 / n]$.

Calculate $\limsup E_{n}$ and $\liminf E_{n}$ if $E_{n}=\left((-1)^{n} / n, 1-(-1)^{n} / n\right]$.

Calculate $\limsup E_{n}$ and $\liminf E_{n}$ if $E_{n}=\left\{ 0,1 / n, 2 / n, \ldots ,(n- 1) / n, 1\right\}$.

Let $\left\{ E_{n}\right\}$ be subsets of $X$ and let $\left\{ A_{n}\right\}$ be a subsequence of $\left\{ E_{n}\right\}$ obtained by discarding the first $N$ members, i.e., $A_{1}=E_{N+1}, A_{2}=E_{N+2}$, etc. Prove that

Let $f: X \rightarrow Y$ and $A, B \subset X$. Prove that:

Let $f: X \rightarrow Y$, let $A \subset X$, and $B \subset Y$. Prove that:

Let $f: X \rightarrow Y$ and $A, B \subset X$. Prove that:

Let $f: X \rightarrow Y$ and $A, B \subset Y$. Prove that

Let $f: X \rightarrow Y, A \subset X$, and $B \subset Y$. Prove that $f\left(A \cap f^{-1}(B)\right)= f(A) \cap B$.

Let $f: X \rightarrow Y$, let $X_{0} \subset X$, let $f_{0}$ be the restriction of $f$ to $X_{0}$, and let $E \subset Y$. Prove that:

Let $f: X \rightarrow Y$, let $\left\{ A_{i}\right\}_{i \in I}$ be a collection of subsets of $X$, and let $\left\{ B_{i}\right\}_{i \in I}$ be a collection of subsets of $Y$. Prove that:

Let $\left\{ A_{i}\right\}_{i \in I}$ and $\left\{ B_{i}\right\}_{i \in I}$ be subsets of $X$. Prove that

Let $f: X \rightarrow \mathbb {R}$ and let $A, B \subset X$. Prove that:

Prove that every infinite subset of a countable set is countable.

Prove that $\operatorname {card}[0,1]=\operatorname {card}[0,1)=\operatorname {card}(0,1)=\operatorname {card}[a, b]$, if $a<b$.

Suppose that $A$ is an infinite set and $F$ is a finite subset of $A$. Prove that $\operatorname {card} A \backslash F=\operatorname {card} A$.

Prove that a countable union of finite sets is countable.

Prove that a countable union of pairwise disjoint, countable sets is countable.

Prove that the plane $\mathbb {R}^{2}$ is not the union of a countable number of lines.

Prove that $\operatorname {card} \mathbb {R}=\operatorname {card} \mathbb {R}^{n}$, for all $n \in \mathbb {N}$.

Let $A$ be the set of all real numbers in ( 0,1 ) that have infinitely many threes in their decimal expansion. Prove that $\operatorname {card} A=\operatorname {card}(0,1)$.

Prove that for any set $A, \operatorname {card} A<\operatorname {card} \mathbb {P}(A)$, where $\mathbb {P}(A)$ is the collection of all subsets of $A$, including the empty set and $A$ itself.

Prove that the collection of ordinals is well-ordered.

Let $S$ be a subset of a well-ordered set $A$ and suppose that:

1. $S$ contains $a_{0}:=\min A$.

2. If $a \in A$ and $s(a) \subset S$ then $a \in S$.

Prove that $S=A$.

Let $A$ be a well-ordered set and $S=\left\{ s(a): a \in A\right\}$, ordered with inclusion. Prove that $f: A \rightarrow S$, defined by $f(x)=s(x)$ is an order isomorphism.

Let $A, B$ be well-ordered sets that are order isomorphic. Prove that there is only one order isomorphism $f: A \rightarrow B$.

Prove that a well-ordered set cannot be ordered isomorphic to one of its initial segments.

Prove that two different initial segments of a well-ordered set cannot be order isomorphic.

Let $\lambda , \mu$ be ordinal numbers, $\lambda =\operatorname {ord} A$, and let $\mu <\lambda$. Prove that there is a unique $a \in A$ such that $\mu =\operatorname {ord} s(a)$.

Let $s(\lambda )$ be the set of ordinal numbers smaller than the ordinal $\lambda$. Prove that $\lambda =\operatorname {ord} s(\lambda )$.

Prove that an arbitrary cartesian product of nonempty sets is nonempty.

Prove that the union of a countable collection of countable sets is countable.

Prove that every surjection has a right inverse.

Let $R$ be a subset of $A \times B$ such that for every $a \in A$ there is $b \in B$ for which $(a, b) \in R$. Prove that there is $F \subset R$ that defines a function from $A$ to $B$, i.e., for every $a \in A$ there is exactly one $b \in B$ for which $(a, b) \in F$.