Are the following 3 statements true and does the cantor-bernstein theorem follow


by Wiz14
Tags: cantor set theory
Wiz14
Wiz14 is offline
#1
Nov23-12, 03:46 AM
P: 20
1.There exists an injection from A to B ⇔ A ≤ B
2.There exists an injection from B to A ⇔ B ≤ A
3.If A ≤ B and B ≤ A, then A = B

Does this prove the Cantor Bernstein theorem? Which says that if 1 and 2 then there exists a Bijection between A and B (A = B)

And if it does, why is there a different, longer proof for it?
Phys.Org News Partner Science news on Phys.org
Better thermal-imaging lens from waste sulfur
Hackathon team's GoogolPlex gives Siri extra powers
Bright points in Sun's atmosphere mark patterns deep in its interior
Norwegian
Norwegian is offline
#2
Nov23-12, 04:35 AM
P: 144
Quote Quote by Wiz14 View Post
1.There exists an injection from A to B ⇔ A ≤ B
2.There exists an injection from B to A ⇔ B ≤ A
3.If A ≤ B and B ≤ A, then A = B

Does this prove the Cantor Bernstein theorem?
No. 1) and 2) are definitions of ≤ and ≥ for cardinalities of sets. 3) is a nontrivial consequence for which you have provided no argument at all.
lugita15
lugita15 is offline
#3
Nov23-12, 01:43 PM
P: 1,583
Statement 3 IS the Cantor-Schroeder-Berstein theorem: "If the cardinality of A is less than or equal to the cardinality of B, and the cardinality of B is less than or equal to the cardinality of A, then the cardinality of A is equal to the cardinality of B." You can also state it as "If there is an injection from A to B, and there is an injection from B to A, then there is a bijection from A to B." As Norweigan said, it requires a nontrivial argument to prove this theorem.

EDIT: See the easy-to-understand proof here.

Wiz14
Wiz14 is offline
#4
Nov23-12, 02:03 PM
P: 20

Are the following 3 statements true and does the cantor-bernstein theorem follow


Quote Quote by lugita15 View Post
Statement 3 IS the Cantor-Schroeder-Berstein theorem: "If the cardinality of A is less than or equal to the cardinality of B, and the cardinality of B is less than or equal to the cardinality of A, then the cardinality of A is equal to the cardinality of B." You can also state it as "If there is an injection from A to B, and there is an injection from B to A, then there is a bijection from A to B." As Norweigan said, it requires a nontrivial argument to prove this theorem.

EDIT: See the easy-to-understand proof here.
I am reading that proof now but where is the flaw in my reasoning?
A ≤B and B ≤ A is like saying A = B or A is strictly less than B and B is strictly less than A, which is a contradiction, so A must = B.
lugita15
lugita15 is offline
#5
Nov23-12, 05:20 PM
P: 1,583
Quote Quote by Wiz14 View Post
I am reading that proof now but where is the flaw in my reasoning?
A ≤B and B ≤ A is like saying A = B or A is strictly less than B and B is strictly less than A, which is a contradiction, so A must = B.
If A and B were numbers, then yes it would be trivially true that if A≤B and B≤A then A would equal B. But A and B are sets, and what we mean by A≤B is that "there exists an injection from A to B". We don't know beforehand whether "less than or equal to" for sets, which has to do with existence of an injection, has the same properties as "less than or equal to" for numbers. We have to prove it. So you can't use your familiar properties of numbers, like the fact that two things can't be strictly less than each other.


Register to reply

Related Discussions
Cantor-schroder-bernstein use in proof Calculus & Beyond Homework 6
True or False Statements Brain Teasers 2
True Statements: Always Provable? Set Theory, Logic, Probability, Statistics 13
Which Statements are true? Introductory Physics Homework 1