Proving set identities: empty set case.
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
add a comment |
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
2
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,
– DonAntonio
1 hour ago
Let $A cap (B cup C)$ empty. Thus, $x notin ldots$ that means : either (i) $x notin A$ or (ii) $x notin (B cup C)$. In the first case, $x notin (A cap B)$ and $x notin (A cap C)$ and thus $x notin$ their union.
– Mauro ALLEGRANZA
44 mins ago
In the secon case : from (ii) $x notin (B cup C)$ we have that $x notin B$ and $x notin C$ and again $x notin [(A cap B) cup (A cap C)]$. Conclusion : in both cases $x notin ldots$. But $x$ is whatever, and thus the result holds for every $x$, i.e. $forall x (x notin [(A cap B) cup (A cap C)])$, that means that the set is empty, and the result holds.
– Mauro ALLEGRANZA
41 mins ago
add a comment |
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
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 1 hour ago
E-mu
405312
405312
2
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,
– DonAntonio
1 hour ago
Let $A cap (B cup C)$ empty. Thus, $x notin ldots$ that means : either (i) $x notin A$ or (ii) $x notin (B cup C)$. In the first case, $x notin (A cap B)$ and $x notin (A cap C)$ and thus $x notin$ their union.
– Mauro ALLEGRANZA
44 mins ago
In the secon case : from (ii) $x notin (B cup C)$ we have that $x notin B$ and $x notin C$ and again $x notin [(A cap B) cup (A cap C)]$. Conclusion : in both cases $x notin ldots$. But $x$ is whatever, and thus the result holds for every $x$, i.e. $forall x (x notin [(A cap B) cup (A cap C)])$, that means that the set is empty, and the result holds.
– Mauro ALLEGRANZA
41 mins ago
add a comment |
2
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,
– DonAntonio
1 hour ago
Let $A cap (B cup C)$ empty. Thus, $x notin ldots$ that means : either (i) $x notin A$ or (ii) $x notin (B cup C)$. In the first case, $x notin (A cap B)$ and $x notin (A cap C)$ and thus $x notin$ their union.
– Mauro ALLEGRANZA
44 mins ago
In the secon case : from (ii) $x notin (B cup C)$ we have that $x notin B$ and $x notin C$ and again $x notin [(A cap B) cup (A cap C)]$. Conclusion : in both cases $x notin ldots$. But $x$ is whatever, and thus the result holds for every $x$, i.e. $forall x (x notin [(A cap B) cup (A cap C)])$, that means that the set is empty, and the result holds.
– Mauro ALLEGRANZA
41 mins ago
2
2
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,
– DonAntonio
1 hour ago
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,
– DonAntonio
1 hour ago
Let $A cap (B cup C)$ empty. Thus, $x notin ldots$ that means : either (i) $x notin A$ or (ii) $x notin (B cup C)$. In the first case, $x notin (A cap B)$ and $x notin (A cap C)$ and thus $x notin$ their union.
– Mauro ALLEGRANZA
44 mins ago
Let $A cap (B cup C)$ empty. Thus, $x notin ldots$ that means : either (i) $x notin A$ or (ii) $x notin (B cup C)$. In the first case, $x notin (A cap B)$ and $x notin (A cap C)$ and thus $x notin$ their union.
– Mauro ALLEGRANZA
44 mins ago
In the secon case : from (ii) $x notin (B cup C)$ we have that $x notin B$ and $x notin C$ and again $x notin [(A cap B) cup (A cap C)]$. Conclusion : in both cases $x notin ldots$. But $x$ is whatever, and thus the result holds for every $x$, i.e. $forall x (x notin [(A cap B) cup (A cap C)])$, that means that the set is empty, and the result holds.
– Mauro ALLEGRANZA
41 mins ago
In the secon case : from (ii) $x notin (B cup C)$ we have that $x notin B$ and $x notin C$ and again $x notin [(A cap B) cup (A cap C)]$. Conclusion : in both cases $x notin ldots$. But $x$ is whatever, and thus the result holds for every $x$, i.e. $forall x (x notin [(A cap B) cup (A cap C)])$, that means that the set is empty, and the result holds.
– Mauro ALLEGRANZA
41 mins ago
add a comment |
3 Answers
3
active
oldest
votes
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$”.
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?
– E-mu
13 mins ago
add a comment |
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.
add a comment |
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 .
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
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$”.
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?
– E-mu
13 mins ago
add a comment |
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$”.
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?
– E-mu
13 mins ago
add a comment |
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$”.
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 1 hour ago
egreg
177k1484198
177k1484198
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?
– E-mu
13 mins ago
add a comment |
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?
– E-mu
13 mins ago
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?
– E-mu
13 mins ago
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?
– E-mu
13 mins ago
add a comment |
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.
add a comment |
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.
add a comment |
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.
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 1 hour ago
answered 1 hour ago
drhab
96.7k544128
96.7k544128
add a comment |
add a comment |
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 .
add a comment |
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 .
add a comment |
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 .
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 1 hour ago
Mohammad Riazi-Kermani
40.5k42058
40.5k42058
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.
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%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
2
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,
– DonAntonio
1 hour ago
Let $A cap (B cup C)$ empty. Thus, $x notin ldots$ that means : either (i) $x notin A$ or (ii) $x notin (B cup C)$. In the first case, $x notin (A cap B)$ and $x notin (A cap C)$ and thus $x notin$ their union.
– Mauro ALLEGRANZA
44 mins ago
In the secon case : from (ii) $x notin (B cup C)$ we have that $x notin B$ and $x notin C$ and again $x notin [(A cap B) cup (A cap C)]$. Conclusion : in both cases $x notin ldots$. But $x$ is whatever, and thus the result holds for every $x$, i.e. $forall x (x notin [(A cap B) cup (A cap C)])$, that means that the set is empty, and the result holds.
– Mauro ALLEGRANZA
41 mins ago