# help with proving relaationship between sets

• May 13th 2011, 09:29 AM
Sneaky
help with proving relaationship between sets
How would I prove this

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

Is this proof ok and formal?

Suppose ¬(AB ^ |A|=|B|)
Then |A|≠|B|
Therefore A
B ^ |A|=|B| -> A=B
• May 13th 2011, 09:41 AM
Plato
Quote:

Originally Posted by Sneaky
How would I prove this
A⊆B ^ |A|=|B| -> A=B

THIS IS ONLY TRUE OF FINITE SETS.

That attempt falls short.
Doing this by contradiction, suppose $A\ne B~.$
But because $A\subseteq B$ what does that imply?
• May 13th 2011, 10:02 AM
Sneaky
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, 10:42 AM
Plato
Quote:

Originally Posted by Sneaky
why wont it work for non-finite sets?
Is it because then you cant say A⊆B ^ |A|=|B| ?

Let $\mathbb{E}$ be the set even positive integers.
Then $\mathbb{E}\subsetneq \mathbb{Z}^+$ BUT $|\mathbb{E}|=|\mathbb{Z}^+|$.
• May 13th 2011, 10:50 AM
Sneaky
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, 12:12 PM
emakarov
Quote:

does the symbol of the C with the 'not equal sign' under mean not a proper subset of ?
No, it means that E is a proper subset of Z^+, i.e., it does not equal the whole Z^+.

Quote:

And also is my proof ok now?
There is still a question whether enough details are provided to justify this statement: "if A≠B then since A⊆B, then |A|<|B|." This statement is true and sufficiently obvious, but whether more needs to be said depends on the course requirements and the definition of |A|.
• May 13th 2011, 01:31 PM
MoeBlee
Quote:

Originally Posted by Sneaky
How would I prove this

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

Is this proof ok and formal?

Suppose ¬(AB ^ |A|=|B|)
Then |A|≠|B|
Therefore AB ^ |A|=|B| -> A=B

(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, 02:31 PM
Sneaky
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, 08:12 AM
MoeBlee
Quote:

Originally Posted by Sneaky
if A≠B then suppose A⊆B, then |A|<|B|

Prove it.