Mixing
Let $f:A to B$ and $phi: C^B to C^A$ be applications, prove: if $f$ is injective then $ phi$ is surjective
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I am struggling with this quite simple problem:
Let $A$, $B$ and $C$ be sets ($neq emptyset$) and let $f:A to B$ be a fixed application. Let be $C^A=h:A to C $ and $C^B=g$. Let $phi: C^B to C^A$ be the application s.t. $phi(g)=g circ f, forall gin C^B$.
Prove: if $f$ is surjective then $phi$ is injective; if $f$ is injective then $phi$ is surjective.
For the first one I think this solution could be good:
Let $f$ be surjective then $exists h:B to A$ s.t.$f circ h = iota_B$.
Let $g_1, g_2 in C^B$ be s.t $phi (g_1) = phi (g_2)$ (that implies $g_1 circ f = g_2 circ f$). So: $g_1 =g_1circ iota_B=g_1 circ (f circ h)= (g_1 circ f) circ h =(g_2 circ f) circ h = g_2 circ (f circ h) = g_2 circ iota_B = g_2$
How to prove that if $f$ is injective $Rightarrow phi$ is surjective? I thought: if $f$ is injective then $exists h:B to A$ s.t. $h circ f= iota_A$ and that if $g$ is surjective then $phi(g) =g circ f$ is surjective, but how to correlate them?
algebra-precalculus functions
edited Jul 15 at 9:33
Pece
7,92211040
asked Jul 15 at 7:52
Arcticmonkey
8710
add a comment |Â
up vote
1
down vote
favorite
I am struggling with this quite simple problem:
Let $A$, $B$ and $C$ be sets ($neq emptyset$) and let $f:A to B$ be a fixed application. Let be $C^A=h:A to C $ and $C^B=g$. Let $phi: C^B to C^A$ be the application s.t. $phi(g)=g circ f, forall gin C^B$.
Prove: if $f$ is surjective then $phi$ is injective; if $f$ is injective then $phi$ is surjective.
For the first one I think this solution could be good:
Let $f$ be surjective then $exists h:B to A$ s.t.$f circ h = iota_B$.
Let $g_1, g_2 in C^B$ be s.t $phi (g_1) = phi (g_2)$ (that implies $g_1 circ f = g_2 circ f$). So: $g_1 =g_1circ iota_B=g_1 circ (f circ h)= (g_1 circ f) circ h =(g_2 circ f) circ h = g_2 circ (f circ h) = g_2 circ iota_B = g_2$
How to prove that if $f$ is injective $Rightarrow phi$ is surjective? I thought: if $f$ is injective then $exists h:B to A$ s.t. $h circ f= iota_A$ and that if $g$ is surjective then $phi(g) =g circ f$ is surjective, but how to correlate them?
algebra-precalculus functions
edited Jul 15 at 9:33
Pece
7,92211040
asked Jul 15 at 7:52
Arcticmonkey
8710
3
Do you mean $phi:C^Bto C^A$?
– Lord Shark the Unknown
Jul 15 at 7:56
1
$Rightarrow$ isn't an abbreviation for "then",
– paf
Jul 15 at 8:18
@LordSharktheUnknown yes! Apologize me for that mistake.
– Arcticmonkey
Jul 15 at 8:29
@paf just edited
– Arcticmonkey
Jul 15 at 8:30
What if $|C|=1$?
– Lord Shark the Unknown
Jul 15 at 8:33
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I am struggling with this quite simple problem:
Let $A$, $B$ and $C$ be sets ($neq emptyset$) and let $f:A to B$ be a fixed application. Let be $C^A=h:A to C $ and $C^B=g$. Let $phi: C^B to C^A$ be the application s.t. $phi(g)=g circ f, forall gin C^B$.
Prove: if $f$ is surjective then $phi$ is injective; if $f$ is injective then $phi$ is surjective.
For the first one I think this solution could be good:
Let $f$ be surjective then $exists h:B to A$ s.t.$f circ h = iota_B$.
Let $g_1, g_2 in C^B$ be s.t $phi (g_1) = phi (g_2)$ (that implies $g_1 circ f = g_2 circ f$). So: $g_1 =g_1circ iota_B=g_1 circ (f circ h)= (g_1 circ f) circ h =(g_2 circ f) circ h = g_2 circ (f circ h) = g_2 circ iota_B = g_2$
How to prove that if $f$ is injective $Rightarrow phi$ is surjective? I thought: if $f$ is injective then $exists h:B to A$ s.t. $h circ f= iota_A$ and that if $g$ is surjective then $phi(g) =g circ f$ is surjective, but how to correlate them?
algebra-precalculus functions
edited Jul 15 at 9:33
Pece
7,92211040
asked Jul 15 at 7:52
Arcticmonkey
8710
I am struggling with this quite simple problem:
Let $A$, $B$ and $C$ be sets ($neq emptyset$) and let $f:A to B$ be a fixed application. Let be $C^A=h:A to C $ and $C^B=g$. Let $phi: C^B to C^A$ be the application s.t. $phi(g)=g circ f, forall gin C^B$.
Prove: if $f$ is surjective then $phi$ is injective; if $f$ is injective then $phi$ is surjective.
For the first one I think this solution could be good:
Let $f$ be surjective then $exists h:B to A$ s.t.$f circ h = iota_B$.
Let $g_1, g_2 in C^B$ be s.t $phi (g_1) = phi (g_2)$ (that implies $g_1 circ f = g_2 circ f$). So: $g_1 =g_1circ iota_B=g_1 circ (f circ h)= (g_1 circ f) circ h =(g_2 circ f) circ h = g_2 circ (f circ h) = g_2 circ iota_B = g_2$
How to prove that if $f$ is injective $Rightarrow phi$ is surjective? I thought: if $f$ is injective then $exists h:B to A$ s.t. $h circ f= iota_A$ and that if $g$ is surjective then $phi(g) =g circ f$ is surjective, but how to correlate them?
algebra-precalculus functions
edited Jul 15 at 9:33
Pece
7,92211040
asked Jul 15 at 7:52
Arcticmonkey
8710
edited Jul 15 at 9:33
Pece
7,92211040
edited Jul 15 at 9:33
Pece
7,92211040
edited Jul 15 at 9:33
Pece
7,92211040
7,92211040
asked Jul 15 at 7:52
Arcticmonkey
8710
asked Jul 15 at 7:52
Arcticmonkey
8710
asked Jul 15 at 7:52
Arcticmonkey
8710
8710
3
Do you mean $phi:C^Bto C^A$?
– Lord Shark the Unknown
Jul 15 at 7:56
1
$Rightarrow$ isn't an abbreviation for "then",
– paf
Jul 15 at 8:18
@LordSharktheUnknown yes! Apologize me for that mistake.
– Arcticmonkey
Jul 15 at 8:29
@paf just edited
– Arcticmonkey
Jul 15 at 8:30
What if $|C|=1$?
– Lord Shark the Unknown
Jul 15 at 8:33
add a comment |Â
3
Do you mean $phi:C^Bto C^A$?
– Lord Shark the Unknown
Jul 15 at 7:56
1
$Rightarrow$ isn't an abbreviation for "then",
– paf
Jul 15 at 8:18
@LordSharktheUnknown yes! Apologize me for that mistake.
– Arcticmonkey
Jul 15 at 8:29
@paf just edited
– Arcticmonkey
Jul 15 at 8:30
What if $|C|=1$?
– Lord Shark the Unknown
Jul 15 at 8:33
3
3
Do you mean $phi:C^Bto C^A$?
– Lord Shark the Unknown
Jul 15 at 7:56
Do you mean $phi:C^Bto C^A$?
– Lord Shark the Unknown
Jul 15 at 7:56
1
1
$Rightarrow$ isn't an abbreviation for "then",
– paf
Jul 15 at 8:18
$Rightarrow$ isn't an abbreviation for "then",
– paf
Jul 15 at 8:18
@LordSharktheUnknown yes! Apologize me for that mistake.
– Arcticmonkey
Jul 15 at 8:29
@LordSharktheUnknown yes! Apologize me for that mistake.
– Arcticmonkey
Jul 15 at 8:29
@paf just edited
– Arcticmonkey
Jul 15 at 8:30
@paf just edited
– Arcticmonkey
Jul 15 at 8:30
What if $|C|=1$?
– Lord Shark the Unknown
Jul 15 at 8:33
What if $|C|=1$?
– Lord Shark the Unknown
Jul 15 at 8:33
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
As you said, if $f$ is injective, then there exists $h : B to A$ such that $h circ f = iota_A$. Given $g in C^A$, you see that $g circ h in C^B$ and $phi(g circ h) = g circ h circ f = g$.
Added:
Adayah has pointed out that we used $A ne emptyset$. But in fact the assumption in the question is $A, B, C ne emptyset$.
However, we can do everything under the assumption $C ne emptyset$ without any assumption on $A, B$. $A, B ne emptyset$ has been treated.
The empty set has the feature that there exists exactly one function $emptyset to X$, where $X$ is any set (the "empty" function $emptyset to X$), which btw is automatically injective.
The are exactly two cases in which one of $A, B$ is empty:
(1) $A = emptyset to B = emptyset$ which is bijective.
(2) $A = emptyset to B ne emptyset$ which is injective but not surjective.
Since $C^emptyset$ has exactly one element and $C^B$ is non-empty, we see that $phi$ is bijective in case (1) and surjective in case (2).
What if $C = emptyset$? If $A, B ne emptyset$, then $C^A , C^B = emptyset$ and $phi$ is a bijection. If $A = B = emptyset$, then $phi$ is also a bijection. Only in case $A = emptyset, B ne emptyset$ we see that $phi$ is not surjective although $f$ is injective.
answered Jul 15 at 8:42
Paul Frost
3,703420
2
Maybe I'm being overzealous, but stating the existence of $h : B to A$ we use the non-emptiness of $A$.
– Adayah
Jul 15 at 8:52
@Adayah I added a remark to my answer.
– Paul Frost
Jul 15 at 9:31
add a comment |Â
up vote
0
down vote
Suppose $f$ is injective and take $alphacolon Ato C$. You wish to find $betacolon Bto C$ such that $phi(beta)=alpha$, that is, $betacirc f=alpha$.
Since $f$ is injective, there exists $gcolon Bto A$ with $hcirc f=iota_A$. Take $beta=alphacirc h$. Then
$$
phi(beta)=betacirc f=alphacirc hcirc f=alphacirciota_A=alpha
$$
as required. In other words, the map $alphamapstoalphacirc h$ is a right inverse to $phi$, so $phi$ is surjective.
The same idea can be used for the other claim. If $f$ is surjective, there is $gcolon Bto A$ such that $fcirc g=iota_B$. If $betain C^B$, then
$$
beta=betacirciota_B=betacirc fcirc g=psi(phi(beta))
$$
where $psi$ is defined similarly to $phi$. Then $phi$ has a left inverse, so it is injective.
answered Jul 15 at 9:56
egreg
164k1180187
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
accepted
As you said, if $f$ is injective, then there exists $h : B to A$ such that $h circ f = iota_A$. Given $g in C^A$, you see that $g circ h in C^B$ and $phi(g circ h) = g circ h circ f = g$.
Added:
Adayah has pointed out that we used $A ne emptyset$. But in fact the assumption in the question is $A, B, C ne emptyset$.
However, we can do everything under the assumption $C ne emptyset$ without any assumption on $A, B$. $A, B ne emptyset$ has been treated.
The empty set has the feature that there exists exactly one function $emptyset to X$, where $X$ is any set (the "empty" function $emptyset to X$), which btw is automatically injective.
The are exactly two cases in which one of $A, B$ is empty:
(1) $A = emptyset to B = emptyset$ which is bijective.
(2) $A = emptyset to B ne emptyset$ which is injective but not surjective.
Since $C^emptyset$ has exactly one element and $C^B$ is non-empty, we see that $phi$ is bijective in case (1) and surjective in case (2).
What if $C = emptyset$? If $A, B ne emptyset$, then $C^A , C^B = emptyset$ and $phi$ is a bijection. If $A = B = emptyset$, then $phi$ is also a bijection. Only in case $A = emptyset, B ne emptyset$ we see that $phi$ is not surjective although $f$ is injective.
answered Jul 15 at 8:42
Paul Frost
3,703420
2
Maybe I'm being overzealous, but stating the existence of $h : B to A$ we use the non-emptiness of $A$.
– Adayah
Jul 15 at 8:52
@Adayah I added a remark to my answer.
– Paul Frost
Jul 15 at 9:31
add a comment |Â
up vote
2
down vote
accepted
As you said, if $f$ is injective, then there exists $h : B to A$ such that $h circ f = iota_A$. Given $g in C^A$, you see that $g circ h in C^B$ and $phi(g circ h) = g circ h circ f = g$.
Added:
Adayah has pointed out that we used $A ne emptyset$. But in fact the assumption in the question is $A, B, C ne emptyset$.
However, we can do everything under the assumption $C ne emptyset$ without any assumption on $A, B$. $A, B ne emptyset$ has been treated.
The empty set has the feature that there exists exactly one function $emptyset to X$, where $X$ is any set (the "empty" function $emptyset to X$), which btw is automatically injective.
The are exactly two cases in which one of $A, B$ is empty:
(1) $A = emptyset to B = emptyset$ which is bijective.
(2) $A = emptyset to B ne emptyset$ which is injective but not surjective.
Since $C^emptyset$ has exactly one element and $C^B$ is non-empty, we see that $phi$ is bijective in case (1) and surjective in case (2).
What if $C = emptyset$? If $A, B ne emptyset$, then $C^A , C^B = emptyset$ and $phi$ is a bijection. If $A = B = emptyset$, then $phi$ is also a bijection. Only in case $A = emptyset, B ne emptyset$ we see that $phi$ is not surjective although $f$ is injective.
answered Jul 15 at 8:42
Paul Frost
3,703420
2
Maybe I'm being overzealous, but stating the existence of $h : B to A$ we use the non-emptiness of $A$.
– Adayah
Jul 15 at 8:52
@Adayah I added a remark to my answer.
– Paul Frost
Jul 15 at 9:31
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
As you said, if $f$ is injective, then there exists $h : B to A$ such that $h circ f = iota_A$. Given $g in C^A$, you see that $g circ h in C^B$ and $phi(g circ h) = g circ h circ f = g$.
Added:
Adayah has pointed out that we used $A ne emptyset$. But in fact the assumption in the question is $A, B, C ne emptyset$.
However, we can do everything under the assumption $C ne emptyset$ without any assumption on $A, B$. $A, B ne emptyset$ has been treated.
The empty set has the feature that there exists exactly one function $emptyset to X$, where $X$ is any set (the "empty" function $emptyset to X$), which btw is automatically injective.
The are exactly two cases in which one of $A, B$ is empty:
(1) $A = emptyset to B = emptyset$ which is bijective.
(2) $A = emptyset to B ne emptyset$ which is injective but not surjective.
Since $C^emptyset$ has exactly one element and $C^B$ is non-empty, we see that $phi$ is bijective in case (1) and surjective in case (2).
What if $C = emptyset$? If $A, B ne emptyset$, then $C^A , C^B = emptyset$ and $phi$ is a bijection. If $A = B = emptyset$, then $phi$ is also a bijection. Only in case $A = emptyset, B ne emptyset$ we see that $phi$ is not surjective although $f$ is injective.
answered Jul 15 at 8:42
Paul Frost
3,703420
As you said, if $f$ is injective, then there exists $h : B to A$ such that $h circ f = iota_A$. Given $g in C^A$, you see that $g circ h in C^B$ and $phi(g circ h) = g circ h circ f = g$.
Added:
Adayah has pointed out that we used $A ne emptyset$. But in fact the assumption in the question is $A, B, C ne emptyset$.
However, we can do everything under the assumption $C ne emptyset$ without any assumption on $A, B$. $A, B ne emptyset$ has been treated.
The empty set has the feature that there exists exactly one function $emptyset to X$, where $X$ is any set (the "empty" function $emptyset to X$), which btw is automatically injective.
The are exactly two cases in which one of $A, B$ is empty:
(1) $A = emptyset to B = emptyset$ which is bijective.
(2) $A = emptyset to B ne emptyset$ which is injective but not surjective.
Since $C^emptyset$ has exactly one element and $C^B$ is non-empty, we see that $phi$ is bijective in case (1) and surjective in case (2).
What if $C = emptyset$? If $A, B ne emptyset$, then $C^A , C^B = emptyset$ and $phi$ is a bijection. If $A = B = emptyset$, then $phi$ is also a bijection. Only in case $A = emptyset, B ne emptyset$ we see that $phi$ is not surjective although $f$ is injective.
answered Jul 15 at 8:42
Paul Frost
3,703420
edited Jul 15 at 9:30
answered Jul 15 at 8:42
Paul Frost
3,703420
answered Jul 15 at 8:42
Paul Frost
3,703420
answered Jul 15 at 8:42
Paul Frost
3,703420
3,703420
2
Maybe I'm being overzealous, but stating the existence of $h : B to A$ we use the non-emptiness of $A$.
– Adayah
Jul 15 at 8:52
@Adayah I added a remark to my answer.
– Paul Frost
Jul 15 at 9:31
add a comment |Â
2
Maybe I'm being overzealous, but stating the existence of $h : B to A$ we use the non-emptiness of $A$.
– Adayah
Jul 15 at 8:52
@Adayah I added a remark to my answer.
– Paul Frost
Jul 15 at 9:31
2
2
Maybe I'm being overzealous, but stating the existence of $h : B to A$ we use the non-emptiness of $A$.
– Adayah
Jul 15 at 8:52
Maybe I'm being overzealous, but stating the existence of $h : B to A$ we use the non-emptiness of $A$.
– Adayah
Jul 15 at 8:52
@Adayah I added a remark to my answer.
– Paul Frost
Jul 15 at 9:31
@Adayah I added a remark to my answer.
– Paul Frost
Jul 15 at 9:31
add a comment |Â
up vote
0
down vote
Suppose $f$ is injective and take $alphacolon Ato C$. You wish to find $betacolon Bto C$ such that $phi(beta)=alpha$, that is, $betacirc f=alpha$.
Since $f$ is injective, there exists $gcolon Bto A$ with $hcirc f=iota_A$. Take $beta=alphacirc h$. Then
$$
phi(beta)=betacirc f=alphacirc hcirc f=alphacirciota_A=alpha
$$
as required. In other words, the map $alphamapstoalphacirc h$ is a right inverse to $phi$, so $phi$ is surjective.
The same idea can be used for the other claim. If $f$ is surjective, there is $gcolon Bto A$ such that $fcirc g=iota_B$. If $betain C^B$, then
$$
beta=betacirciota_B=betacirc fcirc g=psi(phi(beta))
$$
where $psi$ is defined similarly to $phi$. Then $phi$ has a left inverse, so it is injective.
answered Jul 15 at 9:56
egreg
164k1180187
add a comment |Â
up vote
0
down vote
Suppose $f$ is injective and take $alphacolon Ato C$. You wish to find $betacolon Bto C$ such that $phi(beta)=alpha$, that is, $betacirc f=alpha$.
Since $f$ is injective, there exists $gcolon Bto A$ with $hcirc f=iota_A$. Take $beta=alphacirc h$. Then
$$
phi(beta)=betacirc f=alphacirc hcirc f=alphacirciota_A=alpha
$$
as required. In other words, the map $alphamapstoalphacirc h$ is a right inverse to $phi$, so $phi$ is surjective.
The same idea can be used for the other claim. If $f$ is surjective, there is $gcolon Bto A$ such that $fcirc g=iota_B$. If $betain C^B$, then
$$
beta=betacirciota_B=betacirc fcirc g=psi(phi(beta))
$$
where $psi$ is defined similarly to $phi$. Then $phi$ has a left inverse, so it is injective.
answered Jul 15 at 9:56
egreg
164k1180187
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Suppose $f$ is injective and take $alphacolon Ato C$. You wish to find $betacolon Bto C$ such that $phi(beta)=alpha$, that is, $betacirc f=alpha$.
Since $f$ is injective, there exists $gcolon Bto A$ with $hcirc f=iota_A$. Take $beta=alphacirc h$. Then
$$
phi(beta)=betacirc f=alphacirc hcirc f=alphacirciota_A=alpha
$$
as required. In other words, the map $alphamapstoalphacirc h$ is a right inverse to $phi$, so $phi$ is surjective.
The same idea can be used for the other claim. If $f$ is surjective, there is $gcolon Bto A$ such that $fcirc g=iota_B$. If $betain C^B$, then
$$
beta=betacirciota_B=betacirc fcirc g=psi(phi(beta))
$$
where $psi$ is defined similarly to $phi$. Then $phi$ has a left inverse, so it is injective.
answered Jul 15 at 9:56
egreg
164k1180187
Suppose $f$ is injective and take $alphacolon Ato C$. You wish to find $betacolon Bto C$ such that $phi(beta)=alpha$, that is, $betacirc f=alpha$.
Since $f$ is injective, there exists $gcolon Bto A$ with $hcirc f=iota_A$. Take $beta=alphacirc h$. Then
$$
phi(beta)=betacirc f=alphacirc hcirc f=alphacirciota_A=alpha
$$
as required. In other words, the map $alphamapstoalphacirc h$ is a right inverse to $phi$, so $phi$ is surjective.
The same idea can be used for the other claim. If $f$ is surjective, there is $gcolon Bto A$ such that $fcirc g=iota_B$. If $betain C^B$, then
$$
beta=betacirciota_B=betacirc fcirc g=psi(phi(beta))
$$
where $psi$ is defined similarly to $phi$. Then $phi$ has a left inverse, so it is injective.
answered Jul 15 at 9:56
egreg
164k1180187
answered Jul 15 at 9:56
egreg
164k1180187
answered Jul 15 at 9:56
egreg
164k1180187
answered Jul 15 at 9:56
egreg
164k1180187
164k1180187
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%2f2852283%2flet-fa-to-b-and-phi-cb-to-ca-be-applications-prove-if-f-is-inject%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
3
Do you mean $phi:C^Bto C^A$?
– Lord Shark the Unknown
Jul 15 at 7:56
1
$Rightarrow$ isn't an abbreviation for "then",
– paf
Jul 15 at 8:18
@LordSharktheUnknown yes! Apologize me for that mistake.
– Arcticmonkey
Jul 15 at 8:29
@paf just edited
– Arcticmonkey
Jul 15 at 8:30
What if $|C|=1$?
– Lord Shark the Unknown
Jul 15 at 8:33