# is this proof ok?

• Jan 23rd 2013, 03:09 PM
engpro
is this proof ok?
let A and B be subsets of the universal set, prove that: A = AUB IIF B is a subset of A.

Suppose x is in A then x is in (AUB). which implies that B is a subset of A.
conversely Suppose that B is a subset of A, then if x is in B then x is in A. Which implies that x is in AUB = A.

is this proof correct, should i have taken another route, maby proof by contradiction?
it dosent feel like i have proven anything, just restated the problem.
how would you have solved it?
thanks for all help
• Jan 23rd 2013, 03:19 PM
Plato
Re: is this proof ok?
Quote:

Originally Posted by engpro
let A and B be subsets of the universal set, prove that: A = AUB IIF B is a subset of A.
Suppose x is in A then x is in (AUB). which implies that B is a subset of A.

Sorry to say, but that simply does not work.

It is easy to prove that if $B\subseteq A$ then $A\cup B=A$.

If I were you, to prove that $x\notin A$ show $x\notin B.$
• Jan 23rd 2013, 03:31 PM
emakarov
Re: is this proof ok?
Quote:

Originally Posted by engpro
let A and B be subsets of the universal set, prove that: A = AUB IIF B is a subset of A.

In the beginning of the proof, it is good to say whether you are proving the left-to-right direction (only if) or the right-to-left direction (if).

Quote:

Originally Posted by engpro
Suppose x is in A then x is in (AUB). which implies that B is a subset of A.

I don't see how "B is a subset of A" follows. To prove this, you need to assume that some x is in B, not A, and conclude that x is in A.

Quote:

Originally Posted by engpro
conversely Suppose that B is a subset of A, then if x is in B then x is in A. Which implies that x is in AUB = A.

This does not show that A U B = A, only that B is a subset of A U B. To prove equality of two sets, you need to prove that each set is contained in the other.

Remember the main thing: $U\subseteq V$ iff $x\in U$ implies $x\in V$ for all x. So, to prove $U\subseteq V$, you should start with "Suppose $x\in U$" and end with "Therefore, $x\in V$.

It is possible to make a proof by contrapositive here, but I think that a direct proof works better.
• Jan 24th 2013, 04:37 AM
engpro
Re: is this proof ok?
thanks for your pointers.
i have rewritten the proof, tell me what you guys think.

let $A,B\subseteq \Omega,$ where $\Omega$ is the universal set, prove $A = A\cup B \leftrightarrow B\subseteq A.$
1. we need to prove that $A = A\cup B \rightarrow B\subseteq A.$
2. we need to prove that $B\subseteq A\rightarrow A = A\cup B.$
if 1 and 2 are true then $A = A\cup B \leftrightarrow B\subseteq A.$ is also true.

case 1: If $A \neq A\cup B$ then $B\subseteq A$ is vacuously true, so we will assume that $A = A\cup B.$
Suppose $x\in A\cup B$ and $x\notin A$ then $x\in B.$ But then cause of $A = A\cup B$ is true, then $x\in A.$
So by contradiction if $x\in B$ then $x\in A$ which implies $B\subseteq A.$

case 2: if $B\nsubseteq A$ then $A = A\cup B$ is vacuously true, so we will assume that $B\subseteq A.$
Suppose $x\in A\cup B$ then $x\in A$ or $x\in B$, If $x \in A$ then $A\cup B \subseteq A$.
But cause of $B\subseteq A$ if $x \in B$ then $x \in A$. Thus $A \cup B \subseteq A$ in ether case.
Now suppose $x \in A$ then $x \in A\cup B.$ Thus $A \subseteq A\cup B.$ Therefore $A = A\cup B.$

By case 1 and case 2: $A = A\cup B \leftrightarrow B\subseteq A.$ is now proven. Q.E.D.

i know that my language is limited and it feels a little sketchy, But it feels more like a proof this time.
it took me an hour to write this in latex, but i like the result :)
• Jan 24th 2013, 05:59 AM
Deveno
Re: is this proof ok?
it is not the case that if A ≠ AUB then B ⊆ A is vacuously true.

for example, if A = {1,2} and B = {3}, then AUB= {1,2,3}, which is NOT equal to A, AND B is NOT a subset of A, so it isn't true in any sense, vacuous or otherwise.

in case 1), what you want to do is assume that x is in B, to start with. now, ask yourself, is B a subset of AUB? if so, you may safely conclude that x lies in the larger set AUB. since (by assumption) A = AUB, so will then have shown any x in B lies in A.

your argument that starts with "suppose x is in AUB and x is not in A" is nonsensical. our PREMISE is that A = AUB (that these two sets are the same set), so if x is in AUB, and x is NOT in A, x doesn't exist!

any argument which starts with "x not in A", and then leads to "x in A" should be viewed with extreme suspicion (such are the dreams that russell sets are built upon....).

case 2) isn't much better. the statement: "if B is not in A, then A = AUB is vacuously true" is FALSE (not true, not "vacuously true", false). a counter-example: let B = {2,3}, let A = {1,2}.

then B is not a subset of A (3 is in B, but 3 is not in A), and A is not equal to AUB. your next sentence is even worse, you NEVER want to assume what you are trying to PROVE (this is called "circular logic").

what you need to do is start with your basic assumption:

B ⊆ A.

next, pick something in A, call it...y, for example. first we want to show that y is in AUB. since y is already in A, it a fortiori (latin for "all the more", literally "even more strongly") is in either A or B, that is: it is in AUB.

so showing y is in AUB if it's in A isn't much of a challenge. this shows that A is contained in AUB. that is the "easy part".

we also want to show that AUB is contained in A. this is actually the "meat" of what you are trying to prove.

again, pick something in AUB, call it z. what does it mean for z to be in AUB? either it's in A, or it's in B (or maybe both, hard to say).

well...if it's in A, it's in A (do i even have to say this?). so assume that it is in B, instead. but B is a subset of A, so if z is in B, it automatically is in A (that's what "being a subset of" MEANS).

so, either way, if z is in AUB, it's in A, so AUB is a subset of A.

i hate to be so brutal, but if what you wrote was turned in as a homework assignment, it's very likely you would get no marks at all for your effort.
• Jan 24th 2013, 06:34 AM
engpro
Re: is this proof ok?
thank you for your response, i will read your pointers carefully and, try to rethink it all.
clearly i need practice and i dont think that 15 pages in descrete math is enough, do you know any book or website that teach how to do proofs.
with lost of practice problems, and ex solutions or hints.
i want to study real analysis but i think i should spend, more time on general proof practice before that.
• Jan 24th 2013, 07:10 AM
emakarov
Re: is this proof ok?
Quote:

Originally Posted by engpro
do you know any book or website that teach how to do proofs.

Here is a thread that lists some proof-teaching books, though I have not read them myself.
• Jan 24th 2013, 07:26 AM
engpro
Re: is this proof ok?
thanks :)
• Jan 24th 2013, 07:45 AM
Linear046
Re: is this proof ok?
Hi engpro,

Here are 3 good books on proof writing and reading:

1) The Nuts and Bolts of Proof by Antonella Cupillari
2) How to Read and Do Proofs by Daniel Solow
3) How to prove it-A structured Approach by Daniel J. Vellman

I have all 3, but I am just starting the first one. You can get them on Amazon as new and used (If they are available as used, probably can get any of them at a good price).
Good luck with your proof.

Linear046
• Jan 24th 2013, 07:51 AM
Deveno
Re: is this proof ok?
something that "may" be useful. understanding how sets work is a lot like understanding how "logical thinking" works.

here is a list of different ways to think of "how these thoughts get put together"

A⊆B.......A divides B.......A implies B, A is more restrictive a condition than B
AUB.........lcm(A,B)..........A or B (meaning: either/or/both)
A∩B.........gcd(A,B).........A and B (what A and B have in common)
A-B.............................A but not B

some basic things to recognize:

A∩B ⊆ A ⊆ AUB, for any A and B

A = (A-B)U(A∩B) (anything in A is either not in B, or in B)

(A-B)∩(A∩B) = { } (nothing in A is simultaneously not in B, and in B)

if A⊆B⊆C, then A⊆C.

if A⊆B, and B⊆A, then A = B.

it helps to draw venn diagrams. while these are not "proofs" per se, they help picture what is going on. use different colors, it helps.

when in doubt, make some "example sets", to test your theories. they don't have to be big, a handful of elements will often show flaws in your reasoning. if you need to reason about "large" sets, test your ideas on sets of natural numbers, which are (or can be) infinite sets most people are comfortable with. never underestimate the power of simple counting.

get comfortable with "direct proofs" first. proof-by-contrapositive, and proof by contradiction can trip you up if you are not sure of what it is you're trying to negate, and why. forums like these are good, but sounding your proof off another person in real-time is better. if you can convince someone else what you are saying is true, maybe it is. try to find flaws in your argument (hint: it's usually the parts you're not sure about).
• Jan 26th 2013, 06:55 AM
engpro
Re: is this proof ok?
thanks everybody for all your great advice and help. :)