Proving Set Equality and Basic Properties: A Walkthrough

[ice109]

im just starting to work through vol 1 of apostol and these questions are kind of dumbfounding?
#3 on page 15
Let A={1}, B={1,2} Discuss the validity of the following statements (prove the ones that are true)

(a) [tex]A\subset B[/tex]
(b) [tex]A\subseteq B [/tex]
(c) [tex]A \in B[/tex]
(d) [tex] 1 \in A [/tex]
(e) [tex] 1 \subseteq B[/tex]
(f) [tex] 1 \subset B [/tex]

these are all obvious but what does he mean by prove? for (a) i have written: 1 is an element of A and an element of B but 2 is only an element of B hence A subeq B.

i don't know to how "prove" this stuff.
#7 on page 16

Prove the following properties of set equality.
(a){a,a}={a}
(b){a,b}={b,a}
(c){a}={b,c} iff a=b=c

the first two are just notational? the third follows from the first. these are all obvious but i don't know how to rigorously write it down.

 

[rocomath]

i just started working on Spivak's book. i also have the same thought of "how to prove" this stuff ...

too bad we don't have the same book, we could have worked together.

 

[morphism]

It's just a matter of directly applying the definitions. For example, to prove 1, you just verify the statements "if x is in A then x is in B" and "there exists an element in B that is not in A". And for the second bunch of questions, I suppose you can show that the set on the left hand of the equality is contained in the one on the right hand, and vice versa. So yes, it's a complete waste of time.

 

[ice109]

someone check this for me.

prove [itex] A \bigcap (B \bigcup C) = (A \bigcap B) \bigcup (A \bigcap C)[/itex]

proof:

let [itex] X = A \bigcap (B \bigcup C) [/itex]

and [itex] Y = (A \bigcap B) \bigcup (A \bigcap C) [/itex]

prove [itex] X \subseteq Y[/itex] and [itex] Y \subseteq X[/itex]

let [itex] x \in X[/itex] then [itex]x[/itex] is in A and B or C therefore x is in A and B or A and C. therefore x [itex] \in Y [/itex] and [itex] X \subseteq Y[/itex]. similarly [itex]Y \subseteq X[/itex].

it seems suspect to me.

 

[Defennder]

someone check this for me.

prove [itex] A \bigcap (B \bigcup C) = (A \bigcap B) \bigcup (A \bigcap C)[/itex]

Couldn't you draw a Venn diagram to prove this? Or do you want a purely analytic proof?

 

[morphism]

It's fine.

 

[ice109]

Couldn't you draw a Venn diagram to prove this? Or do you want a purely analytic proof?

purely analytical

It's fine.

wow that's terrible.

 

[morphism]

wow that's terrible.

Why? It's not like it's a profound result or anything.

 

[ice109]

Why? It's not like it's a profound result or anything.

it just seems so unrigorous.

 

[morphism]

it just seems so unrigorous.

Why exactly? Everything you did was mathematically sound. Maybe the word you're looking for is "untedious" - if such a word exists.

Your proof is no different from, say, this one:
x in A[itex]\cap[/itex](B[itex]\cup[/itex]C)
=> x in A and x in B[itex]\cup[/itex]C
=> x in A and (x in B or x in C)
=> (x in A and x in B) or (x in A and x in C)
=> x in A[itex]\cap[/itex]B or x in A[itex]\cap[/itex]C
=> x in (A[itex]\cap[/itex]B)[itex]\cup[/itex](A[itex]\cap[/itex]C)
So A[itex]\cap[/itex](B[itex]\cup[/itex]C) [itex]\subset[/itex] (A[itex]\cap[/itex]B)[itex]\cup[/itex](A[itex]\cap[/itex]C). And similarly for the other direction.

Actually there is a difference: your proof isn't as tedious.

 

[Gib Z]

it just seems so unrigorous.

If you wanted to add a load of wishy washy dung to make it seem more mathematically sound you could define a 2 dimensional co-ordinate system where the regions of the Venn Diagrams represent sets of co-ordinates.

 

[ice109]

are these two things equivalent?

A B C are sets.

all elements in A not in B and C; [itex]A-(B \bigcap C)[/itex]

all elements in A but not in B and all elements in A but not in C; [itex](A-B) \bigcup (A-C)[/itex]

If you wanted to add a load of wishy washy dung to make it seem more mathematically sound you could define a 2 dimensional co-ordinate system where the regions of the Venn Diagrams represent sets of co-ordinates.

not general enough?

 

[Gib Z]

You get my argument though, its pointless and adds no real mathematical rigor, just appearances.

 

[ice109]

You get my argument though, its pointless and adds no real mathematical rigor, just appearances.

you have to understand i only vaguely know what mathematical rigor is.

 

[ice109]

ok how about this one that took me all of about an hour. I've never done proofs and i need to make sure I'm doing this right.

prove a(b-c)=ac-ab

given:

field axioms 1-4

theorem 1: cancellation law for addition a+b=a+c -> b=c

theorem 2: b-a=b+(-a)

theorem 3: possibility of subtraction, given a and b there exists one x such that a+x=b and it is defined as x=b-a. in particular 0-a is written as -a and is defined as the negative of a

theorem 4: -(-a)=a

start.

a(b-c)=a(b+(-c)) by theorem two

a(b+(-c))=ab+a(-c) by distributivity

now prove ab+a(-c)=ab-ac. this amounts to proving a(-c)=-ac because of theorem 1
edit: i think i miss something here, namely proving that i can use the results of theorem 1 when there is a minus sign on one of the sides. damn it.

lemma 1: prove -ac=-(ac). using the definition of negatives derived from theorem 3
-ac=-(ac) follows.

hence a(-c)=-(ac) and a(-c)+ac=-(ac)+ac=0

now i need to prove a(-c)+ac=0

using distributive property a((-c)+c)=a*0=0

lemma 2: prove a*0=0. using the definition of zero in axiom 4 a number is zero if some other number plus it equals that number hence a*0 if y+ a*0=y but using subtraction it is obviously that a*0=y-y=0 hence a(b-c)=ab-ac.

qed

i would appreciate if someone took a fine toothed comb to this proof. i am striving for the utmost rigor.

 

[rudinreader]

someone check this for me.
proof:
... similarly [itex]Y \subseteq X[/itex].

For someone just starting out in analysis, if I were grading your paper I would give you an X for saying "similarly..." or "the same thing can be said...", etc. because you should make a point to say everything, even when it seems obvious.
The answer I would look for as a grader is:
(Adapted from morphism with the <= direction added)
x in A[itex]\cap[/itex](B[itex]\cup[/itex]C)
<=> x in A and x in B[itex]\cup[/itex]C
<=> x in A and (x in B or x in C)
<=> (x in A and x in B) or (x in A and x in C)
<=> x in A[itex]\cap[/itex]B or x in A[itex]\cap[/itex]C
<=> x in (A[itex]\cap[/itex]B)[itex]\cup[/itex](A[itex]\cap[/itex]C)
So A[itex]\cap[/itex](B[itex]\cup[/itex]C) = (A[itex]\cap[/itex]B)[itex]\cup[/itex](A[itex]\cap[/itex]C).

In fact I would have graded morphisms as wrong if it finished with "the same argument shows Y[itex]\subseteq[/itex]X", but would have graded correctly if he wrote out the other direction entirely as above, though using <=> would have been more compact. (And of course I wouldn't grade it as wrong if I knew it came from morphism or was in a graduate analysis class..)

As for the problem concerning the properties of real numbers, I would have given you the right answer, though it could have been shortened..

fact: a(-c) = -ac
proof: ac + a(-c) = a(c + -c) = a(0) = 0. Apply uniqueness. (By the way, your theorem 3 should mention that -x is the unique x such that x + -x = 0.)
prove: a(b-c)=ab-ac
proof: a(b-c) = ab + a(-c) = ab + -ac = ab - ac.

**since I brought it up I will just add that I admit I often use the term "similarly", but I am supposed to actually check that it works. Sometimes it's not obvious, but it saves space for the writer, and anyone who is really interested in reading it should be able to follow the related proof and write the "similarly" out on his/her own. It's particularly embarassing when you say "similarly..." and later on someone points out that it was false!

 

[disregardthat]

Are you allowed to use this: a(b-c)=ab-ac
in a proof, for then to prove this: a(b-c)=ab-ac, by using your previously proven fact?

To me it seems like circular logic. That if one thing is true, the other is, and vice versa, but they are both not necessarily true.

 

[rudinreader]

OK I should have added one step.. But b-c = b + (-c). Then I applied the distributive law.
a(b-c) = a(b+(-c)) = ab + a(-c) = ab + -ac = ab - ac.

 

[rudinreader]

i don't know to how "prove" this stuff.

i also have the same thought of "how to prove" this stuff ...

"Prove" usually means "why is this true?". As an example, (one form of) the completeness axiom (theorem) is that every nonempty set of real numbers that is bounded above has a least upper bound in R.

You are usually then asked to "prove" every nonempty set that is bounded below has a greatest lower bound. So you have to ask yourself, "is it true?", "why is it true?" etc.. But this is where your knowledge of other facts gets tested (in this case mainly the fact that a < b if and only if -a > -b).

proof:
Suppose A is a nonempty set that is bounded below, say m <= x for all x in A. Define "-A" = {-x: x in A}. Then you might correctly guess that -m >= y for all y in -A. To see this, fix any y in A. Then y = -x for some x in A. We know m <= x, so it follows that -m >= -x = y. Thus -m is an upper bound of -A. Now you apply the completeness axiom: there exists a least upper bound M of -A. Then you might correctly guess that -M is the greatest lower bound of A. Firstly, is x in A, then -x <= M, thus -M <= x. This shows -M is a lower bound. Now let Q be any other lower bound of A, we have to check that Q <= -M. Again, for any -x in -A, we have Q <= x, thus -Q >= -x. Hence -Q is an upper bound of -A. But M is the least upper bound, so we conclude -Q >= M. It then follows that Q <= -M. We have now shown that -M is a lower bound of A and for any lower bound Q of A, Q <= -M. We conclude -M is the greatest lower bound of A. QED..

Again, after you get more aquianted with mathematics it would in fact probably be easier for mathematicians to read such a proof if it was simplified with "similarly...", "the same result follows...", etc. but it's a good idea when you are first starting to complete every detail in any given proof.. Hope that helps.. It may look intimidating to outsiders but it's actually kind of fun as long as you stick with it and become an insider..

 

[ice109]

fact: a(-c) = -ac
proof: ac + a(-c) = a(c + -c) = a(0) = 0. Apply uniqueness. (By the way, your theorem 3 should mention that -x is the unique x such that x + -x = 0.)
prove: a(b-c)=ab-ac
proof: a(b-c) = ab + a(-c) = ab + -ac = ab - ac.

where did you get this fact?

 

[Moo Of Doom]

where did you get this fact?

From the proof in the next line:

proof: ac + a(-c) = a(c + -c) = a(0) = 0. Apply uniqueness. (By the way, your theorem 3 should mention that -x is the unique x such that x + -x = 0.)

 

[ice109]

i don't know what "apply uniqueness means" either.

btw was my proof that a*0=0 sufficient?

 

[morphism]

Uniqueness of additive inverses, i.e. since ac+a(-c)=0 and ac+-(ac)=0, then a(-c)=-ac.

As for your proof of a0=0 I admit I can't really understand it. You appear to be saying "if a0=0 then a0+y=y but then subtract y to get a0=0", which is circular. One way you can do it is as follows: a0=a(0+0)=a0+a0, and subtract a0 off both sides.

 

[ice109]

yea 6am and i awoke because i realized the proof of a*0 isn't right.

edit

how do we know ac-ac=0?

fact: ac-ac=0
proof: let x=ac ; x-x=0 by definition

im sure you guys think this is redundant but like i am learning how to do proofs using these proofs.

feck this this is the most annoying thing ever.