5
$\begingroup$

I managed to prove existence for the following theorem: $$\forall A\in\mathcal{P}(U)\ \exists!B\in\mathcal{P}(U)\ \forall C\in\mathcal{P}(U)\ (C\setminus A=C\cap B)$$ where U is any set. My assumption is that $B=U\setminus A$, and it works for existence, but I'm stuck with proving uniqueness part with $B$ being defined this way.

For uniqueness we need to prove $$\forall B'\in\mathcal{P}(U)\ \forall C\in\mathcal{P}(U)\ (\ (C\setminus A=C\cap B')\rightarrow B'=B)$$ where A is arbitrary element of $\mathcal{P}(U)$ but I don't how to connect $x\in B'$ or $x\in B$ to the assusmed identitiy $C\setminus A=C\cap B'$.

Any pointers are much appreciated.

EDIT

Here is my attempt of proof.

Proof: Let $A$ be an arbitrary element of $\mathcal{P}(U)$ and let $B=U\setminus A$.
Existence: Let $C$ be an arbitrary element of $\mathcal{P}(U)$. $(\rightarrow)$ Let $x$ be an arbitrary element of $C\setminus A$. Since $C\subseteq U$, then $x\in U\setminus A$. Therefore $x\in C\cap B$. $(\leftarrow)$ Let x be an arbitrary element of $C\cap B$. Then $x\in C\cap (U\setminus A)$, so we can conclude $x\in C\setminus A$.
Uniqueness: Let $B'$ be an arbitrary element of $\mathcal{P}(U)$ and suppose $\forall C\in\mathcal{P}(U)(C\setminus A=C\cap B')$.
$(B'\subseteq B)$ Since $B'\in\mathcal{P}(U)$, then in particular $B'\setminus A=B'\cap B'=B'$, so clearly $B'\cap A=B'\cap (U\setminus B)=\varnothing$. Then $\forall x(x\not\in B'\lor x\not\in U\lor x\in B)$, which is equivalent to $\forall x(x\in B'\cap U\rightarrow x\in B$). Since $B'\subseteq U$, $B'\cap U=B'$, we now have $\forall x(x\in B'\rightarrow x\in B)$, and therefore $B'\subseteq B$.
$(B\subseteq B')$ Let $C=B$. Then $B\setminus A=B\cap B'$, and because $B\cap A=\varnothing$, we have $B=B\cap B'$, so we can conclude $B\subseteq B'$.

  • 2
    If you have $B'\setminus A=B'\cap B'=B'$, then $A$ doesn't share a single element with $B'$, they are disjoint. That's where $B'\cap A=B'\cap (U\setminus B)=\varnothing$ is coming from. Although $A=U\setminus B$ seems arbitrary actually comes from the $B=U\setminus A$ proof of which is left out. In the $(B\subseteq B')$, $B\cap A=\varnothing$ comes from the assumed $B=U\setminus A$, and because they're disjoint, $B\setminus A=B$. There is no favourable answer to your last question. It's just long hours, experimentation, and experience. I hate there's no real method to it, but it is what it is.2016-04-05
  • 0
    @DanielMak In your bounty comment you say, among other things: "For example, how does one know letting B=U∖A and C=B would work?" Have you checked my answer, for a way to _calculate_ that U∖A is _the_ value for B?2016-04-07
  • 0
    @MarnixKlooster I tried understanding your answer, but unfortunately I don't understand the notations you are using; obviously I understand those that are written in standard 1st order logic and set theory but others like '::' are things I have never seen before2016-04-08
  • 0
    @LavaScornedOven If only I could reward you with the bounty; your comment has resolved most of my confusions! I only have two quick follow ups: A=U∖B: How did you know? I can prove it by proving ∀x(x∈A↔x∈U∖B), but I am sure you didn't do it this way, somehow I think you proved by deducing from the meaning of these formulae alone, I tried really hard but I still couldn't crack it, could you give me a hint please? B∩A=∅: Is it because if B=U∖A then B∩A=U∖A ∩ A, i.e. ∀x(x∈U∧~x∈A∧x∈A), and ~x∈A∧x∈A implies nothing can satisfy this (and thus no member - empty set)? Thank you so much! orz2016-04-09
  • 0
    You can show $A=U\setminus B$ with $$U\setminus B=U\cap B^C=U\cap (U\setminus A)^C=U\cap(U\cap A^C)^C=U\cap(U^C\cup (A^C)^C)=U\cap(U^C\cup A)=U\cap A=A$$ I tried to leave every step so you could follow the proof more easily. Note that the proof uses just basic set alebra (see [Algebra of Sets](https://en.wikipedia.org/wiki/Algebra_of_sets)). As for $B\cap A=\varnothing$, by applying set algebra, $$B\cap A=(U\setminus A)\cap A = U\cap A^C\cap A=U\cap\varnothing=\varnothing$$ which is similar to your approach, but avoids dealing with set elements.2016-04-12

5 Answers 5

0

I think this even might be an easier proof:

Proof.

Existence. Let $A$ be an arbitrary element of $\mathscr P(U)$ and let $B = U\setminus A ∈ \mathscr P(U)$. Then clearly for every $C ∈ \mathscr P(U)$, $C ∩ B = C ∩ U\setminus A = C\setminus A$.

Uniqueness. Let $A$ be an arbitrary element of $\mathscr P(U)$. To see that $B$ is unique, suppose that $B' ∈ \mathscr P(U)$ and for all $C ∈ \mathscr P(U)$, $C\setminus A = C ∩ B'$. Then in particular, taking $C = U$, we can conclude that $U\setminus A = U ∩ B' = B'$. So we have $B' = U\setminus A = B.$

5

HINT: An easier way is to show that if $B\ne U\setminus A$, there is a $C\in\wp(U)$ such that $C\setminus A\ne C\cap B$. You’ll want to consider two cases, $B\cap A\ne\varnothing$ (loosely, ‘$B$ is too big’) and $A\cup B\ne U$ (loosely, ‘$B$ is too small’).

4

Hint: Plug $B$ into the $C$ from the $B'$ assertion to get that $B\setminus A\subseteq B'$, and similarly for $B'$ into $C$ from the $B$ assertion, to have $B'\setminus A\subseteq B$.

Now show that $B'\setminus A=B'$ and $B\setminus A=B$ (plug $C=\varnothing$ into both assertions) and you are done.

  • 0
    I don't see any inference rule that would bring me from supposing $x\in B$ or $x\in B'$ to $x\in C$ or $x\not\in C$, except for proving by cases $x\in C$ and $x\not\in C$. If not going for elementhood, how exactly do I plug B or B' into C?2012-12-08
  • 2
    If the claim is true for **all** $C$ then it is true for $C=B'$, for example, therefore $B'\setminus A=B\cap B'$. Show that $B'\setminus A=B'$ then you have that $B'=B\cap B'$; similarly $B=B\cap B'$. From this you can directly deduce the conclusion of equality.2012-12-08
  • 0
    Oh, I see. (Palmface...) :) I missed the fact that I can plug into $C\setminus A=C\cap B'$ whatever I wont from $\mathcal{P}(U)$. Thanks for the help.2012-12-08
  • 0
    No problem! (I think it's facepalm, by the way, not palmface :-))2012-12-08
  • 4
    Facepalm would do, but check this out: http://d24w6bsrhbeh9d.cloudfront.net/photo/3657230_700b.jpg2012-12-08
  • 0
    I added a proof attempt to my original question, and I would be very grateful if you could proofread it. I don't want to spread lies across the Internet... :)2012-12-10
  • 0
    @Verdan: It looks okay except that $B'\subseteq B$. If it is arbitrary you don't know it yet, you need to show it. However I have a much simpler idea (now). Simply write:$${}$$If the property holds for all $C$, then it holds for $U$ and therefore $U\setminus A=U\cap B'=B'$. Therefore $B'=U\setminus A$.2012-12-10
  • 0
    @Vedran: I misunderstood what the $(B'\subseteq B)$ was all about, but now I got it. It looks good. Although to be fair the method in my previous comment just shows that any set with this property has to be equal to $U\setminus A$, and so uniqueness is automatically proved.2012-12-10
  • 0
    Great. I had the same idea, but I was unable to show why a special case for $C$ makes a general assertion about $B'$.2012-12-10
  • 0
    Hi, sorry I know this is an old thread, but I have some questions: 1. I can't follow what's happening in OP's (B′⊆B) proof. To be precise, the step: B′∩A=B′∩(U∖B)=∅ and anything after that. Would you mind explaining a bit please? 2. In OP's (B⊆B′) proof, why is B∩A=∅? I don't understand the steps after that either, presumably because I don't understand the preceding step.2016-03-27
  • 0
    3. Strategy wise, how do you determine what to assume? e.g. letting B=U∖A and C=B. I am struggling immensely on set uniqueness proofs largely because I just don't know what to assume. Thank you so much!2016-03-27
  • 0
    I am not sure why the downvote. But whatever...?2016-04-03
  • 0
    @AsafKaragila I am not the one who down voted you; in fact I am up voting your answer now (which is impossible to do if I did down vote you as your answer hasn't been edited since the original version, the system would not allow such action) But may I ask if you can advise me a little on my confusion please?2016-04-05
  • 2
    @Daniel: I didn't think it was you. Sorry I didn't reply to you. I wanted to tell you that you should ask these questions as a separate thread; but I forgot and it slipped my mind, and then you already set the bounty so it was futile.2016-04-05
  • 0
    @AsafKaragila I was thinking about opening a new thread, but according a MetaMathStack thread apparently I am not supposed to (may get labeled as duplicate?), and should resort to bounty instead. I think if you edit the answer to add in extra bits, I can still give you the bounty haha2016-04-05
3

Here is my attempt at a direct proof for this theorem. Note that $A$, $B$, etc. denote subsets of our 'universe' $U$, and $x$ denotes an element of U.

We start out by simplifying everything inside $\exists!$, as follows: $$ \begin{align*} & \langle \forall C :: C \setminus A \;=\; C \cap B \rangle \\ \equiv & \;\;\;\;\;\text{"extensionality; definitions of $\setminus$ and $\cap$"} \\ & \langle \forall C :: \langle \forall x :: x \in C \land x \notin A \;\equiv\; x \in C \land x \in B \rangle \rangle \\ \equiv & \;\;\;\;\;\text{"logic: move $x \in C$ out of $\equiv$, then into range"} \\ & \langle \forall C :: \langle \forall x : x \in C : x \not\in A \equiv x \in B \rangle \rangle \\ \equiv & \;\;\;\;\;\text{"logic: what Dijkstra calls shunting"} \\ & \langle \forall x : \langle \exists C :: x \in C \rangle : x \not\in A \equiv x \in B \rangle \\ \equiv & \;\;\;\;\;\text{"range is true: take $C:=\lbrace x \rbrace$"} \\ & \langle \forall x :: x \not\in A \equiv x \in B \rangle \\ \equiv & \;\;\;\;\;\text{"definition of complement; extensionality"} \\ & B = A^c \\ \end{align*} $$ This trivially proves existence and uniqueness, but for completeness I will spell it out anyway. Using the following not-so-well-known definition of $\exists!$ (where $w$ is a fresh variable) $$ \langle \exists! v :: P \rangle \;\equiv\; \langle \exists w :: \langle \forall v :: P \:\equiv\: v=w \rangle \rangle $$ the original theorem is proven as follows: $$ \begin{align*} & \langle \forall A :: \langle \exists! B :: \langle \forall C :: C \setminus A \;=\; C \cap B \rangle \rangle \rangle \\ \equiv & \;\;\;\;\;\text{"by the above calculation"} \\ & \langle \forall A :: \langle \exists! B :: B = A^c \rangle \rangle \\ \equiv & \;\;\;\;\;\text{"by the above definition"} \\ & \langle \forall A :: \langle \exists B' :: \langle \forall B :: B = A^c \:\equiv\: B = B' \rangle \rangle \rangle \\ \Leftarrow & \;\;\;\;\;\text{"what Dijkstra calls Leibniz' rule"} \\ & \langle \forall A :: \langle \exists B' :: A^c = B' \rangle \rangle \\ \equiv & \;\;\;\;\;\text{"logic: what Dijkstra calls the one-point rule"} \\ & \langle \forall A :: \mathrm{true} \rangle \\ \equiv & \;\;\;\;\;\text{"logic"} \\ & \mathrm{true} \\ \end{align*} $$

Hope this helps...

  • 0
    Where could I find material with that proving "style"? It looks interesting to explore.2013-03-19
  • 0
    @LavaScornedOven See the note at the end of [another answer of mine](http://math.stackexchange.com/a/332186)./11994.2013-03-19
  • 0
    Thanks for the reply. I'm currently investigating different approaches, and your suggestion comes as very helpful.2013-03-20
3

Let $B := U \setminus A$.
Let $B' \subseteq U$ be any subset that satisfies the hypothesis: $\forall C \in \mathcal P(U) (C \setminus A = C \cap B')$

Case I:
Assume $x \in B' \setminus B$.

\begin{align*} \implies & x \in A \\ \text{Let } & C = \{x\} \\ \implies & \left( C \setminus A \right) = \varnothing \ne C = \left( C \cap B' \right) \\ \implies & \impliedby (contradiction) \end{align*}

Case II:
Assume $y \in B \setminus B'$.

\begin{align*} \implies & y \notin A \\ \text{Let } & C = \{y\} \\ \implies & \left( C \setminus A \right) = C \ne \varnothing = \left( C \cap B' \right) \\ \implies & \impliedby (contradiction) \end{align*}

$\implies B'=B$ is unique.