Mixing
Show that $2$ sets have “the same number of elements”
$begingroup$
Let $A,B,C$ be nonempty sets. We will denote $B^A$ as the number of functions defined $f:Ato B$.
Show that $B^Atimes C^A$ and $(Btimes C)^A$ "have the same number of elements". (in my language this is called "echipotenta" but I don't know how to call it here) To be more explicit, what I mean is: both sets are "equally rich" in elements. How do you show that $2$ sets are "echipotent"?
elementary-set-theory
edited Jan 17 at 17:51
Andrés E. Caicedo
65.5k8159250
asked Jan 17 at 15:46
C. CristiC. Cristi
1,634218
$endgroup$
add a comment |
$begingroup$
Let $A,B,C$ be nonempty sets. We will denote $B^A$ as the number of functions defined $f:Ato B$.
Show that $B^Atimes C^A$ and $(Btimes C)^A$ "have the same number of elements". (in my language this is called "echipotenta" but I don't know how to call it here) To be more explicit, what I mean is: both sets are "equally rich" in elements. How do you show that $2$ sets are "echipotent"?
elementary-set-theory
edited Jan 17 at 17:51
Andrés E. Caicedo
65.5k8159250
asked Jan 17 at 15:46
C. CristiC. Cristi
1,634218
$endgroup$
$begingroup$
The english equivalent of "echipotenta" is "equipotent".
$endgroup$
– Servaes
Jan 17 at 15:47
1
$begingroup$
By definition, two sets have the same number of elements if there is a bijection between them.
$endgroup$
– Wojowu
Jan 17 at 15:48
$begingroup$
@Servaes Oh, I'm sorry.. I tried to google translate it but haven't found anything and also Wikipedia the page in my language then convert it to English and and still haven't found a thing, thanks!
$endgroup$
– C. Cristi
Jan 17 at 15:49
add a comment |
$begingroup$
Let $A,B,C$ be nonempty sets. We will denote $B^A$ as the number of functions defined $f:Ato B$.
Show that $B^Atimes C^A$ and $(Btimes C)^A$ "have the same number of elements". (in my language this is called "echipotenta" but I don't know how to call it here) To be more explicit, what I mean is: both sets are "equally rich" in elements. How do you show that $2$ sets are "echipotent"?
elementary-set-theory
edited Jan 17 at 17:51
Andrés E. Caicedo
65.5k8159250
asked Jan 17 at 15:46
C. CristiC. Cristi
1,634218
$endgroup$
Let $A,B,C$ be nonempty sets. We will denote $B^A$ as the number of functions defined $f:Ato B$.
Show that $B^Atimes C^A$ and $(Btimes C)^A$ "have the same number of elements". (in my language this is called "echipotenta" but I don't know how to call it here) To be more explicit, what I mean is: both sets are "equally rich" in elements. How do you show that $2$ sets are "echipotent"?
elementary-set-theory
elementary-set-theory
edited Jan 17 at 17:51
Andrés E. Caicedo
65.5k8159250
asked Jan 17 at 15:46
C. CristiC. Cristi
1,634218
edited Jan 17 at 17:51
Andrés E. Caicedo
65.5k8159250
asked Jan 17 at 15:46
C. CristiC. Cristi
1,634218
edited Jan 17 at 17:51
Andrés E. Caicedo
65.5k8159250
edited Jan 17 at 17:51
Andrés E. Caicedo
65.5k8159250
edited Jan 17 at 17:51
Andrés E. Caicedo
65.5k8159250
65.5k8159250
asked Jan 17 at 15:46
C. CristiC. Cristi
1,634218
asked Jan 17 at 15:46
C. CristiC. Cristi
1,634218
asked Jan 17 at 15:46
C. CristiC. Cristi
1,634218
1,634218
$begingroup$
The english equivalent of "echipotenta" is "equipotent".
$endgroup$
– Servaes
Jan 17 at 15:47
1
$begingroup$
By definition, two sets have the same number of elements if there is a bijection between them.
$endgroup$
– Wojowu
Jan 17 at 15:48
$begingroup$
@Servaes Oh, I'm sorry.. I tried to google translate it but haven't found anything and also Wikipedia the page in my language then convert it to English and and still haven't found a thing, thanks!
$endgroup$
– C. Cristi
Jan 17 at 15:49
add a comment |
$begingroup$
The english equivalent of "echipotenta" is "equipotent".
$endgroup$
– Servaes
Jan 17 at 15:47
1
$begingroup$
By definition, two sets have the same number of elements if there is a bijection between them.
$endgroup$
– Wojowu
Jan 17 at 15:48
$begingroup$
@Servaes Oh, I'm sorry.. I tried to google translate it but haven't found anything and also Wikipedia the page in my language then convert it to English and and still haven't found a thing, thanks!
$endgroup$
– C. Cristi
Jan 17 at 15:49
$begingroup$
The english equivalent of "echipotenta" is "equipotent".
$endgroup$
– Servaes
Jan 17 at 15:47
$begingroup$
The english equivalent of "echipotenta" is "equipotent".
$endgroup$
– Servaes
Jan 17 at 15:47
1
1
$begingroup$
By definition, two sets have the same number of elements if there is a bijection between them.
$endgroup$
– Wojowu
Jan 17 at 15:48
$begingroup$
By definition, two sets have the same number of elements if there is a bijection between them.
$endgroup$
– Wojowu
Jan 17 at 15:48
$begingroup$
@Servaes Oh, I'm sorry.. I tried to google translate it but haven't found anything and also Wikipedia the page in my language then convert it to English and and still haven't found a thing, thanks!
$endgroup$
– C. Cristi
Jan 17 at 15:49
$begingroup$
@Servaes Oh, I'm sorry.. I tried to google translate it but haven't found anything and also Wikipedia the page in my language then convert it to English and and still haven't found a thing, thanks!
$endgroup$
– C. Cristi
Jan 17 at 15:49
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
In general, the way you can proof two sets $X,Y$ are equipotent is by finding a bijection (i.e., a function that is injective and surjective) $h:Xto Y$ between them.
In this case, notice that an element of the set $(Btimes C)^A$ must be a function $f:Ato Btimes C$, and element by element it looks like $f(a)=(b,c)$. If we call $f_1(a)=b$ and $f_2(a)=c$ whenever $f(a)=(b,c)$, then there is a natural way to obtain an element of the set $B^Atimes C^A$ associated to $f$, namely the ordered pair $(f_1,f_2)$.
If you can show that the assignment
begin{align*}
h:&(Btimes C)^Alongrightarrow B^Atimes C^A\
& f longmapsto h(f)=(f_1,f_2)
end{align*}
is a bijection, you will be done.
answered Jan 17 at 15:52
Darío GDarío G
4,062613
$endgroup$
add a comment |
$begingroup$
We want to show a bijection $f$ exists with $operatorname{dom} f=B^Atimes C^A,,operatorname{rang} f=(Btimes C)^A$. The desired domain is the set of ordered pairs $(g,,h)$, with $g$ ($h$) a function from $A$ to $B$ ($C$). Meanwhile, the desired range is the set of functions from $A$ to ordered pairs $(b,,c)$ with $bin B,,cin C$. So it suffices to define $f((g,,h)):= xmapsto (g(x),,h(x))$.
answered Jan 17 at 15:52
J.G.J.G.
27.9k22843
$endgroup$
$begingroup$
Okay, so correct me if I'm wrong, but what you're saying is, is that $f:B^Atimes C^A to (Btimes C)^A, f(g(x),h(x))=(g(x),h(x))$, where $g:Ato B$ and $h: Ato C$, is the desired bijection which proves the equipotence of the sets?
$endgroup$
– C. Cristi
Jan 17 at 16:15
$begingroup$
What is the intuition behind the chosen function?
$endgroup$
– C. Cristi
Jan 17 at 16:15
$begingroup$
and your $f$ is bijective because...?
$endgroup$
– C. Cristi
Jan 17 at 16:16
$begingroup$
@C.Cristi Injective because changing $g$ or $h$ changes the result for at least one $x$, surjective because any ordered pair can be split to reverse-engineer $g,,h$. The intuition is: how do you pair pairs of functions with pair-valued functions?
$endgroup$
– J.G.
Jan 17 at 16:42
add a comment |
$begingroup$
Let $F : B^A times C^A rightarrow (Btimes C)^A$ be defined by
$$F((f,g)) : A rightarrow(B times C)$$
$$F((f,g)) (a) = (f(a),g(a))$$
for all $a in A$.
$F$ is injective:
All $(f_1,g_1),(f_2,g_2) in B^A times C^A$ with
$$F((f_1,g_1)) = F((f_2,g_2))$$
implies that
$$(f_1(a),g_1(a)) = (f_2(a),g_2(a))$$
for all $a in A$, by definition of the ordered pair. Thus,
$$(f_1,g_1) = (f_2,g_2)$$ so $F$ is injective.
F is surjective:
If $h in (B times C)^A$, then define $(f,g)$ by
$$ (f,g) = (pi_1circ h, pi_2 circ h)$$
where $pi_1$ and $pi_2$ are the projections. See that
$$F((f,g))(a) = (f(a),g(a)) = (pi_1(h(a)),pi_2(h(a))) = h(a)$$
so $F((f,g)) = h$ and hence $F$ is surjective.
Thus $F$ is bijective, so the sets have the same size.
answered Jan 18 at 17:38
MetricMetric
1,23649
$endgroup$
$begingroup$
That is an awesome proof! What was the intuition behind it and why you picked that function that certain way?
$endgroup$
– C. Cristi
Jan 18 at 21:25
$begingroup$
For $(f,g) in B^A times C^A$ I know it's required that $F((f,g)) : A rightarrow (B times C)$. So, how would I define $F((f,g))$? I know that it takes an $a in A$, and produces something in $B times C$. What do I have to work with? I have $f : A rightarrow B$ and $g : A rightarrow C$, so from the domain and codomain of these maps alone, a first guess would be to write $F((f,g))(a) = (f(a),g(a))$, and then I simply checked injectivity and surjectivity. The intuition came simply from the domain and codomain of the maps I had to work with.
$endgroup$
– Metric
Jan 19 at 0:47
$begingroup$
Of course this style doesn't work in general, but it does offer some initial guesses and builds intuition for the map your looking for.
$endgroup$
– Metric
Jan 19 at 0:53
add a comment |
$begingroup$
Consider the projections $pi_1:Btimes Crightarrow B$ and $pi_2:Btimes Crightarrow C$ onto the components.
Then for a given function $f:Arightarrow Btimes C$, define $f_1=pi_1 f$ and $f_2=pi_2f$ with $f_1(a) = pi_1 f(a)= pi_1(b,c)=b$ and $f_2(a)=pi_2f(a) = pi_2(b,c)=c$.
The assignment $fmapsto (pi_1f,pi_2f)$ provides the required bijection.
For instance, take $A=B=C={0,1}$ and the function $f:Arightarrow Btimes C$ with $f(0)=(1,0)$ and $f(1)=(1,1)$.
Then $f_1(0) = pi_1f (0) = pi_1(1,0) = 1$ and $f_2(1)=pi_2f(1) = pi_2(1,1)=1$.
Moreover, $f_2(0) =pi_2f(0) = pi_2(1,0)=0$ and $f_2(1)=pi_2f(1)=pi_2(1,1)=1$.
answered Jan 17 at 15:57
WuestenfuxWuestenfux
4,7311513
$endgroup$
$begingroup$
What do you mean by $pi_1f$?
$endgroup$
– C. Cristi
Jan 17 at 16:35
$begingroup$
Function composition
$endgroup$
– Wuestenfux
Jan 17 at 16:37
$begingroup$
Okay and why $pi_1 f(a)=pi_1(b,c)$?
$endgroup$
– C. Cristi
Jan 17 at 16:40
$begingroup$
What I mean is, can you add more detail and maybe provide the intuition behind all this?
$endgroup$
– C. Cristi
Jan 17 at 16:40
$begingroup$
Added simple example.
$endgroup$
– Wuestenfux
Jan 18 at 11:28
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f3077135%2fshow-that-2-sets-have-the-same-number-of-elements%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
In general, the way you can proof two sets $X,Y$ are equipotent is by finding a bijection (i.e., a function that is injective and surjective) $h:Xto Y$ between them.
In this case, notice that an element of the set $(Btimes C)^A$ must be a function $f:Ato Btimes C$, and element by element it looks like $f(a)=(b,c)$. If we call $f_1(a)=b$ and $f_2(a)=c$ whenever $f(a)=(b,c)$, then there is a natural way to obtain an element of the set $B^Atimes C^A$ associated to $f$, namely the ordered pair $(f_1,f_2)$.
If you can show that the assignment
begin{align*}
h:&(Btimes C)^Alongrightarrow B^Atimes C^A\
& f longmapsto h(f)=(f_1,f_2)
end{align*}
is a bijection, you will be done.
answered Jan 17 at 15:52
Darío GDarío G
4,062613
$endgroup$
add a comment |
$begingroup$
In general, the way you can proof two sets $X,Y$ are equipotent is by finding a bijection (i.e., a function that is injective and surjective) $h:Xto Y$ between them.
In this case, notice that an element of the set $(Btimes C)^A$ must be a function $f:Ato Btimes C$, and element by element it looks like $f(a)=(b,c)$. If we call $f_1(a)=b$ and $f_2(a)=c$ whenever $f(a)=(b,c)$, then there is a natural way to obtain an element of the set $B^Atimes C^A$ associated to $f$, namely the ordered pair $(f_1,f_2)$.
If you can show that the assignment
begin{align*}
h:&(Btimes C)^Alongrightarrow B^Atimes C^A\
& f longmapsto h(f)=(f_1,f_2)
end{align*}
is a bijection, you will be done.
answered Jan 17 at 15:52
Darío GDarío G
4,062613
$endgroup$
add a comment |
$begingroup$
In general, the way you can proof two sets $X,Y$ are equipotent is by finding a bijection (i.e., a function that is injective and surjective) $h:Xto Y$ between them.
In this case, notice that an element of the set $(Btimes C)^A$ must be a function $f:Ato Btimes C$, and element by element it looks like $f(a)=(b,c)$. If we call $f_1(a)=b$ and $f_2(a)=c$ whenever $f(a)=(b,c)$, then there is a natural way to obtain an element of the set $B^Atimes C^A$ associated to $f$, namely the ordered pair $(f_1,f_2)$.
If you can show that the assignment
begin{align*}
h:&(Btimes C)^Alongrightarrow B^Atimes C^A\
& f longmapsto h(f)=(f_1,f_2)
end{align*}
is a bijection, you will be done.
answered Jan 17 at 15:52
Darío GDarío G
4,062613
$endgroup$
In general, the way you can proof two sets $X,Y$ are equipotent is by finding a bijection (i.e., a function that is injective and surjective) $h:Xto Y$ between them.
In this case, notice that an element of the set $(Btimes C)^A$ must be a function $f:Ato Btimes C$, and element by element it looks like $f(a)=(b,c)$. If we call $f_1(a)=b$ and $f_2(a)=c$ whenever $f(a)=(b,c)$, then there is a natural way to obtain an element of the set $B^Atimes C^A$ associated to $f$, namely the ordered pair $(f_1,f_2)$.
If you can show that the assignment
begin{align*}
h:&(Btimes C)^Alongrightarrow B^Atimes C^A\
& f longmapsto h(f)=(f_1,f_2)
end{align*}
is a bijection, you will be done.
answered Jan 17 at 15:52
Darío GDarío G
4,062613
answered Jan 17 at 15:52
Darío GDarío G
4,062613
answered Jan 17 at 15:52
Darío GDarío G
4,062613
answered Jan 17 at 15:52
Darío GDarío G
4,062613
4,062613
add a comment |
add a comment |
$begingroup$
We want to show a bijection $f$ exists with $operatorname{dom} f=B^Atimes C^A,,operatorname{rang} f=(Btimes C)^A$. The desired domain is the set of ordered pairs $(g,,h)$, with $g$ ($h$) a function from $A$ to $B$ ($C$). Meanwhile, the desired range is the set of functions from $A$ to ordered pairs $(b,,c)$ with $bin B,,cin C$. So it suffices to define $f((g,,h)):= xmapsto (g(x),,h(x))$.
answered Jan 17 at 15:52
J.G.J.G.
27.9k22843
$endgroup$
$begingroup$
Okay, so correct me if I'm wrong, but what you're saying is, is that $f:B^Atimes C^A to (Btimes C)^A, f(g(x),h(x))=(g(x),h(x))$, where $g:Ato B$ and $h: Ato C$, is the desired bijection which proves the equipotence of the sets?
$endgroup$
– C. Cristi
Jan 17 at 16:15
$begingroup$
What is the intuition behind the chosen function?
$endgroup$
– C. Cristi
Jan 17 at 16:15
$begingroup$
and your $f$ is bijective because...?
$endgroup$
– C. Cristi
Jan 17 at 16:16
$begingroup$
@C.Cristi Injective because changing $g$ or $h$ changes the result for at least one $x$, surjective because any ordered pair can be split to reverse-engineer $g,,h$. The intuition is: how do you pair pairs of functions with pair-valued functions?
$endgroup$
– J.G.
Jan 17 at 16:42
add a comment |
$begingroup$
We want to show a bijection $f$ exists with $operatorname{dom} f=B^Atimes C^A,,operatorname{rang} f=(Btimes C)^A$. The desired domain is the set of ordered pairs $(g,,h)$, with $g$ ($h$) a function from $A$ to $B$ ($C$). Meanwhile, the desired range is the set of functions from $A$ to ordered pairs $(b,,c)$ with $bin B,,cin C$. So it suffices to define $f((g,,h)):= xmapsto (g(x),,h(x))$.
answered Jan 17 at 15:52
J.G.J.G.
27.9k22843
$endgroup$
$begingroup$
Okay, so correct me if I'm wrong, but what you're saying is, is that $f:B^Atimes C^A to (Btimes C)^A, f(g(x),h(x))=(g(x),h(x))$, where $g:Ato B$ and $h: Ato C$, is the desired bijection which proves the equipotence of the sets?
$endgroup$
– C. Cristi
Jan 17 at 16:15
$begingroup$
What is the intuition behind the chosen function?
$endgroup$
– C. Cristi
Jan 17 at 16:15
$begingroup$
and your $f$ is bijective because...?
$endgroup$
– C. Cristi
Jan 17 at 16:16
$begingroup$
@C.Cristi Injective because changing $g$ or $h$ changes the result for at least one $x$, surjective because any ordered pair can be split to reverse-engineer $g,,h$. The intuition is: how do you pair pairs of functions with pair-valued functions?
$endgroup$
– J.G.
Jan 17 at 16:42
add a comment |
$begingroup$
We want to show a bijection $f$ exists with $operatorname{dom} f=B^Atimes C^A,,operatorname{rang} f=(Btimes C)^A$. The desired domain is the set of ordered pairs $(g,,h)$, with $g$ ($h$) a function from $A$ to $B$ ($C$). Meanwhile, the desired range is the set of functions from $A$ to ordered pairs $(b,,c)$ with $bin B,,cin C$. So it suffices to define $f((g,,h)):= xmapsto (g(x),,h(x))$.
answered Jan 17 at 15:52
J.G.J.G.
27.9k22843
$endgroup$
We want to show a bijection $f$ exists with $operatorname{dom} f=B^Atimes C^A,,operatorname{rang} f=(Btimes C)^A$. The desired domain is the set of ordered pairs $(g,,h)$, with $g$ ($h$) a function from $A$ to $B$ ($C$). Meanwhile, the desired range is the set of functions from $A$ to ordered pairs $(b,,c)$ with $bin B,,cin C$. So it suffices to define $f((g,,h)):= xmapsto (g(x),,h(x))$.
answered Jan 17 at 15:52
J.G.J.G.
27.9k22843
answered Jan 17 at 15:52
J.G.J.G.
27.9k22843
answered Jan 17 at 15:52
J.G.J.G.
27.9k22843
answered Jan 17 at 15:52
J.G.J.G.
27.9k22843
27.9k22843
$begingroup$
Okay, so correct me if I'm wrong, but what you're saying is, is that $f:B^Atimes C^A to (Btimes C)^A, f(g(x),h(x))=(g(x),h(x))$, where $g:Ato B$ and $h: Ato C$, is the desired bijection which proves the equipotence of the sets?
$endgroup$
– C. Cristi
Jan 17 at 16:15
$begingroup$
What is the intuition behind the chosen function?
$endgroup$
– C. Cristi
Jan 17 at 16:15
$begingroup$
and your $f$ is bijective because...?
$endgroup$
– C. Cristi
Jan 17 at 16:16
$begingroup$
@C.Cristi Injective because changing $g$ or $h$ changes the result for at least one $x$, surjective because any ordered pair can be split to reverse-engineer $g,,h$. The intuition is: how do you pair pairs of functions with pair-valued functions?
$endgroup$
– J.G.
Jan 17 at 16:42
add a comment |
$begingroup$
Okay, so correct me if I'm wrong, but what you're saying is, is that $f:B^Atimes C^A to (Btimes C)^A, f(g(x),h(x))=(g(x),h(x))$, where $g:Ato B$ and $h: Ato C$, is the desired bijection which proves the equipotence of the sets?
$endgroup$
– C. Cristi
Jan 17 at 16:15
$begingroup$
What is the intuition behind the chosen function?
$endgroup$
– C. Cristi
Jan 17 at 16:15
$begingroup$
and your $f$ is bijective because...?
$endgroup$
– C. Cristi
Jan 17 at 16:16
$begingroup$
@C.Cristi Injective because changing $g$ or $h$ changes the result for at least one $x$, surjective because any ordered pair can be split to reverse-engineer $g,,h$. The intuition is: how do you pair pairs of functions with pair-valued functions?
$endgroup$
– J.G.
Jan 17 at 16:42
$begingroup$
Okay, so correct me if I'm wrong, but what you're saying is, is that $f:B^Atimes C^A to (Btimes C)^A, f(g(x),h(x))=(g(x),h(x))$, where $g:Ato B$ and $h: Ato C$, is the desired bijection which proves the equipotence of the sets?
$endgroup$
– C. Cristi
Jan 17 at 16:15
$begingroup$
Okay, so correct me if I'm wrong, but what you're saying is, is that $f:B^Atimes C^A to (Btimes C)^A, f(g(x),h(x))=(g(x),h(x))$, where $g:Ato B$ and $h: Ato C$, is the desired bijection which proves the equipotence of the sets?
$endgroup$
– C. Cristi
Jan 17 at 16:15
$begingroup$
What is the intuition behind the chosen function?
$endgroup$
– C. Cristi
Jan 17 at 16:15
$begingroup$
What is the intuition behind the chosen function?
$endgroup$
– C. Cristi
Jan 17 at 16:15
$begingroup$
and your $f$ is bijective because...?
$endgroup$
– C. Cristi
Jan 17 at 16:16
$begingroup$
and your $f$ is bijective because...?
$endgroup$
– C. Cristi
Jan 17 at 16:16
$begingroup$
@C.Cristi Injective because changing $g$ or $h$ changes the result for at least one $x$, surjective because any ordered pair can be split to reverse-engineer $g,,h$. The intuition is: how do you pair pairs of functions with pair-valued functions?
$endgroup$
– J.G.
Jan 17 at 16:42
$begingroup$
@C.Cristi Injective because changing $g$ or $h$ changes the result for at least one $x$, surjective because any ordered pair can be split to reverse-engineer $g,,h$. The intuition is: how do you pair pairs of functions with pair-valued functions?
$endgroup$
– J.G.
Jan 17 at 16:42
add a comment |
$begingroup$
Let $F : B^A times C^A rightarrow (Btimes C)^A$ be defined by
$$F((f,g)) : A rightarrow(B times C)$$
$$F((f,g)) (a) = (f(a),g(a))$$
for all $a in A$.
$F$ is injective:
All $(f_1,g_1),(f_2,g_2) in B^A times C^A$ with
$$F((f_1,g_1)) = F((f_2,g_2))$$
implies that
$$(f_1(a),g_1(a)) = (f_2(a),g_2(a))$$
for all $a in A$, by definition of the ordered pair. Thus,
$$(f_1,g_1) = (f_2,g_2)$$ so $F$ is injective.
F is surjective:
If $h in (B times C)^A$, then define $(f,g)$ by
$$ (f,g) = (pi_1circ h, pi_2 circ h)$$
where $pi_1$ and $pi_2$ are the projections. See that
$$F((f,g))(a) = (f(a),g(a)) = (pi_1(h(a)),pi_2(h(a))) = h(a)$$
so $F((f,g)) = h$ and hence $F$ is surjective.
Thus $F$ is bijective, so the sets have the same size.
answered Jan 18 at 17:38
MetricMetric
1,23649
$endgroup$
$begingroup$
That is an awesome proof! What was the intuition behind it and why you picked that function that certain way?
$endgroup$
– C. Cristi
Jan 18 at 21:25
$begingroup$
For $(f,g) in B^A times C^A$ I know it's required that $F((f,g)) : A rightarrow (B times C)$. So, how would I define $F((f,g))$? I know that it takes an $a in A$, and produces something in $B times C$. What do I have to work with? I have $f : A rightarrow B$ and $g : A rightarrow C$, so from the domain and codomain of these maps alone, a first guess would be to write $F((f,g))(a) = (f(a),g(a))$, and then I simply checked injectivity and surjectivity. The intuition came simply from the domain and codomain of the maps I had to work with.
$endgroup$
– Metric
Jan 19 at 0:47
$begingroup$
Of course this style doesn't work in general, but it does offer some initial guesses and builds intuition for the map your looking for.
$endgroup$
– Metric
Jan 19 at 0:53
add a comment |
$begingroup$
Let $F : B^A times C^A rightarrow (Btimes C)^A$ be defined by
$$F((f,g)) : A rightarrow(B times C)$$
$$F((f,g)) (a) = (f(a),g(a))$$
for all $a in A$.
$F$ is injective:
All $(f_1,g_1),(f_2,g_2) in B^A times C^A$ with
$$F((f_1,g_1)) = F((f_2,g_2))$$
implies that
$$(f_1(a),g_1(a)) = (f_2(a),g_2(a))$$
for all $a in A$, by definition of the ordered pair. Thus,
$$(f_1,g_1) = (f_2,g_2)$$ so $F$ is injective.
F is surjective:
If $h in (B times C)^A$, then define $(f,g)$ by
$$ (f,g) = (pi_1circ h, pi_2 circ h)$$
where $pi_1$ and $pi_2$ are the projections. See that
$$F((f,g))(a) = (f(a),g(a)) = (pi_1(h(a)),pi_2(h(a))) = h(a)$$
so $F((f,g)) = h$ and hence $F$ is surjective.
Thus $F$ is bijective, so the sets have the same size.
answered Jan 18 at 17:38
MetricMetric
1,23649
$endgroup$
$begingroup$
That is an awesome proof! What was the intuition behind it and why you picked that function that certain way?
$endgroup$
– C. Cristi
Jan 18 at 21:25
$begingroup$
For $(f,g) in B^A times C^A$ I know it's required that $F((f,g)) : A rightarrow (B times C)$. So, how would I define $F((f,g))$? I know that it takes an $a in A$, and produces something in $B times C$. What do I have to work with? I have $f : A rightarrow B$ and $g : A rightarrow C$, so from the domain and codomain of these maps alone, a first guess would be to write $F((f,g))(a) = (f(a),g(a))$, and then I simply checked injectivity and surjectivity. The intuition came simply from the domain and codomain of the maps I had to work with.
$endgroup$
– Metric
Jan 19 at 0:47
$begingroup$
Of course this style doesn't work in general, but it does offer some initial guesses and builds intuition for the map your looking for.
$endgroup$
– Metric
Jan 19 at 0:53
add a comment |
$begingroup$
Let $F : B^A times C^A rightarrow (Btimes C)^A$ be defined by
$$F((f,g)) : A rightarrow(B times C)$$
$$F((f,g)) (a) = (f(a),g(a))$$
for all $a in A$.
$F$ is injective:
All $(f_1,g_1),(f_2,g_2) in B^A times C^A$ with
$$F((f_1,g_1)) = F((f_2,g_2))$$
implies that
$$(f_1(a),g_1(a)) = (f_2(a),g_2(a))$$
for all $a in A$, by definition of the ordered pair. Thus,
$$(f_1,g_1) = (f_2,g_2)$$ so $F$ is injective.
F is surjective:
If $h in (B times C)^A$, then define $(f,g)$ by
$$ (f,g) = (pi_1circ h, pi_2 circ h)$$
where $pi_1$ and $pi_2$ are the projections. See that
$$F((f,g))(a) = (f(a),g(a)) = (pi_1(h(a)),pi_2(h(a))) = h(a)$$
so $F((f,g)) = h$ and hence $F$ is surjective.
Thus $F$ is bijective, so the sets have the same size.
answered Jan 18 at 17:38
MetricMetric
1,23649
$endgroup$
Let $F : B^A times C^A rightarrow (Btimes C)^A$ be defined by
$$F((f,g)) : A rightarrow(B times C)$$
$$F((f,g)) (a) = (f(a),g(a))$$
for all $a in A$.
$F$ is injective:
All $(f_1,g_1),(f_2,g_2) in B^A times C^A$ with
$$F((f_1,g_1)) = F((f_2,g_2))$$
implies that
$$(f_1(a),g_1(a)) = (f_2(a),g_2(a))$$
for all $a in A$, by definition of the ordered pair. Thus,
$$(f_1,g_1) = (f_2,g_2)$$ so $F$ is injective.
F is surjective:
If $h in (B times C)^A$, then define $(f,g)$ by
$$ (f,g) = (pi_1circ h, pi_2 circ h)$$
where $pi_1$ and $pi_2$ are the projections. See that
$$F((f,g))(a) = (f(a),g(a)) = (pi_1(h(a)),pi_2(h(a))) = h(a)$$
so $F((f,g)) = h$ and hence $F$ is surjective.
Thus $F$ is bijective, so the sets have the same size.
answered Jan 18 at 17:38
MetricMetric
1,23649
answered Jan 18 at 17:38
MetricMetric
1,23649
answered Jan 18 at 17:38
MetricMetric
1,23649
answered Jan 18 at 17:38
MetricMetric
1,23649
1,23649
$begingroup$
That is an awesome proof! What was the intuition behind it and why you picked that function that certain way?
$endgroup$
– C. Cristi
Jan 18 at 21:25
$begingroup$
For $(f,g) in B^A times C^A$ I know it's required that $F((f,g)) : A rightarrow (B times C)$. So, how would I define $F((f,g))$? I know that it takes an $a in A$, and produces something in $B times C$. What do I have to work with? I have $f : A rightarrow B$ and $g : A rightarrow C$, so from the domain and codomain of these maps alone, a first guess would be to write $F((f,g))(a) = (f(a),g(a))$, and then I simply checked injectivity and surjectivity. The intuition came simply from the domain and codomain of the maps I had to work with.
$endgroup$
– Metric
Jan 19 at 0:47
$begingroup$
Of course this style doesn't work in general, but it does offer some initial guesses and builds intuition for the map your looking for.
$endgroup$
– Metric
Jan 19 at 0:53
add a comment |
$begingroup$
That is an awesome proof! What was the intuition behind it and why you picked that function that certain way?
$endgroup$
– C. Cristi
Jan 18 at 21:25
$begingroup$
For $(f,g) in B^A times C^A$ I know it's required that $F((f,g)) : A rightarrow (B times C)$. So, how would I define $F((f,g))$? I know that it takes an $a in A$, and produces something in $B times C$. What do I have to work with? I have $f : A rightarrow B$ and $g : A rightarrow C$, so from the domain and codomain of these maps alone, a first guess would be to write $F((f,g))(a) = (f(a),g(a))$, and then I simply checked injectivity and surjectivity. The intuition came simply from the domain and codomain of the maps I had to work with.
$endgroup$
– Metric
Jan 19 at 0:47
$begingroup$
Of course this style doesn't work in general, but it does offer some initial guesses and builds intuition for the map your looking for.
$endgroup$
– Metric
Jan 19 at 0:53
$begingroup$
That is an awesome proof! What was the intuition behind it and why you picked that function that certain way?
$endgroup$
– C. Cristi
Jan 18 at 21:25
$begingroup$
That is an awesome proof! What was the intuition behind it and why you picked that function that certain way?
$endgroup$
– C. Cristi
Jan 18 at 21:25
$begingroup$
For $(f,g) in B^A times C^A$ I know it's required that $F((f,g)) : A rightarrow (B times C)$. So, how would I define $F((f,g))$? I know that it takes an $a in A$, and produces something in $B times C$. What do I have to work with? I have $f : A rightarrow B$ and $g : A rightarrow C$, so from the domain and codomain of these maps alone, a first guess would be to write $F((f,g))(a) = (f(a),g(a))$, and then I simply checked injectivity and surjectivity. The intuition came simply from the domain and codomain of the maps I had to work with.
$endgroup$
– Metric
Jan 19 at 0:47
$begingroup$
For $(f,g) in B^A times C^A$ I know it's required that $F((f,g)) : A rightarrow (B times C)$. So, how would I define $F((f,g))$? I know that it takes an $a in A$, and produces something in $B times C$. What do I have to work with? I have $f : A rightarrow B$ and $g : A rightarrow C$, so from the domain and codomain of these maps alone, a first guess would be to write $F((f,g))(a) = (f(a),g(a))$, and then I simply checked injectivity and surjectivity. The intuition came simply from the domain and codomain of the maps I had to work with.
$endgroup$
– Metric
Jan 19 at 0:47
$begingroup$
Of course this style doesn't work in general, but it does offer some initial guesses and builds intuition for the map your looking for.
$endgroup$
– Metric
Jan 19 at 0:53
$begingroup$
Of course this style doesn't work in general, but it does offer some initial guesses and builds intuition for the map your looking for.
$endgroup$
– Metric
Jan 19 at 0:53
add a comment |
$begingroup$
Consider the projections $pi_1:Btimes Crightarrow B$ and $pi_2:Btimes Crightarrow C$ onto the components.
Then for a given function $f:Arightarrow Btimes C$, define $f_1=pi_1 f$ and $f_2=pi_2f$ with $f_1(a) = pi_1 f(a)= pi_1(b,c)=b$ and $f_2(a)=pi_2f(a) = pi_2(b,c)=c$.
The assignment $fmapsto (pi_1f,pi_2f)$ provides the required bijection.
For instance, take $A=B=C={0,1}$ and the function $f:Arightarrow Btimes C$ with $f(0)=(1,0)$ and $f(1)=(1,1)$.
Then $f_1(0) = pi_1f (0) = pi_1(1,0) = 1$ and $f_2(1)=pi_2f(1) = pi_2(1,1)=1$.
Moreover, $f_2(0) =pi_2f(0) = pi_2(1,0)=0$ and $f_2(1)=pi_2f(1)=pi_2(1,1)=1$.
answered Jan 17 at 15:57
WuestenfuxWuestenfux
4,7311513
$endgroup$
$begingroup$
What do you mean by $pi_1f$?
$endgroup$
– C. Cristi
Jan 17 at 16:35
$begingroup$
Function composition
$endgroup$
– Wuestenfux
Jan 17 at 16:37
$begingroup$
Okay and why $pi_1 f(a)=pi_1(b,c)$?
$endgroup$
– C. Cristi
Jan 17 at 16:40
$begingroup$
What I mean is, can you add more detail and maybe provide the intuition behind all this?
$endgroup$
– C. Cristi
Jan 17 at 16:40
$begingroup$
Added simple example.
$endgroup$
– Wuestenfux
Jan 18 at 11:28
add a comment |
$begingroup$
Consider the projections $pi_1:Btimes Crightarrow B$ and $pi_2:Btimes Crightarrow C$ onto the components.
Then for a given function $f:Arightarrow Btimes C$, define $f_1=pi_1 f$ and $f_2=pi_2f$ with $f_1(a) = pi_1 f(a)= pi_1(b,c)=b$ and $f_2(a)=pi_2f(a) = pi_2(b,c)=c$.
The assignment $fmapsto (pi_1f,pi_2f)$ provides the required bijection.
For instance, take $A=B=C={0,1}$ and the function $f:Arightarrow Btimes C$ with $f(0)=(1,0)$ and $f(1)=(1,1)$.
Then $f_1(0) = pi_1f (0) = pi_1(1,0) = 1$ and $f_2(1)=pi_2f(1) = pi_2(1,1)=1$.
Moreover, $f_2(0) =pi_2f(0) = pi_2(1,0)=0$ and $f_2(1)=pi_2f(1)=pi_2(1,1)=1$.
answered Jan 17 at 15:57
WuestenfuxWuestenfux
4,7311513
$endgroup$
$begingroup$
What do you mean by $pi_1f$?
$endgroup$
– C. Cristi
Jan 17 at 16:35
$begingroup$
Function composition
$endgroup$
– Wuestenfux
Jan 17 at 16:37
$begingroup$
Okay and why $pi_1 f(a)=pi_1(b,c)$?
$endgroup$
– C. Cristi
Jan 17 at 16:40
$begingroup$
What I mean is, can you add more detail and maybe provide the intuition behind all this?
$endgroup$
– C. Cristi
Jan 17 at 16:40
$begingroup$
Added simple example.
$endgroup$
– Wuestenfux
Jan 18 at 11:28
add a comment |
$begingroup$
Consider the projections $pi_1:Btimes Crightarrow B$ and $pi_2:Btimes Crightarrow C$ onto the components.
Then for a given function $f:Arightarrow Btimes C$, define $f_1=pi_1 f$ and $f_2=pi_2f$ with $f_1(a) = pi_1 f(a)= pi_1(b,c)=b$ and $f_2(a)=pi_2f(a) = pi_2(b,c)=c$.
The assignment $fmapsto (pi_1f,pi_2f)$ provides the required bijection.
For instance, take $A=B=C={0,1}$ and the function $f:Arightarrow Btimes C$ with $f(0)=(1,0)$ and $f(1)=(1,1)$.
Then $f_1(0) = pi_1f (0) = pi_1(1,0) = 1$ and $f_2(1)=pi_2f(1) = pi_2(1,1)=1$.
Moreover, $f_2(0) =pi_2f(0) = pi_2(1,0)=0$ and $f_2(1)=pi_2f(1)=pi_2(1,1)=1$.
answered Jan 17 at 15:57
WuestenfuxWuestenfux
4,7311513
$endgroup$
Consider the projections $pi_1:Btimes Crightarrow B$ and $pi_2:Btimes Crightarrow C$ onto the components.
Then for a given function $f:Arightarrow Btimes C$, define $f_1=pi_1 f$ and $f_2=pi_2f$ with $f_1(a) = pi_1 f(a)= pi_1(b,c)=b$ and $f_2(a)=pi_2f(a) = pi_2(b,c)=c$.
The assignment $fmapsto (pi_1f,pi_2f)$ provides the required bijection.
For instance, take $A=B=C={0,1}$ and the function $f:Arightarrow Btimes C$ with $f(0)=(1,0)$ and $f(1)=(1,1)$.
Then $f_1(0) = pi_1f (0) = pi_1(1,0) = 1$ and $f_2(1)=pi_2f(1) = pi_2(1,1)=1$.
Moreover, $f_2(0) =pi_2f(0) = pi_2(1,0)=0$ and $f_2(1)=pi_2f(1)=pi_2(1,1)=1$.
answered Jan 17 at 15:57
WuestenfuxWuestenfux
4,7311513
edited Jan 18 at 11:27
answered Jan 17 at 15:57
WuestenfuxWuestenfux
4,7311513
answered Jan 17 at 15:57
WuestenfuxWuestenfux
4,7311513
answered Jan 17 at 15:57
WuestenfuxWuestenfux
4,7311513
4,7311513
$begingroup$
What do you mean by $pi_1f$?
$endgroup$
– C. Cristi
Jan 17 at 16:35
$begingroup$
Function composition
$endgroup$
– Wuestenfux
Jan 17 at 16:37
$begingroup$
Okay and why $pi_1 f(a)=pi_1(b,c)$?
$endgroup$
– C. Cristi
Jan 17 at 16:40
$begingroup$
What I mean is, can you add more detail and maybe provide the intuition behind all this?
$endgroup$
– C. Cristi
Jan 17 at 16:40
$begingroup$
Added simple example.
$endgroup$
– Wuestenfux
Jan 18 at 11:28
add a comment |
$begingroup$
What do you mean by $pi_1f$?
$endgroup$
– C. Cristi
Jan 17 at 16:35
$begingroup$
Function composition
$endgroup$
– Wuestenfux
Jan 17 at 16:37
$begingroup$
Okay and why $pi_1 f(a)=pi_1(b,c)$?
$endgroup$
– C. Cristi
Jan 17 at 16:40
$begingroup$
What I mean is, can you add more detail and maybe provide the intuition behind all this?
$endgroup$
– C. Cristi
Jan 17 at 16:40
$begingroup$
Added simple example.
$endgroup$
– Wuestenfux
Jan 18 at 11:28
$begingroup$
What do you mean by $pi_1f$?
$endgroup$
– C. Cristi
Jan 17 at 16:35
$begingroup$
What do you mean by $pi_1f$?
$endgroup$
– C. Cristi
Jan 17 at 16:35
$begingroup$
Function composition
$endgroup$
– Wuestenfux
Jan 17 at 16:37
$begingroup$
Function composition
$endgroup$
– Wuestenfux
Jan 17 at 16:37
$begingroup$
Okay and why $pi_1 f(a)=pi_1(b,c)$?
$endgroup$
– C. Cristi
Jan 17 at 16:40
$begingroup$
Okay and why $pi_1 f(a)=pi_1(b,c)$?
$endgroup$
– C. Cristi
Jan 17 at 16:40
$begingroup$
What I mean is, can you add more detail and maybe provide the intuition behind all this?
$endgroup$
– C. Cristi
Jan 17 at 16:40
$begingroup$
What I mean is, can you add more detail and maybe provide the intuition behind all this?
$endgroup$
– C. Cristi
Jan 17 at 16:40
$begingroup$
Added simple example.
$endgroup$
– Wuestenfux
Jan 18 at 11:28
$begingroup$
Added simple example.
$endgroup$
– Wuestenfux
Jan 18 at 11:28
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.
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%2f3077135%2fshow-that-2-sets-have-the-same-number-of-elements%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
$begingroup$
The english equivalent of "echipotenta" is "equipotent".
$endgroup$
– Servaes
Jan 17 at 15:47
1
$begingroup$
By definition, two sets have the same number of elements if there is a bijection between them.
$endgroup$
– Wojowu
Jan 17 at 15:48
$begingroup$
@Servaes Oh, I'm sorry.. I tried to google translate it but haven't found anything and also Wikipedia the page in my language then convert it to English and and still haven't found a thing, thanks!
$endgroup$
– C. Cristi
Jan 17 at 15:49