Define a bijection such that $f(x)neq x$
$begingroup$
Let $A$ a set such that $|A|>1$. Iwant to prove that there exists a bijection $f:Arightarrow A$ such that $f(x)neq x$.
First, by AC, I can obtain a well order for $A$, and w.l.o.g I suppose that it has order type $alpha$. So $A={x_xi}_{xi<alpha}$. Now, define the set $C_xi=Asetminus{x_xi}$. By transfinite recursion I can define the element $y_xi=min C_xisetminus{y_beta:beta<xi}$.
Then, the function $f:Arightarrow A$ such that $f(x_xi)=y_xi$ is the desire function.
Is it fine my approach?
elementary-set-theory
edited Dec 3 '18 at 18:24
Federico
4,899514
asked Dec 3 '18 at 17:31
GödelGödel
1,416319
$endgroup$
|
show 4 more comments
$begingroup$
Let $A$ a set such that $|A|>1$. Iwant to prove that there exists a bijection $f:Arightarrow A$ such that $f(x)neq x$.
First, by AC, I can obtain a well order for $A$, and w.l.o.g I suppose that it has order type $alpha$. So $A={x_xi}_{xi<alpha}$. Now, define the set $C_xi=Asetminus{x_xi}$. By transfinite recursion I can define the element $y_xi=min C_xisetminus{y_beta:beta<xi}$.
Then, the function $f:Arightarrow A$ such that $f(x_xi)=y_xi$ is the desire function.
Is it fine my approach?
elementary-set-theory
edited Dec 3 '18 at 18:24
Federico
4,899514
asked Dec 3 '18 at 17:31
GödelGödel
1,416319
$endgroup$
$begingroup$
How do you prove that $C_xi setminus {y_beta : beta<xi} neq emptyset$?
$endgroup$
– Federico
Dec 3 '18 at 17:36
$begingroup$
@Federico Fine, this construction works if $alpha$ is a limit ordinal, right?
$endgroup$
– Gödel
Dec 3 '18 at 17:38
$begingroup$
Well, intuitively I would say that it always works, but I don't see immediately why the set is non-empty
$endgroup$
– Federico
Dec 3 '18 at 17:42
$begingroup$
The axiom of choice tag is meant for questions where you're asking specifically about the necessity of choice in the proof. Not for questions whose answers use choice (since that would encompass a significant portion of this site).
$endgroup$
– Asaf Karagila♦
Dec 3 '18 at 17:44
1
$begingroup$
@Federico: For example math.stackexchange.com/questions/134152/…
$endgroup$
– Asaf Karagila♦
Dec 4 '18 at 8:08
|
show 4 more comments
$begingroup$
Let $A$ a set such that $|A|>1$. Iwant to prove that there exists a bijection $f:Arightarrow A$ such that $f(x)neq x$.
First, by AC, I can obtain a well order for $A$, and w.l.o.g I suppose that it has order type $alpha$. So $A={x_xi}_{xi<alpha}$. Now, define the set $C_xi=Asetminus{x_xi}$. By transfinite recursion I can define the element $y_xi=min C_xisetminus{y_beta:beta<xi}$.
Then, the function $f:Arightarrow A$ such that $f(x_xi)=y_xi$ is the desire function.
Is it fine my approach?
elementary-set-theory
edited Dec 3 '18 at 18:24
Federico
4,899514
asked Dec 3 '18 at 17:31
GödelGödel
1,416319
$endgroup$
Let $A$ a set such that $|A|>1$. Iwant to prove that there exists a bijection $f:Arightarrow A$ such that $f(x)neq x$.
First, by AC, I can obtain a well order for $A$, and w.l.o.g I suppose that it has order type $alpha$. So $A={x_xi}_{xi<alpha}$. Now, define the set $C_xi=Asetminus{x_xi}$. By transfinite recursion I can define the element $y_xi=min C_xisetminus{y_beta:beta<xi}$.
Then, the function $f:Arightarrow A$ such that $f(x_xi)=y_xi$ is the desire function.
Is it fine my approach?
elementary-set-theory
elementary-set-theory
edited Dec 3 '18 at 18:24
Federico
4,899514
asked Dec 3 '18 at 17:31
GödelGödel
1,416319
edited Dec 3 '18 at 18:24
Federico
4,899514
asked Dec 3 '18 at 17:31
GödelGödel
1,416319
edited Dec 3 '18 at 18:24
Federico
4,899514
edited Dec 3 '18 at 18:24
Federico
4,899514
edited Dec 3 '18 at 18:24
Federico
4,899514
4,899514
asked Dec 3 '18 at 17:31
GödelGödel
1,416319
asked Dec 3 '18 at 17:31
GödelGödel
1,416319
asked Dec 3 '18 at 17:31
GödelGödel
1,416319
1,416319
$begingroup$
How do you prove that $C_xi setminus {y_beta : beta<xi} neq emptyset$?
$endgroup$
– Federico
Dec 3 '18 at 17:36
$begingroup$
@Federico Fine, this construction works if $alpha$ is a limit ordinal, right?
$endgroup$
– Gödel
Dec 3 '18 at 17:38
$begingroup$
Well, intuitively I would say that it always works, but I don't see immediately why the set is non-empty
$endgroup$
– Federico
Dec 3 '18 at 17:42
$begingroup$
The axiom of choice tag is meant for questions where you're asking specifically about the necessity of choice in the proof. Not for questions whose answers use choice (since that would encompass a significant portion of this site).
$endgroup$
– Asaf Karagila♦
Dec 3 '18 at 17:44
1
$begingroup$
@Federico: For example math.stackexchange.com/questions/134152/…
$endgroup$
– Asaf Karagila♦
Dec 4 '18 at 8:08
|
show 4 more comments
$begingroup$
How do you prove that $C_xi setminus {y_beta : beta<xi} neq emptyset$?
$endgroup$
– Federico
Dec 3 '18 at 17:36
$begingroup$
@Federico Fine, this construction works if $alpha$ is a limit ordinal, right?
$endgroup$
– Gödel
Dec 3 '18 at 17:38
$begingroup$
Well, intuitively I would say that it always works, but I don't see immediately why the set is non-empty
$endgroup$
– Federico
Dec 3 '18 at 17:42
$begingroup$
The axiom of choice tag is meant for questions where you're asking specifically about the necessity of choice in the proof. Not for questions whose answers use choice (since that would encompass a significant portion of this site).
$endgroup$
– Asaf Karagila♦
Dec 3 '18 at 17:44
1
$begingroup$
@Federico: For example math.stackexchange.com/questions/134152/…
$endgroup$
– Asaf Karagila♦
Dec 4 '18 at 8:08
$begingroup$
How do you prove that $C_xi setminus {y_beta : beta<xi} neq emptyset$?
$endgroup$
– Federico
Dec 3 '18 at 17:36
$begingroup$
How do you prove that $C_xi setminus {y_beta : beta<xi} neq emptyset$?
$endgroup$
– Federico
Dec 3 '18 at 17:36
$begingroup$
@Federico Fine, this construction works if $alpha$ is a limit ordinal, right?
$endgroup$
– Gödel
Dec 3 '18 at 17:38
$begingroup$
@Federico Fine, this construction works if $alpha$ is a limit ordinal, right?
$endgroup$
– Gödel
Dec 3 '18 at 17:38
$begingroup$
Well, intuitively I would say that it always works, but I don't see immediately why the set is non-empty
$endgroup$
– Federico
Dec 3 '18 at 17:42
$begingroup$
Well, intuitively I would say that it always works, but I don't see immediately why the set is non-empty
$endgroup$
– Federico
Dec 3 '18 at 17:42
$begingroup$
The axiom of choice tag is meant for questions where you're asking specifically about the necessity of choice in the proof. Not for questions whose answers use choice (since that would encompass a significant portion of this site).
$endgroup$
– Asaf Karagila♦
Dec 3 '18 at 17:44
$begingroup$
The axiom of choice tag is meant for questions where you're asking specifically about the necessity of choice in the proof. Not for questions whose answers use choice (since that would encompass a significant portion of this site).
$endgroup$
– Asaf Karagila♦
Dec 3 '18 at 17:44
1
1
$begingroup$
@Federico: For example math.stackexchange.com/questions/134152/…
$endgroup$
– Asaf Karagila♦
Dec 4 '18 at 8:08
$begingroup$
@Federico: For example math.stackexchange.com/questions/134152/…
$endgroup$
– Asaf Karagila♦
Dec 4 '18 at 8:08
|
show 4 more comments
2 Answers
2
active
oldest
votes
$begingroup$
You can also use the fact that every infinite set $X$ can be partitioned into blocks of size 2 using ordinal theory; see this. So we partition $X$
$tag 1 X = cup ; F_lambda text{ with #}(F_lambda) = 2$
Once you have that you are in business. Set
$tag 2 F_{(lambda, rho)} = (F_lambda times F_lambda) setminus {(x,x) , | , x in F_lambda}$
The union of the $F_{(lambda, rho)}$ is a bijective correspondence $f$ with $f(x) ne x$. It can be viewed as a union of transpositions.
answered Dec 3 '18 at 20:51
CopyPasteItCopyPasteIt
4,1181628
$endgroup$
add a comment |
$begingroup$
Alternatively, you can do the following.
If $A$ is finite but not a singleton, then it's simple: just cycle the elements.
If $A$ is infinite, show that $A=A_1 sqcup A_2$ with $|A_1|=|A_2|$ and take any bijection $phi:A_1to A_2$. Then $f|_{A_1}=phi$ and $f|_{A_2}=phi^{-1}$ is a solution.
answered Dec 3 '18 at 17:41
FedericoFederico
4,899514
$endgroup$
1
$begingroup$
$A$ can't be a singleton.
$endgroup$
– CopyPasteIt
Dec 3 '18 at 20:04
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%2f3024391%2fdefine-a-bijection-such-that-fx-neq-x%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$
You can also use the fact that every infinite set $X$ can be partitioned into blocks of size 2 using ordinal theory; see this. So we partition $X$
$tag 1 X = cup ; F_lambda text{ with #}(F_lambda) = 2$
Once you have that you are in business. Set
$tag 2 F_{(lambda, rho)} = (F_lambda times F_lambda) setminus {(x,x) , | , x in F_lambda}$
The union of the $F_{(lambda, rho)}$ is a bijective correspondence $f$ with $f(x) ne x$. It can be viewed as a union of transpositions.
answered Dec 3 '18 at 20:51
CopyPasteItCopyPasteIt
4,1181628
$endgroup$
add a comment |
$begingroup$
You can also use the fact that every infinite set $X$ can be partitioned into blocks of size 2 using ordinal theory; see this. So we partition $X$
$tag 1 X = cup ; F_lambda text{ with #}(F_lambda) = 2$
Once you have that you are in business. Set
$tag 2 F_{(lambda, rho)} = (F_lambda times F_lambda) setminus {(x,x) , | , x in F_lambda}$
The union of the $F_{(lambda, rho)}$ is a bijective correspondence $f$ with $f(x) ne x$. It can be viewed as a union of transpositions.
answered Dec 3 '18 at 20:51
CopyPasteItCopyPasteIt
4,1181628
$endgroup$
add a comment |
$begingroup$
You can also use the fact that every infinite set $X$ can be partitioned into blocks of size 2 using ordinal theory; see this. So we partition $X$
$tag 1 X = cup ; F_lambda text{ with #}(F_lambda) = 2$
Once you have that you are in business. Set
$tag 2 F_{(lambda, rho)} = (F_lambda times F_lambda) setminus {(x,x) , | , x in F_lambda}$
The union of the $F_{(lambda, rho)}$ is a bijective correspondence $f$ with $f(x) ne x$. It can be viewed as a union of transpositions.
answered Dec 3 '18 at 20:51
CopyPasteItCopyPasteIt
4,1181628
$endgroup$
You can also use the fact that every infinite set $X$ can be partitioned into blocks of size 2 using ordinal theory; see this. So we partition $X$
$tag 1 X = cup ; F_lambda text{ with #}(F_lambda) = 2$
Once you have that you are in business. Set
$tag 2 F_{(lambda, rho)} = (F_lambda times F_lambda) setminus {(x,x) , | , x in F_lambda}$
The union of the $F_{(lambda, rho)}$ is a bijective correspondence $f$ with $f(x) ne x$. It can be viewed as a union of transpositions.
answered Dec 3 '18 at 20:51
CopyPasteItCopyPasteIt
4,1181628
answered Dec 3 '18 at 20:51
CopyPasteItCopyPasteIt
4,1181628
answered Dec 3 '18 at 20:51
CopyPasteItCopyPasteIt
4,1181628
answered Dec 3 '18 at 20:51
CopyPasteItCopyPasteIt
4,1181628
4,1181628
add a comment |
add a comment |
$begingroup$
Alternatively, you can do the following.
If $A$ is finite but not a singleton, then it's simple: just cycle the elements.
If $A$ is infinite, show that $A=A_1 sqcup A_2$ with $|A_1|=|A_2|$ and take any bijection $phi:A_1to A_2$. Then $f|_{A_1}=phi$ and $f|_{A_2}=phi^{-1}$ is a solution.
answered Dec 3 '18 at 17:41
FedericoFederico
4,899514
$endgroup$
1
$begingroup$
$A$ can't be a singleton.
$endgroup$
– CopyPasteIt
Dec 3 '18 at 20:04
add a comment |
$begingroup$
Alternatively, you can do the following.
If $A$ is finite but not a singleton, then it's simple: just cycle the elements.
If $A$ is infinite, show that $A=A_1 sqcup A_2$ with $|A_1|=|A_2|$ and take any bijection $phi:A_1to A_2$. Then $f|_{A_1}=phi$ and $f|_{A_2}=phi^{-1}$ is a solution.
answered Dec 3 '18 at 17:41
FedericoFederico
4,899514
$endgroup$
1
$begingroup$
$A$ can't be a singleton.
$endgroup$
– CopyPasteIt
Dec 3 '18 at 20:04
add a comment |
$begingroup$
Alternatively, you can do the following.
If $A$ is finite but not a singleton, then it's simple: just cycle the elements.
If $A$ is infinite, show that $A=A_1 sqcup A_2$ with $|A_1|=|A_2|$ and take any bijection $phi:A_1to A_2$. Then $f|_{A_1}=phi$ and $f|_{A_2}=phi^{-1}$ is a solution.
answered Dec 3 '18 at 17:41
FedericoFederico
4,899514
$endgroup$
Alternatively, you can do the following.
If $A$ is finite but not a singleton, then it's simple: just cycle the elements.
If $A$ is infinite, show that $A=A_1 sqcup A_2$ with $|A_1|=|A_2|$ and take any bijection $phi:A_1to A_2$. Then $f|_{A_1}=phi$ and $f|_{A_2}=phi^{-1}$ is a solution.
answered Dec 3 '18 at 17:41
FedericoFederico
4,899514
edited Dec 4 '18 at 13:33
answered Dec 3 '18 at 17:41
FedericoFederico
4,899514
answered Dec 3 '18 at 17:41
FedericoFederico
4,899514
answered Dec 3 '18 at 17:41
FedericoFederico
4,899514
4,899514
1
$begingroup$
$A$ can't be a singleton.
$endgroup$
– CopyPasteIt
Dec 3 '18 at 20:04
add a comment |
1
$begingroup$
$A$ can't be a singleton.
$endgroup$
– CopyPasteIt
Dec 3 '18 at 20:04
1
1
$begingroup$
$A$ can't be a singleton.
$endgroup$
– CopyPasteIt
Dec 3 '18 at 20:04
$begingroup$
$A$ can't be a singleton.
$endgroup$
– CopyPasteIt
Dec 3 '18 at 20:04
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%2f3024391%2fdefine-a-bijection-such-that-fx-neq-x%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
$begingroup$
How do you prove that $C_xi setminus {y_beta : beta<xi} neq emptyset$?
$endgroup$
– Federico
Dec 3 '18 at 17:36
$begingroup$
@Federico Fine, this construction works if $alpha$ is a limit ordinal, right?
$endgroup$
– Gödel
Dec 3 '18 at 17:38
$begingroup$
Well, intuitively I would say that it always works, but I don't see immediately why the set is non-empty
$endgroup$
– Federico
Dec 3 '18 at 17:42
$begingroup$
The axiom of choice tag is meant for questions where you're asking specifically about the necessity of choice in the proof. Not for questions whose answers use choice (since that would encompass a significant portion of this site).
$endgroup$
– Asaf Karagila♦
Dec 3 '18 at 17:44
1
$begingroup$
@Federico: For example math.stackexchange.com/questions/134152/…
$endgroup$
– Asaf Karagila♦
Dec 4 '18 at 8:08