Set Equation: Union

Theorem

Let $A$ and $B$ be sets.

Consider the set equation:

$A \cup X = B$

The solution set of this is given by:

$X = \begin {cases} \O & : A \nsubseteq B \\ \set {\paren {B \setminus A} \cup Y: Y \subseteq A} & : \text {otherwise} \end {cases}$

Proof

In the first case $A$ is a not a subset of $B$.

So there exists an $x \in A$ such that $x \notin B$.

By the definition of union:

$\forall x: x \in A \implies x \in A \cup X$

Hence the solution set is empty.

In the second case, suppose $A$ is a subset of $B$.

Work In Progress You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by completing it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{WIP}} from the code.

In particular, suppose $A$ is a subset of $B$, and $B$ is the empty set.

By Subset of Empty Set:

$A = \O$.

Then, by hypothesis:

\(\ds A \cup X\)

\(=\)

\(\ds B\)

by hypothesis

\(\ds \leadsto \ \ \)

\(\ds \O \cup X\)

\(=\)

\(\ds \O\)

by hypothesis and result shown above

\(\ds \leadsto \ \ \)

\(\ds X\)

\(=\)

\(\ds \O\)

Union of Empty Set

Hence, by Empty Set is Subset of All Sets:

$X = \O \in \set {\paren {B \setminus A} \cup Y: Y \subseteq A}$

as required.

Suppose $A$ is a subset of $B$ and $B$ is non-empty.

By definition of a subset:

$A \subseteq B \iff \forall x: \paren {x \in A \implies x \in B}$

Then, by hypothesis and the Axiom of Extension:

$\forall x: \paren {x \in A \cup X \iff x \in B }$

It follows that:

$\forall x: x \notin B \implies \neg {\paren {\paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} } }$

By Proof by Contraposition:

$\forall x: \paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} \implies x \in B$

Then:

$\forall x: \paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} \implies x \in \paren{\paren{B \cup A } \setminus A }$

By Set is Subset of Itself and the definition of existential quantifier:

$\forall x: \paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} \implies \exists A \subseteq A: x \in \paren{\paren{B \cup A } \setminus A }$

Then, let $Y \subseteq A$ be arbitrary, such that:

$\forall x: \paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} \implies \exists Y \subseteq A: x \in \paren{\paren{B \cup Y } \setminus A }$

By definition of set union:

$\forall x: \paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} \implies \exists Y \subseteq A: \paren{x \in Y \setminus A } \lor \paren{x \in B \setminus A }$

By Set is Subset of Union:

$\forall x: \paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} \implies \exists Y \subseteq A: \paren{x \in Y \setminus A } \lor \paren{x \in Y } \lor \paren{x \in B \setminus A }$

By Union is Commutative:

$\forall x: \paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} \implies \exists Y \subseteq A: \paren{x \in Y \setminus A } \lor \paren{x \in B \setminus A } \lor \paren{x \in Y }$

By definition of set complement:

$\forall x: \paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} \implies \exists Y \subseteq A: \paren{\paren{\paren {x \in Y } \land \paren{x \notin A } } \lor \paren{x \in B \land x \notin A } \lor \paren{x \in Y } }$

By Double Negation/Double Negation Elimination/Proof Rule:

$\forall x: \paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} \implies \exists Y \subseteq A: \paren{\neg \paren{\neg \paren{\paren {x \in Y } \land \paren{x \notin A } } } \lor \paren{x \in B \land x \notin A } \lor \paren{x \in Y } }$

By definition of implication:

$\forall x: \paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} \implies \exists Y \subseteq A: \paren{\neg \paren{\paren {x \in Y } \land \paren{x \notin A } } \implies \paren{x \in B \land x \notin A } \lor \paren{x \in Y } }$

By De Morgan's Laws for Set Complement of Intersection:

$\forall x: \paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} \implies \exists Y \subseteq A: \paren{ \neg \paren{\paren {x \in Y } \lor \paren{x \in A } } \implies \paren{x \in B \land x \notin A } \lor \paren{x \in Y } }$

By definition of set complement:

$\forall x: \paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} \implies \exists Y \subseteq A: \paren{ \neg \paren{\paren {x \in Y } \lor \paren{x \in A } } \implies \paren{x \in B \setminus A } \lor \paren{x \in Y } }$

By definition of implication:

$\forall x: \paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} \implies \exists Y \subseteq A: \paren{\paren{x \in Y \implies x \in A} \implies \paren{x \in B \setminus A } \lor \paren{x \in Y } }$

By definition of set union:

$\forall x: \paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} \implies \exists Y \subseteq A: \paren{\paren{x \in Y \implies x \in A} \implies x \in \set{ \paren{ B \setminus A } \cup Y } }$

By definition of subset:

$\forall x: \paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} \implies \exists Y \subseteq A: \paren{ x \in Y \implies x \in \set{ \paren{ B \setminus A } \cup Y } }$

By definition of set-builder notation:

$\forall x: \paren {x \in A \implies x \in B} \land \paren {x \in A \cup X \iff x \in B} \implies x \in \set {\paren{B \setminus A} \cup Y :Y \subseteq A }$

Hence:

$\forall X: A \subseteq B \land \paren {A \cup X = B} \implies X = \set {\paren {B \setminus A} \cup Y :Y \subseteq A }$

as required.

$\Box$

This theorem requires a proof. In particular: formalising the second case You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.