Proving Set Identities - Why Do I Need Both Directions?
$begingroup$
Say I want to prove $A - B = A cap B'$
I let $x in A - B$
Then $x in A$ and $x notin B$
By definition, $x notin B iff x in B'$ (no?)
So the thing looks proven to me.
Why do I need to prove that $A - B subseteq A cap B'$ and $A cap B' subseteq A - B$ ?
More generally is there a class of set theory proofs which require set equality via mutual subset inclusion and another class which can be proven directly? If so, how do I decide which technique to use please?
elementary-set-theory proof-writing
edited Dec 18 '18 at 16:56
Andrés E. Caicedo
65.2k8158247
asked Dec 18 '18 at 14:48
RobinRobin
1334
$endgroup$
add a comment |
$begingroup$
Say I want to prove $A - B = A cap B'$
I let $x in A - B$
Then $x in A$ and $x notin B$
By definition, $x notin B iff x in B'$ (no?)
So the thing looks proven to me.
Why do I need to prove that $A - B subseteq A cap B'$ and $A cap B' subseteq A - B$ ?
More generally is there a class of set theory proofs which require set equality via mutual subset inclusion and another class which can be proven directly? If so, how do I decide which technique to use please?
elementary-set-theory proof-writing
edited Dec 18 '18 at 16:56
Andrés E. Caicedo
65.2k8158247
asked Dec 18 '18 at 14:48
RobinRobin
1334
$endgroup$
$begingroup$
You only proved that every $xin A-B$ also belongs to $Acap B'$, or that $A-Bsubseteq Acap B'$. You have to prove the converse too, that every element of $Acap B'$ also belongs to $A-B$, so that the two sets are equal.
$endgroup$
– Shubham Johri
Dec 18 '18 at 14:56
$begingroup$
What's the definition of $A - B$? I was always told $A - B$ is "all the elements of $A$ that are explicitely not in $B$" or in other words $A-B = A cap B'$ by definition. But not the less, you have proven that $A-B subset Acap B'$. Hypothetically it is possible that there is a $y in Acup B'$ that is not in $A-B$.
$endgroup$
– fleablood
Dec 18 '18 at 17:05
add a comment |
$begingroup$
Say I want to prove $A - B = A cap B'$
I let $x in A - B$
Then $x in A$ and $x notin B$
By definition, $x notin B iff x in B'$ (no?)
So the thing looks proven to me.
Why do I need to prove that $A - B subseteq A cap B'$ and $A cap B' subseteq A - B$ ?
More generally is there a class of set theory proofs which require set equality via mutual subset inclusion and another class which can be proven directly? If so, how do I decide which technique to use please?
elementary-set-theory proof-writing
edited Dec 18 '18 at 16:56
Andrés E. Caicedo
65.2k8158247
asked Dec 18 '18 at 14:48
RobinRobin
1334
$endgroup$
Say I want to prove $A - B = A cap B'$
I let $x in A - B$
Then $x in A$ and $x notin B$
By definition, $x notin B iff x in B'$ (no?)
So the thing looks proven to me.
Why do I need to prove that $A - B subseteq A cap B'$ and $A cap B' subseteq A - B$ ?
More generally is there a class of set theory proofs which require set equality via mutual subset inclusion and another class which can be proven directly? If so, how do I decide which technique to use please?
elementary-set-theory proof-writing
elementary-set-theory proof-writing
edited Dec 18 '18 at 16:56
Andrés E. Caicedo
65.2k8158247
asked Dec 18 '18 at 14:48
RobinRobin
1334
edited Dec 18 '18 at 16:56
Andrés E. Caicedo
65.2k8158247
asked Dec 18 '18 at 14:48
RobinRobin
1334
edited Dec 18 '18 at 16:56
Andrés E. Caicedo
65.2k8158247
edited Dec 18 '18 at 16:56
Andrés E. Caicedo
65.2k8158247
edited Dec 18 '18 at 16:56
Andrés E. Caicedo
65.2k8158247
65.2k8158247
asked Dec 18 '18 at 14:48
RobinRobin
1334
asked Dec 18 '18 at 14:48
RobinRobin
1334
asked Dec 18 '18 at 14:48
RobinRobin
1334
1334
$begingroup$
You only proved that every $xin A-B$ also belongs to $Acap B'$, or that $A-Bsubseteq Acap B'$. You have to prove the converse too, that every element of $Acap B'$ also belongs to $A-B$, so that the two sets are equal.
$endgroup$
– Shubham Johri
Dec 18 '18 at 14:56
$begingroup$
What's the definition of $A - B$? I was always told $A - B$ is "all the elements of $A$ that are explicitely not in $B$" or in other words $A-B = A cap B'$ by definition. But not the less, you have proven that $A-B subset Acap B'$. Hypothetically it is possible that there is a $y in Acup B'$ that is not in $A-B$.
$endgroup$
– fleablood
Dec 18 '18 at 17:05
add a comment |
$begingroup$
You only proved that every $xin A-B$ also belongs to $Acap B'$, or that $A-Bsubseteq Acap B'$. You have to prove the converse too, that every element of $Acap B'$ also belongs to $A-B$, so that the two sets are equal.
$endgroup$
– Shubham Johri
Dec 18 '18 at 14:56
$begingroup$
What's the definition of $A - B$? I was always told $A - B$ is "all the elements of $A$ that are explicitely not in $B$" or in other words $A-B = A cap B'$ by definition. But not the less, you have proven that $A-B subset Acap B'$. Hypothetically it is possible that there is a $y in Acup B'$ that is not in $A-B$.
$endgroup$
– fleablood
Dec 18 '18 at 17:05
$begingroup$
You only proved that every $xin A-B$ also belongs to $Acap B'$, or that $A-Bsubseteq Acap B'$. You have to prove the converse too, that every element of $Acap B'$ also belongs to $A-B$, so that the two sets are equal.
$endgroup$
– Shubham Johri
Dec 18 '18 at 14:56
$begingroup$
You only proved that every $xin A-B$ also belongs to $Acap B'$, or that $A-Bsubseteq Acap B'$. You have to prove the converse too, that every element of $Acap B'$ also belongs to $A-B$, so that the two sets are equal.
$endgroup$
– Shubham Johri
Dec 18 '18 at 14:56
$begingroup$
What's the definition of $A - B$? I was always told $A - B$ is "all the elements of $A$ that are explicitely not in $B$" or in other words $A-B = A cap B'$ by definition. But not the less, you have proven that $A-B subset Acap B'$. Hypothetically it is possible that there is a $y in Acup B'$ that is not in $A-B$.
$endgroup$
– fleablood
Dec 18 '18 at 17:05
$begingroup$
What's the definition of $A - B$? I was always told $A - B$ is "all the elements of $A$ that are explicitely not in $B$" or in other words $A-B = A cap B'$ by definition. But not the less, you have proven that $A-B subset Acap B'$. Hypothetically it is possible that there is a $y in Acup B'$ that is not in $A-B$.
$endgroup$
– fleablood
Dec 18 '18 at 17:05
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
"$X=Y$" in set theory means that any formula ("property") that the set $X$ satisfies is also satisfied by the set $Y$, and vice versa. This is, in somewhat informal terms, the definition of $=$. Given a specific element $x$, the property $phi(Z)$ given by $xin Z$ is one such property, so by definition of $=$, equal sets contain all the same elements. But there are many other formulas one could ask a set to fulfill as well.
There is an axiom of set theory (at least in ZF set theory, the most used set theory in modern mathematics) which says that when you want to check whether two sets are equal, you don't have to check every formula to see that $X$ and $Y$ either both satisfy the formula, or they both do not satisfy it. The axiom states that if they contain the same elements, they are proclaimed to be equal (in the sense of the first paragraph).
Thus the minimal thing you need to show in order to decide that $X = Y$, according to the axioms of set theory, is exactly that
$$
xin Ximplies xin Y\
yin Y implies yin X
$$
So yes, formally, you do have to go both ways.
Of course, with simple, bare-bones examples like yours, we do get that the proof of one implication looks a whole lot like the proof of the other implication in revese, and with only two or three steps to the proof, it's hard to know where the proof of one implication ends and the proof of the other implication begins if you're not very careful to keep the two apart.
answered Dec 18 '18 at 14:59
ArthurArthur
113k7110193
$endgroup$
$begingroup$
I guess there's an underlying issue here of which sources I trust for learning about this stuff. The proof in this link: compucademy.co.uk/temp/distributive_law_1_proof.jpg for another theorem seems convincing and comes from a YouTube video with an authoritative-sounding presenter. However, from what I've read here, apparently it is seriously incomplete.
$endgroup$
– Robin
Dec 18 '18 at 16:18
$begingroup$
@Robin: The jpg you cite is very bad. It's time to completely ignore anything from that site. If you don't believe me, ask another logician.
$endgroup$
– user21820
Dec 19 '18 at 14:45
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%2f3045247%2fproving-set-identities-why-do-i-need-both-directions%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$
"$X=Y$" in set theory means that any formula ("property") that the set $X$ satisfies is also satisfied by the set $Y$, and vice versa. This is, in somewhat informal terms, the definition of $=$. Given a specific element $x$, the property $phi(Z)$ given by $xin Z$ is one such property, so by definition of $=$, equal sets contain all the same elements. But there are many other formulas one could ask a set to fulfill as well.
There is an axiom of set theory (at least in ZF set theory, the most used set theory in modern mathematics) which says that when you want to check whether two sets are equal, you don't have to check every formula to see that $X$ and $Y$ either both satisfy the formula, or they both do not satisfy it. The axiom states that if they contain the same elements, they are proclaimed to be equal (in the sense of the first paragraph).
Thus the minimal thing you need to show in order to decide that $X = Y$, according to the axioms of set theory, is exactly that
$$
xin Ximplies xin Y\
yin Y implies yin X
$$
So yes, formally, you do have to go both ways.
Of course, with simple, bare-bones examples like yours, we do get that the proof of one implication looks a whole lot like the proof of the other implication in revese, and with only two or three steps to the proof, it's hard to know where the proof of one implication ends and the proof of the other implication begins if you're not very careful to keep the two apart.
answered Dec 18 '18 at 14:59
ArthurArthur
113k7110193
$endgroup$
$begingroup$
I guess there's an underlying issue here of which sources I trust for learning about this stuff. The proof in this link: compucademy.co.uk/temp/distributive_law_1_proof.jpg for another theorem seems convincing and comes from a YouTube video with an authoritative-sounding presenter. However, from what I've read here, apparently it is seriously incomplete.
$endgroup$
– Robin
Dec 18 '18 at 16:18
$begingroup$
@Robin: The jpg you cite is very bad. It's time to completely ignore anything from that site. If you don't believe me, ask another logician.
$endgroup$
– user21820
Dec 19 '18 at 14:45
add a comment |
$begingroup$
"$X=Y$" in set theory means that any formula ("property") that the set $X$ satisfies is also satisfied by the set $Y$, and vice versa. This is, in somewhat informal terms, the definition of $=$. Given a specific element $x$, the property $phi(Z)$ given by $xin Z$ is one such property, so by definition of $=$, equal sets contain all the same elements. But there are many other formulas one could ask a set to fulfill as well.
There is an axiom of set theory (at least in ZF set theory, the most used set theory in modern mathematics) which says that when you want to check whether two sets are equal, you don't have to check every formula to see that $X$ and $Y$ either both satisfy the formula, or they both do not satisfy it. The axiom states that if they contain the same elements, they are proclaimed to be equal (in the sense of the first paragraph).
Thus the minimal thing you need to show in order to decide that $X = Y$, according to the axioms of set theory, is exactly that
$$
xin Ximplies xin Y\
yin Y implies yin X
$$
So yes, formally, you do have to go both ways.
Of course, with simple, bare-bones examples like yours, we do get that the proof of one implication looks a whole lot like the proof of the other implication in revese, and with only two or three steps to the proof, it's hard to know where the proof of one implication ends and the proof of the other implication begins if you're not very careful to keep the two apart.
answered Dec 18 '18 at 14:59
ArthurArthur
113k7110193
$endgroup$
$begingroup$
I guess there's an underlying issue here of which sources I trust for learning about this stuff. The proof in this link: compucademy.co.uk/temp/distributive_law_1_proof.jpg for another theorem seems convincing and comes from a YouTube video with an authoritative-sounding presenter. However, from what I've read here, apparently it is seriously incomplete.
$endgroup$
– Robin
Dec 18 '18 at 16:18
$begingroup$
@Robin: The jpg you cite is very bad. It's time to completely ignore anything from that site. If you don't believe me, ask another logician.
$endgroup$
– user21820
Dec 19 '18 at 14:45
add a comment |
$begingroup$
"$X=Y$" in set theory means that any formula ("property") that the set $X$ satisfies is also satisfied by the set $Y$, and vice versa. This is, in somewhat informal terms, the definition of $=$. Given a specific element $x$, the property $phi(Z)$ given by $xin Z$ is one such property, so by definition of $=$, equal sets contain all the same elements. But there are many other formulas one could ask a set to fulfill as well.
There is an axiom of set theory (at least in ZF set theory, the most used set theory in modern mathematics) which says that when you want to check whether two sets are equal, you don't have to check every formula to see that $X$ and $Y$ either both satisfy the formula, or they both do not satisfy it. The axiom states that if they contain the same elements, they are proclaimed to be equal (in the sense of the first paragraph).
Thus the minimal thing you need to show in order to decide that $X = Y$, according to the axioms of set theory, is exactly that
$$
xin Ximplies xin Y\
yin Y implies yin X
$$
So yes, formally, you do have to go both ways.
Of course, with simple, bare-bones examples like yours, we do get that the proof of one implication looks a whole lot like the proof of the other implication in revese, and with only two or three steps to the proof, it's hard to know where the proof of one implication ends and the proof of the other implication begins if you're not very careful to keep the two apart.
answered Dec 18 '18 at 14:59
ArthurArthur
113k7110193
$endgroup$
"$X=Y$" in set theory means that any formula ("property") that the set $X$ satisfies is also satisfied by the set $Y$, and vice versa. This is, in somewhat informal terms, the definition of $=$. Given a specific element $x$, the property $phi(Z)$ given by $xin Z$ is one such property, so by definition of $=$, equal sets contain all the same elements. But there are many other formulas one could ask a set to fulfill as well.
There is an axiom of set theory (at least in ZF set theory, the most used set theory in modern mathematics) which says that when you want to check whether two sets are equal, you don't have to check every formula to see that $X$ and $Y$ either both satisfy the formula, or they both do not satisfy it. The axiom states that if they contain the same elements, they are proclaimed to be equal (in the sense of the first paragraph).
Thus the minimal thing you need to show in order to decide that $X = Y$, according to the axioms of set theory, is exactly that
$$
xin Ximplies xin Y\
yin Y implies yin X
$$
So yes, formally, you do have to go both ways.
Of course, with simple, bare-bones examples like yours, we do get that the proof of one implication looks a whole lot like the proof of the other implication in revese, and with only two or three steps to the proof, it's hard to know where the proof of one implication ends and the proof of the other implication begins if you're not very careful to keep the two apart.
answered Dec 18 '18 at 14:59
ArthurArthur
113k7110193
edited Dec 18 '18 at 15:09
answered Dec 18 '18 at 14:59
ArthurArthur
113k7110193
answered Dec 18 '18 at 14:59
ArthurArthur
113k7110193
answered Dec 18 '18 at 14:59
ArthurArthur
113k7110193
113k7110193
$begingroup$
I guess there's an underlying issue here of which sources I trust for learning about this stuff. The proof in this link: compucademy.co.uk/temp/distributive_law_1_proof.jpg for another theorem seems convincing and comes from a YouTube video with an authoritative-sounding presenter. However, from what I've read here, apparently it is seriously incomplete.
$endgroup$
– Robin
Dec 18 '18 at 16:18
$begingroup$
@Robin: The jpg you cite is very bad. It's time to completely ignore anything from that site. If you don't believe me, ask another logician.
$endgroup$
– user21820
Dec 19 '18 at 14:45
add a comment |
$begingroup$
I guess there's an underlying issue here of which sources I trust for learning about this stuff. The proof in this link: compucademy.co.uk/temp/distributive_law_1_proof.jpg for another theorem seems convincing and comes from a YouTube video with an authoritative-sounding presenter. However, from what I've read here, apparently it is seriously incomplete.
$endgroup$
– Robin
Dec 18 '18 at 16:18
$begingroup$
@Robin: The jpg you cite is very bad. It's time to completely ignore anything from that site. If you don't believe me, ask another logician.
$endgroup$
– user21820
Dec 19 '18 at 14:45
$begingroup$
I guess there's an underlying issue here of which sources I trust for learning about this stuff. The proof in this link: compucademy.co.uk/temp/distributive_law_1_proof.jpg for another theorem seems convincing and comes from a YouTube video with an authoritative-sounding presenter. However, from what I've read here, apparently it is seriously incomplete.
$endgroup$
– Robin
Dec 18 '18 at 16:18
$begingroup$
I guess there's an underlying issue here of which sources I trust for learning about this stuff. The proof in this link: compucademy.co.uk/temp/distributive_law_1_proof.jpg for another theorem seems convincing and comes from a YouTube video with an authoritative-sounding presenter. However, from what I've read here, apparently it is seriously incomplete.
$endgroup$
– Robin
Dec 18 '18 at 16:18
$begingroup$
@Robin: The jpg you cite is very bad. It's time to completely ignore anything from that site. If you don't believe me, ask another logician.
$endgroup$
– user21820
Dec 19 '18 at 14:45
$begingroup$
@Robin: The jpg you cite is very bad. It's time to completely ignore anything from that site. If you don't believe me, ask another logician.
$endgroup$
– user21820
Dec 19 '18 at 14:45
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%2f3045247%2fproving-set-identities-why-do-i-need-both-directions%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$
You only proved that every $xin A-B$ also belongs to $Acap B'$, or that $A-Bsubseteq Acap B'$. You have to prove the converse too, that every element of $Acap B'$ also belongs to $A-B$, so that the two sets are equal.
$endgroup$
– Shubham Johri
Dec 18 '18 at 14:56
$begingroup$
What's the definition of $A - B$? I was always told $A - B$ is "all the elements of $A$ that are explicitely not in $B$" or in other words $A-B = A cap B'$ by definition. But not the less, you have proven that $A-B subset Acap B'$. Hypothetically it is possible that there is a $y in Acup B'$ that is not in $A-B$.
$endgroup$
– fleablood
Dec 18 '18 at 17:05