Proof of $f(A)=f(A-B)+f(B)$ when $f$ is a injective map
up vote
3
down vote
favorite
I want to prove the following proposition:
Let $A$ be a set, $B$ be a subset of $A$, and $f: Ato B$ be a injective map, then $f(A) = f(A-B) + f(B).$
Could you check my proof below?
Assume $f(A-B)cap f(B) neq emptyset$. For $xin f(A-B)cap f(B)$ there exist $ain A$ which satisfies $f(a)=x$ and $bin A-B$ which satisfies $f(b)=x$. However, this contradicts the original assumption that $f$ is injective: $forall a, b in A, f(a)=f(b)Rightarrow a=b$, thus the above is impossible. Thus, $f(A-B)cap f(B)=emptyset$ and hence $f(A)=f(A-B)+f(B)$.
proof-verification elementary-set-theory
add a comment |
up vote
3
down vote
favorite
I want to prove the following proposition:
Let $A$ be a set, $B$ be a subset of $A$, and $f: Ato B$ be a injective map, then $f(A) = f(A-B) + f(B).$
Could you check my proof below?
Assume $f(A-B)cap f(B) neq emptyset$. For $xin f(A-B)cap f(B)$ there exist $ain A$ which satisfies $f(a)=x$ and $bin A-B$ which satisfies $f(b)=x$. However, this contradicts the original assumption that $f$ is injective: $forall a, b in A, f(a)=f(b)Rightarrow a=b$, thus the above is impossible. Thus, $f(A-B)cap f(B)=emptyset$ and hence $f(A)=f(A-B)+f(B)$.
proof-verification elementary-set-theory
3
Terribly confusing. In the question statement you have a plus sign where a $cup$ is expected. Then right at the start of your proof you consider an intersection of sets, for some reason. This is followed by a dubious argument and you eventually finalize with incoherent conclusions with no sight of an expected double inclusion proof.
– Git Gud
Nov 17 at 9:38
@GitGud I am so sorry, it was a typo.
– orematasaburou
Nov 17 at 9:43
1
There is another typo: You want to say that there is an $b in B$ and an $a in A setminus B$ such that $f(a) = f(b)$.
– Stefan Mesken
Nov 17 at 9:59
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I want to prove the following proposition:
Let $A$ be a set, $B$ be a subset of $A$, and $f: Ato B$ be a injective map, then $f(A) = f(A-B) + f(B).$
Could you check my proof below?
Assume $f(A-B)cap f(B) neq emptyset$. For $xin f(A-B)cap f(B)$ there exist $ain A$ which satisfies $f(a)=x$ and $bin A-B$ which satisfies $f(b)=x$. However, this contradicts the original assumption that $f$ is injective: $forall a, b in A, f(a)=f(b)Rightarrow a=b$, thus the above is impossible. Thus, $f(A-B)cap f(B)=emptyset$ and hence $f(A)=f(A-B)+f(B)$.
proof-verification elementary-set-theory
I want to prove the following proposition:
Let $A$ be a set, $B$ be a subset of $A$, and $f: Ato B$ be a injective map, then $f(A) = f(A-B) + f(B).$
Could you check my proof below?
Assume $f(A-B)cap f(B) neq emptyset$. For $xin f(A-B)cap f(B)$ there exist $ain A$ which satisfies $f(a)=x$ and $bin A-B$ which satisfies $f(b)=x$. However, this contradicts the original assumption that $f$ is injective: $forall a, b in A, f(a)=f(b)Rightarrow a=b$, thus the above is impossible. Thus, $f(A-B)cap f(B)=emptyset$ and hence $f(A)=f(A-B)+f(B)$.
proof-verification elementary-set-theory
proof-verification elementary-set-theory
edited Nov 17 at 9:41
asked Nov 17 at 9:29
orematasaburou
345
345
3
Terribly confusing. In the question statement you have a plus sign where a $cup$ is expected. Then right at the start of your proof you consider an intersection of sets, for some reason. This is followed by a dubious argument and you eventually finalize with incoherent conclusions with no sight of an expected double inclusion proof.
– Git Gud
Nov 17 at 9:38
@GitGud I am so sorry, it was a typo.
– orematasaburou
Nov 17 at 9:43
1
There is another typo: You want to say that there is an $b in B$ and an $a in A setminus B$ such that $f(a) = f(b)$.
– Stefan Mesken
Nov 17 at 9:59
add a comment |
3
Terribly confusing. In the question statement you have a plus sign where a $cup$ is expected. Then right at the start of your proof you consider an intersection of sets, for some reason. This is followed by a dubious argument and you eventually finalize with incoherent conclusions with no sight of an expected double inclusion proof.
– Git Gud
Nov 17 at 9:38
@GitGud I am so sorry, it was a typo.
– orematasaburou
Nov 17 at 9:43
1
There is another typo: You want to say that there is an $b in B$ and an $a in A setminus B$ such that $f(a) = f(b)$.
– Stefan Mesken
Nov 17 at 9:59
3
3
Terribly confusing. In the question statement you have a plus sign where a $cup$ is expected. Then right at the start of your proof you consider an intersection of sets, for some reason. This is followed by a dubious argument and you eventually finalize with incoherent conclusions with no sight of an expected double inclusion proof.
– Git Gud
Nov 17 at 9:38
Terribly confusing. In the question statement you have a plus sign where a $cup$ is expected. Then right at the start of your proof you consider an intersection of sets, for some reason. This is followed by a dubious argument and you eventually finalize with incoherent conclusions with no sight of an expected double inclusion proof.
– Git Gud
Nov 17 at 9:38
@GitGud I am so sorry, it was a typo.
– orematasaburou
Nov 17 at 9:43
@GitGud I am so sorry, it was a typo.
– orematasaburou
Nov 17 at 9:43
1
1
There is another typo: You want to say that there is an $b in B$ and an $a in A setminus B$ such that $f(a) = f(b)$.
– Stefan Mesken
Nov 17 at 9:59
There is another typo: You want to say that there is an $b in B$ and an $a in A setminus B$ such that $f(a) = f(b)$.
– Stefan Mesken
Nov 17 at 9:59
add a comment |
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
Other than the typo I've pointed out in a comment, your proof is fine.
Note, however, that you don't need that $B subseteq A$. The following is true:
Lemma. Let $f colon A to B$ be injective, $C subseteq D subseteq A$ Then
$$f[D] = f[D setminus C] mathbin{dot{cup}} f[C].$$
(The proof is virtually the same as the one you've given.)
Also note that injectivity is necessary:
Lemma. If $f colon A to B$ is not injective, then there is some $C subseteq A$ such that
$$f[A setminus C] cap f[C] neq emptyset.$$
I'll leave the easy proof to you as an exercise. (Hint: You can choose $C$ to be a singleton.)
1
Thank you for the answer and exercise! That actually wasn't typo for me (I meant it). Would you explain why I have to write $bin B, ain A-B$ instead of just $a, bin A$?
– orematasaburou
Nov 17 at 10:12
@oremata You want to show that $f[A setminus B] cap f[B] = emptyset$. Toward a contradiction you must assume there is some $a in A setminus B$ and some $b in B$ such that $f(a) = f(b)$. If $a in A cap B$, it could be that $a = b$ and then there is no contradiction.
– Stefan Mesken
Nov 17 at 10:18
I understand the point. But, before writing about the injection, I mentioned in the proof that there exist $ain A$ and $bin A-B$, so I think I don't have to write it again... Is it wrong? Sorry, I'm new to proof stuff.
– orematasaburou
Nov 17 at 10:27
@oremata The point is that you could have $a = b$ and then you don't get your contradiction. If you fix $a in B$ and $b in A setminus B$, you know that $a neq b$ (because $B$ and $A setminus B$ don't have a common element). If you then have $f(a) = f(b)$, this is a contradiction to injectivity.
– Stefan Mesken
Nov 17 at 10:30
If you want to use a binary operation symbol with an accent on it, it should be coded asmathbin{dot{cup}}
so the spacing is right.
– egreg
Nov 17 at 10:41
|
show 2 more comments
up vote
0
down vote
I assume that $+$ denotes disjoint union. Your idea is good, but you lose yourself in explanations.
The proof that $f(A)=f(A-B)cup f(B)$ is easy and doesn't require injectivity.
Now the proof the sets are disjoint. More generally,
if $X$ and $Y$ are disjoint sets and $f(X)cap f(Y)neemptyset$, then $f$ is not injective.
Indeed, if $zin f(X)cap f(Y)$, then $z=f(x)=f(y)$, with $xin X$ and $yin Y$. Since $X$ and $Y$ are disjoint, $xne y$.
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
Other than the typo I've pointed out in a comment, your proof is fine.
Note, however, that you don't need that $B subseteq A$. The following is true:
Lemma. Let $f colon A to B$ be injective, $C subseteq D subseteq A$ Then
$$f[D] = f[D setminus C] mathbin{dot{cup}} f[C].$$
(The proof is virtually the same as the one you've given.)
Also note that injectivity is necessary:
Lemma. If $f colon A to B$ is not injective, then there is some $C subseteq A$ such that
$$f[A setminus C] cap f[C] neq emptyset.$$
I'll leave the easy proof to you as an exercise. (Hint: You can choose $C$ to be a singleton.)
1
Thank you for the answer and exercise! That actually wasn't typo for me (I meant it). Would you explain why I have to write $bin B, ain A-B$ instead of just $a, bin A$?
– orematasaburou
Nov 17 at 10:12
@oremata You want to show that $f[A setminus B] cap f[B] = emptyset$. Toward a contradiction you must assume there is some $a in A setminus B$ and some $b in B$ such that $f(a) = f(b)$. If $a in A cap B$, it could be that $a = b$ and then there is no contradiction.
– Stefan Mesken
Nov 17 at 10:18
I understand the point. But, before writing about the injection, I mentioned in the proof that there exist $ain A$ and $bin A-B$, so I think I don't have to write it again... Is it wrong? Sorry, I'm new to proof stuff.
– orematasaburou
Nov 17 at 10:27
@oremata The point is that you could have $a = b$ and then you don't get your contradiction. If you fix $a in B$ and $b in A setminus B$, you know that $a neq b$ (because $B$ and $A setminus B$ don't have a common element). If you then have $f(a) = f(b)$, this is a contradiction to injectivity.
– Stefan Mesken
Nov 17 at 10:30
If you want to use a binary operation symbol with an accent on it, it should be coded asmathbin{dot{cup}}
so the spacing is right.
– egreg
Nov 17 at 10:41
|
show 2 more comments
up vote
2
down vote
accepted
Other than the typo I've pointed out in a comment, your proof is fine.
Note, however, that you don't need that $B subseteq A$. The following is true:
Lemma. Let $f colon A to B$ be injective, $C subseteq D subseteq A$ Then
$$f[D] = f[D setminus C] mathbin{dot{cup}} f[C].$$
(The proof is virtually the same as the one you've given.)
Also note that injectivity is necessary:
Lemma. If $f colon A to B$ is not injective, then there is some $C subseteq A$ such that
$$f[A setminus C] cap f[C] neq emptyset.$$
I'll leave the easy proof to you as an exercise. (Hint: You can choose $C$ to be a singleton.)
1
Thank you for the answer and exercise! That actually wasn't typo for me (I meant it). Would you explain why I have to write $bin B, ain A-B$ instead of just $a, bin A$?
– orematasaburou
Nov 17 at 10:12
@oremata You want to show that $f[A setminus B] cap f[B] = emptyset$. Toward a contradiction you must assume there is some $a in A setminus B$ and some $b in B$ such that $f(a) = f(b)$. If $a in A cap B$, it could be that $a = b$ and then there is no contradiction.
– Stefan Mesken
Nov 17 at 10:18
I understand the point. But, before writing about the injection, I mentioned in the proof that there exist $ain A$ and $bin A-B$, so I think I don't have to write it again... Is it wrong? Sorry, I'm new to proof stuff.
– orematasaburou
Nov 17 at 10:27
@oremata The point is that you could have $a = b$ and then you don't get your contradiction. If you fix $a in B$ and $b in A setminus B$, you know that $a neq b$ (because $B$ and $A setminus B$ don't have a common element). If you then have $f(a) = f(b)$, this is a contradiction to injectivity.
– Stefan Mesken
Nov 17 at 10:30
If you want to use a binary operation symbol with an accent on it, it should be coded asmathbin{dot{cup}}
so the spacing is right.
– egreg
Nov 17 at 10:41
|
show 2 more comments
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Other than the typo I've pointed out in a comment, your proof is fine.
Note, however, that you don't need that $B subseteq A$. The following is true:
Lemma. Let $f colon A to B$ be injective, $C subseteq D subseteq A$ Then
$$f[D] = f[D setminus C] mathbin{dot{cup}} f[C].$$
(The proof is virtually the same as the one you've given.)
Also note that injectivity is necessary:
Lemma. If $f colon A to B$ is not injective, then there is some $C subseteq A$ such that
$$f[A setminus C] cap f[C] neq emptyset.$$
I'll leave the easy proof to you as an exercise. (Hint: You can choose $C$ to be a singleton.)
Other than the typo I've pointed out in a comment, your proof is fine.
Note, however, that you don't need that $B subseteq A$. The following is true:
Lemma. Let $f colon A to B$ be injective, $C subseteq D subseteq A$ Then
$$f[D] = f[D setminus C] mathbin{dot{cup}} f[C].$$
(The proof is virtually the same as the one you've given.)
Also note that injectivity is necessary:
Lemma. If $f colon A to B$ is not injective, then there is some $C subseteq A$ such that
$$f[A setminus C] cap f[C] neq emptyset.$$
I'll leave the easy proof to you as an exercise. (Hint: You can choose $C$ to be a singleton.)
edited Nov 17 at 10:46
answered Nov 17 at 10:03
Stefan Mesken
14.4k32046
14.4k32046
1
Thank you for the answer and exercise! That actually wasn't typo for me (I meant it). Would you explain why I have to write $bin B, ain A-B$ instead of just $a, bin A$?
– orematasaburou
Nov 17 at 10:12
@oremata You want to show that $f[A setminus B] cap f[B] = emptyset$. Toward a contradiction you must assume there is some $a in A setminus B$ and some $b in B$ such that $f(a) = f(b)$. If $a in A cap B$, it could be that $a = b$ and then there is no contradiction.
– Stefan Mesken
Nov 17 at 10:18
I understand the point. But, before writing about the injection, I mentioned in the proof that there exist $ain A$ and $bin A-B$, so I think I don't have to write it again... Is it wrong? Sorry, I'm new to proof stuff.
– orematasaburou
Nov 17 at 10:27
@oremata The point is that you could have $a = b$ and then you don't get your contradiction. If you fix $a in B$ and $b in A setminus B$, you know that $a neq b$ (because $B$ and $A setminus B$ don't have a common element). If you then have $f(a) = f(b)$, this is a contradiction to injectivity.
– Stefan Mesken
Nov 17 at 10:30
If you want to use a binary operation symbol with an accent on it, it should be coded asmathbin{dot{cup}}
so the spacing is right.
– egreg
Nov 17 at 10:41
|
show 2 more comments
1
Thank you for the answer and exercise! That actually wasn't typo for me (I meant it). Would you explain why I have to write $bin B, ain A-B$ instead of just $a, bin A$?
– orematasaburou
Nov 17 at 10:12
@oremata You want to show that $f[A setminus B] cap f[B] = emptyset$. Toward a contradiction you must assume there is some $a in A setminus B$ and some $b in B$ such that $f(a) = f(b)$. If $a in A cap B$, it could be that $a = b$ and then there is no contradiction.
– Stefan Mesken
Nov 17 at 10:18
I understand the point. But, before writing about the injection, I mentioned in the proof that there exist $ain A$ and $bin A-B$, so I think I don't have to write it again... Is it wrong? Sorry, I'm new to proof stuff.
– orematasaburou
Nov 17 at 10:27
@oremata The point is that you could have $a = b$ and then you don't get your contradiction. If you fix $a in B$ and $b in A setminus B$, you know that $a neq b$ (because $B$ and $A setminus B$ don't have a common element). If you then have $f(a) = f(b)$, this is a contradiction to injectivity.
– Stefan Mesken
Nov 17 at 10:30
If you want to use a binary operation symbol with an accent on it, it should be coded asmathbin{dot{cup}}
so the spacing is right.
– egreg
Nov 17 at 10:41
1
1
Thank you for the answer and exercise! That actually wasn't typo for me (I meant it). Would you explain why I have to write $bin B, ain A-B$ instead of just $a, bin A$?
– orematasaburou
Nov 17 at 10:12
Thank you for the answer and exercise! That actually wasn't typo for me (I meant it). Would you explain why I have to write $bin B, ain A-B$ instead of just $a, bin A$?
– orematasaburou
Nov 17 at 10:12
@oremata You want to show that $f[A setminus B] cap f[B] = emptyset$. Toward a contradiction you must assume there is some $a in A setminus B$ and some $b in B$ such that $f(a) = f(b)$. If $a in A cap B$, it could be that $a = b$ and then there is no contradiction.
– Stefan Mesken
Nov 17 at 10:18
@oremata You want to show that $f[A setminus B] cap f[B] = emptyset$. Toward a contradiction you must assume there is some $a in A setminus B$ and some $b in B$ such that $f(a) = f(b)$. If $a in A cap B$, it could be that $a = b$ and then there is no contradiction.
– Stefan Mesken
Nov 17 at 10:18
I understand the point. But, before writing about the injection, I mentioned in the proof that there exist $ain A$ and $bin A-B$, so I think I don't have to write it again... Is it wrong? Sorry, I'm new to proof stuff.
– orematasaburou
Nov 17 at 10:27
I understand the point. But, before writing about the injection, I mentioned in the proof that there exist $ain A$ and $bin A-B$, so I think I don't have to write it again... Is it wrong? Sorry, I'm new to proof stuff.
– orematasaburou
Nov 17 at 10:27
@oremata The point is that you could have $a = b$ and then you don't get your contradiction. If you fix $a in B$ and $b in A setminus B$, you know that $a neq b$ (because $B$ and $A setminus B$ don't have a common element). If you then have $f(a) = f(b)$, this is a contradiction to injectivity.
– Stefan Mesken
Nov 17 at 10:30
@oremata The point is that you could have $a = b$ and then you don't get your contradiction. If you fix $a in B$ and $b in A setminus B$, you know that $a neq b$ (because $B$ and $A setminus B$ don't have a common element). If you then have $f(a) = f(b)$, this is a contradiction to injectivity.
– Stefan Mesken
Nov 17 at 10:30
If you want to use a binary operation symbol with an accent on it, it should be coded as
mathbin{dot{cup}}
so the spacing is right.– egreg
Nov 17 at 10:41
If you want to use a binary operation symbol with an accent on it, it should be coded as
mathbin{dot{cup}}
so the spacing is right.– egreg
Nov 17 at 10:41
|
show 2 more comments
up vote
0
down vote
I assume that $+$ denotes disjoint union. Your idea is good, but you lose yourself in explanations.
The proof that $f(A)=f(A-B)cup f(B)$ is easy and doesn't require injectivity.
Now the proof the sets are disjoint. More generally,
if $X$ and $Y$ are disjoint sets and $f(X)cap f(Y)neemptyset$, then $f$ is not injective.
Indeed, if $zin f(X)cap f(Y)$, then $z=f(x)=f(y)$, with $xin X$ and $yin Y$. Since $X$ and $Y$ are disjoint, $xne y$.
add a comment |
up vote
0
down vote
I assume that $+$ denotes disjoint union. Your idea is good, but you lose yourself in explanations.
The proof that $f(A)=f(A-B)cup f(B)$ is easy and doesn't require injectivity.
Now the proof the sets are disjoint. More generally,
if $X$ and $Y$ are disjoint sets and $f(X)cap f(Y)neemptyset$, then $f$ is not injective.
Indeed, if $zin f(X)cap f(Y)$, then $z=f(x)=f(y)$, with $xin X$ and $yin Y$. Since $X$ and $Y$ are disjoint, $xne y$.
add a comment |
up vote
0
down vote
up vote
0
down vote
I assume that $+$ denotes disjoint union. Your idea is good, but you lose yourself in explanations.
The proof that $f(A)=f(A-B)cup f(B)$ is easy and doesn't require injectivity.
Now the proof the sets are disjoint. More generally,
if $X$ and $Y$ are disjoint sets and $f(X)cap f(Y)neemptyset$, then $f$ is not injective.
Indeed, if $zin f(X)cap f(Y)$, then $z=f(x)=f(y)$, with $xin X$ and $yin Y$. Since $X$ and $Y$ are disjoint, $xne y$.
I assume that $+$ denotes disjoint union. Your idea is good, but you lose yourself in explanations.
The proof that $f(A)=f(A-B)cup f(B)$ is easy and doesn't require injectivity.
Now the proof the sets are disjoint. More generally,
if $X$ and $Y$ are disjoint sets and $f(X)cap f(Y)neemptyset$, then $f$ is not injective.
Indeed, if $zin f(X)cap f(Y)$, then $z=f(x)=f(y)$, with $xin X$ and $yin Y$. Since $X$ and $Y$ are disjoint, $xne y$.
answered Nov 17 at 10:51
egreg
175k1383198
175k1383198
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3002134%2fproof-of-fa-fa-bfb-when-f-is-a-injective-map%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
3
Terribly confusing. In the question statement you have a plus sign where a $cup$ is expected. Then right at the start of your proof you consider an intersection of sets, for some reason. This is followed by a dubious argument and you eventually finalize with incoherent conclusions with no sight of an expected double inclusion proof.
– Git Gud
Nov 17 at 9:38
@GitGud I am so sorry, it was a typo.
– orematasaburou
Nov 17 at 9:43
1
There is another typo: You want to say that there is an $b in B$ and an $a in A setminus B$ such that $f(a) = f(b)$.
– Stefan Mesken
Nov 17 at 9:59