Proving set identities: empty set case.
$begingroup$
I am currently refreshing my knowledge in naive set theory, and would like to prove that for all sets $A,B,C$ we have $$Acap(B cup C) = (A cap B) cup (A cap C).$$
I understand that this can be done by proving both $$Acap(B cup C) subset (A cap B) cup (A cap C) text{and} (A cap B) cup (A cap C) subset Acap(B cup C) $$ hold true.
We can do this by letting $x$ be an arbitrary element of $Acap(B cup C)$ and showing that it is an element of $(A cap B) cup (A cap C)$, and vice versa.
But what about when $A cap (B cup C)$ is the empty set? Then I would think we can't let $x$ be an arbitrary element of $A cap (B cup C)$ since there are none. However, I am aware that $A cap (B cup C) subset (A cap B) cup (A cap C)$ is trivially true in this case.
In the discrete mathematics course I took at my university, I did not see such cases be brought to attention. Should they be mentioned in proofs of such identities? Why / why not?
If so, some suggestions as to how to incorporate them into proofs would be helpful :-).
elementary-set-theory proof-writing
$endgroup$
add a comment |
$begingroup$
I am currently refreshing my knowledge in naive set theory, and would like to prove that for all sets $A,B,C$ we have $$Acap(B cup C) = (A cap B) cup (A cap C).$$
I understand that this can be done by proving both $$Acap(B cup C) subset (A cap B) cup (A cap C) text{and} (A cap B) cup (A cap C) subset Acap(B cup C) $$ hold true.
We can do this by letting $x$ be an arbitrary element of $Acap(B cup C)$ and showing that it is an element of $(A cap B) cup (A cap C)$, and vice versa.
But what about when $A cap (B cup C)$ is the empty set? Then I would think we can't let $x$ be an arbitrary element of $A cap (B cup C)$ since there are none. However, I am aware that $A cap (B cup C) subset (A cap B) cup (A cap C)$ is trivially true in this case.
In the discrete mathematics course I took at my university, I did not see such cases be brought to attention. Should they be mentioned in proofs of such identities? Why / why not?
If so, some suggestions as to how to incorporate them into proofs would be helpful :-).
elementary-set-theory proof-writing
$endgroup$
5
$begingroup$
Because some of the two sides being the empty set is no problem. Your claim is: for any element here, I prove it also is an element there. If there is no element at all then that is not your problem (mathematicalwise, of course): the proof still holds! Anyway, if you still feel something else must be done (though it really mustn't), then you can make a separate case: if this side is empty then so and so. and also the other side is, and the other way around, too. But you really don't need that,
$endgroup$
– DonAntonio
Dec 22 '18 at 18:35
$begingroup$
Words to live by: "vacuous truth". I am almost tempted to say this is a duplicate of many other questions that were asked before. For example, math.stackexchange.com/questions/734418/… math.stackexchange.com/questions/2723860/… math.stackexchange.com/questions/1953218/… and there are many others which are similar.
$endgroup$
– Asaf Karagila♦
Dec 23 '18 at 10:24
add a comment |
$begingroup$
I am currently refreshing my knowledge in naive set theory, and would like to prove that for all sets $A,B,C$ we have $$Acap(B cup C) = (A cap B) cup (A cap C).$$
I understand that this can be done by proving both $$Acap(B cup C) subset (A cap B) cup (A cap C) text{and} (A cap B) cup (A cap C) subset Acap(B cup C) $$ hold true.
We can do this by letting $x$ be an arbitrary element of $Acap(B cup C)$ and showing that it is an element of $(A cap B) cup (A cap C)$, and vice versa.
But what about when $A cap (B cup C)$ is the empty set? Then I would think we can't let $x$ be an arbitrary element of $A cap (B cup C)$ since there are none. However, I am aware that $A cap (B cup C) subset (A cap B) cup (A cap C)$ is trivially true in this case.
In the discrete mathematics course I took at my university, I did not see such cases be brought to attention. Should they be mentioned in proofs of such identities? Why / why not?
If so, some suggestions as to how to incorporate them into proofs would be helpful :-).
elementary-set-theory proof-writing
$endgroup$
I am currently refreshing my knowledge in naive set theory, and would like to prove that for all sets $A,B,C$ we have $$Acap(B cup C) = (A cap B) cup (A cap C).$$
I understand that this can be done by proving both $$Acap(B cup C) subset (A cap B) cup (A cap C) text{and} (A cap B) cup (A cap C) subset Acap(B cup C) $$ hold true.
We can do this by letting $x$ be an arbitrary element of $Acap(B cup C)$ and showing that it is an element of $(A cap B) cup (A cap C)$, and vice versa.
But what about when $A cap (B cup C)$ is the empty set? Then I would think we can't let $x$ be an arbitrary element of $A cap (B cup C)$ since there are none. However, I am aware that $A cap (B cup C) subset (A cap B) cup (A cap C)$ is trivially true in this case.
In the discrete mathematics course I took at my university, I did not see such cases be brought to attention. Should they be mentioned in proofs of such identities? Why / why not?
If so, some suggestions as to how to incorporate them into proofs would be helpful :-).
elementary-set-theory proof-writing
elementary-set-theory proof-writing
asked Dec 22 '18 at 18:24
E-muE-mu
767417
767417
5
$begingroup$
Because some of the two sides being the empty set is no problem. Your claim is: for any element here, I prove it also is an element there. If there is no element at all then that is not your problem (mathematicalwise, of course): the proof still holds! Anyway, if you still feel something else must be done (though it really mustn't), then you can make a separate case: if this side is empty then so and so. and also the other side is, and the other way around, too. But you really don't need that,
$endgroup$
– DonAntonio
Dec 22 '18 at 18:35
$begingroup$
Words to live by: "vacuous truth". I am almost tempted to say this is a duplicate of many other questions that were asked before. For example, math.stackexchange.com/questions/734418/… math.stackexchange.com/questions/2723860/… math.stackexchange.com/questions/1953218/… and there are many others which are similar.
$endgroup$
– Asaf Karagila♦
Dec 23 '18 at 10:24
add a comment |
5
$begingroup$
Because some of the two sides being the empty set is no problem. Your claim is: for any element here, I prove it also is an element there. If there is no element at all then that is not your problem (mathematicalwise, of course): the proof still holds! Anyway, if you still feel something else must be done (though it really mustn't), then you can make a separate case: if this side is empty then so and so. and also the other side is, and the other way around, too. But you really don't need that,
$endgroup$
– DonAntonio
Dec 22 '18 at 18:35
$begingroup$
Words to live by: "vacuous truth". I am almost tempted to say this is a duplicate of many other questions that were asked before. For example, math.stackexchange.com/questions/734418/… math.stackexchange.com/questions/2723860/… math.stackexchange.com/questions/1953218/… and there are many others which are similar.
$endgroup$
– Asaf Karagila♦
Dec 23 '18 at 10:24
5
5
$begingroup$
Because some of the two sides being the empty set is no problem. Your claim is: for any element here, I prove it also is an element there. If there is no element at all then that is not your problem (mathematicalwise, of course): the proof still holds! Anyway, if you still feel something else must be done (though it really mustn't), then you can make a separate case: if this side is empty then so and so. and also the other side is, and the other way around, too. But you really don't need that,
$endgroup$
– DonAntonio
Dec 22 '18 at 18:35
$begingroup$
Because some of the two sides being the empty set is no problem. Your claim is: for any element here, I prove it also is an element there. If there is no element at all then that is not your problem (mathematicalwise, of course): the proof still holds! Anyway, if you still feel something else must be done (though it really mustn't), then you can make a separate case: if this side is empty then so and so. and also the other side is, and the other way around, too. But you really don't need that,
$endgroup$
– DonAntonio
Dec 22 '18 at 18:35
$begingroup$
Words to live by: "vacuous truth". I am almost tempted to say this is a duplicate of many other questions that were asked before. For example, math.stackexchange.com/questions/734418/… math.stackexchange.com/questions/2723860/… math.stackexchange.com/questions/1953218/… and there are many others which are similar.
$endgroup$
– Asaf Karagila♦
Dec 23 '18 at 10:24
$begingroup$
Words to live by: "vacuous truth". I am almost tempted to say this is a duplicate of many other questions that were asked before. For example, math.stackexchange.com/questions/734418/… math.stackexchange.com/questions/2723860/… math.stackexchange.com/questions/1953218/… and there are many others which are similar.
$endgroup$
– Asaf Karagila♦
Dec 23 '18 at 10:24
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
In order to show that for two sets $X$ and $Y$ it holds that $Xsubseteq Y$, you have to prove that
for every $x$, if $xin X$, then $xin Y$.
Note that a statement of the form “if $mathscr{A}$ then $mathscr{B}$” is true when
either $mathscr{A}$ is false or both $mathscr{A}$ and $mathscr{B}$ are true
If $X$ is the empty set, then “$xin X$” is false for every $x$; hence “if $xin X$ then $xin Y$” is true.
The phrase “take an arbitrary element $xin X$” is possibly misleading, but its intended meaning is “suppose $xin X$”.
$endgroup$
1
$begingroup$
Ah, so if we write "suppose $x in X$" and successfully deduce that "$x in Y$" , we have shown that "if $x in X$, then $x in Y$" is true. But, if "$x in X$" is always false, we have still shown "if $x in X$ then $x in Y$" is true, since as you wrote, the implication would be true for all $x$ in that case. I.e. we are allowed to suppose things are true, even when they may never be. Is my understanding correct?
$endgroup$
– E-mu
Dec 22 '18 at 19:39
$begingroup$
@E-mu Basically so
$endgroup$
– egreg
Dec 22 '18 at 20:27
add a comment |
$begingroup$
If $D$ is the empty set then the following statement is always true:$$text{If }xin Dtext{ then }cdots$$no matter what the dots are standing for.
It is false that $xin D$ and "ex falso sequitur quodlibet". A false statement implies whatever you want.
So the assumption will not bring you into troubles, but - on the contrary - will give you freedom to accept whatever you want.
$endgroup$
add a comment |
$begingroup$
Since the empty set is a subset of any set, there is no need of including that in a formal proof.
However it is a good idea to be aware of the fact that the equality holds even in the case of empty sets .
$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%2f3049718%2fproving-set-identities-empty-set-case%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
In order to show that for two sets $X$ and $Y$ it holds that $Xsubseteq Y$, you have to prove that
for every $x$, if $xin X$, then $xin Y$.
Note that a statement of the form “if $mathscr{A}$ then $mathscr{B}$” is true when
either $mathscr{A}$ is false or both $mathscr{A}$ and $mathscr{B}$ are true
If $X$ is the empty set, then “$xin X$” is false for every $x$; hence “if $xin X$ then $xin Y$” is true.
The phrase “take an arbitrary element $xin X$” is possibly misleading, but its intended meaning is “suppose $xin X$”.
$endgroup$
1
$begingroup$
Ah, so if we write "suppose $x in X$" and successfully deduce that "$x in Y$" , we have shown that "if $x in X$, then $x in Y$" is true. But, if "$x in X$" is always false, we have still shown "if $x in X$ then $x in Y$" is true, since as you wrote, the implication would be true for all $x$ in that case. I.e. we are allowed to suppose things are true, even when they may never be. Is my understanding correct?
$endgroup$
– E-mu
Dec 22 '18 at 19:39
$begingroup$
@E-mu Basically so
$endgroup$
– egreg
Dec 22 '18 at 20:27
add a comment |
$begingroup$
In order to show that for two sets $X$ and $Y$ it holds that $Xsubseteq Y$, you have to prove that
for every $x$, if $xin X$, then $xin Y$.
Note that a statement of the form “if $mathscr{A}$ then $mathscr{B}$” is true when
either $mathscr{A}$ is false or both $mathscr{A}$ and $mathscr{B}$ are true
If $X$ is the empty set, then “$xin X$” is false for every $x$; hence “if $xin X$ then $xin Y$” is true.
The phrase “take an arbitrary element $xin X$” is possibly misleading, but its intended meaning is “suppose $xin X$”.
$endgroup$
1
$begingroup$
Ah, so if we write "suppose $x in X$" and successfully deduce that "$x in Y$" , we have shown that "if $x in X$, then $x in Y$" is true. But, if "$x in X$" is always false, we have still shown "if $x in X$ then $x in Y$" is true, since as you wrote, the implication would be true for all $x$ in that case. I.e. we are allowed to suppose things are true, even when they may never be. Is my understanding correct?
$endgroup$
– E-mu
Dec 22 '18 at 19:39
$begingroup$
@E-mu Basically so
$endgroup$
– egreg
Dec 22 '18 at 20:27
add a comment |
$begingroup$
In order to show that for two sets $X$ and $Y$ it holds that $Xsubseteq Y$, you have to prove that
for every $x$, if $xin X$, then $xin Y$.
Note that a statement of the form “if $mathscr{A}$ then $mathscr{B}$” is true when
either $mathscr{A}$ is false or both $mathscr{A}$ and $mathscr{B}$ are true
If $X$ is the empty set, then “$xin X$” is false for every $x$; hence “if $xin X$ then $xin Y$” is true.
The phrase “take an arbitrary element $xin X$” is possibly misleading, but its intended meaning is “suppose $xin X$”.
$endgroup$
In order to show that for two sets $X$ and $Y$ it holds that $Xsubseteq Y$, you have to prove that
for every $x$, if $xin X$, then $xin Y$.
Note that a statement of the form “if $mathscr{A}$ then $mathscr{B}$” is true when
either $mathscr{A}$ is false or both $mathscr{A}$ and $mathscr{B}$ are true
If $X$ is the empty set, then “$xin X$” is false for every $x$; hence “if $xin X$ then $xin Y$” is true.
The phrase “take an arbitrary element $xin X$” is possibly misleading, but its intended meaning is “suppose $xin X$”.
answered Dec 22 '18 at 18:43
egregegreg
180k1485202
180k1485202
1
$begingroup$
Ah, so if we write "suppose $x in X$" and successfully deduce that "$x in Y$" , we have shown that "if $x in X$, then $x in Y$" is true. But, if "$x in X$" is always false, we have still shown "if $x in X$ then $x in Y$" is true, since as you wrote, the implication would be true for all $x$ in that case. I.e. we are allowed to suppose things are true, even when they may never be. Is my understanding correct?
$endgroup$
– E-mu
Dec 22 '18 at 19:39
$begingroup$
@E-mu Basically so
$endgroup$
– egreg
Dec 22 '18 at 20:27
add a comment |
1
$begingroup$
Ah, so if we write "suppose $x in X$" and successfully deduce that "$x in Y$" , we have shown that "if $x in X$, then $x in Y$" is true. But, if "$x in X$" is always false, we have still shown "if $x in X$ then $x in Y$" is true, since as you wrote, the implication would be true for all $x$ in that case. I.e. we are allowed to suppose things are true, even when they may never be. Is my understanding correct?
$endgroup$
– E-mu
Dec 22 '18 at 19:39
$begingroup$
@E-mu Basically so
$endgroup$
– egreg
Dec 22 '18 at 20:27
1
1
$begingroup$
Ah, so if we write "suppose $x in X$" and successfully deduce that "$x in Y$" , we have shown that "if $x in X$, then $x in Y$" is true. But, if "$x in X$" is always false, we have still shown "if $x in X$ then $x in Y$" is true, since as you wrote, the implication would be true for all $x$ in that case. I.e. we are allowed to suppose things are true, even when they may never be. Is my understanding correct?
$endgroup$
– E-mu
Dec 22 '18 at 19:39
$begingroup$
Ah, so if we write "suppose $x in X$" and successfully deduce that "$x in Y$" , we have shown that "if $x in X$, then $x in Y$" is true. But, if "$x in X$" is always false, we have still shown "if $x in X$ then $x in Y$" is true, since as you wrote, the implication would be true for all $x$ in that case. I.e. we are allowed to suppose things are true, even when they may never be. Is my understanding correct?
$endgroup$
– E-mu
Dec 22 '18 at 19:39
$begingroup$
@E-mu Basically so
$endgroup$
– egreg
Dec 22 '18 at 20:27
$begingroup$
@E-mu Basically so
$endgroup$
– egreg
Dec 22 '18 at 20:27
add a comment |
$begingroup$
If $D$ is the empty set then the following statement is always true:$$text{If }xin Dtext{ then }cdots$$no matter what the dots are standing for.
It is false that $xin D$ and "ex falso sequitur quodlibet". A false statement implies whatever you want.
So the assumption will not bring you into troubles, but - on the contrary - will give you freedom to accept whatever you want.
$endgroup$
add a comment |
$begingroup$
If $D$ is the empty set then the following statement is always true:$$text{If }xin Dtext{ then }cdots$$no matter what the dots are standing for.
It is false that $xin D$ and "ex falso sequitur quodlibet". A false statement implies whatever you want.
So the assumption will not bring you into troubles, but - on the contrary - will give you freedom to accept whatever you want.
$endgroup$
add a comment |
$begingroup$
If $D$ is the empty set then the following statement is always true:$$text{If }xin Dtext{ then }cdots$$no matter what the dots are standing for.
It is false that $xin D$ and "ex falso sequitur quodlibet". A false statement implies whatever you want.
So the assumption will not bring you into troubles, but - on the contrary - will give you freedom to accept whatever you want.
$endgroup$
If $D$ is the empty set then the following statement is always true:$$text{If }xin Dtext{ then }cdots$$no matter what the dots are standing for.
It is false that $xin D$ and "ex falso sequitur quodlibet". A false statement implies whatever you want.
So the assumption will not bring you into troubles, but - on the contrary - will give you freedom to accept whatever you want.
edited Dec 22 '18 at 18:46
answered Dec 22 '18 at 18:45
drhabdrhab
99.1k544130
99.1k544130
add a comment |
add a comment |
$begingroup$
Since the empty set is a subset of any set, there is no need of including that in a formal proof.
However it is a good idea to be aware of the fact that the equality holds even in the case of empty sets .
$endgroup$
add a comment |
$begingroup$
Since the empty set is a subset of any set, there is no need of including that in a formal proof.
However it is a good idea to be aware of the fact that the equality holds even in the case of empty sets .
$endgroup$
add a comment |
$begingroup$
Since the empty set is a subset of any set, there is no need of including that in a formal proof.
However it is a good idea to be aware of the fact that the equality holds even in the case of empty sets .
$endgroup$
Since the empty set is a subset of any set, there is no need of including that in a formal proof.
However it is a good idea to be aware of the fact that the equality holds even in the case of empty sets .
answered Dec 22 '18 at 18:39
Mohammad Riazi-KermaniMohammad Riazi-Kermani
41.5k42061
41.5k42061
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%2f3049718%2fproving-set-identities-empty-set-case%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
5
$begingroup$
Because some of the two sides being the empty set is no problem. Your claim is: for any element here, I prove it also is an element there. If there is no element at all then that is not your problem (mathematicalwise, of course): the proof still holds! Anyway, if you still feel something else must be done (though it really mustn't), then you can make a separate case: if this side is empty then so and so. and also the other side is, and the other way around, too. But you really don't need that,
$endgroup$
– DonAntonio
Dec 22 '18 at 18:35
$begingroup$
Words to live by: "vacuous truth". I am almost tempted to say this is a duplicate of many other questions that were asked before. For example, math.stackexchange.com/questions/734418/… math.stackexchange.com/questions/2723860/… math.stackexchange.com/questions/1953218/… and there are many others which are similar.
$endgroup$
– Asaf Karagila♦
Dec 23 '18 at 10:24