Proving $Y \setminus (Y\setminus B) = B$

[Guest2]

Problem: Let $B$ be a subset of $Y$, prove that $Y \setminus (Y\setminus B) = B$.

Attempt: Since we're given $B \subset Y$, I tried to show $Y \subset B$. Let $a \in Y \setminus (Y\setminus B)$. Then $a \not \in Y\setminus B. $ I'm unable to manipulate this to $a \in B$ -- because it seems perfectly possible for $a$ to be in neither $Y \setminus B$ nor $B$.

 

[Plato2]

Problem: Let $B$ be a subset of $Y$, prove that $Y \setminus (Y\setminus B) = B$.

$$\begin{align*} Y\setminus(Y\setminus B)&=Y\cap(Y\cap B^c)^c \\ &= Y\cap(Y^c\cup B)\\&=(Y\cap Y^c)\cup(Y\cap B) \\&=\emptyset\cup B\\&=B \end{align*}$$

 

[Guest2]

Thanks. De Morgan's laws are not available to me. Is it possible to prove it without De Morgan's laws?

 

[Plato2]

Thanks. De Morgan's laws are not available to me. Is it possible to prove it without De Morgan's laws?

Who kind of course are you in? No DeMorgan?

$$\begin{array}{l} x \in Y\backslash (Y\backslash B)\\ \Leftrightarrow x \in Y \wedge x \notin \left( {Y\backslash B} \right)\\ \Leftrightarrow x \in Y \wedge \left( {x \notin Y \vee x \in B} \right)\\ \Leftrightarrow \left( {x \in Y \wedge x \notin Y} \right) \vee \left( {x \in Y \wedge x \in B} \right)\\ \Leftrightarrow x \in B \end{array}$$

 

[Guest2]

Thanks, Plato!

Who kind of course are you in? No DeMorgan?

(Rofl)

We're yet to reach the section where they introduce De Morgan.

 

[Deveno]

What rules of complementation or set difference do you have available to you?

For example, have you proved yet that for any $A,B$:

$(A\setminus B) \cup (A\cap B) = A$ and:

$(A \setminus B) \cap (A\cap B) = \emptyset$?

Or, even more pointedly, can you say:

"a not not in A" is the same as "a is in A"?

 

[Guest2]

What rules of complementation or set difference do you have available to you?

For example, have you proved yet that for any $A,B$:

$(A\setminus B) \cup (A\cap B) = A$ and:

$(A \setminus B) \cap (A\cap B) = \emptyset$?

Or, even more pointedly, can you say:

"a not not in A" is the same as "a is in A"?

No, and no to the first two. We covered the last one for propositions in my logic class where we had a rule that eliminated double negations. But I kind of intuitively got it when following Plato's proof.

I've tried your first one.

Let $x \in (A\setminus B) \cup (A\cap B)$ then $x \in (A\setminus B)$ or $ x \in (A\cap B)$ both of which imply $x \in A$. Let $ x \in A$ then $x \not \in A \setminus B$ but $ x \in (A \cap B)$ - therefore we have $x \in (A \setminus B) \cup (A \cap B)$. We have shown that $ (A \setminus B) \cup (A \cap B) \subseteq A$ and $ (A \setminus B) \cup (A \cap B) \subseteq A$ therefore we have proven that $ (A \setminus B) \cup (A \cap B) = A$.

The above is probably rubbish though.

 

[Guest2]

I'm not sure about the second one. Let $x \in (A \setminus B) \cap (A \cap B)$. Then $x \in A$, and $x \in B$ and $x \not \in B$. As $x \in B$ and $x \not \in B$ is not possible, no such $x$ exists. Thus the set empty, i.e. $(A \setminus B) \cap (A \cap B) = \emptyset$.

 

[Guest2]

I now realize my attempt for the first was rubbish, of course. (Rofl) I'll try it again.

Realised I didn't answer the question regarding what rules I've got. I got none. Just the basic definitions of set, subset, union, intersection, complement, and symmetric difference.

 

[Deveno]

No, and no to the first two. We covered the last one for propositions in my logic class where we had a rule that eliminated double negations. But I kind of intuitively got it when following Plato's proof.

I've tried your first one.

Let $x \in (A\setminus B) \cup (A\cap B)$ then $x \in (A\setminus B)$ or $ x \in (A\cap B)$ both of which imply $x \in A$. Let $ x \in A$ then $x \not \in A \setminus B$ but $ x \in (A \cap B)$ - therefore we have $x \in (A \setminus B) \cup (A \cap B)$. We have shown that $ (A \setminus B) \cup (A \cap B) \subseteq A$ and $ (A \setminus B) \cup (A \cap B) \subseteq A$ therefore we have proven that $ (A \setminus B) \cup (A \cap B) = A$.

The above is probably rubbish though.

Not rubbish at all, but your proof that:

$x \in A \implies (x \in A\setminus B) \vee (x \in A \cap B)$ needs some work.

The trick is to tackle these two cases:

1. $x \in B$
2. $x \not \in B$.

That these are the ONLY two cases possible is known as "the law of the excluded middle". While some forms of mathematical logic (most notably "intuitionist logic") disallow this, it is standard practice in most forms of math that entail some set theory.

In other words, we think of a statement:

"x is in (some set) A" as being either true, or false, there's no "middle ground" of it being "probably in A", or "sort of in A".

Plato is really good at this sort of stuff (I suspect he's had some practice). A few words concerning his terse explanation:

The first 3 lines are just "unraveling" definitions. Line 3 in particular uses the "not not" rule to say that:

$\neg (x \not \in B) \iff x \in B$

line 4 is just a distributive rule, presumably you "accept" his proof because you have already been exposed to those.

Finally, any expression:

$a \wedge \neg a$ is always false, so:

$(a \wedge \neg a) \vee b \iff b$

and his last line is an example of "conjunctive elimination":

if a and b are BOTH true, we can conclude either a or b (whichever one gets us where we want to go), that is:

$(a \wedge b) \implies a$
$(a \wedge b) \implies b$ are both valid.

 

[Plato2]

Let $x \in (A\setminus B) \cup (A\cap B)$ then $x \in (A\setminus B)$ or $ x \in (A\cap B)$ both of which imply $x \in A$. Let $ x \in A$ then $x \not \in A \setminus B$ but $ x \in (A \cap B)$ - therefore we have $x \in (A \setminus B) \cup (A \cap B)$. We have shown that $ (A \setminus B) \cup (A \cap B) \subseteq A$ and $ (A \setminus B) \cup (A \cap B) \subseteq A$ therefore we have proven that $ (A \setminus B) \cup (A \cap B) = A$.

$$\begin{array}{l} x \in \left[ {(A\backslash B) \cup (A \cap B)} \right]\\ \Leftrightarrow x \in (A\backslash B) \vee x \in (A \cap B)\\ \Leftrightarrow \left[ {x \in A \wedge x \notin B} \right] \vee \left[ {x \in A \wedge x \in B} \right]\\ \Leftrightarrow \left( {x \in A} \right) \wedge \left[ {x \notin B \vee x \in B} \right]\\ \Leftrightarrow (x \in A) \end{array}$$

 

[Guest2]

Not rubbish at all, but your proof that:

$x \in A \implies (x \in A\setminus B) \vee (x \in A \cap B)$ needs some work.

Take #2: Let $x \in (A\setminus B) \cup (A\cap B)$ then $x \in (A\setminus B)$ or $ x \in (A\cap B)$ both of which imply $x \in A$. Let $ x \in A$, then consider the cases $ x \in B$ and $x \not \in B$. If $x \in B$ then $x \in (A \cap B) $, so $ x \in (A\setminus B) \cup (A\cap B)$. If $x \not \in B$ then $ x \in A \setminus B$ and so again $ x \in (A\setminus B) \cup (A\cap B)$. We have shown that $ (A \setminus B) \cup (A \cap B) \subseteq A$ and $ A \subseteq (A \setminus B) \cup (A \cap B) $ therefore we have proven that $ (A \setminus B) \cup (A \cap B) = A$.

I get the logic parts because I did a course in logic, but I'm new to sets and they seem weird.

Thanks for the detailed answer!

 

[Plato2]

I get the logic parts because I did a course in logic, but I'm new to sets and they seem weird.

There is no difference in logic & set theory.

All set theory concepts are stated in terms of logic.

UNION is simply the same as OR.

INTERSECTION is simply the same as AND.

COMPLIMENT is simply the same as NOT.

 

[Guest2]

$\Leftrightarrow x \in Y \wedge x \notin \left( {Y\backslash B} \right)\\
\Leftrightarrow x \in Y \wedge \left( {x \notin Y \vee x \in B} \right)\\$

Trying to get my head around this step. Let Y = {1, 2, 3} and B = {3}. Then 3 is not in Y\B = {1,2} yet 3 is in both Y and B. Also, 4 is not in Y\B, but it's also neither in Y nor B. I'm guessing both of these can be fixed as they imply the disjunctive, but then the implication only goes one way. I'm probably missing something stupid. I'm going to sleep on this.

 

[Deveno]

There is no difference in logic & set theory.

All set theory concepts are stated in terms of logic.

UNION is simply the same as OR.

INTERSECTION is simply the same as AND.

COMPLIMENT is simply the same as NOT.

I don't quite agree with this. To me, it's like saying there is no difference between the set of natural numbers $\Bbb N$, and the set of rational numbers:

{0/1,1/1,2/1,3/1,...}

Now, philosophically, I lean towards structuralism, I'm fine with things being "equal up to isomorphism", but "what things actually *are*" seems to me to be a matter of context, and sometimes context *matters*.

To be more specific: propositions have "truth-values", whereas sets are "constructions" (entities). It doesn't make sense to me to say:

$A \cap B = $ true.

But, yes, there are certain obvious "parallel constructions":

$x \in A \iff P(x)$, where $P$ is the property that defines $A$.
$A \subset B \iff P(x) \implies Q(x)$ where $P,Q$ are defined analogously to above.
$x \in A \cup B \iff P(x) \vee Q(x)$
$x \in A \cap B \iff P(x) \wedge Q(x)$
$x \in A^c \iff \neg P(x)$

some of these parallels depend on some "background set of discourse", which in the "general case" gets a bit murky...there is, after all, no universal "set of all sets", so we usually are talking about some "background universe" (our sets are subsets of some power set). Because of this, I have no idea what a set is, although I know that several things are sets.

When I look at foundational material on sets, the axioms are usually stated in terms of a first- or second-order propositional calculus. When I try to delve deeper into what a predicate logic is, I often encounter statements like:

"L consists of a set $\Sigma$, called the alphabet..." which seems a bit unfair. I feel like a snake trying to eat his own tail...

 

[Guest2]

The first 3 lines are just "unraveling" definitions. Line 3 in particular uses the "not not" rule to say that:

$\neg (x \not \in B) \iff x \in B$

Seeing as I've an issue understanding that particular line, could you please elaborate a bit? See post #14.

 

[Plato2]

Seeing as I've an issue understanding that particular line, could you please elaborate a bit? See post #14.

$$\neg \left( {x \notin B} \right)$$ reads "It is not the case that x is not in B."
That is a very stilted literal translation.
How would one normally say that: "x is in B"??

 

[Guest2]

$$\neg \left( {x \notin B} \right)$$ reads "It is not the case that x is not in B."
That is a very stilted literal translation.
How would one normally say that: "x is in B"??

I understand what that means. My problem is I don't understand how it would give the line:

$ x \in Y \wedge x \notin \left( {Y\backslash B} \right)\\
\Leftrightarrow x \in Y \wedge \left( {x \notin Y \vee x \in B} \right)\\$

I can't see how $x \notin \left( {Y\backslash B} \right)$ is equivalent to $\left( {x \notin Y \vee x \in B} \right)$.

 

[Deveno]

In "natural language":

Either x is in B, or x is not in B (law of the excluded middle), and never both or neither.

Now suppose we are told it is not the case that x is not in B

(this is what $\neg (x \not \in B)$ means).

The only other possibility is then that x is in B, that is:

$\neg (x \not \in B) \implies x \in B$.

On the other hand, if we are told x is in B, then x not in B is never true, so the opposite is true: it is not the case that x is not in B. This is:

$x \in B \implies \neg(x \not \in B)$.

To be more explicit: suppose our "universal set" is $U$ (This set is often denoted as "1").

We have, for any subset $B \subseteq U$:

$B \cup (U - B) = B$

or: $B \cup B^c = U$, which is logically equivalent to the proposition:

$p \vee \neg p$, which is always true (1 is also used as indicating "true" or "always true").

For example:

the union of all boys and all girls is all people.

We also have:

$B \cap (U - B) = \emptyset$ which is logically equivalent to:

$\neg (p \wedge \neg p)$, which is also "always true" (that is $p \wedge \neg p$ is "never true", or "always false").

For example:

No person is a boy and a girl.

(You hermaphrodites out there keep quiet, j00 messin' wit' mah flow!).

These rules in a boolean algebra are sometimes written:

$a + (-a) = 1$
$a(-a) = 0$.

Again, somewhat informally:

If x is in A: x is either in B, or not in B.

If x is in A, and x is in B, x is in $A \cap B$.

If x is in A, but x is not in B, then x is in $A - B$.

So, in all cases, x is in $(A \cap B) \cup (A - B)$, so $A \subseteq (A \cap B) \cup (A - B)$.

On the other hand, if x is in $(A \cap B) \cup (A - B)$, then either:

1. $x \in A \cap B$, whence x is in A and x is in B, so x is in A (x also being in B is not needed, here).

2. or $x \in A - B$, in which case x is in A, but not in B, so x is in A (the fact that x is not in B likewise has no bearing).

So in all cases, x is in A, thus $(A \cap B) \cup (A - B) \subseteq A$.

***********

For the other identity:

$(A - B) \cap (A \cap B) = \emptyset$.

Suppose x is both in $A - B$ and $A \cap B$.

Then x is in A, and x is not in B, and x is in A, and x is in B.

We therefore conclude x is both in B and not in B, which is impossible.

So no such x exists, and the empty set is precisely all such non-existent x:

$\emptyset = \{x \in U: x \not \in U\}$.

on the other hand, the empty set is a subset of any set, so no argument is needed for the reverse containment.

Being "very" imprecise: not a single element of "everything" is "nothing".

It's kind of "weird", but to prove a given set X is a subset of the empty set, one has to shown X is empty (for even one legitimate element of X would be a counter-example).

 

[Guest2]

I got both right then (the first one on take two)? Thanks for the explanation.

Do you have one or more like these that I can try, if you don't mind? Thanks.

 

[Plato2]

$ x \in Y \wedge x \notin \left( {Y\backslash B} \right)\\
\Leftrightarrow x \in Y \wedge \left( {x \notin Y \vee x \in B} \right)\\$

I can't see how $x \notin \left( {Y\backslash B} \right)$ is equivalent to $\left( {x \notin Y \vee x \in B} \right)$.

$$x\in(A\setminus B)$$ means $$x \in A\, \wedge \,x \notin B$$.

What is the negation: $$x \notin A\, \vee \,x \in B~~??$$

 

[Guest2]

$$x\in(A\setminus B)$$ means $$x \in A\, \wedge \,x \notin B$$.

What is the negation: $$x \notin A\, \vee \,x \in B~~??$$

Yep. Got it now. Thanks. So we're using De Morgan's laws? (Giggle)

 

[Plato2]

Yep. Got it now. Thanks. So we're using De Morgan's laws?

I remember that you have not studied De Morgan's laws.
But I still do not understand your reasoning.
Many, many years ago as a young assistant professor I was assigned to teach a foundations course. The department had chosen the textbook for the course before I was hired. In that text, the author presented basic set theory before he did logic.
It was a nightmare for me. I have completely put it out of my brain.

I ask you to please tell me what textbook and/or author you are following.