# Proving Existence/Uniqueness of a Set.

1. Aug 24, 2014

### pandaBee

1. The problem statement, all variables and given/known data
Let U be any set.
(a) Prove that for every A ∈ P (U) there is a unique B ∈ P (U) such
that for every C ∈ P (U), C \ A = C ∩ B.
Remark: P(U) = the Power set of U, i.e. A ∈ P (U) then A⊆U

2. Relevant equations

3. The attempt at a solution
The question's form is as follows:
∀A(A∈P(U)⇒∃!B(Q(B)))
Where Q(B) = B∈P(U)∧∀C(C∈P(U)⇒C\A=C∩B)
I first let A be an arbitrary element, then
A∈P(U)⇒∃!B(Q(B))

Suppose A⊆U, then I want to prove ∃!B(Q(B))

Existence: I want to prove ∃B(Q(B))
Uniqueness: I want to prove that, ∀r∀s(Q(r)∧(Q(s)⇒r=s)

To find a B such that Q(B) is true, I consider all subsets of U and their relation to A in order to find a suitable B using the hint C\A=C∩B
Let u be an arbitrary subset of U

Since both A and the subsets of U are both subsets of U, then there are two possibilities: either A∩u=∅∨A∩u≠∅
In the first case u\A is just u, therefore B can be any set such that u⊆B since u∩B=u =u\A
In the second case u\A = some subset of u, say u’ since u∩A≠∅. We want to find the choices for B such that u∩B = u’. Therefore B can be any set that does not contain u∩A and contains u’; For example: U\A, or U\(u∩A)

Even considering these choices for B, I cannot narrow it down to a choice where B satisfies Q(B) since the possibilities for B in both cases are case-specific and do not apply to both cases. This is where I’m stuck, any hints or even the solution would be much appreciated. I feel like I’m overlooking something simple and that I might be over-complicating things.

2. Aug 24, 2014

### pasmith

Your statement here is simply "either A is empty or it isn't".

The best way to prove existence of B is to find a B which works. So consider B = U \ A. Then for any subset C, we can partition C into disjoint subsets $C \cap A$ and $C \cap B$. Then $C \setminus A = C \cap B$ as required.

It remains to show that B = U \ A is the only possibility. That's straightforward: $C \setminus A = C \cap B$ must hold for all $C \subset U$, so in particular it holds for $C = U$.