An Elementary Problem About Sets

Question

$A, B, A', B'$ are finite sets, $A \subset A'$, $B \subset B'$, and$$ |A'| = |A| + 1, \quad |B'| = |B| + 1. $$ If $A$ is a proper subset of $B'$, $B$ is a proper subset of $A'$, prove that $A = B$ or $A' = B'$.

Answer 1

$A,B^{\prime}$ are finite, $A$ is a proper subset of $B^{\prime}\Rightarrow\left|A\right|<\left|B^{\prime}\right|=\left|B\right|+1\Rightarrow\left|A\right|\leq\left|B\right|$

$B,A^{\prime}$ are finite, $B$ is a proper subset of $A^{\prime}\Rightarrow\left|B\right|<\left|A^{\prime}\right|=\left|A\right|+1\Rightarrow\left|B\right|\leq\left|A\right|$

So, we have $\left|A\right|=\left|B\right|$.

Because the sets are finite so $\left(\left|A^{\prime}\right|=\left|A\right|+1\right)\wedge\left(A\subset A^{\prime}\right)\Rightarrow\left(\exists m\in A^{\prime}\right)\left(\left\{ m\right\} \cup A=A^{\prime}\right)$

Similarly, $\left(\left|A^{\prime}\right|=\left|B\right|+1\right)\wedge\left(B\subset A^{\prime}\right)\Rightarrow\left(\exists n\in A^{\prime}\right)\left(\left\{ n\right\} \cup B=A^{\prime}\right)$.

If $m=n\Rightarrow A=B$.

If $m\neq n\Rightarrow A^{\prime}\setminus\left\{ m\right\} =A=\left(\left\{ n\right\} \cup B\right)\setminus\left\{ m\right\} =\left\{ n\right\} \cup\left(B\setminus\left\{ m\right\} \right)\Rightarrow n\in A$. Similarly, we have $m\in B$, so $\left\{ m\right\} \cup A\cup\left\{ n\right\} \cup B=A^{\prime}=A\cup B$.

Apply the same steps with the the case of set $B^{\prime}$, we have $B^{\prime}=A\cup B$, then $A^{\prime}=B^{\prime}$.

Answer 2

Setup: The OP's hypotheses.
Task: Prove that $A = B$ or $A' = B'$.

To begin, observe the following:

If $A$ is a proper subset of $B'$, then $|A| \lt |B'| = |B| + 1$. So $|A| \le |B|$. Similarly, $|B| \le |A|$. So both $A$ and $B$ have the same number of elements, which we denote by $n$. So $A'$ and $B'$ also have the same number, $n + 1$, of distinct elements.

All that is required now is to show that if $A' \ne B'$, then $A$ and $B$ are identical sets. We claim that the intersection of $A'$ with $B'$ contains exactly $n$ elements. The number of elements in the intersection is certainly strictly less than $n + 1$. But since $A$ is contained in both $A'$ and $B'$, so the number of elements in $A' \cap B'$ contains exactly $n$ elements, and must in fact be equal to $A$. Similarly, the intersection must be equal to $B$. Therefore, $A$ must be equal to $B$

Answer 3

Some observations:

• The assumptions on the cardinalities of the sets imply that $A' = A \cup \{ a \}$ and $B' = B \cup \{ b \}$ for some $a,b$ with $a \not\in A$ and $b \not\in B$. Intuitively this is clear, but you can prove it by induction or using the addition principle.

• Write $m=|A|$ and $n=|B|$. The assumptions that $B \subsetneqq A'$ and $A \subsetneqq B'$ tell you that $m<n+1$ and $n<m+1$. The only way this is possible is if $m=n$.

Now either $A \subseteq B$ or $A \nsubseteq B$.

• If $A \subseteq B$ then $A=B$.
• If $A \nsubseteq B$ then also $B \nsubseteq A$ (since $B \subseteq A$ would also imply $A=B$). Hence $A = B' \setminus \{b'\}$ for some $b' \ne b$ and $B = A' \setminus \{ a' \}$ for some $a' \ne a$. It is now straightforward to deduce that $A'=B'$ in this case.

Answer 4

Let $A'=A\cup\{u\}$, $B'=B\cup\{v\}$ with $u\notin A$, $v\notin B$.

If $v\notin A \ \wedge\ u\notin B$ then $A\subset B'$ and $B\subset A'$ imply $A\subset B$ and $B\subset A$, hence $A=B$.

If, e.g., $v\in A$ then $A\subsetneq B'$ implies that there is a $b\in B\setminus A$, so that from $B\subset A'$ we conclude $b=u$, or $u\in B$. From $B\subset A'$ and $v\notin B$ we then infer $B\setminus\{u\}\subset A\setminus\{v\}$, and by symmetry we also have $A\setminus\{v\}\subset B\setminus\{u\}$, so that $$B\setminus\{u\}=A\setminus\{v\}\ .\tag{1}$$ Take the union with $\{u\}\cup\{v\}$ on both sides of $(1)$, and obtain $A'=B'$.