### Discrete Math Final: Questions 1 and 2

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

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

notbegin your proof with the equation to be proven! (Rather, begin with (A-B)-C = XXXXX [where XXXXX differs from “(A-B)-C” byone “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)

Commutative Law (of intersection)Set Difference Law

(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.)* and that *(ii)* (*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 , for example, and showing that turns out to be (slightly) easier than .

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 . Therefore, and by definition of “-“. Next, and by def of “-“. This gives by “-” and . Combining, we get by “-“.

(ii)Let A, B, and C denote sets and . By def. of “-” and . Further, by “-“, and . Since and , then (by “-“). Also so by def of “-” .We have shown

(i)and(ii). 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 ]; 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.

(Set Difference)

(Set Difference)

(Associativity)

(Commutativity)

(Associativity)

(Set Difference)

(Set Difference)

OK. Breakfast.

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

depends on the existence of

(the “complement” of Y: the set of elements

of the universal setthat 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.

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.