YAMT: Set Theory Proof

[stan394]

actually, can you fill us people (who left school for a while) in what an 'injection' and a 'bijection' is?

 

[Goosemaster]

Originally posted by: DVK916

Originally posted by: Goosemaster

Originally posted by: blustori

Originally posted by: Goosemaster
<----knows what hte answer is but tryign to put it in the correct ofrm

which is the same thing as not knowing the answer.

Assuming that both A and B are sets for the function f


by definition if there exists an injection both ways, every Value in set A inputed into function F has a unique and corressponding value in Set B and every valin in set B has a unique and corressponding value in set A.

Therefore, there are no values that disprove an injection and by definition, that is the definition of a bijection


but I can't say that

You seem to be making a leap. I don't think you can go from that to that.

I know...and I made an error...

 

[DVK916]

Originally posted by: stan394
actually, can you fill us people (who left school for a while) in what an 'injection' and a 'bijection' is?

Injection means there exsist a one to one function. Bijection means there is a one to one and onto function.

 

[Goosemaster]

Originally posted by: stan394
actually, can you fill us people (who left school for a while) in what an 'injection' and a 'bijection' is?

say you have a function f(), where f(x)=y

Say that you have a set of input valus (x's) let's call that A

Say that you have a set of output valus (y's) let's call that B

Let's say that for every value you input from set A into the function f you have a unique and coressponding value in set B.

Injection, by definition, states that for value in set A, there is a distinct value in set B.

IF that is the case, then this is an example of injection.

What if you have values in B that are not results of inputted values from a? (think of them as stragglers)

Well, in that case, as long as every value from A has a unique value in B, then it is still injection


however, the OP statedthat there is injection both ways, in that for every Value in B, there is a distinct value in A for it.

the definition of bijection ( I call it onto) is that every value in set A has a corressponding and unique value in Set B, and vice versa.

 

[DVK916]

Also if there is a injection from A to B the cardinality of A is lesser than or equal to the cardinality of B.

 

[Goosemaster]

lol..I jsut wrote the wrong proof...it proved injection..not bijection
lol

one swec

btw, this whole typing stuff out stuff drives me nuts:|

 

[Dissipate]

This is easy. Try proof by contradiction.

Suppose you have a function f that sends an element of A to an element of B and a function g that sends an element of B to an element of A. What if f cannot be constructed so as to be an injection from A to B or g cannot be constructed so as to be an injection from from B to A? Hmm, wonder what that tells you about one of the sets....

 

[Goosemaster]

Originally posted by: Dissipate
This is easy. Try proof by contradiction.

Suppose you have a function f that sends an element of A to an element of B and a function g that sends an element of B to an element of A. What if f cannot be constructed so as to be an injection from A to B or g cannot be constructed so as to be an injection from from B to A? Hmm, wonder what that tells you about one of the sets....

for the fnction f(x)=2x+1:

suppose that set B is a set of all odd positive integers defined by all y in R begining with 5.

suppose that set A is defined by all x in R.





is this bijection?

 

[DVK916]

The name of this Theorm is Cantor Shroder Bernstiene Theorm. It was first proven by Cantor with the Axiom of choice. Prof though wants us to try and figure out a proof that does not use the Axiom of choice.

 

[Dissipate]

Originally posted by: Goosemaster

Originally posted by: Dissipate
This is easy. Try proof by contradiction.

Suppose you have a function f that sends an element of A to an element of B and a function g that sends an element of B to an element of A. What if f cannot be constructed so as to be an injection from A to B or g cannot be constructed so as to be an injection from from B to A? Hmm, wonder what that tells you about one of the sets....

suppose that set B is a set of all odd positive integers begining with 5.

suppose that set A is defined by the set 2n+1 for all x in R.

A is defined by the set 2n + 1 for all x in R? HuH?

 

[Goosemaster]

Originally posted by: DVK916
The name of this Theorm is Cantor Shroder Bernstiene Theorm. It was first proven by Cantor with the Axiom of choice. Prof though wants us to try and figure out a proof that does not use the Axiom of choice.

I don't care what his name is.read what we wrote. Dissipate is giving you good stuff.

 

[Goosemaster]

Originally posted by: Dissipate

Originally posted by: Goosemaster

Originally posted by: Dissipate
This is easy. Try proof by contradiction.

Suppose you have a function f that sends an element of A to an element of B and a function g that sends an element of B to an element of A. What if f cannot be constructed so as to be an injection from A to B or g cannot be constructed so as to be an injection from from B to A? Hmm, wonder what that tells you about one of the sets....

suppose that set B is a set of all odd positive integers begining with 5.

suppose that set A is defined by the set 2n+1 for all x in R.

A is defined by the set 2n + 1 for all x in R? HuH?

I fixed it

 

[DVK916]

Originally posted by: Goosemaster

Originally posted by: DVK916
The name of this Theorm is Cantor Shroder Bernstiene Theorm. It was first proven by Cantor with the Axiom of choice. Prof though wants us to try and figure out a proof that does not use the Axiom of choice.

I don't care what his name is.read what we wrote. Dissipate is giving you good stuff.

I am. I think I can figure out the whole proof now.

 

[Goosemaster]

Originally posted by: DVK916

Originally posted by: Goosemaster

Originally posted by: DVK916
The name of this Theorm is Cantor Shroder Bernstiene Theorm. It was first proven by Cantor with the Axiom of choice. Prof though wants us to try and figure out a proof that does not use the Axiom of choice.

I don't care what his name is.read what we wrote. Dissipate is giving you good stuff.

I am. I think I can figure out the whole proof now.

:thumbsup:

 

[DVK916]

Thanks for all of the help people.

 

[Dissipate]

Originally posted by: Goosemaster

Originally posted by: Dissipate
This is easy. Try proof by contradiction.

Suppose you have a function f that sends an element of A to an element of B and a function g that sends an element of B to an element of A. What if f cannot be constructed so as to be an injection from A to B or g cannot be constructed so as to be an injection from from B to A? Hmm, wonder what that tells you about one of the sets....

for the fnction f(x)=2x+1:

suppose that set B is a set of all odd positive integers defined by all y in R begining with 5.

suppose that set A is defined by all x in R.





is this bijection?

No. Cantor's theorem proves that.

 

[Goosemaster]

Originally posted by: Dissipate

Originally posted by: Goosemaster

Originally posted by: Dissipate
This is easy. Try proof by contradiction.

Suppose you have a function f that sends an element of A to an element of B and a function g that sends an element of B to an element of A. What if f cannot be constructed so as to be an injection from A to B or g cannot be constructed so as to be an injection from from B to A? Hmm, wonder what that tells you about one of the sets....

for the fnction f(x)=2x+1:

suppose that set B is a set of all odd positive integers defined by all y in R begining with 5.

suppose that set A is defined by all x in R.





is this bijection?

No. Cantor's theorem proves that.

I know it is not....

 

[stan394]

If there is injection from A to B, and an injection from B to A then there must exist a bijection from A to B.

bijection is both 1 to 1 and onto. The 1 to 1 part is already given by the problem. So we need to prove the onto part.

Assume the contrary, there is a b in B, where there is no a in A and f(a) = b. Since f is injective, each distinct a in A is mapped to a distinct b in B. So there are at least 1 more element in B than in A. So there is no way you can map each distinct b in B back to a distinct a in A (pigeon hole theory) without having 2 b mapping to the same a.

can this be right?

 

[Goosemaster]

Originally posted by: stan394

If there is injection from A to B, and an injection from B to A then there must exist a bijection from A to B.

bijection is both 1 to 1 and onto. The 1 to 1 part is already given by the problem. So we need to prove the onto part.

Assume the contrary, there is a b in B, where there is no a in A and f(a) = b. Since f is injective, each distinct a in A is mapped to a distinct b in B. So there are at least 1 more element in B than in A. So there is no way you can map each distinct b in B back to a distinct a in A (pigeon hole theory) without having 2 b mapping to the same a.

can this be right?

yeah.

Each set needs to satisfy the other, which means that they must be the same

 

[crt1530]

Use a proof by contradiction like stan394 suggested. You have the injections from A to B and from B to A. Assume that there is no surjection from A to B. Using the defintion of surjective and injective, you come to a contradiction that violates your assumption (no surjection). Thus, there is a surjection. Since there is a surjection and an injection (from A to B) there is a bijection. QED

 

[Goosemaster]

Originally posted by: crt1530
Use a proof by contradiction like stan394 suggested. You have the injections from A to B and from B to A. Assume that there is no surjection from A to B. Using the defintion of surjective and injective, you come to a contradiction that violates your assumption (no surjection). Thus, there is a surjection. Since there is a surjection and an injection (from A to B) there is a bijection. QED

contraposition ftw