Giving an explicit example showing that AC is independent of ZF.












4












$begingroup$


I know that the axiom of choice (AC)




For any set $X$ of nonempty sets, there exists a choice function defined on $X$.




is independent of ZF. Can one give an explicit example of such a set $X$ so that we have this independence?










share|cite|improve this question











$endgroup$












  • $begingroup$
    No, it's a forcing argument, combined with the existence of the constructible universe that shows this independence. I'll leave this to @AsafKaragila, the expert on these matters.
    $endgroup$
    – Henno Brandsma
    Nov 25 '18 at 16:14
















4












$begingroup$


I know that the axiom of choice (AC)




For any set $X$ of nonempty sets, there exists a choice function defined on $X$.




is independent of ZF. Can one give an explicit example of such a set $X$ so that we have this independence?










share|cite|improve this question











$endgroup$












  • $begingroup$
    No, it's a forcing argument, combined with the existence of the constructible universe that shows this independence. I'll leave this to @AsafKaragila, the expert on these matters.
    $endgroup$
    – Henno Brandsma
    Nov 25 '18 at 16:14














4












4








4


1



$begingroup$


I know that the axiom of choice (AC)




For any set $X$ of nonempty sets, there exists a choice function defined on $X$.




is independent of ZF. Can one give an explicit example of such a set $X$ so that we have this independence?










share|cite|improve this question











$endgroup$




I know that the axiom of choice (AC)




For any set $X$ of nonempty sets, there exists a choice function defined on $X$.




is independent of ZF. Can one give an explicit example of such a set $X$ so that we have this independence?







logic set-theory axiom-of-choice






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 25 '18 at 16:12









Henno Brandsma

112k348120




112k348120










asked Nov 25 '18 at 16:11









A. ChuA. Chu

7,04093384




7,04093384












  • $begingroup$
    No, it's a forcing argument, combined with the existence of the constructible universe that shows this independence. I'll leave this to @AsafKaragila, the expert on these matters.
    $endgroup$
    – Henno Brandsma
    Nov 25 '18 at 16:14


















  • $begingroup$
    No, it's a forcing argument, combined with the existence of the constructible universe that shows this independence. I'll leave this to @AsafKaragila, the expert on these matters.
    $endgroup$
    – Henno Brandsma
    Nov 25 '18 at 16:14
















$begingroup$
No, it's a forcing argument, combined with the existence of the constructible universe that shows this independence. I'll leave this to @AsafKaragila, the expert on these matters.
$endgroup$
– Henno Brandsma
Nov 25 '18 at 16:14




$begingroup$
No, it's a forcing argument, combined with the existence of the constructible universe that shows this independence. I'll leave this to @AsafKaragila, the expert on these matters.
$endgroup$
– Henno Brandsma
Nov 25 '18 at 16:14










2 Answers
2






active

oldest

votes


















4












$begingroup$

Depending on what exactly you mean by "explicit example," we can do this.



The situation is simpler with respect to the well-ordering principle, which after all is equivalent to the axiom of choice: it is consistent with ZF that $mathbb{R}$ cannot be well-ordered.



To translate this into a concrete example of a possible failure of the axiom of choice, we can look at the proof that the axiom of choice implies the well-ordering principle: all we need to do in order to well-order $mathbb{R}$ is have a way to, given $Asubsetneqmathbb{R}$, pick some $ainmathbb{R}setminus A$, and so this means that the family $$(mathbb{R}setminus A)_{Asubsetneqmathbb{R}}$$ consistently has no choice function.



Of course, a snappier way to say this is that consistently the family of nonempty (as opposed to proper) subsets of $mathbb{R}$ does not have a choice function - we just switch from $A$ to $mathbb{R}setminus A$ - but the formulation above makes the connection with the well-orderability of $mathbb{R}$ clearer.





Now there are many subtleties around this. I'll mention just one (looking at the well-ordering principle instead of choice, just for simplicity):



Since $mathbb{R}$ is consistently non-well-orderable, there is no formula $varphi$ in the language of set theory which ZF proves is a well-ordering of $mathbb{R}$. However, this does notmean that there can be no definable well-ordering of $mathbb{R}$! There are many formulas which consistently define well-orderings of $mathbb{R}$, chiefly among them the following:




$rtriangleleft s$ iff $r$ precedes $s$ in the canonical well-ordering of $L$.




Here $L$ is Godel's constructible universe, which has a definable (class) well-ordering (if you prefer to avoid proper classes, you can just look at $L_{omega_1}$ since $mathbb{R}cap L=mathbb{R}cap L_{omega_1}$).



We can, however, do even snappier. It is disturbingly possible for everything to be definable: that is, there are models $Mmodels$ ZF such that every element of $M$ is definable in $M$ without parameters. In this case, the usual lexicographic well-ordering on the set of formulas in the language of set theory yields a well-ordering of the whole model, which restricts to a well-ordering of $mathbb{R}$ (or rather, what the model thinks is $mathbb{R}$). I mention this because it's a good example of just how subtle the situation can be, and starts to indicate why the "explicit example" above may not be as satisfying as it first appears.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    You missed the clause $Aneemptyset$.
    $endgroup$
    – Andrés E. Caicedo
    Nov 25 '18 at 18:59










  • $begingroup$
    @AndrésE.Caicedo Hm? I'm picking a real not in $A$, so $A=emptyset$ is fine - it's $A=mathbb{R}$ I need to rule out, which I did via "$subsetneq$" instead of "$subseteq$." Or am I missing something?
    $endgroup$
    – Noah Schweber
    Nov 25 '18 at 19:43












  • $begingroup$
    @AndrésE.Caicedo I've added a clause to clarify.
    $endgroup$
    – Noah Schweber
    Nov 25 '18 at 20:11










  • $begingroup$
    Ah, yes. Sorry) :-)
    $endgroup$
    – Andrés E. Caicedo
    Nov 25 '18 at 20:20



















4












$begingroup$

The simplest example, I guess, is the power set of the real numbers (without the real numbers).



It is consistent that there is no choice function from that set, and of course assuming choice, there is a choice function.



But there is a subtle issue here or syntactic and semantic point. Since we can add a choice function for a fixed family by forcing, or similarly we can always extend a model of ZF so there is no choice function from the sets of real numbers, we need to be careful and ask what are the sets of reals. In different models the answer would be different.



In addition to that, starting from a model of ZFC, we can make choice fail badly but keeping some initial segment of the universe well ordered (and thus admitting a choice function). So this adds even more confusion to the fire, as Henno points out in the comments, which set is not well ordered is not something that ZF itself can decide. Not even ZF with the failure of AC.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Quibble: $mathcal{P}(mathbb{R})setminus{emptyset}$.
    $endgroup$
    – Noah Schweber
    Nov 25 '18 at 20:12










  • $begingroup$
    I wrote this from my phone in a car on the way to Rome with shoddy connection. What's your excuse? :-)
    $endgroup$
    – Asaf Karagila
    Nov 25 '18 at 22:21











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',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3013027%2fgiving-an-explicit-example-showing-that-ac-is-independent-of-zf%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









4












$begingroup$

Depending on what exactly you mean by "explicit example," we can do this.



The situation is simpler with respect to the well-ordering principle, which after all is equivalent to the axiom of choice: it is consistent with ZF that $mathbb{R}$ cannot be well-ordered.



To translate this into a concrete example of a possible failure of the axiom of choice, we can look at the proof that the axiom of choice implies the well-ordering principle: all we need to do in order to well-order $mathbb{R}$ is have a way to, given $Asubsetneqmathbb{R}$, pick some $ainmathbb{R}setminus A$, and so this means that the family $$(mathbb{R}setminus A)_{Asubsetneqmathbb{R}}$$ consistently has no choice function.



Of course, a snappier way to say this is that consistently the family of nonempty (as opposed to proper) subsets of $mathbb{R}$ does not have a choice function - we just switch from $A$ to $mathbb{R}setminus A$ - but the formulation above makes the connection with the well-orderability of $mathbb{R}$ clearer.





Now there are many subtleties around this. I'll mention just one (looking at the well-ordering principle instead of choice, just for simplicity):



Since $mathbb{R}$ is consistently non-well-orderable, there is no formula $varphi$ in the language of set theory which ZF proves is a well-ordering of $mathbb{R}$. However, this does notmean that there can be no definable well-ordering of $mathbb{R}$! There are many formulas which consistently define well-orderings of $mathbb{R}$, chiefly among them the following:




$rtriangleleft s$ iff $r$ precedes $s$ in the canonical well-ordering of $L$.




Here $L$ is Godel's constructible universe, which has a definable (class) well-ordering (if you prefer to avoid proper classes, you can just look at $L_{omega_1}$ since $mathbb{R}cap L=mathbb{R}cap L_{omega_1}$).



We can, however, do even snappier. It is disturbingly possible for everything to be definable: that is, there are models $Mmodels$ ZF such that every element of $M$ is definable in $M$ without parameters. In this case, the usual lexicographic well-ordering on the set of formulas in the language of set theory yields a well-ordering of the whole model, which restricts to a well-ordering of $mathbb{R}$ (or rather, what the model thinks is $mathbb{R}$). I mention this because it's a good example of just how subtle the situation can be, and starts to indicate why the "explicit example" above may not be as satisfying as it first appears.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    You missed the clause $Aneemptyset$.
    $endgroup$
    – Andrés E. Caicedo
    Nov 25 '18 at 18:59










  • $begingroup$
    @AndrésE.Caicedo Hm? I'm picking a real not in $A$, so $A=emptyset$ is fine - it's $A=mathbb{R}$ I need to rule out, which I did via "$subsetneq$" instead of "$subseteq$." Or am I missing something?
    $endgroup$
    – Noah Schweber
    Nov 25 '18 at 19:43












  • $begingroup$
    @AndrésE.Caicedo I've added a clause to clarify.
    $endgroup$
    – Noah Schweber
    Nov 25 '18 at 20:11










  • $begingroup$
    Ah, yes. Sorry) :-)
    $endgroup$
    – Andrés E. Caicedo
    Nov 25 '18 at 20:20
















4












$begingroup$

Depending on what exactly you mean by "explicit example," we can do this.



The situation is simpler with respect to the well-ordering principle, which after all is equivalent to the axiom of choice: it is consistent with ZF that $mathbb{R}$ cannot be well-ordered.



To translate this into a concrete example of a possible failure of the axiom of choice, we can look at the proof that the axiom of choice implies the well-ordering principle: all we need to do in order to well-order $mathbb{R}$ is have a way to, given $Asubsetneqmathbb{R}$, pick some $ainmathbb{R}setminus A$, and so this means that the family $$(mathbb{R}setminus A)_{Asubsetneqmathbb{R}}$$ consistently has no choice function.



Of course, a snappier way to say this is that consistently the family of nonempty (as opposed to proper) subsets of $mathbb{R}$ does not have a choice function - we just switch from $A$ to $mathbb{R}setminus A$ - but the formulation above makes the connection with the well-orderability of $mathbb{R}$ clearer.





Now there are many subtleties around this. I'll mention just one (looking at the well-ordering principle instead of choice, just for simplicity):



Since $mathbb{R}$ is consistently non-well-orderable, there is no formula $varphi$ in the language of set theory which ZF proves is a well-ordering of $mathbb{R}$. However, this does notmean that there can be no definable well-ordering of $mathbb{R}$! There are many formulas which consistently define well-orderings of $mathbb{R}$, chiefly among them the following:




$rtriangleleft s$ iff $r$ precedes $s$ in the canonical well-ordering of $L$.




Here $L$ is Godel's constructible universe, which has a definable (class) well-ordering (if you prefer to avoid proper classes, you can just look at $L_{omega_1}$ since $mathbb{R}cap L=mathbb{R}cap L_{omega_1}$).



We can, however, do even snappier. It is disturbingly possible for everything to be definable: that is, there are models $Mmodels$ ZF such that every element of $M$ is definable in $M$ without parameters. In this case, the usual lexicographic well-ordering on the set of formulas in the language of set theory yields a well-ordering of the whole model, which restricts to a well-ordering of $mathbb{R}$ (or rather, what the model thinks is $mathbb{R}$). I mention this because it's a good example of just how subtle the situation can be, and starts to indicate why the "explicit example" above may not be as satisfying as it first appears.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    You missed the clause $Aneemptyset$.
    $endgroup$
    – Andrés E. Caicedo
    Nov 25 '18 at 18:59










  • $begingroup$
    @AndrésE.Caicedo Hm? I'm picking a real not in $A$, so $A=emptyset$ is fine - it's $A=mathbb{R}$ I need to rule out, which I did via "$subsetneq$" instead of "$subseteq$." Or am I missing something?
    $endgroup$
    – Noah Schweber
    Nov 25 '18 at 19:43












  • $begingroup$
    @AndrésE.Caicedo I've added a clause to clarify.
    $endgroup$
    – Noah Schweber
    Nov 25 '18 at 20:11










  • $begingroup$
    Ah, yes. Sorry) :-)
    $endgroup$
    – Andrés E. Caicedo
    Nov 25 '18 at 20:20














4












4








4





$begingroup$

Depending on what exactly you mean by "explicit example," we can do this.



The situation is simpler with respect to the well-ordering principle, which after all is equivalent to the axiom of choice: it is consistent with ZF that $mathbb{R}$ cannot be well-ordered.



To translate this into a concrete example of a possible failure of the axiom of choice, we can look at the proof that the axiom of choice implies the well-ordering principle: all we need to do in order to well-order $mathbb{R}$ is have a way to, given $Asubsetneqmathbb{R}$, pick some $ainmathbb{R}setminus A$, and so this means that the family $$(mathbb{R}setminus A)_{Asubsetneqmathbb{R}}$$ consistently has no choice function.



Of course, a snappier way to say this is that consistently the family of nonempty (as opposed to proper) subsets of $mathbb{R}$ does not have a choice function - we just switch from $A$ to $mathbb{R}setminus A$ - but the formulation above makes the connection with the well-orderability of $mathbb{R}$ clearer.





Now there are many subtleties around this. I'll mention just one (looking at the well-ordering principle instead of choice, just for simplicity):



Since $mathbb{R}$ is consistently non-well-orderable, there is no formula $varphi$ in the language of set theory which ZF proves is a well-ordering of $mathbb{R}$. However, this does notmean that there can be no definable well-ordering of $mathbb{R}$! There are many formulas which consistently define well-orderings of $mathbb{R}$, chiefly among them the following:




$rtriangleleft s$ iff $r$ precedes $s$ in the canonical well-ordering of $L$.




Here $L$ is Godel's constructible universe, which has a definable (class) well-ordering (if you prefer to avoid proper classes, you can just look at $L_{omega_1}$ since $mathbb{R}cap L=mathbb{R}cap L_{omega_1}$).



We can, however, do even snappier. It is disturbingly possible for everything to be definable: that is, there are models $Mmodels$ ZF such that every element of $M$ is definable in $M$ without parameters. In this case, the usual lexicographic well-ordering on the set of formulas in the language of set theory yields a well-ordering of the whole model, which restricts to a well-ordering of $mathbb{R}$ (or rather, what the model thinks is $mathbb{R}$). I mention this because it's a good example of just how subtle the situation can be, and starts to indicate why the "explicit example" above may not be as satisfying as it first appears.






share|cite|improve this answer











$endgroup$



Depending on what exactly you mean by "explicit example," we can do this.



The situation is simpler with respect to the well-ordering principle, which after all is equivalent to the axiom of choice: it is consistent with ZF that $mathbb{R}$ cannot be well-ordered.



To translate this into a concrete example of a possible failure of the axiom of choice, we can look at the proof that the axiom of choice implies the well-ordering principle: all we need to do in order to well-order $mathbb{R}$ is have a way to, given $Asubsetneqmathbb{R}$, pick some $ainmathbb{R}setminus A$, and so this means that the family $$(mathbb{R}setminus A)_{Asubsetneqmathbb{R}}$$ consistently has no choice function.



Of course, a snappier way to say this is that consistently the family of nonempty (as opposed to proper) subsets of $mathbb{R}$ does not have a choice function - we just switch from $A$ to $mathbb{R}setminus A$ - but the formulation above makes the connection with the well-orderability of $mathbb{R}$ clearer.





Now there are many subtleties around this. I'll mention just one (looking at the well-ordering principle instead of choice, just for simplicity):



Since $mathbb{R}$ is consistently non-well-orderable, there is no formula $varphi$ in the language of set theory which ZF proves is a well-ordering of $mathbb{R}$. However, this does notmean that there can be no definable well-ordering of $mathbb{R}$! There are many formulas which consistently define well-orderings of $mathbb{R}$, chiefly among them the following:




$rtriangleleft s$ iff $r$ precedes $s$ in the canonical well-ordering of $L$.




Here $L$ is Godel's constructible universe, which has a definable (class) well-ordering (if you prefer to avoid proper classes, you can just look at $L_{omega_1}$ since $mathbb{R}cap L=mathbb{R}cap L_{omega_1}$).



We can, however, do even snappier. It is disturbingly possible for everything to be definable: that is, there are models $Mmodels$ ZF such that every element of $M$ is definable in $M$ without parameters. In this case, the usual lexicographic well-ordering on the set of formulas in the language of set theory yields a well-ordering of the whole model, which restricts to a well-ordering of $mathbb{R}$ (or rather, what the model thinks is $mathbb{R}$). I mention this because it's a good example of just how subtle the situation can be, and starts to indicate why the "explicit example" above may not be as satisfying as it first appears.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Nov 25 '18 at 20:11

























answered Nov 25 '18 at 17:32









Noah SchweberNoah Schweber

126k10151290




126k10151290












  • $begingroup$
    You missed the clause $Aneemptyset$.
    $endgroup$
    – Andrés E. Caicedo
    Nov 25 '18 at 18:59










  • $begingroup$
    @AndrésE.Caicedo Hm? I'm picking a real not in $A$, so $A=emptyset$ is fine - it's $A=mathbb{R}$ I need to rule out, which I did via "$subsetneq$" instead of "$subseteq$." Or am I missing something?
    $endgroup$
    – Noah Schweber
    Nov 25 '18 at 19:43












  • $begingroup$
    @AndrésE.Caicedo I've added a clause to clarify.
    $endgroup$
    – Noah Schweber
    Nov 25 '18 at 20:11










  • $begingroup$
    Ah, yes. Sorry) :-)
    $endgroup$
    – Andrés E. Caicedo
    Nov 25 '18 at 20:20


















  • $begingroup$
    You missed the clause $Aneemptyset$.
    $endgroup$
    – Andrés E. Caicedo
    Nov 25 '18 at 18:59










  • $begingroup$
    @AndrésE.Caicedo Hm? I'm picking a real not in $A$, so $A=emptyset$ is fine - it's $A=mathbb{R}$ I need to rule out, which I did via "$subsetneq$" instead of "$subseteq$." Or am I missing something?
    $endgroup$
    – Noah Schweber
    Nov 25 '18 at 19:43












  • $begingroup$
    @AndrésE.Caicedo I've added a clause to clarify.
    $endgroup$
    – Noah Schweber
    Nov 25 '18 at 20:11










  • $begingroup$
    Ah, yes. Sorry) :-)
    $endgroup$
    – Andrés E. Caicedo
    Nov 25 '18 at 20:20
















$begingroup$
You missed the clause $Aneemptyset$.
$endgroup$
– Andrés E. Caicedo
Nov 25 '18 at 18:59




$begingroup$
You missed the clause $Aneemptyset$.
$endgroup$
– Andrés E. Caicedo
Nov 25 '18 at 18:59












$begingroup$
@AndrésE.Caicedo Hm? I'm picking a real not in $A$, so $A=emptyset$ is fine - it's $A=mathbb{R}$ I need to rule out, which I did via "$subsetneq$" instead of "$subseteq$." Or am I missing something?
$endgroup$
– Noah Schweber
Nov 25 '18 at 19:43






$begingroup$
@AndrésE.Caicedo Hm? I'm picking a real not in $A$, so $A=emptyset$ is fine - it's $A=mathbb{R}$ I need to rule out, which I did via "$subsetneq$" instead of "$subseteq$." Or am I missing something?
$endgroup$
– Noah Schweber
Nov 25 '18 at 19:43














$begingroup$
@AndrésE.Caicedo I've added a clause to clarify.
$endgroup$
– Noah Schweber
Nov 25 '18 at 20:11




$begingroup$
@AndrésE.Caicedo I've added a clause to clarify.
$endgroup$
– Noah Schweber
Nov 25 '18 at 20:11












$begingroup$
Ah, yes. Sorry) :-)
$endgroup$
– Andrés E. Caicedo
Nov 25 '18 at 20:20




$begingroup$
Ah, yes. Sorry) :-)
$endgroup$
– Andrés E. Caicedo
Nov 25 '18 at 20:20











4












$begingroup$

The simplest example, I guess, is the power set of the real numbers (without the real numbers).



It is consistent that there is no choice function from that set, and of course assuming choice, there is a choice function.



But there is a subtle issue here or syntactic and semantic point. Since we can add a choice function for a fixed family by forcing, or similarly we can always extend a model of ZF so there is no choice function from the sets of real numbers, we need to be careful and ask what are the sets of reals. In different models the answer would be different.



In addition to that, starting from a model of ZFC, we can make choice fail badly but keeping some initial segment of the universe well ordered (and thus admitting a choice function). So this adds even more confusion to the fire, as Henno points out in the comments, which set is not well ordered is not something that ZF itself can decide. Not even ZF with the failure of AC.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Quibble: $mathcal{P}(mathbb{R})setminus{emptyset}$.
    $endgroup$
    – Noah Schweber
    Nov 25 '18 at 20:12










  • $begingroup$
    I wrote this from my phone in a car on the way to Rome with shoddy connection. What's your excuse? :-)
    $endgroup$
    – Asaf Karagila
    Nov 25 '18 at 22:21
















4












$begingroup$

The simplest example, I guess, is the power set of the real numbers (without the real numbers).



It is consistent that there is no choice function from that set, and of course assuming choice, there is a choice function.



But there is a subtle issue here or syntactic and semantic point. Since we can add a choice function for a fixed family by forcing, or similarly we can always extend a model of ZF so there is no choice function from the sets of real numbers, we need to be careful and ask what are the sets of reals. In different models the answer would be different.



In addition to that, starting from a model of ZFC, we can make choice fail badly but keeping some initial segment of the universe well ordered (and thus admitting a choice function). So this adds even more confusion to the fire, as Henno points out in the comments, which set is not well ordered is not something that ZF itself can decide. Not even ZF with the failure of AC.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Quibble: $mathcal{P}(mathbb{R})setminus{emptyset}$.
    $endgroup$
    – Noah Schweber
    Nov 25 '18 at 20:12










  • $begingroup$
    I wrote this from my phone in a car on the way to Rome with shoddy connection. What's your excuse? :-)
    $endgroup$
    – Asaf Karagila
    Nov 25 '18 at 22:21














4












4








4





$begingroup$

The simplest example, I guess, is the power set of the real numbers (without the real numbers).



It is consistent that there is no choice function from that set, and of course assuming choice, there is a choice function.



But there is a subtle issue here or syntactic and semantic point. Since we can add a choice function for a fixed family by forcing, or similarly we can always extend a model of ZF so there is no choice function from the sets of real numbers, we need to be careful and ask what are the sets of reals. In different models the answer would be different.



In addition to that, starting from a model of ZFC, we can make choice fail badly but keeping some initial segment of the universe well ordered (and thus admitting a choice function). So this adds even more confusion to the fire, as Henno points out in the comments, which set is not well ordered is not something that ZF itself can decide. Not even ZF with the failure of AC.






share|cite|improve this answer











$endgroup$



The simplest example, I guess, is the power set of the real numbers (without the real numbers).



It is consistent that there is no choice function from that set, and of course assuming choice, there is a choice function.



But there is a subtle issue here or syntactic and semantic point. Since we can add a choice function for a fixed family by forcing, or similarly we can always extend a model of ZF so there is no choice function from the sets of real numbers, we need to be careful and ask what are the sets of reals. In different models the answer would be different.



In addition to that, starting from a model of ZFC, we can make choice fail badly but keeping some initial segment of the universe well ordered (and thus admitting a choice function). So this adds even more confusion to the fire, as Henno points out in the comments, which set is not well ordered is not something that ZF itself can decide. Not even ZF with the failure of AC.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Nov 25 '18 at 22:22

























answered Nov 25 '18 at 17:31









Asaf KaragilaAsaf Karagila

305k33436767




305k33436767












  • $begingroup$
    Quibble: $mathcal{P}(mathbb{R})setminus{emptyset}$.
    $endgroup$
    – Noah Schweber
    Nov 25 '18 at 20:12










  • $begingroup$
    I wrote this from my phone in a car on the way to Rome with shoddy connection. What's your excuse? :-)
    $endgroup$
    – Asaf Karagila
    Nov 25 '18 at 22:21


















  • $begingroup$
    Quibble: $mathcal{P}(mathbb{R})setminus{emptyset}$.
    $endgroup$
    – Noah Schweber
    Nov 25 '18 at 20:12










  • $begingroup$
    I wrote this from my phone in a car on the way to Rome with shoddy connection. What's your excuse? :-)
    $endgroup$
    – Asaf Karagila
    Nov 25 '18 at 22:21
















$begingroup$
Quibble: $mathcal{P}(mathbb{R})setminus{emptyset}$.
$endgroup$
– Noah Schweber
Nov 25 '18 at 20:12




$begingroup$
Quibble: $mathcal{P}(mathbb{R})setminus{emptyset}$.
$endgroup$
– Noah Schweber
Nov 25 '18 at 20:12












$begingroup$
I wrote this from my phone in a car on the way to Rome with shoddy connection. What's your excuse? :-)
$endgroup$
– Asaf Karagila
Nov 25 '18 at 22:21




$begingroup$
I wrote this from my phone in a car on the way to Rome with shoddy connection. What's your excuse? :-)
$endgroup$
– Asaf Karagila
Nov 25 '18 at 22:21


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3013027%2fgiving-an-explicit-example-showing-that-ac-is-independent-of-zf%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

404 Error Contact Form 7 ajax form submitting

How to know if a Active Directory user can login interactively

Refactoring coordinates for Minecraft Pi buildings written in Python