(a C b) and (b C a) implies a=b?

[David Carroll]

Greetings. I have been studying David Poole's Linear Algebra textbook and I discovered in the Appendix that if it can be shown that if the set A is a sub-set of B and B is a sub-set of A, then the set A is exactly the same as the set B. And this all seems intuitively plausible, but for the life of me I couldn't prove it. No proof was adduced in the textbook, but I assume such a proof exists.

Is it simply an axiom or is it derived from something else?

I tried to take it along these lines: Some of the elements of B form the entirety of the elements of A. And the some of the elements of B form the entirety of the elements of B.

I even tried to pictorialize it with an ad hoc variation of the Venn diagram, where the bubble representing B curled around and entered A in a sort of two-dimensional Klein bottle. No help here either.

Any suggestions?

 

[Orodruin]

Try to assume the opposite and show that it leads to a contradiction.

 

[David Carroll]

Hmmmm. I'll try.

Okay, let N_a represent the number of elements of the set A. Let N_b represent the number of elements of set B.

Then, if every element of set A is an element of set B it follows that N_a is less than or equal to N_b. Also, if every element of set B is an element of set A, it follows that N_b is less than or equal to N_a.

But if N_a < N_b then N_b cannot < N_a, therefore the number of elements of B equals the number of elements of A.

Does that work? Or is something missing?

 

[PeroK]

Greetings. I have been studying David Poole's Linear Algebra textbook and I discovered in the Appendix that if it can be shown that if the set A is a sub-set of B and B is a sub-set of A, then the set A is exactly the same as the set B. And this all seems intuitively plausible, but for the life of me I couldn't prove it. No proof was adduced in the textbook, but I assume such a proof exists.

Is it simply an axiom or is it derived from something else?

I tried to take it along these lines: Some of the elements of B form the entirety of the elements of A. And the some of the elements of B form the entirety of the elements of B.

I even tried to pictorialize it with an ad hoc variation of the Venn diagram, where the bubble representing B curled around and entered A in a sort of two-dimensional Klein bottle. No help here either.

Any suggestions?

I'm not sure what you are trying to picture. A = B clearly meets the criteria. Remember that "subset of" means "proper subset of or equal to".

There can be no other option. B cannot be a proper subset of A, because then A cannot be a subset of B, so B must be equal to A.

You can in fact take this as the definition of equality for sets:

$A = B$ iff $A \subset B$ and $B \subset A$

It's a similar argument to: $a \le b$ and $b \le a$ implies $a = b$

 

[micromass]

This is an axiom called the axiom of extensionality.
http://en.wikipedia.org/wiki/Axiom_of_extensionality

 

[FactChecker]

Hmmmm. I'll try.

Okay, let N_a represent the number of elements of the set A. Let N_b represent the number of elements of set B.

Then, if every element of set A is an element of set B it follows that N_a is less than or equal to N_b. Also, if every element of set B is an element of set A, it follows that N_b is less than or equal to N_a.

But if N_a < N_b then N_b cannot < N_a, therefore the number of elements of B equals the number of elements of A.

Does that work? Or is something missing?

No. Two different sets can have the same number of elements. So proving that the sets have the same cardinality will not prove that the sets are equal. For a formal proof, you need to rely on the formal definition of equality of 2 sets. I am sure you can prove it directly or by contradiction. Assume A and B are different. Does that mean there is an element in one that is not in the other? Then where does that lead you?

 

[David Carroll]

That last one did it for me. Thank you, FactChecker.

 

[Helolo]

I'm not sure what you are trying to picture. A = B clearly meets the criteria. Remember that "subset of" means "proper subset of or equal to".

There can be no other option. B cannot be a proper subset of A, because then A cannot be a subset of B, so B must be equal to A.

You can in fact take this as the definition of equality for sets:

$A = B$ iff $A \subset B$ and $B \subset A$

It's a similar argument to: $a \le b$ and $b \le a$ implies $a = b$

Yup, that's right. But this is wrong $a < b, b < a \Rightarrow a = b$