The Whatjection?
True or false? :
"If there is an injection f : A → B , and a surjection g : A → B , then there is a bijection h : A → B ."
Assume that the axiom of choice is true.
Adapted from a book by Richard Hammack.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
You say "If there is a surjection from A to B , then ∣ A ∣ ≥ ∣ B ∣ " How do we know that?
Log in to reply
Assuming the axiom of choice, this seems to be a valid statement. Or is there some trick going on here after all?
Log in to reply
Who said we are assuming the axiom of choice? I think in set-theoretical matters this assumption should always be spelled out...
Log in to reply
@Otto Bretscher – Good point; perhaps @Pi Han Goh may want to consider adding this condition so that the answer is unambiguously "True".
And this is yet another example of why I tend to avoid MCQs. :)
Log in to reply
@Brian Charlesworth – I doubt there is a need to clarify, I used some fancy theorem that I just learned recently to get this. I don't think Mursalin Habib's answer is 100% valid but I'm waiting for responses.
Log in to reply
@Pi Han Goh – are you saying you can prove this without the Axiom of Choice? I always felt that not relying on the Axiom of Choice is the only thing that makes set theory (mildly) interesting ;)
Log in to reply
@Otto Bretscher – I believe so, I'm fairly new to this so I won't jump into any conclusion by posting a solution that I'm not definitely sure of. MILDLY?!?!?!!?! Are you mad!?
Log in to reply
@Pi Han Goh – Yes, as you may have figured our by now, I am indeed (mildly) mad ;)
As you can infer from my remark, set theory is not one of my fortes or interests, but I would be very surprised to see a proof of this without the Axiom of Choice. "If there is a surjection from A to B , then ∣ A ∣ ≥ ∣ B ∣ " is known as the "Partition Principle"... you can't get it without the axiom of Choice.
@Pi Han Goh – I guess that the "fancy theorem" you speak of is the Cantor-Bernstein Theorem .
Although, this is not necessarily true if you assume ZF . Check out the following two posts: Math SE post and referenced MO post .
Log in to reply
@Prasun Biswas – WoW that's quick! Can you post a solution?
Log in to reply
@Pi Han Goh – Sadly, no. Since this is not necessarily true in ZF, I answered "False". So, my answer is marked "incorrect" and hence, I can't post a solution officially. If you say, I can try to provide a solution in the comments.
Log in to reply
@Prasun Biswas – I'm starting to think that the answer should be "Like the continuum hypothesis, ... " because of your last link. Sure, post your solution here in the comment section, or filing a report works too!
Log in to reply
@Pi Han Goh – Done! Sorry for the delay, the power at my place went out for a couple of hours. If you agree with the dispute, do upvote it. Thanks.
MCQs are super super scary indeed. In exams I always do pretty well in the open-ended sections, but suffer for MCQs.
Except in Bio. I can't bring myself to regurgitate everything, you know.
Haha. And here I thought I was the only one who fears MCQs. I'm always expecting there to be some trick involved, but at least in this case there wasn't.
It is a simple sum.If a function which is both surjection and injection then the function is bijection.
Careful. What you say is in general true when we are talking about one function. But here we have two, potentially different functions f : A → B and g : B → A
True.
If there is an injection from A to B , then ∣ A ∣ ≤ ∣ B ∣ .
If there is a surjection from A to B , then ∣ A ∣ ≥ ∣ B ∣ .
Combine the two and you have ∣ A ∣ = ∣ B ∣ .
That means there is a bijection from A to B .
I read this question at least five times before answering. MCQs scare the hell out of me.