Discrete Math Final: Questions 1 and 2

December 11, 2010 in Exercises

1. Let A, B, and C denote subsets of some Universal Set. Use an “element” argument to prove the set equation: $(A-B)-C = (A-C)-B$ . (“Let $x \in (A-B)-C$ …”).

2. Let A, B, and C denote subsets of some Universal Set. Use an “algebraic” argument to prove the set equation $(A-B)-C = (A-C)-B$ .

Do not begin your proof with the equation to be proven! (Rather, begin with (A-B)-C = XXXXX [where XXXXX differs from "(A-B)-C" by one "step"]; then write out another step” [a new set expression and a reason we know it's equal to the latest one... and so on until (A-C)-B is reached).

The necessary "reasons" are all in the list below.

Associative Law (of intersection) $(X\cap Y)\cap Z = X\cap (Y\cap Z)$
Commutative Law (of intersection) $X \cap Y = Y \cap X$

Set Difference Law $X-Y = X\cap Y^c$

(Lecture without diagrams; solutions included somewhere I hope.)

The given equation is true for any sets and so can be proved "within Set Theory"... by which I mean, without any other math (so we don't need to know anything about counting or adding or exponentiating or any such number-like stuff, for example). This is why an "algebraic" proof is even possible.

To prove sets S and T equal outside the context of Set Theory, one typically shows that (i.) $S \subset T$ and that (ii) $T \subset S$ (i.e., that S is a subset of T and that T is a subset of S); various calculations are typically carried out ("number-like" calculations are common); typically the calculations for the two directions ("S is a subset of T" is one "direction" here) aren't very much alike. Quite often, in fact, one direction is "easy" and one is harder.

In Quiz #3 we had $A \cap (A \cup B) = A$ , for example, and showing that $A \cap (A \cup B) \subset A$ turns out to be (slightly) easier than $A \subset A \cap (A \cup B)$ .

The equation for this problem is a non-example of this one-way-is-harder phenomenon because of its "symmetry".

(The expressions on the two sides of the equation are very much alike... specifically, one may interchange the "B" with the "C" [wherever they appear] to obtain one side from the other. Graphical representations of suchlike situations display “symmetries” literally; typically one may “rotate” or “reflect” certain pictures back on to themselves. This means that certain “measurements” in certain drawings are “the same”; in the word symmetry “sym-” means “same” and “metr” means “measure” [think of the "metric" system to see that this is so].)

Anyhow, the point for us right now is that in proving (A-B)-C = (A-C)-B the two “directions” are very much alike. This makes it rather a poor choice for Problem #1 as I now realize. I got a little too cute. I wanted to use the same equation for both contexts and rather liked the “algebraic” proof (for requiring associativity and commutativity; for requiring only one other “reason”; for its take-it-apart-and-put-it-back-together quality [a result of the symmetry of the situation]).

Anyhow, here’s a proof (by a student).

(i) Let A, B, and C be sets and $x \in (A-B)-C$ . Therefore, $x \in (A-B)$ and $x \not\in C$ by definition of “-”. Next, $x \in A$ and $x \not\in B$ by def of “-”. This gives $x \in (A-C)$ by “-” and $x \not\in B$ . Combining, we get $x \in (A-C)-B$ by “-”.

(ii) Let A, B, and C denote sets and $x \in (A-C)-B$ . By def. of “-” $x \in (A-C)$ and $x \not\in B$ . Further, by “-”, $x\in A$ and $x\not\in C$ . Since $x \in A$ and $x\not\in B$ , then $x \in (A-B)$ (by “-”). Also $x \not\in C$ so by def of “-” $x \in (A-B)-C$ .

We have shown (i) $(A-B)-C \subset (A-C)-B$ and (ii) $(A-C)-B \subset (A-B)-C$ . Therefore we are done.

On the actual marked exam there appear three checkmarks on this work and no other marks by me… but of course there’s much here to discuss. One need not (for example) have redefined A, B, and C; I’ve done that already in the problem statement. It’s likely that some other instructor might frown on the declension “by definition of ‘-’ “/ “by def of ‘-’ “/ “by ‘-’ “… but I myself consider it quite tastefully done. Another sign of this student’s good taste is the wrap-up step where she’s reminded the reader that (x\in S)\implies(x\in T) is the form of a proof that S\subset T (I have [tastefully, hopefully] here slipped into my “easy-type” style; for “\in” read “is an element of” [and mentally substitute $\in$ ]; other backslashed terms stand for [what I hope are "obvious"] other math symbols).

There were some full-credit versions of this problem omitting the wrap-up altogether. Again, other instructors might’ve required it. Grading on writing style still gives me the heebie-jeebies but I’m getting used to it. On this exercise I had plenty of other fish to fry.

Some students gave, essentially, verbal versions of the algebraic proof. (“Let x \in (A-B)-C. Then x\in A, x\not\in B, and x\not\in C. But then x\in (A-C)-B.” [Then say it again backwards.]) Some even went so far as to mention the algebraic “laws” (commutativity and associativity) that apply in the equation-based proof. I considered this at least partly my fault. Some, of course, blanked out entirely or otherwise missed the point of an “element” style proof. This is not my fault.

Anyhow, here is that algebraic proof. Probably most of the right answers… but not all… used the same steps in (essentially) the same order as I did so I’ll just write mine out again here.

$(A-B)-C$
$= (A-B)\cap C^c$ (Set Difference)
$= (A\cap B^c) \cap C^c$ (Set Difference)
$= A \cap (B^c \cap C^c)$ (Associativity)
$= A \cap (C^c \cap B^c)$ (Commutativity)
$= (A \cap C^c) \cap B^c$ (Associativity)
$= (A\cap C^c) - B$ (Set Difference)
$= (A-C)-B$ (Set Difference)

OK. Breakfast.

Like this:

Be the first to like this post.

2 Replies

vlorbik

December 11, 2010 at 6:05 pm

i meant to’ve mentioned… as i might *not* have done
with the class… that one does *not* require
a “universal set” in the first problem but
one *does* require a universal set for the second.

the point is that X-Y is *defined* as
{ a | a \in X \logical-and a \not\in Y}…
which makes sense as soon as X and Y
are defined (without any further context)
but that $X-Y = X\cap Y^c$
depends on the existence of $Y^c$
(the “complement” of Y: the set of elements
of the universal set that are not in Y).

you might think this is rather a fine point;
indeed i’m inclined to agree. but it’s exactly
the *kind* of fine point that should matter
in, anyway, reading a text like ours.
specifically, the material on set theory
depends very heavily on the earlier
presentation of (symbolic) *logic*.

in *any* presentation of both topics,
one quickly becomes aware of numerous
“parallels”. specifically (the logical
operations), conjunction, disjunction,
and negation can be “translated” into
(the set operations) union, intersection,
and complementation.

what we have here (in all this fuss
about presence-or-absence of a
universal set) illustrates one
(rather minor) *difference* in
the theories. when things are
very much alike, even minor
differences can be important.

Reply
vlorbik

December 11, 2010 at 6:16 pm

breakfast was great, btw.
i put some bacon in the big pan
(4 slices from the package,
trimmed slightly and cut
in half) and some butter in
the little one… and started
grating up a couple potatoes
(peels still on). then started
a couple eggs-over-easy in
the butter. more grating;
add the taters into the hot
bacon fat. the eggs were
done while everything else
was still cooking, so i *ate*
‘em… salted and peppered…
while everything else was
still cooking (madeline doesn’t
like eggs anyhow). i had my part
of my bacon serving (a rasher
of course but why say so now)
before i was done with the eggs.
the rest of the bacon came up first
so i served it separately; when
the hashbrowns were done i put
‘em on a plate and served with
ketchup. madeline left a little
so i had that. microwave instant
coffee. ice water. serves two.

Reply