Mixing
Question on injective-surjective functions, regarding cardinality of domain, codomain
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Ok so we know that if A, B are finite sets and f: A to B is injective, then cardinality(A)≤cardinality(B),
and that the opposite inequality holds for a surjection. My question is, if we know that f is not injective, can we assume that cardinality(A)>cardinality(B)
(and similarly for a surjection)? I'm asking this because I need to prove that there is no f:A to A that is either (injective but not surjective) or (surjective but not injective), with A finite. Thanks! (Sorry for my bad typing, I can't figure out how to use the symbols)
functions cardinals
asked 5 hours ago
JBuck
263
add a comment |Â
up vote
2
down vote
favorite
Ok so we know that if A, B are finite sets and f: A to B is injective, then cardinality(A)≤cardinality(B),
and that the opposite inequality holds for a surjection. My question is, if we know that f is not injective, can we assume that cardinality(A)>cardinality(B)
(and similarly for a surjection)? I'm asking this because I need to prove that there is no f:A to A that is either (injective but not surjective) or (surjective but not injective), with A finite. Thanks! (Sorry for my bad typing, I can't figure out how to use the symbols)
functions cardinals
asked 5 hours ago
JBuck
263
1
Regarding about how to use symbols, just add$...$, where...means "any math expression". Search for MathJax to see some common commands.
– manooooh
5 hours ago
1
For what you are trying to prove, given $f$ is injective from $A$ to $A$, then $f$ is a bijection from $A$ to Range($f$), so Range($f$) is a subset of $A$ with the same cardinality as $A$. Since $A$ is finite, ....
– Ned
5 hours ago
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Ok so we know that if A, B are finite sets and f: A to B is injective, then cardinality(A)≤cardinality(B),
and that the opposite inequality holds for a surjection. My question is, if we know that f is not injective, can we assume that cardinality(A)>cardinality(B)
(and similarly for a surjection)? I'm asking this because I need to prove that there is no f:A to A that is either (injective but not surjective) or (surjective but not injective), with A finite. Thanks! (Sorry for my bad typing, I can't figure out how to use the symbols)
functions cardinals
asked 5 hours ago
JBuck
263
Ok so we know that if A, B are finite sets and f: A to B is injective, then cardinality(A)≤cardinality(B),
and that the opposite inequality holds for a surjection. My question is, if we know that f is not injective, can we assume that cardinality(A)>cardinality(B)
(and similarly for a surjection)? I'm asking this because I need to prove that there is no f:A to A that is either (injective but not surjective) or (surjective but not injective), with A finite. Thanks! (Sorry for my bad typing, I can't figure out how to use the symbols)
functions cardinals
functions cardinals
asked 5 hours ago
JBuck
263
asked 5 hours ago
JBuck
263
asked 5 hours ago
JBuck
263
asked 5 hours ago
JBuck
263
asked 5 hours ago
JBuck
263
263
1
Regarding about how to use symbols, just add$...$, where...means "any math expression". Search for MathJax to see some common commands.
– manooooh
5 hours ago
1
For what you are trying to prove, given $f$ is injective from $A$ to $A$, then $f$ is a bijection from $A$ to Range($f$), so Range($f$) is a subset of $A$ with the same cardinality as $A$. Since $A$ is finite, ....
– Ned
5 hours ago
add a comment |Â
1
Regarding about how to use symbols, just add$...$, where...means "any math expression". Search for MathJax to see some common commands.
– manooooh
5 hours ago
1
For what you are trying to prove, given $f$ is injective from $A$ to $A$, then $f$ is a bijection from $A$ to Range($f$), so Range($f$) is a subset of $A$ with the same cardinality as $A$. Since $A$ is finite, ....
– Ned
5 hours ago
1
1
Regarding about how to use symbols, just add
$...$, where ... means "any math expression". Search for MathJax to see some common commands.– manooooh
5 hours ago
Regarding about how to use symbols, just add
$...$, where ... means "any math expression". Search for MathJax to see some common commands.– manooooh
5 hours ago
1
1
For what you are trying to prove, given $f$ is injective from $A$ to $A$, then $f$ is a bijection from $A$ to Range($f$), so Range($f$) is a subset of $A$ with the same cardinality as $A$. Since $A$ is finite, ....
– Ned
5 hours ago
For what you are trying to prove, given $f$ is injective from $A$ to $A$, then $f$ is a bijection from $A$ to Range($f$), so Range($f$) is a subset of $A$ with the same cardinality as $A$. Since $A$ is finite, ....
– Ned
5 hours ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
Nope. Let $X=mathbbR$ and $Y=mathbbZ$ $|mathbbZ| < |mathbbR|$. Consider the function $f:X to Y$ defined $f(x)=1$ for all $x$. This map is not injective, but, as stated, $|X|<|Y|$.
If you want an example with finite sets $X=1,2,3$ and $Y=1,2,3,4,5,6,7,8,9$ and define the same map. The same issue arises. It is similar when a map fails to be surjective.
As a hint for your problem. Suppose $f:A to A$ is injective but surjective. So there is in $a in A$ which does not have a partner. But what happens to $f(a)$?. The idea is similar for the surjective case.
answered 5 hours ago
RhythmInk
1,036420
Yeah I see, I should have noticed that before. Thanks!
– JBuck
5 hours ago
1
No problem. This stuff can be funny at first.
– RhythmInk
5 hours ago
2
If $Y=Z$ how is $f(x)=1$ is a function from $Bbb R$ into $Y$? Unless, $Z=1$.
– Asaf Karagila♦
5 hours ago
1
Just a mistake in notation. All fixed.
– RhythmInk
5 hours ago
1
Please upvote/accept answer if this is what you were looking for.
– RhythmInk
5 hours ago
add a comment |Â
up vote
2
down vote
Unfortunately, knowing that you have a non-injective function $f$ from $A$ to $B$ doesn't tell you that $|A| > |B|$. For a counterexample with finite sets, consider the function
$f : 1, 2, 3 rightarrow 1, 2, 3, 4$
defined by:
$f(x) = 1, forall x in 1,2,3$.
This function is not injective, since $f(1) = f(2) = f(3)$, but $1 neq 2$, $2 neq 3$, and $1 neq 3$, but $|1,2,3| < |1,2,3,4|$.
A good point to keep in mind when thinking about questions like this is that for most sets $A$ and $B$, there are many different possible functions from $A$ to $B$. Just because you have one particular function from $A$ to $B$ that isn't injective, doesn't mean that no function from $A$ to $B$ is injective. In the above example, we can see that while $f$ is not injective, we can define $g : 1, 2, 3 rightarrow 1, 2, 3, 4$ by $g(x) = x$, and $g$ is in fact injective, showing that $|1,2,3| leq |1,2,3,4|$.
I hope this helps!
answered 4 hours ago
Eli.Orvis
685
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Nope. Let $X=mathbbR$ and $Y=mathbbZ$ $|mathbbZ| < |mathbbR|$. Consider the function $f:X to Y$ defined $f(x)=1$ for all $x$. This map is not injective, but, as stated, $|X|<|Y|$.
If you want an example with finite sets $X=1,2,3$ and $Y=1,2,3,4,5,6,7,8,9$ and define the same map. The same issue arises. It is similar when a map fails to be surjective.
As a hint for your problem. Suppose $f:A to A$ is injective but surjective. So there is in $a in A$ which does not have a partner. But what happens to $f(a)$?. The idea is similar for the surjective case.
answered 5 hours ago
RhythmInk
1,036420
Yeah I see, I should have noticed that before. Thanks!
– JBuck
5 hours ago
1
No problem. This stuff can be funny at first.
– RhythmInk
5 hours ago
2
If $Y=Z$ how is $f(x)=1$ is a function from $Bbb R$ into $Y$? Unless, $Z=1$.
– Asaf Karagila♦
5 hours ago
1
Just a mistake in notation. All fixed.
– RhythmInk
5 hours ago
1
Please upvote/accept answer if this is what you were looking for.
– RhythmInk
5 hours ago
add a comment |Â
up vote
2
down vote
Nope. Let $X=mathbbR$ and $Y=mathbbZ$ $|mathbbZ| < |mathbbR|$. Consider the function $f:X to Y$ defined $f(x)=1$ for all $x$. This map is not injective, but, as stated, $|X|<|Y|$.
If you want an example with finite sets $X=1,2,3$ and $Y=1,2,3,4,5,6,7,8,9$ and define the same map. The same issue arises. It is similar when a map fails to be surjective.
As a hint for your problem. Suppose $f:A to A$ is injective but surjective. So there is in $a in A$ which does not have a partner. But what happens to $f(a)$?. The idea is similar for the surjective case.
answered 5 hours ago
RhythmInk
1,036420
Yeah I see, I should have noticed that before. Thanks!
– JBuck
5 hours ago
1
No problem. This stuff can be funny at first.
– RhythmInk
5 hours ago
2
If $Y=Z$ how is $f(x)=1$ is a function from $Bbb R$ into $Y$? Unless, $Z=1$.
– Asaf Karagila♦
5 hours ago
1
Just a mistake in notation. All fixed.
– RhythmInk
5 hours ago
1
Please upvote/accept answer if this is what you were looking for.
– RhythmInk
5 hours ago
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Nope. Let $X=mathbbR$ and $Y=mathbbZ$ $|mathbbZ| < |mathbbR|$. Consider the function $f:X to Y$ defined $f(x)=1$ for all $x$. This map is not injective, but, as stated, $|X|<|Y|$.
If you want an example with finite sets $X=1,2,3$ and $Y=1,2,3,4,5,6,7,8,9$ and define the same map. The same issue arises. It is similar when a map fails to be surjective.
As a hint for your problem. Suppose $f:A to A$ is injective but surjective. So there is in $a in A$ which does not have a partner. But what happens to $f(a)$?. The idea is similar for the surjective case.
answered 5 hours ago
RhythmInk
1,036420
Nope. Let $X=mathbbR$ and $Y=mathbbZ$ $|mathbbZ| < |mathbbR|$. Consider the function $f:X to Y$ defined $f(x)=1$ for all $x$. This map is not injective, but, as stated, $|X|<|Y|$.
If you want an example with finite sets $X=1,2,3$ and $Y=1,2,3,4,5,6,7,8,9$ and define the same map. The same issue arises. It is similar when a map fails to be surjective.
As a hint for your problem. Suppose $f:A to A$ is injective but surjective. So there is in $a in A$ which does not have a partner. But what happens to $f(a)$?. The idea is similar for the surjective case.
answered 5 hours ago
RhythmInk
1,036420
edited 5 hours ago
answered 5 hours ago
RhythmInk
1,036420
answered 5 hours ago
RhythmInk
1,036420
answered 5 hours ago
RhythmInk
1,036420
1,036420
Yeah I see, I should have noticed that before. Thanks!
– JBuck
5 hours ago
1
No problem. This stuff can be funny at first.
– RhythmInk
5 hours ago
2
If $Y=Z$ how is $f(x)=1$ is a function from $Bbb R$ into $Y$? Unless, $Z=1$.
– Asaf Karagila♦
5 hours ago
1
Just a mistake in notation. All fixed.
– RhythmInk
5 hours ago
1
Please upvote/accept answer if this is what you were looking for.
– RhythmInk
5 hours ago
add a comment |Â
Yeah I see, I should have noticed that before. Thanks!
– JBuck
5 hours ago
1
No problem. This stuff can be funny at first.
– RhythmInk
5 hours ago
2
If $Y=Z$ how is $f(x)=1$ is a function from $Bbb R$ into $Y$? Unless, $Z=1$.
– Asaf Karagila♦
5 hours ago
1
Just a mistake in notation. All fixed.
– RhythmInk
5 hours ago
1
Please upvote/accept answer if this is what you were looking for.
– RhythmInk
5 hours ago
Yeah I see, I should have noticed that before. Thanks!
– JBuck
5 hours ago
Yeah I see, I should have noticed that before. Thanks!
– JBuck
5 hours ago
1
1
No problem. This stuff can be funny at first.
– RhythmInk
5 hours ago
No problem. This stuff can be funny at first.
– RhythmInk
5 hours ago
2
2
If $Y=Z$ how is $f(x)=1$ is a function from $Bbb R$ into $Y$? Unless, $Z=1$.
– Asaf Karagila♦
5 hours ago
If $Y=Z$ how is $f(x)=1$ is a function from $Bbb R$ into $Y$? Unless, $Z=1$.
– Asaf Karagila♦
5 hours ago
1
1
Just a mistake in notation. All fixed.
– RhythmInk
5 hours ago
Just a mistake in notation. All fixed.
– RhythmInk
5 hours ago
1
1
Please upvote/accept answer if this is what you were looking for.
– RhythmInk
5 hours ago
Please upvote/accept answer if this is what you were looking for.
– RhythmInk
5 hours ago
add a comment |Â
up vote
2
down vote
Unfortunately, knowing that you have a non-injective function $f$ from $A$ to $B$ doesn't tell you that $|A| > |B|$. For a counterexample with finite sets, consider the function
$f : 1, 2, 3 rightarrow 1, 2, 3, 4$
defined by:
$f(x) = 1, forall x in 1,2,3$.
This function is not injective, since $f(1) = f(2) = f(3)$, but $1 neq 2$, $2 neq 3$, and $1 neq 3$, but $|1,2,3| < |1,2,3,4|$.
A good point to keep in mind when thinking about questions like this is that for most sets $A$ and $B$, there are many different possible functions from $A$ to $B$. Just because you have one particular function from $A$ to $B$ that isn't injective, doesn't mean that no function from $A$ to $B$ is injective. In the above example, we can see that while $f$ is not injective, we can define $g : 1, 2, 3 rightarrow 1, 2, 3, 4$ by $g(x) = x$, and $g$ is in fact injective, showing that $|1,2,3| leq |1,2,3,4|$.
I hope this helps!
answered 4 hours ago
Eli.Orvis
685
add a comment |Â
up vote
2
down vote
Unfortunately, knowing that you have a non-injective function $f$ from $A$ to $B$ doesn't tell you that $|A| > |B|$. For a counterexample with finite sets, consider the function
$f : 1, 2, 3 rightarrow 1, 2, 3, 4$
defined by:
$f(x) = 1, forall x in 1,2,3$.
This function is not injective, since $f(1) = f(2) = f(3)$, but $1 neq 2$, $2 neq 3$, and $1 neq 3$, but $|1,2,3| < |1,2,3,4|$.
A good point to keep in mind when thinking about questions like this is that for most sets $A$ and $B$, there are many different possible functions from $A$ to $B$. Just because you have one particular function from $A$ to $B$ that isn't injective, doesn't mean that no function from $A$ to $B$ is injective. In the above example, we can see that while $f$ is not injective, we can define $g : 1, 2, 3 rightarrow 1, 2, 3, 4$ by $g(x) = x$, and $g$ is in fact injective, showing that $|1,2,3| leq |1,2,3,4|$.
I hope this helps!
answered 4 hours ago
Eli.Orvis
685
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Unfortunately, knowing that you have a non-injective function $f$ from $A$ to $B$ doesn't tell you that $|A| > |B|$. For a counterexample with finite sets, consider the function
$f : 1, 2, 3 rightarrow 1, 2, 3, 4$
defined by:
$f(x) = 1, forall x in 1,2,3$.
This function is not injective, since $f(1) = f(2) = f(3)$, but $1 neq 2$, $2 neq 3$, and $1 neq 3$, but $|1,2,3| < |1,2,3,4|$.
A good point to keep in mind when thinking about questions like this is that for most sets $A$ and $B$, there are many different possible functions from $A$ to $B$. Just because you have one particular function from $A$ to $B$ that isn't injective, doesn't mean that no function from $A$ to $B$ is injective. In the above example, we can see that while $f$ is not injective, we can define $g : 1, 2, 3 rightarrow 1, 2, 3, 4$ by $g(x) = x$, and $g$ is in fact injective, showing that $|1,2,3| leq |1,2,3,4|$.
I hope this helps!
answered 4 hours ago
Eli.Orvis
685
Unfortunately, knowing that you have a non-injective function $f$ from $A$ to $B$ doesn't tell you that $|A| > |B|$. For a counterexample with finite sets, consider the function
$f : 1, 2, 3 rightarrow 1, 2, 3, 4$
defined by:
$f(x) = 1, forall x in 1,2,3$.
This function is not injective, since $f(1) = f(2) = f(3)$, but $1 neq 2$, $2 neq 3$, and $1 neq 3$, but $|1,2,3| < |1,2,3,4|$.
A good point to keep in mind when thinking about questions like this is that for most sets $A$ and $B$, there are many different possible functions from $A$ to $B$. Just because you have one particular function from $A$ to $B$ that isn't injective, doesn't mean that no function from $A$ to $B$ is injective. In the above example, we can see that while $f$ is not injective, we can define $g : 1, 2, 3 rightarrow 1, 2, 3, 4$ by $g(x) = x$, and $g$ is in fact injective, showing that $|1,2,3| leq |1,2,3,4|$.
I hope this helps!
answered 4 hours ago
Eli.Orvis
685
answered 4 hours ago
Eli.Orvis
685
answered 4 hours ago
Eli.Orvis
685
answered 4 hours ago
Eli.Orvis
685
685
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2964991%2fquestion-on-injective-surjective-functions-regarding-cardinality-of-domain-cod%23new-answer', 'question_page');
);
Post as a guest
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
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
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
1
Regarding about how to use symbols, just add
$...$, where...means "any math expression". Search for MathJax to see some common commands.– manooooh
5 hours ago
1
For what you are trying to prove, given $f$ is injective from $A$ to $A$, then $f$ is a bijection from $A$ to Range($f$), so Range($f$) is a subset of $A$ with the same cardinality as $A$. Since $A$ is finite, ....
– Ned
5 hours ago