About a bijective function with the disjoint sets
$begingroup$
In this video by 0:55, it says
Lemma: Let $A,B,C,D$ be sets with $Acap B=emptyset$ and $Ccap D=emptyset$. Suppose that $F_1:Ato C$ and $F_2:Bto D$ are both bijections. Define $F:Acup Bto Ccup D$ by
$$
F(x)=begin{cases}
F_1(x) & text{ if } xin A \
F_2(x) & text{ if } xin B
end{cases}
$$
Then $F$ is a bijection.
To me, it is easy to prove it by looking at the $F|_A$ and $F|_B$ seperately, and then, by construction, $F$ is bijective by collecting the elements of $A$ and $B$. The question is, why do the intersections $Acap B$ and $Ccap D$ have to be empty, in particular the last one?
discrete-mathematics
$endgroup$
add a comment |
$begingroup$
In this video by 0:55, it says
Lemma: Let $A,B,C,D$ be sets with $Acap B=emptyset$ and $Ccap D=emptyset$. Suppose that $F_1:Ato C$ and $F_2:Bto D$ are both bijections. Define $F:Acup Bto Ccup D$ by
$$
F(x)=begin{cases}
F_1(x) & text{ if } xin A \
F_2(x) & text{ if } xin B
end{cases}
$$
Then $F$ is a bijection.
To me, it is easy to prove it by looking at the $F|_A$ and $F|_B$ seperately, and then, by construction, $F$ is bijective by collecting the elements of $A$ and $B$. The question is, why do the intersections $Acap B$ and $Ccap D$ have to be empty, in particular the last one?
discrete-mathematics
$endgroup$
add a comment |
$begingroup$
In this video by 0:55, it says
Lemma: Let $A,B,C,D$ be sets with $Acap B=emptyset$ and $Ccap D=emptyset$. Suppose that $F_1:Ato C$ and $F_2:Bto D$ are both bijections. Define $F:Acup Bto Ccup D$ by
$$
F(x)=begin{cases}
F_1(x) & text{ if } xin A \
F_2(x) & text{ if } xin B
end{cases}
$$
Then $F$ is a bijection.
To me, it is easy to prove it by looking at the $F|_A$ and $F|_B$ seperately, and then, by construction, $F$ is bijective by collecting the elements of $A$ and $B$. The question is, why do the intersections $Acap B$ and $Ccap D$ have to be empty, in particular the last one?
discrete-mathematics
$endgroup$
In this video by 0:55, it says
Lemma: Let $A,B,C,D$ be sets with $Acap B=emptyset$ and $Ccap D=emptyset$. Suppose that $F_1:Ato C$ and $F_2:Bto D$ are both bijections. Define $F:Acup Bto Ccup D$ by
$$
F(x)=begin{cases}
F_1(x) & text{ if } xin A \
F_2(x) & text{ if } xin B
end{cases}
$$
Then $F$ is a bijection.
To me, it is easy to prove it by looking at the $F|_A$ and $F|_B$ seperately, and then, by construction, $F$ is bijective by collecting the elements of $A$ and $B$. The question is, why do the intersections $Acap B$ and $Ccap D$ have to be empty, in particular the last one?
discrete-mathematics
discrete-mathematics
asked Dec 2 '18 at 3:24
UnknownWUnknownW
1,001922
1,001922
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
If the intersection $A cap B$ is nonempty, the function may not be well-defined — if $xin A cap B$ and $F_1(x) neq F_2(x)$, which one do you choose when evaluating $F(x)$?
If the intersection $C cap D$ is nonempty, the function may not be an injection. For $y in C cap D$, there must be $x_1 in A$ and $x_2 in B$ such that $F_1(x_1) = y$ and $F_2(x_2) = y$. But then $F(x_1) = F(x_2)$; if $x_1 neq x_2$ (which may very well be true), then $F$ is not an injection.
$endgroup$
$begingroup$
I think you mean the function will not be a bijection. Non-empty intersection does not imply undefined function even by the answer you have posed. Please fix it.
$endgroup$
– Bertrand Wittgenstein's Ghost
Dec 2 '18 at 3:33
1
$begingroup$
@BertrandWittgenstein'sGhost Nope, I meant what I said. If there is $x in A cap B$ such that $F_1(x) neq F_2(x)$, then the function $F$ will not be well-defined, as we would have both $F(x) = F_1(x)$ and $F(x) = F_2(x)$. It certainly does not imply that the function is always undefined if the intersection is nonempty, but in order to guarantee that the function is well-defined, you want this to hold.
$endgroup$
– platty
Dec 2 '18 at 3:37
$begingroup$
I still do not see the logic, your answer and the comment imply the function is not surjective. Which is fine, but not necessarily undefined.
$endgroup$
– Bertrand Wittgenstein's Ghost
Dec 2 '18 at 3:42
1
$begingroup$
Nothing I wrote implies that the function will necessarily not be surjective, as it is quite possible that the function is actually bijective (let $A = C = {1,2}$ and $B = D = {2,3}$ and take all three functions to be the identity). My point is that, if we do not add the constraint that $A cap B$, you cannot even guarantee that $F$ is well-defined. Is there some aspect of this argument in particular which you do not understand?
$endgroup$
– platty
Dec 2 '18 at 3:45
1
$begingroup$
By definition, a function maps each element do the domain to exactly one element of the codomain. Ergo, in the chance that $F_1(x) neq F_2(x)$, the function $F$ is not well-defined.
$endgroup$
– platty
Dec 2 '18 at 4:09
|
show 3 more comments
$begingroup$
If $y in Acap B$ then which do you choose to define $F(y)$ as? $F_1(y)$ or $F_2(y)$? If you define it as $F_1(y)$ then it's possible that nothing will be mapped to $F_2(y)$ and vice versa so it may not be surjective. (And if $Ccap D = emptyset$ then definitely on of $F_1(y)$ or $F_2(y)$ will not be mapped to.)
Likewise if $z in Ccap D$ then it's possible there is an $a in A$ and a $b in B$ so that $F_1(a) = F_2(b) = z$. So $F$ may not be one to one.
$endgroup$
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%2f3022189%2fabout-a-bijective-function-with-the-disjoint-sets%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$
If the intersection $A cap B$ is nonempty, the function may not be well-defined — if $xin A cap B$ and $F_1(x) neq F_2(x)$, which one do you choose when evaluating $F(x)$?
If the intersection $C cap D$ is nonempty, the function may not be an injection. For $y in C cap D$, there must be $x_1 in A$ and $x_2 in B$ such that $F_1(x_1) = y$ and $F_2(x_2) = y$. But then $F(x_1) = F(x_2)$; if $x_1 neq x_2$ (which may very well be true), then $F$ is not an injection.
$endgroup$
$begingroup$
I think you mean the function will not be a bijection. Non-empty intersection does not imply undefined function even by the answer you have posed. Please fix it.
$endgroup$
– Bertrand Wittgenstein's Ghost
Dec 2 '18 at 3:33
1
$begingroup$
@BertrandWittgenstein'sGhost Nope, I meant what I said. If there is $x in A cap B$ such that $F_1(x) neq F_2(x)$, then the function $F$ will not be well-defined, as we would have both $F(x) = F_1(x)$ and $F(x) = F_2(x)$. It certainly does not imply that the function is always undefined if the intersection is nonempty, but in order to guarantee that the function is well-defined, you want this to hold.
$endgroup$
– platty
Dec 2 '18 at 3:37
$begingroup$
I still do not see the logic, your answer and the comment imply the function is not surjective. Which is fine, but not necessarily undefined.
$endgroup$
– Bertrand Wittgenstein's Ghost
Dec 2 '18 at 3:42
1
$begingroup$
Nothing I wrote implies that the function will necessarily not be surjective, as it is quite possible that the function is actually bijective (let $A = C = {1,2}$ and $B = D = {2,3}$ and take all three functions to be the identity). My point is that, if we do not add the constraint that $A cap B$, you cannot even guarantee that $F$ is well-defined. Is there some aspect of this argument in particular which you do not understand?
$endgroup$
– platty
Dec 2 '18 at 3:45
1
$begingroup$
By definition, a function maps each element do the domain to exactly one element of the codomain. Ergo, in the chance that $F_1(x) neq F_2(x)$, the function $F$ is not well-defined.
$endgroup$
– platty
Dec 2 '18 at 4:09
|
show 3 more comments
$begingroup$
If the intersection $A cap B$ is nonempty, the function may not be well-defined — if $xin A cap B$ and $F_1(x) neq F_2(x)$, which one do you choose when evaluating $F(x)$?
If the intersection $C cap D$ is nonempty, the function may not be an injection. For $y in C cap D$, there must be $x_1 in A$ and $x_2 in B$ such that $F_1(x_1) = y$ and $F_2(x_2) = y$. But then $F(x_1) = F(x_2)$; if $x_1 neq x_2$ (which may very well be true), then $F$ is not an injection.
$endgroup$
$begingroup$
I think you mean the function will not be a bijection. Non-empty intersection does not imply undefined function even by the answer you have posed. Please fix it.
$endgroup$
– Bertrand Wittgenstein's Ghost
Dec 2 '18 at 3:33
1
$begingroup$
@BertrandWittgenstein'sGhost Nope, I meant what I said. If there is $x in A cap B$ such that $F_1(x) neq F_2(x)$, then the function $F$ will not be well-defined, as we would have both $F(x) = F_1(x)$ and $F(x) = F_2(x)$. It certainly does not imply that the function is always undefined if the intersection is nonempty, but in order to guarantee that the function is well-defined, you want this to hold.
$endgroup$
– platty
Dec 2 '18 at 3:37
$begingroup$
I still do not see the logic, your answer and the comment imply the function is not surjective. Which is fine, but not necessarily undefined.
$endgroup$
– Bertrand Wittgenstein's Ghost
Dec 2 '18 at 3:42
1
$begingroup$
Nothing I wrote implies that the function will necessarily not be surjective, as it is quite possible that the function is actually bijective (let $A = C = {1,2}$ and $B = D = {2,3}$ and take all three functions to be the identity). My point is that, if we do not add the constraint that $A cap B$, you cannot even guarantee that $F$ is well-defined. Is there some aspect of this argument in particular which you do not understand?
$endgroup$
– platty
Dec 2 '18 at 3:45
1
$begingroup$
By definition, a function maps each element do the domain to exactly one element of the codomain. Ergo, in the chance that $F_1(x) neq F_2(x)$, the function $F$ is not well-defined.
$endgroup$
– platty
Dec 2 '18 at 4:09
|
show 3 more comments
$begingroup$
If the intersection $A cap B$ is nonempty, the function may not be well-defined — if $xin A cap B$ and $F_1(x) neq F_2(x)$, which one do you choose when evaluating $F(x)$?
If the intersection $C cap D$ is nonempty, the function may not be an injection. For $y in C cap D$, there must be $x_1 in A$ and $x_2 in B$ such that $F_1(x_1) = y$ and $F_2(x_2) = y$. But then $F(x_1) = F(x_2)$; if $x_1 neq x_2$ (which may very well be true), then $F$ is not an injection.
$endgroup$
If the intersection $A cap B$ is nonempty, the function may not be well-defined — if $xin A cap B$ and $F_1(x) neq F_2(x)$, which one do you choose when evaluating $F(x)$?
If the intersection $C cap D$ is nonempty, the function may not be an injection. For $y in C cap D$, there must be $x_1 in A$ and $x_2 in B$ such that $F_1(x_1) = y$ and $F_2(x_2) = y$. But then $F(x_1) = F(x_2)$; if $x_1 neq x_2$ (which may very well be true), then $F$ is not an injection.
edited Dec 2 '18 at 4:22
answered Dec 2 '18 at 3:28
plattyplatty
3,370320
3,370320
$begingroup$
I think you mean the function will not be a bijection. Non-empty intersection does not imply undefined function even by the answer you have posed. Please fix it.
$endgroup$
– Bertrand Wittgenstein's Ghost
Dec 2 '18 at 3:33
1
$begingroup$
@BertrandWittgenstein'sGhost Nope, I meant what I said. If there is $x in A cap B$ such that $F_1(x) neq F_2(x)$, then the function $F$ will not be well-defined, as we would have both $F(x) = F_1(x)$ and $F(x) = F_2(x)$. It certainly does not imply that the function is always undefined if the intersection is nonempty, but in order to guarantee that the function is well-defined, you want this to hold.
$endgroup$
– platty
Dec 2 '18 at 3:37
$begingroup$
I still do not see the logic, your answer and the comment imply the function is not surjective. Which is fine, but not necessarily undefined.
$endgroup$
– Bertrand Wittgenstein's Ghost
Dec 2 '18 at 3:42
1
$begingroup$
Nothing I wrote implies that the function will necessarily not be surjective, as it is quite possible that the function is actually bijective (let $A = C = {1,2}$ and $B = D = {2,3}$ and take all three functions to be the identity). My point is that, if we do not add the constraint that $A cap B$, you cannot even guarantee that $F$ is well-defined. Is there some aspect of this argument in particular which you do not understand?
$endgroup$
– platty
Dec 2 '18 at 3:45
1
$begingroup$
By definition, a function maps each element do the domain to exactly one element of the codomain. Ergo, in the chance that $F_1(x) neq F_2(x)$, the function $F$ is not well-defined.
$endgroup$
– platty
Dec 2 '18 at 4:09
|
show 3 more comments
$begingroup$
I think you mean the function will not be a bijection. Non-empty intersection does not imply undefined function even by the answer you have posed. Please fix it.
$endgroup$
– Bertrand Wittgenstein's Ghost
Dec 2 '18 at 3:33
1
$begingroup$
@BertrandWittgenstein'sGhost Nope, I meant what I said. If there is $x in A cap B$ such that $F_1(x) neq F_2(x)$, then the function $F$ will not be well-defined, as we would have both $F(x) = F_1(x)$ and $F(x) = F_2(x)$. It certainly does not imply that the function is always undefined if the intersection is nonempty, but in order to guarantee that the function is well-defined, you want this to hold.
$endgroup$
– platty
Dec 2 '18 at 3:37
$begingroup$
I still do not see the logic, your answer and the comment imply the function is not surjective. Which is fine, but not necessarily undefined.
$endgroup$
– Bertrand Wittgenstein's Ghost
Dec 2 '18 at 3:42
1
$begingroup$
Nothing I wrote implies that the function will necessarily not be surjective, as it is quite possible that the function is actually bijective (let $A = C = {1,2}$ and $B = D = {2,3}$ and take all three functions to be the identity). My point is that, if we do not add the constraint that $A cap B$, you cannot even guarantee that $F$ is well-defined. Is there some aspect of this argument in particular which you do not understand?
$endgroup$
– platty
Dec 2 '18 at 3:45
1
$begingroup$
By definition, a function maps each element do the domain to exactly one element of the codomain. Ergo, in the chance that $F_1(x) neq F_2(x)$, the function $F$ is not well-defined.
$endgroup$
– platty
Dec 2 '18 at 4:09
$begingroup$
I think you mean the function will not be a bijection. Non-empty intersection does not imply undefined function even by the answer you have posed. Please fix it.
$endgroup$
– Bertrand Wittgenstein's Ghost
Dec 2 '18 at 3:33
$begingroup$
I think you mean the function will not be a bijection. Non-empty intersection does not imply undefined function even by the answer you have posed. Please fix it.
$endgroup$
– Bertrand Wittgenstein's Ghost
Dec 2 '18 at 3:33
1
1
$begingroup$
@BertrandWittgenstein'sGhost Nope, I meant what I said. If there is $x in A cap B$ such that $F_1(x) neq F_2(x)$, then the function $F$ will not be well-defined, as we would have both $F(x) = F_1(x)$ and $F(x) = F_2(x)$. It certainly does not imply that the function is always undefined if the intersection is nonempty, but in order to guarantee that the function is well-defined, you want this to hold.
$endgroup$
– platty
Dec 2 '18 at 3:37
$begingroup$
@BertrandWittgenstein'sGhost Nope, I meant what I said. If there is $x in A cap B$ such that $F_1(x) neq F_2(x)$, then the function $F$ will not be well-defined, as we would have both $F(x) = F_1(x)$ and $F(x) = F_2(x)$. It certainly does not imply that the function is always undefined if the intersection is nonempty, but in order to guarantee that the function is well-defined, you want this to hold.
$endgroup$
– platty
Dec 2 '18 at 3:37
$begingroup$
I still do not see the logic, your answer and the comment imply the function is not surjective. Which is fine, but not necessarily undefined.
$endgroup$
– Bertrand Wittgenstein's Ghost
Dec 2 '18 at 3:42
$begingroup$
I still do not see the logic, your answer and the comment imply the function is not surjective. Which is fine, but not necessarily undefined.
$endgroup$
– Bertrand Wittgenstein's Ghost
Dec 2 '18 at 3:42
1
1
$begingroup$
Nothing I wrote implies that the function will necessarily not be surjective, as it is quite possible that the function is actually bijective (let $A = C = {1,2}$ and $B = D = {2,3}$ and take all three functions to be the identity). My point is that, if we do not add the constraint that $A cap B$, you cannot even guarantee that $F$ is well-defined. Is there some aspect of this argument in particular which you do not understand?
$endgroup$
– platty
Dec 2 '18 at 3:45
$begingroup$
Nothing I wrote implies that the function will necessarily not be surjective, as it is quite possible that the function is actually bijective (let $A = C = {1,2}$ and $B = D = {2,3}$ and take all three functions to be the identity). My point is that, if we do not add the constraint that $A cap B$, you cannot even guarantee that $F$ is well-defined. Is there some aspect of this argument in particular which you do not understand?
$endgroup$
– platty
Dec 2 '18 at 3:45
1
1
$begingroup$
By definition, a function maps each element do the domain to exactly one element of the codomain. Ergo, in the chance that $F_1(x) neq F_2(x)$, the function $F$ is not well-defined.
$endgroup$
– platty
Dec 2 '18 at 4:09
$begingroup$
By definition, a function maps each element do the domain to exactly one element of the codomain. Ergo, in the chance that $F_1(x) neq F_2(x)$, the function $F$ is not well-defined.
$endgroup$
– platty
Dec 2 '18 at 4:09
|
show 3 more comments
$begingroup$
If $y in Acap B$ then which do you choose to define $F(y)$ as? $F_1(y)$ or $F_2(y)$? If you define it as $F_1(y)$ then it's possible that nothing will be mapped to $F_2(y)$ and vice versa so it may not be surjective. (And if $Ccap D = emptyset$ then definitely on of $F_1(y)$ or $F_2(y)$ will not be mapped to.)
Likewise if $z in Ccap D$ then it's possible there is an $a in A$ and a $b in B$ so that $F_1(a) = F_2(b) = z$. So $F$ may not be one to one.
$endgroup$
add a comment |
$begingroup$
If $y in Acap B$ then which do you choose to define $F(y)$ as? $F_1(y)$ or $F_2(y)$? If you define it as $F_1(y)$ then it's possible that nothing will be mapped to $F_2(y)$ and vice versa so it may not be surjective. (And if $Ccap D = emptyset$ then definitely on of $F_1(y)$ or $F_2(y)$ will not be mapped to.)
Likewise if $z in Ccap D$ then it's possible there is an $a in A$ and a $b in B$ so that $F_1(a) = F_2(b) = z$. So $F$ may not be one to one.
$endgroup$
add a comment |
$begingroup$
If $y in Acap B$ then which do you choose to define $F(y)$ as? $F_1(y)$ or $F_2(y)$? If you define it as $F_1(y)$ then it's possible that nothing will be mapped to $F_2(y)$ and vice versa so it may not be surjective. (And if $Ccap D = emptyset$ then definitely on of $F_1(y)$ or $F_2(y)$ will not be mapped to.)
Likewise if $z in Ccap D$ then it's possible there is an $a in A$ and a $b in B$ so that $F_1(a) = F_2(b) = z$. So $F$ may not be one to one.
$endgroup$
If $y in Acap B$ then which do you choose to define $F(y)$ as? $F_1(y)$ or $F_2(y)$? If you define it as $F_1(y)$ then it's possible that nothing will be mapped to $F_2(y)$ and vice versa so it may not be surjective. (And if $Ccap D = emptyset$ then definitely on of $F_1(y)$ or $F_2(y)$ will not be mapped to.)
Likewise if $z in Ccap D$ then it's possible there is an $a in A$ and a $b in B$ so that $F_1(a) = F_2(b) = z$. So $F$ may not be one to one.
answered Dec 2 '18 at 4:53
fleabloodfleablood
71k22686
71k22686
add a comment |
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%2f3022189%2fabout-a-bijective-function-with-the-disjoint-sets%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