Mixing
When does surjectivity imply injectivity?
$begingroup$
Let $A$ and $B$ be two finite sets, such that $|A| = |B|$. If I define a function $f: A to B$ which is surjective, does that imply that $f$ is injective? I feel like I have been told this in some class, and intuitively it makes sense. But I cannot find any resources that confirm this.
functions elementary-set-theory
asked Jan 30 at 18:35
Matthew RileyMatthew Riley
896
$endgroup$
add a comment |
$begingroup$
Let $A$ and $B$ be two finite sets, such that $|A| = |B|$. If I define a function $f: A to B$ which is surjective, does that imply that $f$ is injective? I feel like I have been told this in some class, and intuitively it makes sense. But I cannot find any resources that confirm this.
functions elementary-set-theory
asked Jan 30 at 18:35
Matthew RileyMatthew Riley
896
$endgroup$
1
$begingroup$
It's a consequence of the pigeonhole principle.
$endgroup$
– Michael Burr
Jan 30 at 18:41
add a comment |
$begingroup$
Let $A$ and $B$ be two finite sets, such that $|A| = |B|$. If I define a function $f: A to B$ which is surjective, does that imply that $f$ is injective? I feel like I have been told this in some class, and intuitively it makes sense. But I cannot find any resources that confirm this.
functions elementary-set-theory
asked Jan 30 at 18:35
Matthew RileyMatthew Riley
896
$endgroup$
Let $A$ and $B$ be two finite sets, such that $|A| = |B|$. If I define a function $f: A to B$ which is surjective, does that imply that $f$ is injective? I feel like I have been told this in some class, and intuitively it makes sense. But I cannot find any resources that confirm this.
functions elementary-set-theory
functions elementary-set-theory
asked Jan 30 at 18:35
Matthew RileyMatthew Riley
896
asked Jan 30 at 18:35
Matthew RileyMatthew Riley
896
asked Jan 30 at 18:35
Matthew RileyMatthew Riley
896
asked Jan 30 at 18:35
Matthew RileyMatthew Riley
896
asked Jan 30 at 18:35
Matthew RileyMatthew Riley
896
896
1
$begingroup$
It's a consequence of the pigeonhole principle.
$endgroup$
– Michael Burr
Jan 30 at 18:41
add a comment |
1
$begingroup$
It's a consequence of the pigeonhole principle.
$endgroup$
– Michael Burr
Jan 30 at 18:41
1
1
$begingroup$
It's a consequence of the pigeonhole principle.
$endgroup$
– Michael Burr
Jan 30 at 18:41
$begingroup$
It's a consequence of the pigeonhole principle.
$endgroup$
– Michael Burr
Jan 30 at 18:41
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Yes. If it wasn't injective, there would be $a_1ne a_2$ with the same image $b_0$, and then $|A|ge |B|+1$ would hold, as we can choose at least one preimage for each $b$ and at least two for $b_0$, all different.
answered Jan 30 at 18:38
BerciBerci
61.9k23776
$endgroup$
add a comment |
$begingroup$
For finite sets it indeed holds. Let $n = |A| = |B|$. If it was true that for some $x,yin A$ we have $xneq y$, but $f(x) = f(y)$, we would be left with only $n-2$ elements of $A$ ( that is $A$/{$x,y$} ) and with $n-1$ elements of $B$ ( that is $B$/{$f(x)$} = $B$/{$f$($y$)} ) they need to go to, so it would be impossible for $f$ to be surjective.
answered Jan 30 at 18:42
Jakub AndruszkiewiczJakub Andruszkiewicz
2116
$endgroup$
add a comment |
$begingroup$
If $A$ and $B$ are finite and $|A| = |B|$ then means that $A$ and $B$ have some finite number, call it $n$, elements.
If $f:Ato B$ is surjerctive then if $x in B$ then there is a $y$ so that $f(x) =y$. If we remove $x$ from $B$ to get $B' = Bsetminus {x}$ and if we remove $y$ from $A$ to get $A' = Asetminus{x}$. ANd $A'$ and $B'$ both have $n-1$ elements.
If we take $z in B'$ then there is a $w in A$ so that $f(w) = z$. But $w ne x$ because $f(x) = y ne z$. SO $w in A'$. We repeat the procedure all over again.
After we do this $n$ times we will end up going through all the elements of each set and demonstrating that each of the element of $A$ goes to a different element of $B$.
So $f$ is injective.
Two things to note. One, that sets be finite is absolutely essential. We needed the process to end.
But another is that this is sound and complete but complete unrigorous and informal. At this point, I think most mathematicians would tsk-tsk, explain the necessary virtues of rigour and set you on the rigorous pathway of righteousness.
I'm going to take a slightly different stance and say that the purpose of rigor is to define things coherently.
The very first statement I made that wasn't rigorous was when I said "$A$ and $B$ both have $n$ elements". What does that mean and how do we know if something as $n$ elements? If you had a plate of fish and said you had $5$ fish what does that mean and how do you know? Well, you'd just count them! Right.
And that really is what all the complicated definition of "Finite means there is a bijection between the set $mathbb N_n = {1,...,n}$ for some $j$ and the set $A$... " all means. It means, nothing more or less than "you can count the elements and there are $n$ elements". YOu count by make the bijection.
And a rigorous proof is just a matter of making the above argument in terms of that definition "there are $n$ elements".
answered Jan 30 at 19:16
fleabloodfleablood
73.8k22891
$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%2f3093930%2fwhen-does-surjectivity-imply-injectivity%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Yes. If it wasn't injective, there would be $a_1ne a_2$ with the same image $b_0$, and then $|A|ge |B|+1$ would hold, as we can choose at least one preimage for each $b$ and at least two for $b_0$, all different.
answered Jan 30 at 18:38
BerciBerci
61.9k23776
$endgroup$
add a comment |
$begingroup$
Yes. If it wasn't injective, there would be $a_1ne a_2$ with the same image $b_0$, and then $|A|ge |B|+1$ would hold, as we can choose at least one preimage for each $b$ and at least two for $b_0$, all different.
answered Jan 30 at 18:38
BerciBerci
61.9k23776
$endgroup$
add a comment |
$begingroup$
Yes. If it wasn't injective, there would be $a_1ne a_2$ with the same image $b_0$, and then $|A|ge |B|+1$ would hold, as we can choose at least one preimage for each $b$ and at least two for $b_0$, all different.
answered Jan 30 at 18:38
BerciBerci
61.9k23776
$endgroup$
Yes. If it wasn't injective, there would be $a_1ne a_2$ with the same image $b_0$, and then $|A|ge |B|+1$ would hold, as we can choose at least one preimage for each $b$ and at least two for $b_0$, all different.
answered Jan 30 at 18:38
BerciBerci
61.9k23776
answered Jan 30 at 18:38
BerciBerci
61.9k23776
answered Jan 30 at 18:38
BerciBerci
61.9k23776
answered Jan 30 at 18:38
BerciBerci
61.9k23776
61.9k23776
add a comment |
add a comment |
$begingroup$
For finite sets it indeed holds. Let $n = |A| = |B|$. If it was true that for some $x,yin A$ we have $xneq y$, but $f(x) = f(y)$, we would be left with only $n-2$ elements of $A$ ( that is $A$/{$x,y$} ) and with $n-1$ elements of $B$ ( that is $B$/{$f(x)$} = $B$/{$f$($y$)} ) they need to go to, so it would be impossible for $f$ to be surjective.
answered Jan 30 at 18:42
Jakub AndruszkiewiczJakub Andruszkiewicz
2116
$endgroup$
add a comment |
$begingroup$
For finite sets it indeed holds. Let $n = |A| = |B|$. If it was true that for some $x,yin A$ we have $xneq y$, but $f(x) = f(y)$, we would be left with only $n-2$ elements of $A$ ( that is $A$/{$x,y$} ) and with $n-1$ elements of $B$ ( that is $B$/{$f(x)$} = $B$/{$f$($y$)} ) they need to go to, so it would be impossible for $f$ to be surjective.
answered Jan 30 at 18:42
Jakub AndruszkiewiczJakub Andruszkiewicz
2116
$endgroup$
add a comment |
$begingroup$
For finite sets it indeed holds. Let $n = |A| = |B|$. If it was true that for some $x,yin A$ we have $xneq y$, but $f(x) = f(y)$, we would be left with only $n-2$ elements of $A$ ( that is $A$/{$x,y$} ) and with $n-1$ elements of $B$ ( that is $B$/{$f(x)$} = $B$/{$f$($y$)} ) they need to go to, so it would be impossible for $f$ to be surjective.
answered Jan 30 at 18:42
Jakub AndruszkiewiczJakub Andruszkiewicz
2116
$endgroup$
For finite sets it indeed holds. Let $n = |A| = |B|$. If it was true that for some $x,yin A$ we have $xneq y$, but $f(x) = f(y)$, we would be left with only $n-2$ elements of $A$ ( that is $A$/{$x,y$} ) and with $n-1$ elements of $B$ ( that is $B$/{$f(x)$} = $B$/{$f$($y$)} ) they need to go to, so it would be impossible for $f$ to be surjective.
answered Jan 30 at 18:42
Jakub AndruszkiewiczJakub Andruszkiewicz
2116
answered Jan 30 at 18:42
Jakub AndruszkiewiczJakub Andruszkiewicz
2116
answered Jan 30 at 18:42
Jakub AndruszkiewiczJakub Andruszkiewicz
2116
answered Jan 30 at 18:42
Jakub AndruszkiewiczJakub Andruszkiewicz
2116
2116
add a comment |
add a comment |
$begingroup$
If $A$ and $B$ are finite and $|A| = |B|$ then means that $A$ and $B$ have some finite number, call it $n$, elements.
If $f:Ato B$ is surjerctive then if $x in B$ then there is a $y$ so that $f(x) =y$. If we remove $x$ from $B$ to get $B' = Bsetminus {x}$ and if we remove $y$ from $A$ to get $A' = Asetminus{x}$. ANd $A'$ and $B'$ both have $n-1$ elements.
If we take $z in B'$ then there is a $w in A$ so that $f(w) = z$. But $w ne x$ because $f(x) = y ne z$. SO $w in A'$. We repeat the procedure all over again.
After we do this $n$ times we will end up going through all the elements of each set and demonstrating that each of the element of $A$ goes to a different element of $B$.
So $f$ is injective.
Two things to note. One, that sets be finite is absolutely essential. We needed the process to end.
But another is that this is sound and complete but complete unrigorous and informal. At this point, I think most mathematicians would tsk-tsk, explain the necessary virtues of rigour and set you on the rigorous pathway of righteousness.
I'm going to take a slightly different stance and say that the purpose of rigor is to define things coherently.
The very first statement I made that wasn't rigorous was when I said "$A$ and $B$ both have $n$ elements". What does that mean and how do we know if something as $n$ elements? If you had a plate of fish and said you had $5$ fish what does that mean and how do you know? Well, you'd just count them! Right.
And that really is what all the complicated definition of "Finite means there is a bijection between the set $mathbb N_n = {1,...,n}$ for some $j$ and the set $A$... " all means. It means, nothing more or less than "you can count the elements and there are $n$ elements". YOu count by make the bijection.
And a rigorous proof is just a matter of making the above argument in terms of that definition "there are $n$ elements".
answered Jan 30 at 19:16
fleabloodfleablood
73.8k22891
$endgroup$
add a comment |
$begingroup$
If $A$ and $B$ are finite and $|A| = |B|$ then means that $A$ and $B$ have some finite number, call it $n$, elements.
If $f:Ato B$ is surjerctive then if $x in B$ then there is a $y$ so that $f(x) =y$. If we remove $x$ from $B$ to get $B' = Bsetminus {x}$ and if we remove $y$ from $A$ to get $A' = Asetminus{x}$. ANd $A'$ and $B'$ both have $n-1$ elements.
If we take $z in B'$ then there is a $w in A$ so that $f(w) = z$. But $w ne x$ because $f(x) = y ne z$. SO $w in A'$. We repeat the procedure all over again.
After we do this $n$ times we will end up going through all the elements of each set and demonstrating that each of the element of $A$ goes to a different element of $B$.
So $f$ is injective.
Two things to note. One, that sets be finite is absolutely essential. We needed the process to end.
But another is that this is sound and complete but complete unrigorous and informal. At this point, I think most mathematicians would tsk-tsk, explain the necessary virtues of rigour and set you on the rigorous pathway of righteousness.
I'm going to take a slightly different stance and say that the purpose of rigor is to define things coherently.
The very first statement I made that wasn't rigorous was when I said "$A$ and $B$ both have $n$ elements". What does that mean and how do we know if something as $n$ elements? If you had a plate of fish and said you had $5$ fish what does that mean and how do you know? Well, you'd just count them! Right.
And that really is what all the complicated definition of "Finite means there is a bijection between the set $mathbb N_n = {1,...,n}$ for some $j$ and the set $A$... " all means. It means, nothing more or less than "you can count the elements and there are $n$ elements". YOu count by make the bijection.
And a rigorous proof is just a matter of making the above argument in terms of that definition "there are $n$ elements".
answered Jan 30 at 19:16
fleabloodfleablood
73.8k22891
$endgroup$
add a comment |
$begingroup$
If $A$ and $B$ are finite and $|A| = |B|$ then means that $A$ and $B$ have some finite number, call it $n$, elements.
If $f:Ato B$ is surjerctive then if $x in B$ then there is a $y$ so that $f(x) =y$. If we remove $x$ from $B$ to get $B' = Bsetminus {x}$ and if we remove $y$ from $A$ to get $A' = Asetminus{x}$. ANd $A'$ and $B'$ both have $n-1$ elements.
If we take $z in B'$ then there is a $w in A$ so that $f(w) = z$. But $w ne x$ because $f(x) = y ne z$. SO $w in A'$. We repeat the procedure all over again.
After we do this $n$ times we will end up going through all the elements of each set and demonstrating that each of the element of $A$ goes to a different element of $B$.
So $f$ is injective.
Two things to note. One, that sets be finite is absolutely essential. We needed the process to end.
But another is that this is sound and complete but complete unrigorous and informal. At this point, I think most mathematicians would tsk-tsk, explain the necessary virtues of rigour and set you on the rigorous pathway of righteousness.
I'm going to take a slightly different stance and say that the purpose of rigor is to define things coherently.
The very first statement I made that wasn't rigorous was when I said "$A$ and $B$ both have $n$ elements". What does that mean and how do we know if something as $n$ elements? If you had a plate of fish and said you had $5$ fish what does that mean and how do you know? Well, you'd just count them! Right.
And that really is what all the complicated definition of "Finite means there is a bijection between the set $mathbb N_n = {1,...,n}$ for some $j$ and the set $A$... " all means. It means, nothing more or less than "you can count the elements and there are $n$ elements". YOu count by make the bijection.
And a rigorous proof is just a matter of making the above argument in terms of that definition "there are $n$ elements".
answered Jan 30 at 19:16
fleabloodfleablood
73.8k22891
$endgroup$
If $A$ and $B$ are finite and $|A| = |B|$ then means that $A$ and $B$ have some finite number, call it $n$, elements.
If $f:Ato B$ is surjerctive then if $x in B$ then there is a $y$ so that $f(x) =y$. If we remove $x$ from $B$ to get $B' = Bsetminus {x}$ and if we remove $y$ from $A$ to get $A' = Asetminus{x}$. ANd $A'$ and $B'$ both have $n-1$ elements.
If we take $z in B'$ then there is a $w in A$ so that $f(w) = z$. But $w ne x$ because $f(x) = y ne z$. SO $w in A'$. We repeat the procedure all over again.
After we do this $n$ times we will end up going through all the elements of each set and demonstrating that each of the element of $A$ goes to a different element of $B$.
So $f$ is injective.
Two things to note. One, that sets be finite is absolutely essential. We needed the process to end.
But another is that this is sound and complete but complete unrigorous and informal. At this point, I think most mathematicians would tsk-tsk, explain the necessary virtues of rigour and set you on the rigorous pathway of righteousness.
I'm going to take a slightly different stance and say that the purpose of rigor is to define things coherently.
The very first statement I made that wasn't rigorous was when I said "$A$ and $B$ both have $n$ elements". What does that mean and how do we know if something as $n$ elements? If you had a plate of fish and said you had $5$ fish what does that mean and how do you know? Well, you'd just count them! Right.
And that really is what all the complicated definition of "Finite means there is a bijection between the set $mathbb N_n = {1,...,n}$ for some $j$ and the set $A$... " all means. It means, nothing more or less than "you can count the elements and there are $n$ elements". YOu count by make the bijection.
And a rigorous proof is just a matter of making the above argument in terms of that definition "there are $n$ elements".
answered Jan 30 at 19:16
fleabloodfleablood
73.8k22891
answered Jan 30 at 19:16
fleabloodfleablood
73.8k22891
answered Jan 30 at 19:16
fleabloodfleablood
73.8k22891
answered Jan 30 at 19:16
fleabloodfleablood
73.8k22891
73.8k22891
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%2f3093930%2fwhen-does-surjectivity-imply-injectivity%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
1
$begingroup$
It's a consequence of the pigeonhole principle.
$endgroup$
– Michael Burr
Jan 30 at 18:41