Mixing
Is the set of all choice sets on a infinite partition on $mathbb N$ equal in cardinality to $mathcal P(mathbb...
$begingroup$
Let $mathcal S={{2n,2n+1} | n in mathbb N}$
Define: $X text{ is a choice set on } mathcal S iff X subset mathbb N wedge forall s in mathcal S exists! x in X (x in s)$
Define $mathcal P^c(mathcal S)={X| X text{ is a choice set on } mathcal S }$
Does $text{ZF}$ prove: $mathcal |P^c(mathcal S)| = |mathcal P(mathbb N)| $?
elementary-set-theory
edited Jan 24 at 12:29
Andrés E. Caicedo
65.7k8160250
asked Jan 23 at 23:40
ZuhairZuhair
345212
$endgroup$
add a comment |
$begingroup$
Let $mathcal S={{2n,2n+1} | n in mathbb N}$
Define: $X text{ is a choice set on } mathcal S iff X subset mathbb N wedge forall s in mathcal S exists! x in X (x in s)$
Define $mathcal P^c(mathcal S)={X| X text{ is a choice set on } mathcal S }$
Does $text{ZF}$ prove: $mathcal |P^c(mathcal S)| = |mathcal P(mathbb N)| $?
elementary-set-theory
edited Jan 24 at 12:29
Andrés E. Caicedo
65.7k8160250
asked Jan 23 at 23:40
ZuhairZuhair
345212
$endgroup$
add a comment |
$begingroup$
Let $mathcal S={{2n,2n+1} | n in mathbb N}$
Define: $X text{ is a choice set on } mathcal S iff X subset mathbb N wedge forall s in mathcal S exists! x in X (x in s)$
Define $mathcal P^c(mathcal S)={X| X text{ is a choice set on } mathcal S }$
Does $text{ZF}$ prove: $mathcal |P^c(mathcal S)| = |mathcal P(mathbb N)| $?
elementary-set-theory
edited Jan 24 at 12:29
Andrés E. Caicedo
65.7k8160250
asked Jan 23 at 23:40
ZuhairZuhair
345212
$endgroup$
Let $mathcal S={{2n,2n+1} | n in mathbb N}$
Define: $X text{ is a choice set on } mathcal S iff X subset mathbb N wedge forall s in mathcal S exists! x in X (x in s)$
Define $mathcal P^c(mathcal S)={X| X text{ is a choice set on } mathcal S }$
Does $text{ZF}$ prove: $mathcal |P^c(mathcal S)| = |mathcal P(mathbb N)| $?
elementary-set-theory
elementary-set-theory
edited Jan 24 at 12:29
Andrés E. Caicedo
65.7k8160250
asked Jan 23 at 23:40
ZuhairZuhair
345212
edited Jan 24 at 12:29
Andrés E. Caicedo
65.7k8160250
asked Jan 23 at 23:40
ZuhairZuhair
345212
edited Jan 24 at 12:29
Andrés E. Caicedo
65.7k8160250
edited Jan 24 at 12:29
Andrés E. Caicedo
65.7k8160250
edited Jan 24 at 12:29
Andrés E. Caicedo
65.7k8160250
65.7k8160250
asked Jan 23 at 23:40
ZuhairZuhair
345212
asked Jan 23 at 23:40
ZuhairZuhair
345212
asked Jan 23 at 23:40
ZuhairZuhair
345212
345212
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Yes.
Consider the map $F:mathcal{P}^c(mathcal{S})rightarrowmathcal{P}(mathbb{N})$ sending a choice set $X$ to the set $$F(X)={n: 2nin X}.$$ It's easy to check that this is a bijection, and vastly less than ZF is required.
Similarly, ZF proves that if $mathcal{S}$ is any partition of $mathbb{N}$ into infinitely many pieces, infinitely many of which has more than one element, then $vertmathcal{P}^c(mathcal{S})vert=vertmathcal{P}(mathbb{N})vert.$ Conversely, it's clear that if $mathcal{S}$ has only finitely many pieces with more than one element then $mathcal{P}^c(mathcal{S})$ is countable, so this is optimal.
To see this, first note that we can assume WLOG that in fact every piece in $mathcal{S}$ has more than one element (just throw out the pieces with one element). Enumerate the elements of $mathcal{S}$ as $(S_i)_{iinmathbb{N}}$, let $a_i$ be the least element of $S_i$, and let $b_i$ be the second least element of $S_i$. Now consider the map $F:mathcal{P}(mathbb{N})rightarrowmathcal{P}^c(mathcal{S})$ given by $$F(A)={a_i: iin A}cup{b_i: inotin A}.$$ This is clearly an injection, and since the inclusion map $mathcal{P}^c(mathcal{S})subseteqmathcal{P}(mathbb{N})$ gives an injection in the other direction, we get a bijection from Cantor-Schroeder-Bernstein (which does not require choice). And again, even ZF is massive overkill.
answered Jan 23 at 23:46
Noah SchweberNoah Schweber
127k10151290
$endgroup$
$begingroup$
@Zuhair I literally gave a bijection between the two ...
$endgroup$
– Noah Schweber
Jan 23 at 23:52
$begingroup$
Correct, thank you!
$endgroup$
– Zuhair
Jan 24 at 0:03
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%2f3085232%2fis-the-set-of-all-choice-sets-on-a-infinite-partition-on-mathbb-n-equal-in-ca%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Yes.
Consider the map $F:mathcal{P}^c(mathcal{S})rightarrowmathcal{P}(mathbb{N})$ sending a choice set $X$ to the set $$F(X)={n: 2nin X}.$$ It's easy to check that this is a bijection, and vastly less than ZF is required.
Similarly, ZF proves that if $mathcal{S}$ is any partition of $mathbb{N}$ into infinitely many pieces, infinitely many of which has more than one element, then $vertmathcal{P}^c(mathcal{S})vert=vertmathcal{P}(mathbb{N})vert.$ Conversely, it's clear that if $mathcal{S}$ has only finitely many pieces with more than one element then $mathcal{P}^c(mathcal{S})$ is countable, so this is optimal.
To see this, first note that we can assume WLOG that in fact every piece in $mathcal{S}$ has more than one element (just throw out the pieces with one element). Enumerate the elements of $mathcal{S}$ as $(S_i)_{iinmathbb{N}}$, let $a_i$ be the least element of $S_i$, and let $b_i$ be the second least element of $S_i$. Now consider the map $F:mathcal{P}(mathbb{N})rightarrowmathcal{P}^c(mathcal{S})$ given by $$F(A)={a_i: iin A}cup{b_i: inotin A}.$$ This is clearly an injection, and since the inclusion map $mathcal{P}^c(mathcal{S})subseteqmathcal{P}(mathbb{N})$ gives an injection in the other direction, we get a bijection from Cantor-Schroeder-Bernstein (which does not require choice). And again, even ZF is massive overkill.
answered Jan 23 at 23:46
Noah SchweberNoah Schweber
127k10151290
$endgroup$
$begingroup$
@Zuhair I literally gave a bijection between the two ...
$endgroup$
– Noah Schweber
Jan 23 at 23:52
$begingroup$
Correct, thank you!
$endgroup$
– Zuhair
Jan 24 at 0:03
add a comment |
$begingroup$
Yes.
Consider the map $F:mathcal{P}^c(mathcal{S})rightarrowmathcal{P}(mathbb{N})$ sending a choice set $X$ to the set $$F(X)={n: 2nin X}.$$ It's easy to check that this is a bijection, and vastly less than ZF is required.
Similarly, ZF proves that if $mathcal{S}$ is any partition of $mathbb{N}$ into infinitely many pieces, infinitely many of which has more than one element, then $vertmathcal{P}^c(mathcal{S})vert=vertmathcal{P}(mathbb{N})vert.$ Conversely, it's clear that if $mathcal{S}$ has only finitely many pieces with more than one element then $mathcal{P}^c(mathcal{S})$ is countable, so this is optimal.
To see this, first note that we can assume WLOG that in fact every piece in $mathcal{S}$ has more than one element (just throw out the pieces with one element). Enumerate the elements of $mathcal{S}$ as $(S_i)_{iinmathbb{N}}$, let $a_i$ be the least element of $S_i$, and let $b_i$ be the second least element of $S_i$. Now consider the map $F:mathcal{P}(mathbb{N})rightarrowmathcal{P}^c(mathcal{S})$ given by $$F(A)={a_i: iin A}cup{b_i: inotin A}.$$ This is clearly an injection, and since the inclusion map $mathcal{P}^c(mathcal{S})subseteqmathcal{P}(mathbb{N})$ gives an injection in the other direction, we get a bijection from Cantor-Schroeder-Bernstein (which does not require choice). And again, even ZF is massive overkill.
answered Jan 23 at 23:46
Noah SchweberNoah Schweber
127k10151290
$endgroup$
$begingroup$
@Zuhair I literally gave a bijection between the two ...
$endgroup$
– Noah Schweber
Jan 23 at 23:52
$begingroup$
Correct, thank you!
$endgroup$
– Zuhair
Jan 24 at 0:03
add a comment |
$begingroup$
Yes.
Consider the map $F:mathcal{P}^c(mathcal{S})rightarrowmathcal{P}(mathbb{N})$ sending a choice set $X$ to the set $$F(X)={n: 2nin X}.$$ It's easy to check that this is a bijection, and vastly less than ZF is required.
Similarly, ZF proves that if $mathcal{S}$ is any partition of $mathbb{N}$ into infinitely many pieces, infinitely many of which has more than one element, then $vertmathcal{P}^c(mathcal{S})vert=vertmathcal{P}(mathbb{N})vert.$ Conversely, it's clear that if $mathcal{S}$ has only finitely many pieces with more than one element then $mathcal{P}^c(mathcal{S})$ is countable, so this is optimal.
To see this, first note that we can assume WLOG that in fact every piece in $mathcal{S}$ has more than one element (just throw out the pieces with one element). Enumerate the elements of $mathcal{S}$ as $(S_i)_{iinmathbb{N}}$, let $a_i$ be the least element of $S_i$, and let $b_i$ be the second least element of $S_i$. Now consider the map $F:mathcal{P}(mathbb{N})rightarrowmathcal{P}^c(mathcal{S})$ given by $$F(A)={a_i: iin A}cup{b_i: inotin A}.$$ This is clearly an injection, and since the inclusion map $mathcal{P}^c(mathcal{S})subseteqmathcal{P}(mathbb{N})$ gives an injection in the other direction, we get a bijection from Cantor-Schroeder-Bernstein (which does not require choice). And again, even ZF is massive overkill.
answered Jan 23 at 23:46
Noah SchweberNoah Schweber
127k10151290
$endgroup$
Yes.
Consider the map $F:mathcal{P}^c(mathcal{S})rightarrowmathcal{P}(mathbb{N})$ sending a choice set $X$ to the set $$F(X)={n: 2nin X}.$$ It's easy to check that this is a bijection, and vastly less than ZF is required.
Similarly, ZF proves that if $mathcal{S}$ is any partition of $mathbb{N}$ into infinitely many pieces, infinitely many of which has more than one element, then $vertmathcal{P}^c(mathcal{S})vert=vertmathcal{P}(mathbb{N})vert.$ Conversely, it's clear that if $mathcal{S}$ has only finitely many pieces with more than one element then $mathcal{P}^c(mathcal{S})$ is countable, so this is optimal.
To see this, first note that we can assume WLOG that in fact every piece in $mathcal{S}$ has more than one element (just throw out the pieces with one element). Enumerate the elements of $mathcal{S}$ as $(S_i)_{iinmathbb{N}}$, let $a_i$ be the least element of $S_i$, and let $b_i$ be the second least element of $S_i$. Now consider the map $F:mathcal{P}(mathbb{N})rightarrowmathcal{P}^c(mathcal{S})$ given by $$F(A)={a_i: iin A}cup{b_i: inotin A}.$$ This is clearly an injection, and since the inclusion map $mathcal{P}^c(mathcal{S})subseteqmathcal{P}(mathbb{N})$ gives an injection in the other direction, we get a bijection from Cantor-Schroeder-Bernstein (which does not require choice). And again, even ZF is massive overkill.
answered Jan 23 at 23:46
Noah SchweberNoah Schweber
127k10151290
edited Jan 23 at 23:55
answered Jan 23 at 23:46
Noah SchweberNoah Schweber
127k10151290
answered Jan 23 at 23:46
Noah SchweberNoah Schweber
127k10151290
answered Jan 23 at 23:46
Noah SchweberNoah Schweber
127k10151290
127k10151290
$begingroup$
@Zuhair I literally gave a bijection between the two ...
$endgroup$
– Noah Schweber
Jan 23 at 23:52
$begingroup$
Correct, thank you!
$endgroup$
– Zuhair
Jan 24 at 0:03
add a comment |
$begingroup$
@Zuhair I literally gave a bijection between the two ...
$endgroup$
– Noah Schweber
Jan 23 at 23:52
$begingroup$
Correct, thank you!
$endgroup$
– Zuhair
Jan 24 at 0:03
$begingroup$
@Zuhair I literally gave a bijection between the two ...
$endgroup$
– Noah Schweber
Jan 23 at 23:52
$begingroup$
@Zuhair I literally gave a bijection between the two ...
$endgroup$
– Noah Schweber
Jan 23 at 23:52
$begingroup$
Correct, thank you!
$endgroup$
– Zuhair
Jan 24 at 0:03
$begingroup$
Correct, thank you!
$endgroup$
– Zuhair
Jan 24 at 0:03
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%2f3085232%2fis-the-set-of-all-choice-sets-on-a-infinite-partition-on-mathbb-n-equal-in-ca%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
