Mixing
Prove that there exists an injective mapping $f : B → A$
up vote
1
down vote
favorite
Given a set $A$ with $n$ elements and $B = {A_1,A_2,...,A_n} ⊆ 2^A$. Prove that there exists an injective mapping $f : B → A$ such that $f(A_i) ∈ A_i$ for all $i ∈ {1,2,...,n}$ if and only if for all I ⊆ {1, 2, . . . , n} the cardinality of $bigcuplimits_{i∈I}^{} A_i$ is at least equal to the cardinality of $I$.
I am not sure how to solve this one.
elementary-set-theory
asked 2 days ago
plsneedhelp
434
|
show 1 more comment
up vote
1
down vote
favorite
Given a set $A$ with $n$ elements and $B = {A_1,A_2,...,A_n} ⊆ 2^A$. Prove that there exists an injective mapping $f : B → A$ such that $f(A_i) ∈ A_i$ for all $i ∈ {1,2,...,n}$ if and only if for all I ⊆ {1, 2, . . . , n} the cardinality of $bigcuplimits_{i∈I}^{} A_i$ is at least equal to the cardinality of $I$.
I am not sure how to solve this one.
elementary-set-theory
asked 2 days ago
plsneedhelp
434
1
What exactly does $2A$ mean.
– fleablood
2 days ago
1
I assume $2A$ should be $2^A$...
– Eugen
2 days ago
Sorry typo, is fixed now
– plsneedhelp
2 days ago
Does $2^A$ stand for all the permutations of A?
– plsneedhelp
2 days ago
1
All subset of $A$. I think
– mathnoob
2 days ago
|
show 1 more comment
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Given a set $A$ with $n$ elements and $B = {A_1,A_2,...,A_n} ⊆ 2^A$. Prove that there exists an injective mapping $f : B → A$ such that $f(A_i) ∈ A_i$ for all $i ∈ {1,2,...,n}$ if and only if for all I ⊆ {1, 2, . . . , n} the cardinality of $bigcuplimits_{i∈I}^{} A_i$ is at least equal to the cardinality of $I$.
I am not sure how to solve this one.
elementary-set-theory
asked 2 days ago
plsneedhelp
434
Given a set $A$ with $n$ elements and $B = {A_1,A_2,...,A_n} ⊆ 2^A$. Prove that there exists an injective mapping $f : B → A$ such that $f(A_i) ∈ A_i$ for all $i ∈ {1,2,...,n}$ if and only if for all I ⊆ {1, 2, . . . , n} the cardinality of $bigcuplimits_{i∈I}^{} A_i$ is at least equal to the cardinality of $I$.
I am not sure how to solve this one.
elementary-set-theory
elementary-set-theory
asked 2 days ago
plsneedhelp
434
asked 2 days ago
plsneedhelp
434
edited 2 days ago
asked 2 days ago
plsneedhelp
434
asked 2 days ago
plsneedhelp
434
asked 2 days ago
plsneedhelp
434
434
1
What exactly does $2A$ mean.
– fleablood
2 days ago
1
I assume $2A$ should be $2^A$...
– Eugen
2 days ago
Sorry typo, is fixed now
– plsneedhelp
2 days ago
Does $2^A$ stand for all the permutations of A?
– plsneedhelp
2 days ago
1
All subset of $A$. I think
– mathnoob
2 days ago
|
show 1 more comment
1
What exactly does $2A$ mean.
– fleablood
2 days ago
1
I assume $2A$ should be $2^A$...
– Eugen
2 days ago
Sorry typo, is fixed now
– plsneedhelp
2 days ago
Does $2^A$ stand for all the permutations of A?
– plsneedhelp
2 days ago
1
All subset of $A$. I think
– mathnoob
2 days ago
1
1
What exactly does $2A$ mean.
– fleablood
2 days ago
What exactly does $2A$ mean.
– fleablood
2 days ago
1
1
I assume $2A$ should be $2^A$...
– Eugen
2 days ago
I assume $2A$ should be $2^A$...
– Eugen
2 days ago
Sorry typo, is fixed now
– plsneedhelp
2 days ago
Sorry typo, is fixed now
– plsneedhelp
2 days ago
Does $2^A$ stand for all the permutations of A?
– plsneedhelp
2 days ago
Does $2^A$ stand for all the permutations of A?
– plsneedhelp
2 days ago
1
1
All subset of $A$. I think
– mathnoob
2 days ago
All subset of $A$. I think
– mathnoob
2 days ago
|
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
$Rightarrow$. $|bigcup_{iin I}A_i| ge |{ f(A_i) mid iin I}| ge |I|$. For the first inequality just select one element from each $A_i$, namely $f(A_i)$. For the second inequality, use the injectivity of $f$.
$Leftarrow$. By an easy induction on $j$, one can show that $bigcup_{jin{1,dots,i+1}}A_j$ contains at least one element from $A_{i+1}$ that is not in $bigcup_{jin{1,dots,i}}A_j$. Pick this element as $f(A_{i+1})$.
answered 2 days ago
Eugen
1292
What exactly does the first statement show that we need for the second statement? Second one: i goes from 1..n but i+1 can be more than n?
– plsneedhelp
2 days ago
To me it seems that $|{f(A_i)∣i∈I}|≥|I|$ is more like $|{f(A_i)∣i∈I}|=|I|$?
– plsneedhelp
2 days ago
The first and second statements are independent. In the second statement $i$ goes from $0$ to $n-1$. I don't think $|{f(A_i)mid iin I}| = |I|$ is correct. You could take $A_i=A$ and then for $I={1}$ one has $n$ on the left-hand side and $1$ on the right-hand side.
– Eugen
2 days ago
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
$Rightarrow$. $|bigcup_{iin I}A_i| ge |{ f(A_i) mid iin I}| ge |I|$. For the first inequality just select one element from each $A_i$, namely $f(A_i)$. For the second inequality, use the injectivity of $f$.
$Leftarrow$. By an easy induction on $j$, one can show that $bigcup_{jin{1,dots,i+1}}A_j$ contains at least one element from $A_{i+1}$ that is not in $bigcup_{jin{1,dots,i}}A_j$. Pick this element as $f(A_{i+1})$.
answered 2 days ago
Eugen
1292
What exactly does the first statement show that we need for the second statement? Second one: i goes from 1..n but i+1 can be more than n?
– plsneedhelp
2 days ago
To me it seems that $|{f(A_i)∣i∈I}|≥|I|$ is more like $|{f(A_i)∣i∈I}|=|I|$?
– plsneedhelp
2 days ago
The first and second statements are independent. In the second statement $i$ goes from $0$ to $n-1$. I don't think $|{f(A_i)mid iin I}| = |I|$ is correct. You could take $A_i=A$ and then for $I={1}$ one has $n$ on the left-hand side and $1$ on the right-hand side.
– Eugen
2 days ago
add a comment |
up vote
0
down vote
accepted
$Rightarrow$. $|bigcup_{iin I}A_i| ge |{ f(A_i) mid iin I}| ge |I|$. For the first inequality just select one element from each $A_i$, namely $f(A_i)$. For the second inequality, use the injectivity of $f$.
$Leftarrow$. By an easy induction on $j$, one can show that $bigcup_{jin{1,dots,i+1}}A_j$ contains at least one element from $A_{i+1}$ that is not in $bigcup_{jin{1,dots,i}}A_j$. Pick this element as $f(A_{i+1})$.
answered 2 days ago
Eugen
1292
What exactly does the first statement show that we need for the second statement? Second one: i goes from 1..n but i+1 can be more than n?
– plsneedhelp
2 days ago
To me it seems that $|{f(A_i)∣i∈I}|≥|I|$ is more like $|{f(A_i)∣i∈I}|=|I|$?
– plsneedhelp
2 days ago
The first and second statements are independent. In the second statement $i$ goes from $0$ to $n-1$. I don't think $|{f(A_i)mid iin I}| = |I|$ is correct. You could take $A_i=A$ and then for $I={1}$ one has $n$ on the left-hand side and $1$ on the right-hand side.
– Eugen
2 days ago
add a comment |
up vote
0
down vote
accepted
up vote
0
down vote
accepted
$Rightarrow$. $|bigcup_{iin I}A_i| ge |{ f(A_i) mid iin I}| ge |I|$. For the first inequality just select one element from each $A_i$, namely $f(A_i)$. For the second inequality, use the injectivity of $f$.
$Leftarrow$. By an easy induction on $j$, one can show that $bigcup_{jin{1,dots,i+1}}A_j$ contains at least one element from $A_{i+1}$ that is not in $bigcup_{jin{1,dots,i}}A_j$. Pick this element as $f(A_{i+1})$.
answered 2 days ago
Eugen
1292
$Rightarrow$. $|bigcup_{iin I}A_i| ge |{ f(A_i) mid iin I}| ge |I|$. For the first inequality just select one element from each $A_i$, namely $f(A_i)$. For the second inequality, use the injectivity of $f$.
$Leftarrow$. By an easy induction on $j$, one can show that $bigcup_{jin{1,dots,i+1}}A_j$ contains at least one element from $A_{i+1}$ that is not in $bigcup_{jin{1,dots,i}}A_j$. Pick this element as $f(A_{i+1})$.
answered 2 days ago
Eugen
1292
answered 2 days ago
Eugen
1292
answered 2 days ago
Eugen
1292
answered 2 days ago
Eugen
1292
1292
What exactly does the first statement show that we need for the second statement? Second one: i goes from 1..n but i+1 can be more than n?
– plsneedhelp
2 days ago
To me it seems that $|{f(A_i)∣i∈I}|≥|I|$ is more like $|{f(A_i)∣i∈I}|=|I|$?
– plsneedhelp
2 days ago
The first and second statements are independent. In the second statement $i$ goes from $0$ to $n-1$. I don't think $|{f(A_i)mid iin I}| = |I|$ is correct. You could take $A_i=A$ and then for $I={1}$ one has $n$ on the left-hand side and $1$ on the right-hand side.
– Eugen
2 days ago
add a comment |
What exactly does the first statement show that we need for the second statement? Second one: i goes from 1..n but i+1 can be more than n?
– plsneedhelp
2 days ago
To me it seems that $|{f(A_i)∣i∈I}|≥|I|$ is more like $|{f(A_i)∣i∈I}|=|I|$?
– plsneedhelp
2 days ago
The first and second statements are independent. In the second statement $i$ goes from $0$ to $n-1$. I don't think $|{f(A_i)mid iin I}| = |I|$ is correct. You could take $A_i=A$ and then for $I={1}$ one has $n$ on the left-hand side and $1$ on the right-hand side.
– Eugen
2 days ago
What exactly does the first statement show that we need for the second statement? Second one: i goes from 1..n but i+1 can be more than n?
– plsneedhelp
2 days ago
What exactly does the first statement show that we need for the second statement? Second one: i goes from 1..n but i+1 can be more than n?
– plsneedhelp
2 days ago
To me it seems that $|{f(A_i)∣i∈I}|≥|I|$ is more like $|{f(A_i)∣i∈I}|=|I|$?
– plsneedhelp
2 days ago
To me it seems that $|{f(A_i)∣i∈I}|≥|I|$ is more like $|{f(A_i)∣i∈I}|=|I|$?
– plsneedhelp
2 days ago
The first and second statements are independent. In the second statement $i$ goes from $0$ to $n-1$. I don't think $|{f(A_i)mid iin I}| = |I|$ is correct. You could take $A_i=A$ and then for $I={1}$ one has $n$ on the left-hand side and $1$ on the right-hand side.
– Eugen
2 days ago
The first and second statements are independent. In the second statement $i$ goes from $0$ to $n-1$. I don't think $|{f(A_i)mid iin I}| = |I|$ is correct. You could take $A_i=A$ and then for $I={1}$ one has $n$ on the left-hand side and $1$ on the right-hand side.
– Eugen
2 days ago
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3005535%2fprove-that-there-exists-an-injective-mapping-f-b-%25e2%2586%2592-a%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
What exactly does $2A$ mean.
– fleablood
2 days ago
1
I assume $2A$ should be $2^A$...
– Eugen
2 days ago
Sorry typo, is fixed now
– plsneedhelp
2 days ago
Does $2^A$ stand for all the permutations of A?
– plsneedhelp
2 days ago
1
All subset of $A$. I think
– mathnoob
2 days ago