Mixing
Choosing a Cauchy sequence for a real
$begingroup$
It is easy to form in ZF, for each real $a$, a "canonical" Cauchy sequence that converges to $a$. For example, one can take the sequence of finite initial segments of the decimal expansion of $a$, being careful when $a$ is a base-10 rational to pick one of the two decimal expansions explicitly.
But what if we are given a set of Cauchy sequences of rationals, all converging to the same real. The set might not contain all the Cauchy sequences for that real. How hard is it to pick a "canonical" representative from the sequences that are in the set?
To make this question precise: consider a family of sets $C$ so that each $X in C$ is a set of Cauchy sequences of rationals that all converge to the same real $a(X)$. Note that $X$ is not required to have the entire set of Cauchy sequences for $a(X)$. Does ZF prove the existence of a choice function for each family $C$ of this kind?
There are two aspects of Cauchy sequences that make this problem interesting. First, every infinite subsequence of a Cauchy sequence is again a Cauchy sequence converging to the same real. So we cannot hope for a "minimal" sequence. Also, we may prepend any finite sequence to a Cauchy sequence to yield a new Cauchy sequence converging to the same real. So we cannot hope for a "maximal" sequence. Cauchy sequences are very slippery in this way.
Dedekind cuts behave differently: once we specify whether cuts for rationals can have a maximum element, we have a unique Dedekind cut for each real, whereas we always have infinitely many Cauchy sequences.
I have a vague memory of encountering something similar to this question in the past, but I cannot remember any details. It also seems to have a flavor related to Borel equivalence relations, although this question is not written in that way.
elementary-set-theory logic axiom-of-choice
asked May 4 '15 at 17:52
Carl MummertCarl Mummert
67.6k7133252
$endgroup$
add a comment |
$begingroup$
It is easy to form in ZF, for each real $a$, a "canonical" Cauchy sequence that converges to $a$. For example, one can take the sequence of finite initial segments of the decimal expansion of $a$, being careful when $a$ is a base-10 rational to pick one of the two decimal expansions explicitly.
But what if we are given a set of Cauchy sequences of rationals, all converging to the same real. The set might not contain all the Cauchy sequences for that real. How hard is it to pick a "canonical" representative from the sequences that are in the set?
To make this question precise: consider a family of sets $C$ so that each $X in C$ is a set of Cauchy sequences of rationals that all converge to the same real $a(X)$. Note that $X$ is not required to have the entire set of Cauchy sequences for $a(X)$. Does ZF prove the existence of a choice function for each family $C$ of this kind?
There are two aspects of Cauchy sequences that make this problem interesting. First, every infinite subsequence of a Cauchy sequence is again a Cauchy sequence converging to the same real. So we cannot hope for a "minimal" sequence. Also, we may prepend any finite sequence to a Cauchy sequence to yield a new Cauchy sequence converging to the same real. So we cannot hope for a "maximal" sequence. Cauchy sequences are very slippery in this way.
Dedekind cuts behave differently: once we specify whether cuts for rationals can have a maximum element, we have a unique Dedekind cut for each real, whereas we always have infinitely many Cauchy sequences.
I have a vague memory of encountering something similar to this question in the past, but I cannot remember any details. It also seems to have a flavor related to Borel equivalence relations, although this question is not written in that way.
elementary-set-theory logic axiom-of-choice
asked May 4 '15 at 17:52
Carl MummertCarl Mummert
67.6k7133252
$endgroup$
add a comment |
$begingroup$
It is easy to form in ZF, for each real $a$, a "canonical" Cauchy sequence that converges to $a$. For example, one can take the sequence of finite initial segments of the decimal expansion of $a$, being careful when $a$ is a base-10 rational to pick one of the two decimal expansions explicitly.
But what if we are given a set of Cauchy sequences of rationals, all converging to the same real. The set might not contain all the Cauchy sequences for that real. How hard is it to pick a "canonical" representative from the sequences that are in the set?
To make this question precise: consider a family of sets $C$ so that each $X in C$ is a set of Cauchy sequences of rationals that all converge to the same real $a(X)$. Note that $X$ is not required to have the entire set of Cauchy sequences for $a(X)$. Does ZF prove the existence of a choice function for each family $C$ of this kind?
There are two aspects of Cauchy sequences that make this problem interesting. First, every infinite subsequence of a Cauchy sequence is again a Cauchy sequence converging to the same real. So we cannot hope for a "minimal" sequence. Also, we may prepend any finite sequence to a Cauchy sequence to yield a new Cauchy sequence converging to the same real. So we cannot hope for a "maximal" sequence. Cauchy sequences are very slippery in this way.
Dedekind cuts behave differently: once we specify whether cuts for rationals can have a maximum element, we have a unique Dedekind cut for each real, whereas we always have infinitely many Cauchy sequences.
I have a vague memory of encountering something similar to this question in the past, but I cannot remember any details. It also seems to have a flavor related to Borel equivalence relations, although this question is not written in that way.
elementary-set-theory logic axiom-of-choice
asked May 4 '15 at 17:52
Carl MummertCarl Mummert
67.6k7133252
$endgroup$
It is easy to form in ZF, for each real $a$, a "canonical" Cauchy sequence that converges to $a$. For example, one can take the sequence of finite initial segments of the decimal expansion of $a$, being careful when $a$ is a base-10 rational to pick one of the two decimal expansions explicitly.
But what if we are given a set of Cauchy sequences of rationals, all converging to the same real. The set might not contain all the Cauchy sequences for that real. How hard is it to pick a "canonical" representative from the sequences that are in the set?
To make this question precise: consider a family of sets $C$ so that each $X in C$ is a set of Cauchy sequences of rationals that all converge to the same real $a(X)$. Note that $X$ is not required to have the entire set of Cauchy sequences for $a(X)$. Does ZF prove the existence of a choice function for each family $C$ of this kind?
There are two aspects of Cauchy sequences that make this problem interesting. First, every infinite subsequence of a Cauchy sequence is again a Cauchy sequence converging to the same real. So we cannot hope for a "minimal" sequence. Also, we may prepend any finite sequence to a Cauchy sequence to yield a new Cauchy sequence converging to the same real. So we cannot hope for a "maximal" sequence. Cauchy sequences are very slippery in this way.
Dedekind cuts behave differently: once we specify whether cuts for rationals can have a maximum element, we have a unique Dedekind cut for each real, whereas we always have infinitely many Cauchy sequences.
I have a vague memory of encountering something similar to this question in the past, but I cannot remember any details. It also seems to have a flavor related to Borel equivalence relations, although this question is not written in that way.
elementary-set-theory logic axiom-of-choice
elementary-set-theory logic axiom-of-choice
asked May 4 '15 at 17:52
Carl MummertCarl Mummert
67.6k7133252
asked May 4 '15 at 17:52
Carl MummertCarl Mummert
67.6k7133252
edited Jan 27 at 17:09
Carl Mummert
asked May 4 '15 at 17:52
Carl MummertCarl Mummert
67.6k7133252
asked May 4 '15 at 17:52
Carl MummertCarl Mummert
67.6k7133252
asked May 4 '15 at 17:52
Carl MummertCarl Mummert
67.6k7133252
67.6k7133252
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Let me take Lord_Farin's answer, and crank it all the way to $2^{aleph_0}$.
Suppose that we could have chosen from any family of Cauchy sequences. Fix for each real number a canonical Cauchy sequence of rationals $r_n$ which is strictly increasing. This is of course doable without choice.
Now suppose that $A_rsubseteq 2^omegasetminus 2^{<omega}$ is non-empty for each $rinBbb R$, then consider $C_r={langle r_nmid a_nneq 0ranglemidlangle a_nranglein A_r}$. Namely we encode each $ain A_r$ as a subsequence of $r_n$, with the assumption that $a$ is not eventually $0$.
By the assumption there will be a choice from each $C_r$, and then we can easily decode this into a choice from $A_r$. So we have proved the axiom of choice for families of size $leq2^{aleph_0}$ of sets of reals. And of course we cannot even prove choice for countable families of sets of reals in $sf ZF$ itself.
answered May 4 '15 at 18:22
Asaf Karagila♦Asaf Karagila
307k33439770
$endgroup$
$begingroup$
There might be some minor corrections to this idea, but I need to write an exercise, and it's getting late. So I'll address them once that part of the evening is over!
$endgroup$
– Asaf Karagila♦
May 4 '15 at 18:25
2
$begingroup$
I don't follow yet; does this give back a Cauchy sequence that was in the original set of Cauchy sequences, which may not be the full equivalence class?
$endgroup$
– Carl Mummert
May 4 '15 at 18:38
$begingroup$
Oh. I sort of missed that "subsets of equivalence classes" part. No, I don't see at all why there can be canonical choices for subsets of equivalence classes. I answered indeed for "choice for the equivalence classes". Should I delete this answer?
$endgroup$
– Asaf Karagila♦
May 4 '15 at 18:44
1
$begingroup$
All better. I hope. Now I can finally quell my mind and write that exercise about definable truth predicates in $Bbb N$. :-)
$endgroup$
– Asaf Karagila♦
May 4 '15 at 19:05
1
$begingroup$
No, this won't work. Suppose $C={f_1,f_2,f_3,ldots}$ where $$f_k(m)=begin{cases} 0 & m<k \ 1 & text{otherwise}end{cases}$$ and use an enumeration of $mathbb Q$ where $0$ comes before $1$. Then your $bigcap C_n$ is empty!
$endgroup$
– Henning Makholm
May 4 '15 at 19:22
|
show 6 more comments
$begingroup$
Such a choice mechanism would translate to a canonical choice for a function $Bbb N to Bbb N_{>0}$ from a given set $S$ of such functions. If I'm not mistaken, this is some nontrivial choice principle (and if I am, please do correct me).
Given $f: Bbb N to Bbb N_{>0}$, define: $$b_f (n) = begin{cases}2^{-k} &: n = sumlimits_{i=0}^k f(i) \0&: text{otherwise}end{cases}$$
Now define $s_f(n) = sumlimits_{i=0}^n b_f(i)$. Then for all $f$: $$lim_{ntoinfty} s_f(n) = 2$$
and $f leftrightarrow s_f$ is a bijective correspondence. Hence a choice function for each set ${s_f: f in S}$ amounts to a choice function for each $S subseteq (Bbb N_{>0})^{Bbb N}$.
By defining, for $f: Bbb N to 2$: $$b_f(n) = begin{cases}2^{-k} &: n = k + sumlimits_{i=0}^k f(i) \0&: text{otherwise}end{cases}$$ the argument seems to carry over to $2^{Bbb N}$.
answered May 4 '15 at 19:06
Lord_FarinLord_Farin
15.7k636110
$endgroup$
$begingroup$
I believe the correspondence here is correct (and $mathbb{N} to mathbb{N}_{>0}$ is in effective bijection with $mathbb{N} to mathbb{N}$ via the math $T(f)(x) = f(x) - 1$. So the argument carries over to $mathbb{N}^mathbb{N}$. But then the argument in Asaf's answer seems to apply equally well, which leads to a fact I had not realized, which is that ZF proves choice for families of subsets of $mathbb{N}^mathbb{N}$. (I think this answer is very relevant, by the way; +1)
$endgroup$
– Carl Mummert
May 4 '15 at 19:11
$begingroup$
@Carl I was also straining my mind to see the possible flaw in Asaf's answer, but it seems fine. Thus, we seem to have proven choice for subsets of $Bbb N^{Bbb N}$ :).
$endgroup$
– Lord_Farin
May 4 '15 at 19:15
$begingroup$
So you translate a set functions into Cauchy sequences approaching $2$. I'm not sure this would be an issue. But I do agree that given a countable collection of sets of functions, translating each to a set of Cauchy sequences approaching $n$; then being able to choose would prove at least countable choice for sets of reals, which we know is impossible to prove in $sf ZF$.
$endgroup$
– Asaf Karagila♦
May 4 '15 at 20:35
$begingroup$
@Carl: I originally had a hunch that this would be unprovable. But I managed to convince myself that it can be done. I blame the time stress that I needed to write an exercise! :-)
$endgroup$
– Asaf Karagila♦
May 4 '15 at 20:37
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',
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
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1266792%2fchoosing-a-cauchy-sequence-for-a-real%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
$begingroup$
Let me take Lord_Farin's answer, and crank it all the way to $2^{aleph_0}$.
Suppose that we could have chosen from any family of Cauchy sequences. Fix for each real number a canonical Cauchy sequence of rationals $r_n$ which is strictly increasing. This is of course doable without choice.
Now suppose that $A_rsubseteq 2^omegasetminus 2^{<omega}$ is non-empty for each $rinBbb R$, then consider $C_r={langle r_nmid a_nneq 0ranglemidlangle a_nranglein A_r}$. Namely we encode each $ain A_r$ as a subsequence of $r_n$, with the assumption that $a$ is not eventually $0$.
By the assumption there will be a choice from each $C_r$, and then we can easily decode this into a choice from $A_r$. So we have proved the axiom of choice for families of size $leq2^{aleph_0}$ of sets of reals. And of course we cannot even prove choice for countable families of sets of reals in $sf ZF$ itself.
answered May 4 '15 at 18:22
Asaf Karagila♦Asaf Karagila
307k33439770
$endgroup$
$begingroup$
There might be some minor corrections to this idea, but I need to write an exercise, and it's getting late. So I'll address them once that part of the evening is over!
$endgroup$
– Asaf Karagila♦
May 4 '15 at 18:25
2
$begingroup$
I don't follow yet; does this give back a Cauchy sequence that was in the original set of Cauchy sequences, which may not be the full equivalence class?
$endgroup$
– Carl Mummert
May 4 '15 at 18:38
$begingroup$
Oh. I sort of missed that "subsets of equivalence classes" part. No, I don't see at all why there can be canonical choices for subsets of equivalence classes. I answered indeed for "choice for the equivalence classes". Should I delete this answer?
$endgroup$
– Asaf Karagila♦
May 4 '15 at 18:44
1
$begingroup$
All better. I hope. Now I can finally quell my mind and write that exercise about definable truth predicates in $Bbb N$. :-)
$endgroup$
– Asaf Karagila♦
May 4 '15 at 19:05
1
$begingroup$
No, this won't work. Suppose $C={f_1,f_2,f_3,ldots}$ where $$f_k(m)=begin{cases} 0 & m<k \ 1 & text{otherwise}end{cases}$$ and use an enumeration of $mathbb Q$ where $0$ comes before $1$. Then your $bigcap C_n$ is empty!
$endgroup$
– Henning Makholm
May 4 '15 at 19:22
|
show 6 more comments
$begingroup$
Let me take Lord_Farin's answer, and crank it all the way to $2^{aleph_0}$.
Suppose that we could have chosen from any family of Cauchy sequences. Fix for each real number a canonical Cauchy sequence of rationals $r_n$ which is strictly increasing. This is of course doable without choice.
Now suppose that $A_rsubseteq 2^omegasetminus 2^{<omega}$ is non-empty for each $rinBbb R$, then consider $C_r={langle r_nmid a_nneq 0ranglemidlangle a_nranglein A_r}$. Namely we encode each $ain A_r$ as a subsequence of $r_n$, with the assumption that $a$ is not eventually $0$.
By the assumption there will be a choice from each $C_r$, and then we can easily decode this into a choice from $A_r$. So we have proved the axiom of choice for families of size $leq2^{aleph_0}$ of sets of reals. And of course we cannot even prove choice for countable families of sets of reals in $sf ZF$ itself.
answered May 4 '15 at 18:22
Asaf Karagila♦Asaf Karagila
307k33439770
$endgroup$
$begingroup$
There might be some minor corrections to this idea, but I need to write an exercise, and it's getting late. So I'll address them once that part of the evening is over!
$endgroup$
– Asaf Karagila♦
May 4 '15 at 18:25
2
$begingroup$
I don't follow yet; does this give back a Cauchy sequence that was in the original set of Cauchy sequences, which may not be the full equivalence class?
$endgroup$
– Carl Mummert
May 4 '15 at 18:38
$begingroup$
Oh. I sort of missed that "subsets of equivalence classes" part. No, I don't see at all why there can be canonical choices for subsets of equivalence classes. I answered indeed for "choice for the equivalence classes". Should I delete this answer?
$endgroup$
– Asaf Karagila♦
May 4 '15 at 18:44
1
$begingroup$
All better. I hope. Now I can finally quell my mind and write that exercise about definable truth predicates in $Bbb N$. :-)
$endgroup$
– Asaf Karagila♦
May 4 '15 at 19:05
1
$begingroup$
No, this won't work. Suppose $C={f_1,f_2,f_3,ldots}$ where $$f_k(m)=begin{cases} 0 & m<k \ 1 & text{otherwise}end{cases}$$ and use an enumeration of $mathbb Q$ where $0$ comes before $1$. Then your $bigcap C_n$ is empty!
$endgroup$
– Henning Makholm
May 4 '15 at 19:22
|
show 6 more comments
$begingroup$
Let me take Lord_Farin's answer, and crank it all the way to $2^{aleph_0}$.
Suppose that we could have chosen from any family of Cauchy sequences. Fix for each real number a canonical Cauchy sequence of rationals $r_n$ which is strictly increasing. This is of course doable without choice.
Now suppose that $A_rsubseteq 2^omegasetminus 2^{<omega}$ is non-empty for each $rinBbb R$, then consider $C_r={langle r_nmid a_nneq 0ranglemidlangle a_nranglein A_r}$. Namely we encode each $ain A_r$ as a subsequence of $r_n$, with the assumption that $a$ is not eventually $0$.
By the assumption there will be a choice from each $C_r$, and then we can easily decode this into a choice from $A_r$. So we have proved the axiom of choice for families of size $leq2^{aleph_0}$ of sets of reals. And of course we cannot even prove choice for countable families of sets of reals in $sf ZF$ itself.
answered May 4 '15 at 18:22
Asaf Karagila♦Asaf Karagila
307k33439770
$endgroup$
Let me take Lord_Farin's answer, and crank it all the way to $2^{aleph_0}$.
Suppose that we could have chosen from any family of Cauchy sequences. Fix for each real number a canonical Cauchy sequence of rationals $r_n$ which is strictly increasing. This is of course doable without choice.
Now suppose that $A_rsubseteq 2^omegasetminus 2^{<omega}$ is non-empty for each $rinBbb R$, then consider $C_r={langle r_nmid a_nneq 0ranglemidlangle a_nranglein A_r}$. Namely we encode each $ain A_r$ as a subsequence of $r_n$, with the assumption that $a$ is not eventually $0$.
By the assumption there will be a choice from each $C_r$, and then we can easily decode this into a choice from $A_r$. So we have proved the axiom of choice for families of size $leq2^{aleph_0}$ of sets of reals. And of course we cannot even prove choice for countable families of sets of reals in $sf ZF$ itself.
answered May 4 '15 at 18:22
Asaf Karagila♦Asaf Karagila
307k33439770
edited May 4 '15 at 20:53
answered May 4 '15 at 18:22
Asaf Karagila♦Asaf Karagila
307k33439770
answered May 4 '15 at 18:22
Asaf Karagila♦Asaf Karagila
307k33439770
answered May 4 '15 at 18:22
Asaf Karagila♦Asaf Karagila
307k33439770
307k33439770
$begingroup$
There might be some minor corrections to this idea, but I need to write an exercise, and it's getting late. So I'll address them once that part of the evening is over!
$endgroup$
– Asaf Karagila♦
May 4 '15 at 18:25
2
$begingroup$
I don't follow yet; does this give back a Cauchy sequence that was in the original set of Cauchy sequences, which may not be the full equivalence class?
$endgroup$
– Carl Mummert
May 4 '15 at 18:38
$begingroup$
Oh. I sort of missed that "subsets of equivalence classes" part. No, I don't see at all why there can be canonical choices for subsets of equivalence classes. I answered indeed for "choice for the equivalence classes". Should I delete this answer?
$endgroup$
– Asaf Karagila♦
May 4 '15 at 18:44
1
$begingroup$
All better. I hope. Now I can finally quell my mind and write that exercise about definable truth predicates in $Bbb N$. :-)
$endgroup$
– Asaf Karagila♦
May 4 '15 at 19:05
1
$begingroup$
No, this won't work. Suppose $C={f_1,f_2,f_3,ldots}$ where $$f_k(m)=begin{cases} 0 & m<k \ 1 & text{otherwise}end{cases}$$ and use an enumeration of $mathbb Q$ where $0$ comes before $1$. Then your $bigcap C_n$ is empty!
$endgroup$
– Henning Makholm
May 4 '15 at 19:22
|
show 6 more comments
$begingroup$
There might be some minor corrections to this idea, but I need to write an exercise, and it's getting late. So I'll address them once that part of the evening is over!
$endgroup$
– Asaf Karagila♦
May 4 '15 at 18:25
2
$begingroup$
I don't follow yet; does this give back a Cauchy sequence that was in the original set of Cauchy sequences, which may not be the full equivalence class?
$endgroup$
– Carl Mummert
May 4 '15 at 18:38
$begingroup$
Oh. I sort of missed that "subsets of equivalence classes" part. No, I don't see at all why there can be canonical choices for subsets of equivalence classes. I answered indeed for "choice for the equivalence classes". Should I delete this answer?
$endgroup$
– Asaf Karagila♦
May 4 '15 at 18:44
1
$begingroup$
All better. I hope. Now I can finally quell my mind and write that exercise about definable truth predicates in $Bbb N$. :-)
$endgroup$
– Asaf Karagila♦
May 4 '15 at 19:05
1
$begingroup$
No, this won't work. Suppose $C={f_1,f_2,f_3,ldots}$ where $$f_k(m)=begin{cases} 0 & m<k \ 1 & text{otherwise}end{cases}$$ and use an enumeration of $mathbb Q$ where $0$ comes before $1$. Then your $bigcap C_n$ is empty!
$endgroup$
– Henning Makholm
May 4 '15 at 19:22
$begingroup$
There might be some minor corrections to this idea, but I need to write an exercise, and it's getting late. So I'll address them once that part of the evening is over!
$endgroup$
– Asaf Karagila♦
May 4 '15 at 18:25
$begingroup$
There might be some minor corrections to this idea, but I need to write an exercise, and it's getting late. So I'll address them once that part of the evening is over!
$endgroup$
– Asaf Karagila♦
May 4 '15 at 18:25
2
2
$begingroup$
I don't follow yet; does this give back a Cauchy sequence that was in the original set of Cauchy sequences, which may not be the full equivalence class?
$endgroup$
– Carl Mummert
May 4 '15 at 18:38
$begingroup$
I don't follow yet; does this give back a Cauchy sequence that was in the original set of Cauchy sequences, which may not be the full equivalence class?
$endgroup$
– Carl Mummert
May 4 '15 at 18:38
$begingroup$
Oh. I sort of missed that "subsets of equivalence classes" part. No, I don't see at all why there can be canonical choices for subsets of equivalence classes. I answered indeed for "choice for the equivalence classes". Should I delete this answer?
$endgroup$
– Asaf Karagila♦
May 4 '15 at 18:44
$begingroup$
Oh. I sort of missed that "subsets of equivalence classes" part. No, I don't see at all why there can be canonical choices for subsets of equivalence classes. I answered indeed for "choice for the equivalence classes". Should I delete this answer?
$endgroup$
– Asaf Karagila♦
May 4 '15 at 18:44
1
1
$begingroup$
All better. I hope. Now I can finally quell my mind and write that exercise about definable truth predicates in $Bbb N$. :-)
$endgroup$
– Asaf Karagila♦
May 4 '15 at 19:05
$begingroup$
All better. I hope. Now I can finally quell my mind and write that exercise about definable truth predicates in $Bbb N$. :-)
$endgroup$
– Asaf Karagila♦
May 4 '15 at 19:05
1
1
$begingroup$
No, this won't work. Suppose $C={f_1,f_2,f_3,ldots}$ where $$f_k(m)=begin{cases} 0 & m<k \ 1 & text{otherwise}end{cases}$$ and use an enumeration of $mathbb Q$ where $0$ comes before $1$. Then your $bigcap C_n$ is empty!
$endgroup$
– Henning Makholm
May 4 '15 at 19:22
$begingroup$
No, this won't work. Suppose $C={f_1,f_2,f_3,ldots}$ where $$f_k(m)=begin{cases} 0 & m<k \ 1 & text{otherwise}end{cases}$$ and use an enumeration of $mathbb Q$ where $0$ comes before $1$. Then your $bigcap C_n$ is empty!
$endgroup$
– Henning Makholm
May 4 '15 at 19:22
|
show 6 more comments
$begingroup$
Such a choice mechanism would translate to a canonical choice for a function $Bbb N to Bbb N_{>0}$ from a given set $S$ of such functions. If I'm not mistaken, this is some nontrivial choice principle (and if I am, please do correct me).
Given $f: Bbb N to Bbb N_{>0}$, define: $$b_f (n) = begin{cases}2^{-k} &: n = sumlimits_{i=0}^k f(i) \0&: text{otherwise}end{cases}$$
Now define $s_f(n) = sumlimits_{i=0}^n b_f(i)$. Then for all $f$: $$lim_{ntoinfty} s_f(n) = 2$$
and $f leftrightarrow s_f$ is a bijective correspondence. Hence a choice function for each set ${s_f: f in S}$ amounts to a choice function for each $S subseteq (Bbb N_{>0})^{Bbb N}$.
By defining, for $f: Bbb N to 2$: $$b_f(n) = begin{cases}2^{-k} &: n = k + sumlimits_{i=0}^k f(i) \0&: text{otherwise}end{cases}$$ the argument seems to carry over to $2^{Bbb N}$.
answered May 4 '15 at 19:06
Lord_FarinLord_Farin
15.7k636110
$endgroup$
$begingroup$
I believe the correspondence here is correct (and $mathbb{N} to mathbb{N}_{>0}$ is in effective bijection with $mathbb{N} to mathbb{N}$ via the math $T(f)(x) = f(x) - 1$. So the argument carries over to $mathbb{N}^mathbb{N}$. But then the argument in Asaf's answer seems to apply equally well, which leads to a fact I had not realized, which is that ZF proves choice for families of subsets of $mathbb{N}^mathbb{N}$. (I think this answer is very relevant, by the way; +1)
$endgroup$
– Carl Mummert
May 4 '15 at 19:11
$begingroup$
@Carl I was also straining my mind to see the possible flaw in Asaf's answer, but it seems fine. Thus, we seem to have proven choice for subsets of $Bbb N^{Bbb N}$ :).
$endgroup$
– Lord_Farin
May 4 '15 at 19:15
$begingroup$
So you translate a set functions into Cauchy sequences approaching $2$. I'm not sure this would be an issue. But I do agree that given a countable collection of sets of functions, translating each to a set of Cauchy sequences approaching $n$; then being able to choose would prove at least countable choice for sets of reals, which we know is impossible to prove in $sf ZF$.
$endgroup$
– Asaf Karagila♦
May 4 '15 at 20:35
$begingroup$
@Carl: I originally had a hunch that this would be unprovable. But I managed to convince myself that it can be done. I blame the time stress that I needed to write an exercise! :-)
$endgroup$
– Asaf Karagila♦
May 4 '15 at 20:37
add a comment |
$begingroup$
Such a choice mechanism would translate to a canonical choice for a function $Bbb N to Bbb N_{>0}$ from a given set $S$ of such functions. If I'm not mistaken, this is some nontrivial choice principle (and if I am, please do correct me).
Given $f: Bbb N to Bbb N_{>0}$, define: $$b_f (n) = begin{cases}2^{-k} &: n = sumlimits_{i=0}^k f(i) \0&: text{otherwise}end{cases}$$
Now define $s_f(n) = sumlimits_{i=0}^n b_f(i)$. Then for all $f$: $$lim_{ntoinfty} s_f(n) = 2$$
and $f leftrightarrow s_f$ is a bijective correspondence. Hence a choice function for each set ${s_f: f in S}$ amounts to a choice function for each $S subseteq (Bbb N_{>0})^{Bbb N}$.
By defining, for $f: Bbb N to 2$: $$b_f(n) = begin{cases}2^{-k} &: n = k + sumlimits_{i=0}^k f(i) \0&: text{otherwise}end{cases}$$ the argument seems to carry over to $2^{Bbb N}$.
answered May 4 '15 at 19:06
Lord_FarinLord_Farin
15.7k636110
$endgroup$
$begingroup$
I believe the correspondence here is correct (and $mathbb{N} to mathbb{N}_{>0}$ is in effective bijection with $mathbb{N} to mathbb{N}$ via the math $T(f)(x) = f(x) - 1$. So the argument carries over to $mathbb{N}^mathbb{N}$. But then the argument in Asaf's answer seems to apply equally well, which leads to a fact I had not realized, which is that ZF proves choice for families of subsets of $mathbb{N}^mathbb{N}$. (I think this answer is very relevant, by the way; +1)
$endgroup$
– Carl Mummert
May 4 '15 at 19:11
$begingroup$
@Carl I was also straining my mind to see the possible flaw in Asaf's answer, but it seems fine. Thus, we seem to have proven choice for subsets of $Bbb N^{Bbb N}$ :).
$endgroup$
– Lord_Farin
May 4 '15 at 19:15
$begingroup$
So you translate a set functions into Cauchy sequences approaching $2$. I'm not sure this would be an issue. But I do agree that given a countable collection of sets of functions, translating each to a set of Cauchy sequences approaching $n$; then being able to choose would prove at least countable choice for sets of reals, which we know is impossible to prove in $sf ZF$.
$endgroup$
– Asaf Karagila♦
May 4 '15 at 20:35
$begingroup$
@Carl: I originally had a hunch that this would be unprovable. But I managed to convince myself that it can be done. I blame the time stress that I needed to write an exercise! :-)
$endgroup$
– Asaf Karagila♦
May 4 '15 at 20:37
add a comment |
$begingroup$
Such a choice mechanism would translate to a canonical choice for a function $Bbb N to Bbb N_{>0}$ from a given set $S$ of such functions. If I'm not mistaken, this is some nontrivial choice principle (and if I am, please do correct me).
Given $f: Bbb N to Bbb N_{>0}$, define: $$b_f (n) = begin{cases}2^{-k} &: n = sumlimits_{i=0}^k f(i) \0&: text{otherwise}end{cases}$$
Now define $s_f(n) = sumlimits_{i=0}^n b_f(i)$. Then for all $f$: $$lim_{ntoinfty} s_f(n) = 2$$
and $f leftrightarrow s_f$ is a bijective correspondence. Hence a choice function for each set ${s_f: f in S}$ amounts to a choice function for each $S subseteq (Bbb N_{>0})^{Bbb N}$.
By defining, for $f: Bbb N to 2$: $$b_f(n) = begin{cases}2^{-k} &: n = k + sumlimits_{i=0}^k f(i) \0&: text{otherwise}end{cases}$$ the argument seems to carry over to $2^{Bbb N}$.
answered May 4 '15 at 19:06
Lord_FarinLord_Farin
15.7k636110
$endgroup$
Such a choice mechanism would translate to a canonical choice for a function $Bbb N to Bbb N_{>0}$ from a given set $S$ of such functions. If I'm not mistaken, this is some nontrivial choice principle (and if I am, please do correct me).
Given $f: Bbb N to Bbb N_{>0}$, define: $$b_f (n) = begin{cases}2^{-k} &: n = sumlimits_{i=0}^k f(i) \0&: text{otherwise}end{cases}$$
Now define $s_f(n) = sumlimits_{i=0}^n b_f(i)$. Then for all $f$: $$lim_{ntoinfty} s_f(n) = 2$$
and $f leftrightarrow s_f$ is a bijective correspondence. Hence a choice function for each set ${s_f: f in S}$ amounts to a choice function for each $S subseteq (Bbb N_{>0})^{Bbb N}$.
By defining, for $f: Bbb N to 2$: $$b_f(n) = begin{cases}2^{-k} &: n = k + sumlimits_{i=0}^k f(i) \0&: text{otherwise}end{cases}$$ the argument seems to carry over to $2^{Bbb N}$.
answered May 4 '15 at 19:06
Lord_FarinLord_Farin
15.7k636110
edited May 4 '15 at 19:18
answered May 4 '15 at 19:06
Lord_FarinLord_Farin
15.7k636110
answered May 4 '15 at 19:06
Lord_FarinLord_Farin
15.7k636110
answered May 4 '15 at 19:06
Lord_FarinLord_Farin
15.7k636110
15.7k636110
$begingroup$
I believe the correspondence here is correct (and $mathbb{N} to mathbb{N}_{>0}$ is in effective bijection with $mathbb{N} to mathbb{N}$ via the math $T(f)(x) = f(x) - 1$. So the argument carries over to $mathbb{N}^mathbb{N}$. But then the argument in Asaf's answer seems to apply equally well, which leads to a fact I had not realized, which is that ZF proves choice for families of subsets of $mathbb{N}^mathbb{N}$. (I think this answer is very relevant, by the way; +1)
$endgroup$
– Carl Mummert
May 4 '15 at 19:11
$begingroup$
@Carl I was also straining my mind to see the possible flaw in Asaf's answer, but it seems fine. Thus, we seem to have proven choice for subsets of $Bbb N^{Bbb N}$ :).
$endgroup$
– Lord_Farin
May 4 '15 at 19:15
$begingroup$
So you translate a set functions into Cauchy sequences approaching $2$. I'm not sure this would be an issue. But I do agree that given a countable collection of sets of functions, translating each to a set of Cauchy sequences approaching $n$; then being able to choose would prove at least countable choice for sets of reals, which we know is impossible to prove in $sf ZF$.
$endgroup$
– Asaf Karagila♦
May 4 '15 at 20:35
$begingroup$
@Carl: I originally had a hunch that this would be unprovable. But I managed to convince myself that it can be done. I blame the time stress that I needed to write an exercise! :-)
$endgroup$
– Asaf Karagila♦
May 4 '15 at 20:37
add a comment |
$begingroup$
I believe the correspondence here is correct (and $mathbb{N} to mathbb{N}_{>0}$ is in effective bijection with $mathbb{N} to mathbb{N}$ via the math $T(f)(x) = f(x) - 1$. So the argument carries over to $mathbb{N}^mathbb{N}$. But then the argument in Asaf's answer seems to apply equally well, which leads to a fact I had not realized, which is that ZF proves choice for families of subsets of $mathbb{N}^mathbb{N}$. (I think this answer is very relevant, by the way; +1)
$endgroup$
– Carl Mummert
May 4 '15 at 19:11
$begingroup$
@Carl I was also straining my mind to see the possible flaw in Asaf's answer, but it seems fine. Thus, we seem to have proven choice for subsets of $Bbb N^{Bbb N}$ :).
$endgroup$
– Lord_Farin
May 4 '15 at 19:15
$begingroup$
So you translate a set functions into Cauchy sequences approaching $2$. I'm not sure this would be an issue. But I do agree that given a countable collection of sets of functions, translating each to a set of Cauchy sequences approaching $n$; then being able to choose would prove at least countable choice for sets of reals, which we know is impossible to prove in $sf ZF$.
$endgroup$
– Asaf Karagila♦
May 4 '15 at 20:35
$begingroup$
@Carl: I originally had a hunch that this would be unprovable. But I managed to convince myself that it can be done. I blame the time stress that I needed to write an exercise! :-)
$endgroup$
– Asaf Karagila♦
May 4 '15 at 20:37
$begingroup$
I believe the correspondence here is correct (and $mathbb{N} to mathbb{N}_{>0}$ is in effective bijection with $mathbb{N} to mathbb{N}$ via the math $T(f)(x) = f(x) - 1$. So the argument carries over to $mathbb{N}^mathbb{N}$. But then the argument in Asaf's answer seems to apply equally well, which leads to a fact I had not realized, which is that ZF proves choice for families of subsets of $mathbb{N}^mathbb{N}$. (I think this answer is very relevant, by the way; +1)
$endgroup$
– Carl Mummert
May 4 '15 at 19:11
$begingroup$
I believe the correspondence here is correct (and $mathbb{N} to mathbb{N}_{>0}$ is in effective bijection with $mathbb{N} to mathbb{N}$ via the math $T(f)(x) = f(x) - 1$. So the argument carries over to $mathbb{N}^mathbb{N}$. But then the argument in Asaf's answer seems to apply equally well, which leads to a fact I had not realized, which is that ZF proves choice for families of subsets of $mathbb{N}^mathbb{N}$. (I think this answer is very relevant, by the way; +1)
$endgroup$
– Carl Mummert
May 4 '15 at 19:11
$begingroup$
@Carl I was also straining my mind to see the possible flaw in Asaf's answer, but it seems fine. Thus, we seem to have proven choice for subsets of $Bbb N^{Bbb N}$ :).
$endgroup$
– Lord_Farin
May 4 '15 at 19:15
$begingroup$
@Carl I was also straining my mind to see the possible flaw in Asaf's answer, but it seems fine. Thus, we seem to have proven choice for subsets of $Bbb N^{Bbb N}$ :).
$endgroup$
– Lord_Farin
May 4 '15 at 19:15
$begingroup$
So you translate a set functions into Cauchy sequences approaching $2$. I'm not sure this would be an issue. But I do agree that given a countable collection of sets of functions, translating each to a set of Cauchy sequences approaching $n$; then being able to choose would prove at least countable choice for sets of reals, which we know is impossible to prove in $sf ZF$.
$endgroup$
– Asaf Karagila♦
May 4 '15 at 20:35
$begingroup$
So you translate a set functions into Cauchy sequences approaching $2$. I'm not sure this would be an issue. But I do agree that given a countable collection of sets of functions, translating each to a set of Cauchy sequences approaching $n$; then being able to choose would prove at least countable choice for sets of reals, which we know is impossible to prove in $sf ZF$.
$endgroup$
– Asaf Karagila♦
May 4 '15 at 20:35
$begingroup$
@Carl: I originally had a hunch that this would be unprovable. But I managed to convince myself that it can be done. I blame the time stress that I needed to write an exercise! :-)
$endgroup$
– Asaf Karagila♦
May 4 '15 at 20:37
$begingroup$
@Carl: I originally had a hunch that this would be unprovable. But I managed to convince myself that it can be done. I blame the time stress that I needed to write an exercise! :-)
$endgroup$
– Asaf Karagila♦
May 4 '15 at 20:37
add a comment |
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.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1266792%2fchoosing-a-cauchy-sequence-for-a-real%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
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
