How would I prove this

A⊆B ^ |A|=|B| -> A=B

Is this proof ok and formal?

Suppose ¬(A⊆B ^ |A|=|B|)

Then |A|≠|B|

Therefore A⊆B ^ |A|=|B| -> A=B

Printable View

- May 13th 2011, 10:29 AMSneakyhelp with proving relaationship between sets
How would I prove this

A⊆B ^ |A|=|B| -> A=B

Is this proof ok and formal?

Suppose ¬(A⊆B ^ |A|=|B|)

Then |A|≠|B|

Therefore A⊆B ^ |A|=|B| -> A=B - May 13th 2011, 10:41 AMPlato
- May 13th 2011, 11:02 AMSneaky
I forgot to mention that the sets were finite.

So if A≠B then since A⊆B, then |A|<|B|

therefore A⊆B ^ |A|=|B| -> A=B

is this better?

why wont it work for non-finite sets?

Is it because then you cant say

A⊆B ^ |A|=|B| ? - May 13th 2011, 11:42 AMPlato
- May 13th 2011, 11:50 AMSneaky
does the symbol of the C with the 'not equal sign' under mean not a proper subset of ?

And also is my proof ok now? - May 13th 2011, 01:12 PMemakarovQuote:

does the symbol of the C with the 'not equal sign' under mean not a proper subset of ?

*proper*subset of Z^+, i.e., it does not equal the whole Z^+.

Quote:

And also is my proof ok now?

- May 13th 2011, 02:31 PMMoeBlee
(1) As has been pointed out, we need to assume that either A or B is finite.

(2) Your logic is wrong anyway. You don't prove P -> Q by assuming ~P and showing ~Q. You have it backwards. What you want here is to assume ~Q and show ~P.

So suppose ~A=B. Show ~(A subset of B & |A|=|B|). Suppose A subset of B. Then, since ~A=B, we have A proper subset of B. But no finite set has the same cardinality as a proper subset of itself (this is called 'the pigeonhole principle').

However, if you haven't already proven the pigeonhole principle, then you have to prove it, and that is a longer, more involved proof. - May 13th 2011, 03:31 PMSneaky
i dont understand what more i can add to this:

A and B are finite sets.

if A≠B then suppose A⊆B, then |A|<|B|

therefore A⊆B ^ |A|=|B| -> A=B - May 14th 2011, 09:12 AMMoeBlee