Welcome to our community

Be a part of something great, join today!

Set equality

Guest

Active member
Jan 4, 2014
199
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$.
 

Plato

Well-known member
MHB Math Helper
Jan 27, 2012
196
Problem: Let $B$ be a subset of $Y$, prove that $Y \setminus (Y\setminus B) = B$.
[TEX] \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*}[/TEX]
 

Guest

Active member
Jan 4, 2014
199
Thanks. De Morgan's laws are not available to me. Is it possible to prove it without De Morgan's laws?
 

Plato

Well-known member
MHB Math Helper
Jan 27, 2012
196
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???

[tex]\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}[/tex]
 

Guest

Active member
Jan 4, 2014
199
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

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
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"?
 

Guest

Active member
Jan 4, 2014
199
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.
 

Guest

Active member
Jan 4, 2014
199
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$.
 

Guest

Active member
Jan 4, 2014
199
I now realise 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.
 
Last edited:

Deveno

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
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.
 

Plato

Well-known member
MHB Math Helper
Jan 27, 2012
196
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$.
[tex]\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}[/tex]
 

Guest

Active member
Jan 4, 2014
199
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!
 
Last edited:

Plato

Well-known member
MHB Math Helper
Jan 27, 2012
196
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.
 

Guest

Active member
Jan 4, 2014
199
$\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.
 
Last edited:

Deveno

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
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...
 

Guest

Active member
Jan 4, 2014
199
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.
 

Plato

Well-known member
MHB Math Helper
Jan 27, 2012
196
Seeing as I've an issue understanding that particular line, could you please elaborate a bit? See post #14.
[tex]\neg \left( {x \notin B} \right)[/tex] 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"??
 

Guest

Active member
Jan 4, 2014
199
[tex]\neg \left( {x \notin B} \right)[/tex] 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

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
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).
 

Guest

Active member
Jan 4, 2014
199
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.
 

Plato

Well-known member
MHB Math Helper
Jan 27, 2012
196
$ 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)$.
[tex]x\in(A\setminus B)[/tex] means [tex]x \in A\, \wedge \,x \notin B[/tex].

What is the negation: [tex]x \notin A\, \vee \,x \in B~~??[/tex]
 

Guest

Active member
Jan 4, 2014
199
[tex]x\in(A\setminus B)[/tex] means [tex]x \in A\, \wedge \,x \notin B[/tex].

What is the negation: [tex]x \notin A\, \vee \,x \in B~~??[/tex]
Yep. Got it now. Thanks. So we're using De Morgan's laws? (Giggle)
 

Plato

Well-known member
MHB Math Helper
Jan 27, 2012
196
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.