Posted by Joel on October 02, 2002 at 10:06:30:
In Reply to: Re: Set operations - CORRECTED - please look at this one instead posted by T.Gracken on October 02, 2002 at 07:57:31:
: : : using the following symbols:
: : : u = union
: : : e = "is member of"
: : : v = disjunction (THIS IS THE CORRECTION)
: : : | = such that
: : : c= = "is subset of"
: : : is this a valid proof that
: : : (A u B) c= (A u B u C) ("A union B is a subset of A union B union C")?
: : : given an X | X e (A u B)
: : : then (X e A) v (X e B)
: : : then (X e A) v (X e B) v (X e C) [this is the step that worries me, since no information is given regarding membership or non-membership in C, but there has to be some way to introduce C into the picture]
: : : then X e (A u B u C)
: : : therefore any (X | X e (A u B)) e (A u B u B)
: : : so by the definition of subset, (A u B) c= (A u B u C)
: : : The whole question seems so obvious and trivial, and this argument seems so simple that it is hard to believe that this is a legitimate proof. Also, I'm bothered by the fact that "C" seems to materialize out of thin air, but there has to be some "legal" way to get C into the argument. Is this it?
: There is no proof needed. By definition, if x is an element of set A, then x is an element of any union of sets in which A is included.
Not exactly. The definition states that the union of the sets A and B is the set that contains those elements that are either in A or in B or in both. What you are stating is probably a theorem derived from the definition. Anyway, my discrete structures professor and the author of the textbook both seem to agree that the statement (A u B) c= (A u B u C)
needs to be proven, even though it is painfully obvious that it is true. I guess the point is to teach how to construct a formal proof, step by logical step.
Anyway, I did find something that allows the step that was worrying me. Since "P -> P v Q" is a tautology, (P v Q) -> (P v Q) v X (or any other proposition), so (X e A) v (X e B) => (X e A) v (X e B) v (X e C)