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: (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.

Advertisements

  1. 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.

  2. 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.




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s



%d bloggers like this: