Without axiom of choice

Clash Royale CLAN TAG#URR8PPP

up vote
2
down vote

favorite

We denote by $A$, $A′$, $B$, $B′$ the four sets.

We are given mapping $u:A′→A$, $v:B→B′$.

We denote by $F(A, B)$ the set maps $A→B$ ，$F(A′, B′)$ the set maps $A′→B′$.

Let $Φ : F(A, B) → F(A′, B′)$ be a mappig which makes $v◦f ◦ u ∈ F(A′, B′)$ correspond with for $f ∈ F(A, B)$.

Prove that we can't prove "$u$ is injective and $v$ is surjective $⇒$ $Φ$ is surjective." without Axiom of choice.

axiom-of-choice

share|cite|improve this question

edited Jul 15 at 8:34

md2perpe

6,00011022

asked Jul 15 at 7:29

Pacifica

458

• 
  
  
  

  
  

  
  
  
  
  
  

  
  I'm confused. Are we to show the validity of your implication implies the axiom of choice?
  – Alvin Lepik
  Jul 15 at 8:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I just want to show that it's impossible to prove "$u$ is injective and $v$ is surjective $⇒$ $Φ$ is surjective" without using Axiom of choice.
  – Pacifica
  Jul 15 at 8:57
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  So you want to show the undecidability of this implication in ZF, right?
  – joriki
  Jul 15 at 9:28
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @AlvinLepik : essentially OP wants a choiceless model with $2$ maps $u,v$ that are injective (resp. surjective) such that $fmapsto vcirc fcirc u$ is not surjective
  – Max
  Jul 15 at 9:28
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Either that or a proof of AC from the implication
  – Max
  Jul 15 at 9:29
  

  
  
  
  

 | 
show 1 more comment

up vote
2
down vote

favorite

We denote by $A$, $A′$, $B$, $B′$ the four sets.

We are given mapping $u:A′→A$, $v:B→B′$.

We denote by $F(A, B)$ the set maps $A→B$ ，$F(A′, B′)$ the set maps $A′→B′$.

Let $Φ : F(A, B) → F(A′, B′)$ be a mappig which makes $v◦f ◦ u ∈ F(A′, B′)$ correspond with for $f ∈ F(A, B)$.

Prove that we can't prove "$u$ is injective and $v$ is surjective $⇒$ $Φ$ is surjective." without Axiom of choice.

axiom-of-choice

share|cite|improve this question

edited Jul 15 at 8:34

md2perpe

6,00011022

asked Jul 15 at 7:29

Pacifica

458

• 
  
  
  

  
  

  
  
  
  
  
  

  
  I'm confused. Are we to show the validity of your implication implies the axiom of choice?
  – Alvin Lepik
  Jul 15 at 8:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I just want to show that it's impossible to prove "$u$ is injective and $v$ is surjective $⇒$ $Φ$ is surjective" without using Axiom of choice.
  – Pacifica
  Jul 15 at 8:57
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  So you want to show the undecidability of this implication in ZF, right?
  – joriki
  Jul 15 at 9:28
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @AlvinLepik : essentially OP wants a choiceless model with $2$ maps $u,v$ that are injective (resp. surjective) such that $fmapsto vcirc fcirc u$ is not surjective
  – Max
  Jul 15 at 9:28
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Either that or a proof of AC from the implication
  – Max
  Jul 15 at 9:29
  

  
  
  
  

 | 
show 1 more comment

up vote
2
down vote

favorite

up vote
2
down vote

favorite

We denote by $A$, $A′$, $B$, $B′$ the four sets.

We are given mapping $u:A′→A$, $v:B→B′$.

We denote by $F(A, B)$ the set maps $A→B$ ，$F(A′, B′)$ the set maps $A′→B′$.

Let $Φ : F(A, B) → F(A′, B′)$ be a mappig which makes $v◦f ◦ u ∈ F(A′, B′)$ correspond with for $f ∈ F(A, B)$.

Prove that we can't prove "$u$ is injective and $v$ is surjective $⇒$ $Φ$ is surjective." without Axiom of choice.

axiom-of-choice

share|cite|improve this question

edited Jul 15 at 8:34

md2perpe

6,00011022

asked Jul 15 at 7:29

Pacifica

458

We denote by $A$, $A′$, $B$, $B′$ the four sets.

We are given mapping $u:A′→A$, $v:B→B′$.

We denote by $F(A, B)$ the set maps $A→B$ ，$F(A′, B′)$ the set maps $A′→B′$.

Let $Φ : F(A, B) → F(A′, B′)$ be a mappig which makes $v◦f ◦ u ∈ F(A′, B′)$ correspond with for $f ∈ F(A, B)$.

Prove that we can't prove "$u$ is injective and $v$ is surjective $⇒$ $Φ$ is surjective." without Axiom of choice.

axiom-of-choice

share|cite|improve this question

edited Jul 15 at 8:34

md2perpe

6,00011022

asked Jul 15 at 7:29

Pacifica

458

share|cite|improve this question

share|cite|improve this question

edited Jul 15 at 8:34

md2perpe

6,00011022

edited Jul 15 at 8:34

md2perpe

6,00011022

edited Jul 15 at 8:34

md2perpe

6,00011022

6,00011022

asked Jul 15 at 7:29

Pacifica

458

asked Jul 15 at 7:29

Pacifica

458

asked Jul 15 at 7:29

Pacifica

458

458

• 
  
  
  

  
  

  
  
  
  
  
  

  
  I'm confused. Are we to show the validity of your implication implies the axiom of choice?
  – Alvin Lepik
  Jul 15 at 8:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I just want to show that it's impossible to prove "$u$ is injective and $v$ is surjective $⇒$ $Φ$ is surjective" without using Axiom of choice.
  – Pacifica
  Jul 15 at 8:57
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  So you want to show the undecidability of this implication in ZF, right?
  – joriki
  Jul 15 at 9:28
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @AlvinLepik : essentially OP wants a choiceless model with $2$ maps $u,v$ that are injective (resp. surjective) such that $fmapsto vcirc fcirc u$ is not surjective
  – Max
  Jul 15 at 9:28
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Either that or a proof of AC from the implication
  – Max
  Jul 15 at 9:29
  

  
  
  
  

 | 
show 1 more comment

• 
  
  
  

  
  

  
  
  
  
  
  

  
  I'm confused. Are we to show the validity of your implication implies the axiom of choice?
  – Alvin Lepik
  Jul 15 at 8:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I just want to show that it's impossible to prove "$u$ is injective and $v$ is surjective $⇒$ $Φ$ is surjective" without using Axiom of choice.
  – Pacifica
  Jul 15 at 8:57
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  So you want to show the undecidability of this implication in ZF, right?
  – joriki
  Jul 15 at 9:28
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @AlvinLepik : essentially OP wants a choiceless model with $2$ maps $u,v$ that are injective (resp. surjective) such that $fmapsto vcirc fcirc u$ is not surjective
  – Max
  Jul 15 at 9:28
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Either that or a proof of AC from the implication
  – Max
  Jul 15 at 9:29
  

  
  
  
  

I'm confused. Are we to show the validity of your implication implies the axiom of choice?
– Alvin Lepik
Jul 15 at 8:49

I'm confused. Are we to show the validity of your implication implies the axiom of choice?
– Alvin Lepik
Jul 15 at 8:49

I just want to show that it's impossible to prove "$u$ is injective and $v$ is surjective $⇒$ $Φ$ is surjective" without using Axiom of choice.
– Pacifica
Jul 15 at 8:57

I just want to show that it's impossible to prove "$u$ is injective and $v$ is surjective $⇒$ $Φ$ is surjective" without using Axiom of choice.
– Pacifica
Jul 15 at 8:57

So you want to show the undecidability of this implication in ZF, right?
– joriki
Jul 15 at 9:28

So you want to show the undecidability of this implication in ZF, right?
– joriki
Jul 15 at 9:28

@AlvinLepik : essentially OP wants a choiceless model with $2$ maps $u,v$ that are injective (resp. surjective) such that $fmapsto vcirc fcirc u$ is not surjective
– Max
Jul 15 at 9:28

@AlvinLepik : essentially OP wants a choiceless model with $2$ maps $u,v$ that are injective (resp. surjective) such that $fmapsto vcirc fcirc u$ is not surjective
– Max
Jul 15 at 9:28

Either that or a proof of AC from the implication
– Max
Jul 15 at 9:29

Either that or a proof of AC from the implication
– Max
Jul 15 at 9:29

 | 
show 1 more comment

1 Answer
1

active

oldest

votes

up vote
5
down vote



accepted

Actually, the $u$ part is misleading, because $fmapsto fcirc u$ is surjective if $u$ is injective, without the axiom of choice. The interesting part is about $v$ !

So we may as well take $u= id_A'$. And now the implication we have is "$v$ surjective implies $fmapsto vcirc f$ surjective" and we want to see that this implies the axiom of choice.

Consider : $fmapsto vcirc f$, $F(B', B)to F(B',B')$.

If you take $id_B'in F(B',B')$, the surjectivity of this map implies that $v$ has a section, i.e. there is a function $B'to B$ that picks out an antecedent for each element of $B'$.

It's known that "every surjective function has a section" implies the axiom of choice, so there you go

share|cite|improve this answer

answered Jul 15 at 9:36

Max

10.4k1836

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Actually, there was another proposition: "$u$ is surjective and $v$ is injective $⇒$ $Φ$ is injective"...(ii) We can prove (ii) without the axiom of choice simply. So, without the axiom of choice: We can prove the question I posted, but can't prove (ii). So, I think this would be one of the reasons which vindicate the axiom of choice.
  – Pacifica
  Jul 15 at 13:57
  
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2852272%2fwithout-axiom-of-choice%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
5
down vote



accepted

Actually, the $u$ part is misleading, because $fmapsto fcirc u$ is surjective if $u$ is injective, without the axiom of choice. The interesting part is about $v$ !

So we may as well take $u= id_A'$. And now the implication we have is "$v$ surjective implies $fmapsto vcirc f$ surjective" and we want to see that this implies the axiom of choice.

Consider : $fmapsto vcirc f$, $F(B', B)to F(B',B')$.

If you take $id_B'in F(B',B')$, the surjectivity of this map implies that $v$ has a section, i.e. there is a function $B'to B$ that picks out an antecedent for each element of $B'$.

It's known that "every surjective function has a section" implies the axiom of choice, so there you go

share|cite|improve this answer

answered Jul 15 at 9:36

Max

10.4k1836

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Actually, there was another proposition: "$u$ is surjective and $v$ is injective $⇒$ $Φ$ is injective"...(ii) We can prove (ii) without the axiom of choice simply. So, without the axiom of choice: We can prove the question I posted, but can't prove (ii). So, I think this would be one of the reasons which vindicate the axiom of choice.
  – Pacifica
  Jul 15 at 13:57
  
  

  
  
  
  

add a comment | 

up vote
5
down vote



accepted

Actually, the $u$ part is misleading, because $fmapsto fcirc u$ is surjective if $u$ is injective, without the axiom of choice. The interesting part is about $v$ !

So we may as well take $u= id_A'$. And now the implication we have is "$v$ surjective implies $fmapsto vcirc f$ surjective" and we want to see that this implies the axiom of choice.

Consider : $fmapsto vcirc f$, $F(B', B)to F(B',B')$.

If you take $id_B'in F(B',B')$, the surjectivity of this map implies that $v$ has a section, i.e. there is a function $B'to B$ that picks out an antecedent for each element of $B'$.

It's known that "every surjective function has a section" implies the axiom of choice, so there you go

share|cite|improve this answer

answered Jul 15 at 9:36

Max

10.4k1836

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Actually, there was another proposition: "$u$ is surjective and $v$ is injective $⇒$ $Φ$ is injective"...(ii) We can prove (ii) without the axiom of choice simply. So, without the axiom of choice: We can prove the question I posted, but can't prove (ii). So, I think this would be one of the reasons which vindicate the axiom of choice.
  – Pacifica
  Jul 15 at 13:57
  
  

  
  
  
  

add a comment | 

up vote
5
down vote



accepted

up vote
5
down vote



accepted

Actually, the $u$ part is misleading, because $fmapsto fcirc u$ is surjective if $u$ is injective, without the axiom of choice. The interesting part is about $v$ !

So we may as well take $u= id_A'$. And now the implication we have is "$v$ surjective implies $fmapsto vcirc f$ surjective" and we want to see that this implies the axiom of choice.

Consider : $fmapsto vcirc f$, $F(B', B)to F(B',B')$.

If you take $id_B'in F(B',B')$, the surjectivity of this map implies that $v$ has a section, i.e. there is a function $B'to B$ that picks out an antecedent for each element of $B'$.

It's known that "every surjective function has a section" implies the axiom of choice, so there you go

share|cite|improve this answer

answered Jul 15 at 9:36

Max

10.4k1836

Actually, the $u$ part is misleading, because $fmapsto fcirc u$ is surjective if $u$ is injective, without the axiom of choice. The interesting part is about $v$ !

So we may as well take $u= id_A'$. And now the implication we have is "$v$ surjective implies $fmapsto vcirc f$ surjective" and we want to see that this implies the axiom of choice.

Consider : $fmapsto vcirc f$, $F(B', B)to F(B',B')$.

If you take $id_B'in F(B',B')$, the surjectivity of this map implies that $v$ has a section, i.e. there is a function $B'to B$ that picks out an antecedent for each element of $B'$.

It's known that "every surjective function has a section" implies the axiom of choice, so there you go

share|cite|improve this answer

answered Jul 15 at 9:36

Max

10.4k1836

share|cite|improve this answer

share|cite|improve this answer

answered Jul 15 at 9:36

Max

10.4k1836

answered Jul 15 at 9:36

Max

10.4k1836

answered Jul 15 at 9:36

Max

10.4k1836

10.4k1836

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Actually, there was another proposition: "$u$ is surjective and $v$ is injective $⇒$ $Φ$ is injective"...(ii) We can prove (ii) without the axiom of choice simply. So, without the axiom of choice: We can prove the question I posted, but can't prove (ii). So, I think this would be one of the reasons which vindicate the axiom of choice.
  – Pacifica
  Jul 15 at 13:57
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Actually, there was another proposition: "$u$ is surjective and $v$ is injective $⇒$ $Φ$ is injective"...(ii) We can prove (ii) without the axiom of choice simply. So, without the axiom of choice: We can prove the question I posted, but can't prove (ii). So, I think this would be one of the reasons which vindicate the axiom of choice.
  – Pacifica
  Jul 15 at 13:57
  
  

  
  
  
  

Actually, there was another proposition: "$u$ is surjective and $v$ is injective $⇒$ $Φ$ is injective"...(ii) We can prove (ii) without the axiom of choice simply. So, without the axiom of choice: We can prove the question I posted, but can't prove (ii). So, I think this would be one of the reasons which vindicate the axiom of choice.
– Pacifica
Jul 15 at 13:57

Actually, there was another proposition: "$u$ is surjective and $v$ is injective $⇒$ $Φ$ is injective"...(ii) We can prove (ii) without the axiom of choice simply. So, without the axiom of choice: We can prove the question I posted, but can't prove (ii). So, I think this would be one of the reasons which vindicate the axiom of choice.
– Pacifica
Jul 15 at 13:57

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2852272%2fwithout-axiom-of-choice%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email