Prove that if sets $A$ and $B$ are finite, then $|Atimes B| = |A|cdot|B|$.
$begingroup$
Prove that if sets $A$ and $B$ are finite, then $|Atimes B| = |A|cdot|B|$.
I started to show that if $B$ is a singleton ${b}$, then
$|Atimes B| = |Atimes {b}|=|A|.$ Then, if $B = {b_1, b_2, dots, b_n}$ for $ninmathbb{N}$, so
$Atimes B = bigcuplimits_{i=1}^{n} (Atimes {b_i})$.
My question is what should I do next? I though about showing that
$A = {a_1, a_2,dots, a_m}$, but I do not know how to "connect" it with $|Atimes B|$ and then with $|A|cdot|B|$, to get the final result.
elementary-set-theory
asked Jan 12 at 0:05
whiskeyowhiskeyo
1368
$endgroup$
add a comment |
$begingroup$
Prove that if sets $A$ and $B$ are finite, then $|Atimes B| = |A|cdot|B|$.
I started to show that if $B$ is a singleton ${b}$, then
$|Atimes B| = |Atimes {b}|=|A|.$ Then, if $B = {b_1, b_2, dots, b_n}$ for $ninmathbb{N}$, so
$Atimes B = bigcuplimits_{i=1}^{n} (Atimes {b_i})$.
My question is what should I do next? I though about showing that
$A = {a_1, a_2,dots, a_m}$, but I do not know how to "connect" it with $|Atimes B|$ and then with $|A|cdot|B|$, to get the final result.
elementary-set-theory
asked Jan 12 at 0:05
whiskeyowhiskeyo
1368
$endgroup$
6
$begingroup$
You're essentially done (apart form the typoe: $Atimes B = cup_{i=1}^n (A times {b_i})$, not $|Atimes B$: that's just a number): your union is disjoint, so $|Atimes B| = sum_{i=1}^n|A times {b_i} = sum_{i=1}^n|A| = n|A| = |B|cdot|A| = |A|cdot|B|$.
$endgroup$
– user3482749
Jan 12 at 0:10
$begingroup$
So is the part $A={a_1,a_2,dots,a_m}$ unnecessary?
$endgroup$
– whiskeyo
Jan 12 at 0:17
1
$begingroup$
Did you prove that the cardinality of a finite fisjoint union is the sum of the cardinalities?
$endgroup$
– Math_QED
Jan 12 at 0:19
$begingroup$
No, I did not prove it.
$endgroup$
– whiskeyo
Jan 12 at 0:22
$begingroup$
To answer your question in the comments, it is necessary to include that to help show that the cardinality of $A$ is $m$ and the cardinality of $A times B$ is the cardinality of $A$ added up $n$ times. And as for the proof of cardinality of finite disjoint union, this link will be of some help
$endgroup$
– WaveX
Jan 12 at 1:03
add a comment |
$begingroup$
Prove that if sets $A$ and $B$ are finite, then $|Atimes B| = |A|cdot|B|$.
I started to show that if $B$ is a singleton ${b}$, then
$|Atimes B| = |Atimes {b}|=|A|.$ Then, if $B = {b_1, b_2, dots, b_n}$ for $ninmathbb{N}$, so
$Atimes B = bigcuplimits_{i=1}^{n} (Atimes {b_i})$.
My question is what should I do next? I though about showing that
$A = {a_1, a_2,dots, a_m}$, but I do not know how to "connect" it with $|Atimes B|$ and then with $|A|cdot|B|$, to get the final result.
elementary-set-theory
asked Jan 12 at 0:05
whiskeyowhiskeyo
1368
$endgroup$
Prove that if sets $A$ and $B$ are finite, then $|Atimes B| = |A|cdot|B|$.
I started to show that if $B$ is a singleton ${b}$, then
$|Atimes B| = |Atimes {b}|=|A|.$ Then, if $B = {b_1, b_2, dots, b_n}$ for $ninmathbb{N}$, so
$Atimes B = bigcuplimits_{i=1}^{n} (Atimes {b_i})$.
My question is what should I do next? I though about showing that
$A = {a_1, a_2,dots, a_m}$, but I do not know how to "connect" it with $|Atimes B|$ and then with $|A|cdot|B|$, to get the final result.
elementary-set-theory
elementary-set-theory
asked Jan 12 at 0:05
whiskeyowhiskeyo
1368
asked Jan 12 at 0:05
whiskeyowhiskeyo
1368
edited Jan 12 at 0:15
whiskeyo
asked Jan 12 at 0:05
whiskeyowhiskeyo
1368
asked Jan 12 at 0:05
whiskeyowhiskeyo
1368
asked Jan 12 at 0:05
whiskeyowhiskeyo
1368
1368
6
$begingroup$
You're essentially done (apart form the typoe: $Atimes B = cup_{i=1}^n (A times {b_i})$, not $|Atimes B$: that's just a number): your union is disjoint, so $|Atimes B| = sum_{i=1}^n|A times {b_i} = sum_{i=1}^n|A| = n|A| = |B|cdot|A| = |A|cdot|B|$.
$endgroup$
– user3482749
Jan 12 at 0:10
$begingroup$
So is the part $A={a_1,a_2,dots,a_m}$ unnecessary?
$endgroup$
– whiskeyo
Jan 12 at 0:17
1
$begingroup$
Did you prove that the cardinality of a finite fisjoint union is the sum of the cardinalities?
$endgroup$
– Math_QED
Jan 12 at 0:19
$begingroup$
No, I did not prove it.
$endgroup$
– whiskeyo
Jan 12 at 0:22
$begingroup$
To answer your question in the comments, it is necessary to include that to help show that the cardinality of $A$ is $m$ and the cardinality of $A times B$ is the cardinality of $A$ added up $n$ times. And as for the proof of cardinality of finite disjoint union, this link will be of some help
$endgroup$
– WaveX
Jan 12 at 1:03
add a comment |
6
$begingroup$
You're essentially done (apart form the typoe: $Atimes B = cup_{i=1}^n (A times {b_i})$, not $|Atimes B$: that's just a number): your union is disjoint, so $|Atimes B| = sum_{i=1}^n|A times {b_i} = sum_{i=1}^n|A| = n|A| = |B|cdot|A| = |A|cdot|B|$.
$endgroup$
– user3482749
Jan 12 at 0:10
$begingroup$
So is the part $A={a_1,a_2,dots,a_m}$ unnecessary?
$endgroup$
– whiskeyo
Jan 12 at 0:17
1
$begingroup$
Did you prove that the cardinality of a finite fisjoint union is the sum of the cardinalities?
$endgroup$
– Math_QED
Jan 12 at 0:19
$begingroup$
No, I did not prove it.
$endgroup$
– whiskeyo
Jan 12 at 0:22
$begingroup$
To answer your question in the comments, it is necessary to include that to help show that the cardinality of $A$ is $m$ and the cardinality of $A times B$ is the cardinality of $A$ added up $n$ times. And as for the proof of cardinality of finite disjoint union, this link will be of some help
$endgroup$
– WaveX
Jan 12 at 1:03
6
6
$begingroup$
You're essentially done (apart form the typoe: $Atimes B = cup_{i=1}^n (A times {b_i})$, not $|Atimes B$: that's just a number): your union is disjoint, so $|Atimes B| = sum_{i=1}^n|A times {b_i} = sum_{i=1}^n|A| = n|A| = |B|cdot|A| = |A|cdot|B|$.
$endgroup$
– user3482749
Jan 12 at 0:10
$begingroup$
You're essentially done (apart form the typoe: $Atimes B = cup_{i=1}^n (A times {b_i})$, not $|Atimes B$: that's just a number): your union is disjoint, so $|Atimes B| = sum_{i=1}^n|A times {b_i} = sum_{i=1}^n|A| = n|A| = |B|cdot|A| = |A|cdot|B|$.
$endgroup$
– user3482749
Jan 12 at 0:10
$begingroup$
So is the part $A={a_1,a_2,dots,a_m}$ unnecessary?
$endgroup$
– whiskeyo
Jan 12 at 0:17
$begingroup$
So is the part $A={a_1,a_2,dots,a_m}$ unnecessary?
$endgroup$
– whiskeyo
Jan 12 at 0:17
1
1
$begingroup$
Did you prove that the cardinality of a finite fisjoint union is the sum of the cardinalities?
$endgroup$
– Math_QED
Jan 12 at 0:19
$begingroup$
Did you prove that the cardinality of a finite fisjoint union is the sum of the cardinalities?
$endgroup$
– Math_QED
Jan 12 at 0:19
$begingroup$
No, I did not prove it.
$endgroup$
– whiskeyo
Jan 12 at 0:22
$begingroup$
No, I did not prove it.
$endgroup$
– whiskeyo
Jan 12 at 0:22
$begingroup$
To answer your question in the comments, it is necessary to include that to help show that the cardinality of $A$ is $m$ and the cardinality of $A times B$ is the cardinality of $A$ added up $n$ times. And as for the proof of cardinality of finite disjoint union, this link will be of some help
$endgroup$
– WaveX
Jan 12 at 1:03
$begingroup$
To answer your question in the comments, it is necessary to include that to help show that the cardinality of $A$ is $m$ and the cardinality of $A times B$ is the cardinality of $A$ added up $n$ times. And as for the proof of cardinality of finite disjoint union, this link will be of some help
$endgroup$
– WaveX
Jan 12 at 1:03
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
One possible way:
Show first that if $X$ and $Y$ are disjoint, then the size of their union is $lvert X rvert + lvert Y rvert$. Use this fact to prove your assertion by using induction on the size of $B$:
Firstly, we have your (very useful!) result here:
$$A times B = bigcup_{i=1}^n ( A times {b_i})$$
The base case where the size of $lvert B rvert$ is $1$ is proven already, as you've shown in your post. Suppose the size of $lvert B rvert$ is $n$. Then, by using your useful result and the inductive hypothesis:
$$ lvert A times B rvert = lvert bigcup_{i=1}^n(A times {b_i}) rvert = lvert bigcup_{i=1}^{n-1}(Atimes {b_i})cup(A times {b_n}) rvert = $$
$$lvert A rvert (n-1) + lvert A rvert = lvert A rvert n = lvert A rvert cdot lvert B rvert$$
where we used the fact that the size of a disjoint union is the sum of their sizes.
answered Jan 12 at 18:17
MetricMetric
1,25159
$endgroup$
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%2f3070468%2fprove-that-if-sets-a-and-b-are-finite-then-a-times-b-a-cdotb%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
One possible way:
Show first that if $X$ and $Y$ are disjoint, then the size of their union is $lvert X rvert + lvert Y rvert$. Use this fact to prove your assertion by using induction on the size of $B$:
Firstly, we have your (very useful!) result here:
$$A times B = bigcup_{i=1}^n ( A times {b_i})$$
The base case where the size of $lvert B rvert$ is $1$ is proven already, as you've shown in your post. Suppose the size of $lvert B rvert$ is $n$. Then, by using your useful result and the inductive hypothesis:
$$ lvert A times B rvert = lvert bigcup_{i=1}^n(A times {b_i}) rvert = lvert bigcup_{i=1}^{n-1}(Atimes {b_i})cup(A times {b_n}) rvert = $$
$$lvert A rvert (n-1) + lvert A rvert = lvert A rvert n = lvert A rvert cdot lvert B rvert$$
where we used the fact that the size of a disjoint union is the sum of their sizes.
answered Jan 12 at 18:17
MetricMetric
1,25159
$endgroup$
add a comment |
$begingroup$
One possible way:
Show first that if $X$ and $Y$ are disjoint, then the size of their union is $lvert X rvert + lvert Y rvert$. Use this fact to prove your assertion by using induction on the size of $B$:
Firstly, we have your (very useful!) result here:
$$A times B = bigcup_{i=1}^n ( A times {b_i})$$
The base case where the size of $lvert B rvert$ is $1$ is proven already, as you've shown in your post. Suppose the size of $lvert B rvert$ is $n$. Then, by using your useful result and the inductive hypothesis:
$$ lvert A times B rvert = lvert bigcup_{i=1}^n(A times {b_i}) rvert = lvert bigcup_{i=1}^{n-1}(Atimes {b_i})cup(A times {b_n}) rvert = $$
$$lvert A rvert (n-1) + lvert A rvert = lvert A rvert n = lvert A rvert cdot lvert B rvert$$
where we used the fact that the size of a disjoint union is the sum of their sizes.
answered Jan 12 at 18:17
MetricMetric
1,25159
$endgroup$
add a comment |
$begingroup$
One possible way:
Show first that if $X$ and $Y$ are disjoint, then the size of their union is $lvert X rvert + lvert Y rvert$. Use this fact to prove your assertion by using induction on the size of $B$:
Firstly, we have your (very useful!) result here:
$$A times B = bigcup_{i=1}^n ( A times {b_i})$$
The base case where the size of $lvert B rvert$ is $1$ is proven already, as you've shown in your post. Suppose the size of $lvert B rvert$ is $n$. Then, by using your useful result and the inductive hypothesis:
$$ lvert A times B rvert = lvert bigcup_{i=1}^n(A times {b_i}) rvert = lvert bigcup_{i=1}^{n-1}(Atimes {b_i})cup(A times {b_n}) rvert = $$
$$lvert A rvert (n-1) + lvert A rvert = lvert A rvert n = lvert A rvert cdot lvert B rvert$$
where we used the fact that the size of a disjoint union is the sum of their sizes.
answered Jan 12 at 18:17
MetricMetric
1,25159
$endgroup$
One possible way:
Show first that if $X$ and $Y$ are disjoint, then the size of their union is $lvert X rvert + lvert Y rvert$. Use this fact to prove your assertion by using induction on the size of $B$:
Firstly, we have your (very useful!) result here:
$$A times B = bigcup_{i=1}^n ( A times {b_i})$$
The base case where the size of $lvert B rvert$ is $1$ is proven already, as you've shown in your post. Suppose the size of $lvert B rvert$ is $n$. Then, by using your useful result and the inductive hypothesis:
$$ lvert A times B rvert = lvert bigcup_{i=1}^n(A times {b_i}) rvert = lvert bigcup_{i=1}^{n-1}(Atimes {b_i})cup(A times {b_n}) rvert = $$
$$lvert A rvert (n-1) + lvert A rvert = lvert A rvert n = lvert A rvert cdot lvert B rvert$$
where we used the fact that the size of a disjoint union is the sum of their sizes.
answered Jan 12 at 18:17
MetricMetric
1,25159
edited Jan 12 at 18:44
answered Jan 12 at 18:17
MetricMetric
1,25159
answered Jan 12 at 18:17
MetricMetric
1,25159
answered Jan 12 at 18:17
MetricMetric
1,25159
1,25159
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.
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%2f3070468%2fprove-that-if-sets-a-and-b-are-finite-then-a-times-b-a-cdotb%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
6
$begingroup$
You're essentially done (apart form the typoe: $Atimes B = cup_{i=1}^n (A times {b_i})$, not $|Atimes B$: that's just a number): your union is disjoint, so $|Atimes B| = sum_{i=1}^n|A times {b_i} = sum_{i=1}^n|A| = n|A| = |B|cdot|A| = |A|cdot|B|$.
$endgroup$
– user3482749
Jan 12 at 0:10
$begingroup$
So is the part $A={a_1,a_2,dots,a_m}$ unnecessary?
$endgroup$
– whiskeyo
Jan 12 at 0:17
1
$begingroup$
Did you prove that the cardinality of a finite fisjoint union is the sum of the cardinalities?
$endgroup$
– Math_QED
Jan 12 at 0:19
$begingroup$
No, I did not prove it.
$endgroup$
– whiskeyo
Jan 12 at 0:22
$begingroup$
To answer your question in the comments, it is necessary to include that to help show that the cardinality of $A$ is $m$ and the cardinality of $A times B$ is the cardinality of $A$ added up $n$ times. And as for the proof of cardinality of finite disjoint union, this link will be of some help
$endgroup$
– WaveX
Jan 12 at 1:03