proof injective mapping of $A$ with $n$ elements and $B = {A_1, A_2, …, A_n} subseteq 2^A$
up vote
0
down vote
favorite
Given a set $A$ with $n$ elements and $B = {A_1, A_2, ..., A_n} subseteq 2^A$. Prove that there exists an injective mapping $f : B to A$ such that $f(A_i) in A_i$ for all $i in {1,2,...,n}$ if and only
if for all $I subseteq {1,2,...,n}$ the cardinality of
$bigcup_{iin I}A_i$ is at least equal to the cardinality
of $I$.
I really don't even know where to begin with this one.
- What is $2^A$ supposed to be? Just the 2 power each element of $A$?
- And why do I need $A_1, ...,A_n$?
- Isn't the cardinality of $bigcup_{iin I}A_i$ always at least equal to $I$ unless an $A_i = emptyset$?
How do I even start to prove an injective mapping? The only thing similar to this covered in our lecture were graph colorings and we didn't really do a proof of this sort, the main message was just that colorings are really hard to prove.
discrete-mathematics
asked Nov 18 at 10:31
likelightning
11
add a comment |
up vote
0
down vote
favorite
Given a set $A$ with $n$ elements and $B = {A_1, A_2, ..., A_n} subseteq 2^A$. Prove that there exists an injective mapping $f : B to A$ such that $f(A_i) in A_i$ for all $i in {1,2,...,n}$ if and only
if for all $I subseteq {1,2,...,n}$ the cardinality of
$bigcup_{iin I}A_i$ is at least equal to the cardinality
of $I$.
I really don't even know where to begin with this one.
- What is $2^A$ supposed to be? Just the 2 power each element of $A$?
- And why do I need $A_1, ...,A_n$?
- Isn't the cardinality of $bigcup_{iin I}A_i$ always at least equal to $I$ unless an $A_i = emptyset$?
How do I even start to prove an injective mapping? The only thing similar to this covered in our lecture were graph colorings and we didn't really do a proof of this sort, the main message was just that colorings are really hard to prove.
discrete-mathematics
asked Nov 18 at 10:31
likelightning
11
For a proof, this is a simple consequence of Hall's Marriage Theorem: en.wikipedia.org/wiki/Hall%27s_marriage_theorem.
– Batominovski
Nov 18 at 13:55
thank you, that hint makes it actually very easy to solve this problem!
– likelightning
Nov 18 at 14:16
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Given a set $A$ with $n$ elements and $B = {A_1, A_2, ..., A_n} subseteq 2^A$. Prove that there exists an injective mapping $f : B to A$ such that $f(A_i) in A_i$ for all $i in {1,2,...,n}$ if and only
if for all $I subseteq {1,2,...,n}$ the cardinality of
$bigcup_{iin I}A_i$ is at least equal to the cardinality
of $I$.
I really don't even know where to begin with this one.
- What is $2^A$ supposed to be? Just the 2 power each element of $A$?
- And why do I need $A_1, ...,A_n$?
- Isn't the cardinality of $bigcup_{iin I}A_i$ always at least equal to $I$ unless an $A_i = emptyset$?
How do I even start to prove an injective mapping? The only thing similar to this covered in our lecture were graph colorings and we didn't really do a proof of this sort, the main message was just that colorings are really hard to prove.
discrete-mathematics
asked Nov 18 at 10:31
likelightning
11
Given a set $A$ with $n$ elements and $B = {A_1, A_2, ..., A_n} subseteq 2^A$. Prove that there exists an injective mapping $f : B to A$ such that $f(A_i) in A_i$ for all $i in {1,2,...,n}$ if and only
if for all $I subseteq {1,2,...,n}$ the cardinality of
$bigcup_{iin I}A_i$ is at least equal to the cardinality
of $I$.
I really don't even know where to begin with this one.
- What is $2^A$ supposed to be? Just the 2 power each element of $A$?
- And why do I need $A_1, ...,A_n$?
- Isn't the cardinality of $bigcup_{iin I}A_i$ always at least equal to $I$ unless an $A_i = emptyset$?
How do I even start to prove an injective mapping? The only thing similar to this covered in our lecture were graph colorings and we didn't really do a proof of this sort, the main message was just that colorings are really hard to prove.
discrete-mathematics
discrete-mathematics
asked Nov 18 at 10:31
likelightning
11
asked Nov 18 at 10:31
likelightning
11
asked Nov 18 at 10:31
likelightning
11
asked Nov 18 at 10:31
likelightning
11
asked Nov 18 at 10:31
likelightning
11
11
For a proof, this is a simple consequence of Hall's Marriage Theorem: en.wikipedia.org/wiki/Hall%27s_marriage_theorem.
– Batominovski
Nov 18 at 13:55
thank you, that hint makes it actually very easy to solve this problem!
– likelightning
Nov 18 at 14:16
add a comment |
For a proof, this is a simple consequence of Hall's Marriage Theorem: en.wikipedia.org/wiki/Hall%27s_marriage_theorem.
– Batominovski
Nov 18 at 13:55
thank you, that hint makes it actually very easy to solve this problem!
– likelightning
Nov 18 at 14:16
For a proof, this is a simple consequence of Hall's Marriage Theorem: en.wikipedia.org/wiki/Hall%27s_marriage_theorem.
– Batominovski
Nov 18 at 13:55
For a proof, this is a simple consequence of Hall's Marriage Theorem: en.wikipedia.org/wiki/Hall%27s_marriage_theorem.
– Batominovski
Nov 18 at 13:55
thank you, that hint makes it actually very easy to solve this problem!
– likelightning
Nov 18 at 14:16
thank you, that hint makes it actually very easy to solve this problem!
– likelightning
Nov 18 at 14:16
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3003358%2fproof-injective-mapping-of-a-with-n-elements-and-b-a-1-a-2-a-n%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
For a proof, this is a simple consequence of Hall's Marriage Theorem: en.wikipedia.org/wiki/Hall%27s_marriage_theorem.
– Batominovski
Nov 18 at 13:55
thank you, that hint makes it actually very easy to solve this problem!
– likelightning
Nov 18 at 14:16