Mixing
Set theory proofs
$begingroup$
Let $X$ be the set of $A, B subseteq X$. Show that:
a) $(A cup B)^c = A^c cap B^c$
b) If $A subseteq B $, then $B^c subseteq A^c$
c) $(A^c)^c = A$
d) $A - B = A cap B^c$
Using the Venn diagrams is easy to check that is true, but I need to prove the equalities.
How can I do that in a proper, formal manner?
elementary-set-theory proof-writing self-learning
asked Jan 21 at 10:09
ArduinArduin
307
$endgroup$
add a comment |
$begingroup$
Let $X$ be the set of $A, B subseteq X$. Show that:
a) $(A cup B)^c = A^c cap B^c$
b) If $A subseteq B $, then $B^c subseteq A^c$
c) $(A^c)^c = A$
d) $A - B = A cap B^c$
Using the Venn diagrams is easy to check that is true, but I need to prove the equalities.
How can I do that in a proper, formal manner?
elementary-set-theory proof-writing self-learning
asked Jan 21 at 10:09
ArduinArduin
307
$endgroup$
2
$begingroup$
You use “double inclusion”, ie you prove that any element in one member of the equality must belong to the other as well.
$endgroup$
– Mindlack
Jan 21 at 10:11
$begingroup$
Note that your (c) should probably be $(A^c)^c = A$.
$endgroup$
– Mees de Vries
Jan 21 at 10:13
$begingroup$
@MeesdeVries You're right. I will fix that. Thank you!
$endgroup$
– Arduin
Jan 21 at 10:14
add a comment |
$begingroup$
Let $X$ be the set of $A, B subseteq X$. Show that:
a) $(A cup B)^c = A^c cap B^c$
b) If $A subseteq B $, then $B^c subseteq A^c$
c) $(A^c)^c = A$
d) $A - B = A cap B^c$
Using the Venn diagrams is easy to check that is true, but I need to prove the equalities.
How can I do that in a proper, formal manner?
elementary-set-theory proof-writing self-learning
asked Jan 21 at 10:09
ArduinArduin
307
$endgroup$
Let $X$ be the set of $A, B subseteq X$. Show that:
a) $(A cup B)^c = A^c cap B^c$
b) If $A subseteq B $, then $B^c subseteq A^c$
c) $(A^c)^c = A$
d) $A - B = A cap B^c$
Using the Venn diagrams is easy to check that is true, but I need to prove the equalities.
How can I do that in a proper, formal manner?
elementary-set-theory proof-writing self-learning
elementary-set-theory proof-writing self-learning
asked Jan 21 at 10:09
ArduinArduin
307
asked Jan 21 at 10:09
ArduinArduin
307
edited Jan 22 at 16:01
Arduin
asked Jan 21 at 10:09
ArduinArduin
307
asked Jan 21 at 10:09
ArduinArduin
307
asked Jan 21 at 10:09
ArduinArduin
307
307
2
$begingroup$
You use “double inclusion”, ie you prove that any element in one member of the equality must belong to the other as well.
$endgroup$
– Mindlack
Jan 21 at 10:11
$begingroup$
Note that your (c) should probably be $(A^c)^c = A$.
$endgroup$
– Mees de Vries
Jan 21 at 10:13
$begingroup$
@MeesdeVries You're right. I will fix that. Thank you!
$endgroup$
– Arduin
Jan 21 at 10:14
add a comment |
2
$begingroup$
You use “double inclusion”, ie you prove that any element in one member of the equality must belong to the other as well.
$endgroup$
– Mindlack
Jan 21 at 10:11
$begingroup$
Note that your (c) should probably be $(A^c)^c = A$.
$endgroup$
– Mees de Vries
Jan 21 at 10:13
$begingroup$
@MeesdeVries You're right. I will fix that. Thank you!
$endgroup$
– Arduin
Jan 21 at 10:14
2
2
$begingroup$
You use “double inclusion”, ie you prove that any element in one member of the equality must belong to the other as well.
$endgroup$
– Mindlack
Jan 21 at 10:11
$begingroup$
You use “double inclusion”, ie you prove that any element in one member of the equality must belong to the other as well.
$endgroup$
– Mindlack
Jan 21 at 10:11
$begingroup$
Note that your (c) should probably be $(A^c)^c = A$.
$endgroup$
– Mees de Vries
Jan 21 at 10:13
$begingroup$
Note that your (c) should probably be $(A^c)^c = A$.
$endgroup$
– Mees de Vries
Jan 21 at 10:13
$begingroup$
@MeesdeVries You're right. I will fix that. Thank you!
$endgroup$
– Arduin
Jan 21 at 10:14
$begingroup$
@MeesdeVries You're right. I will fix that. Thank you!
$endgroup$
– Arduin
Jan 21 at 10:14
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
To show two sets $A,B$ are equal, you show
$$A subseteq B ;;; text{and} ;;; B subseteq A$$
This in turn implies $A = B$.
How would one show this? Typically, you do this in two parts. First, you take $x in A$, then use the definitions of the identities and such to show $x in B$, and similarly start with $x in B$ and show $x in A$.
Some of the identities involved and the implications you'll use. (These are mostly "if and only if" statements, so the left implies the right, and the right implies the left. Usually going left-to-right is when you "unravel" as I speak on later, and right-to-left to "wrap it back up.")
- $x in A iff x not in A^c$
- $x in A^c iff x not in A$
- $x in A cup B iff x in A ;;; text{OR} ;;; x in B$
- $x in A cap B iff x in A ;;; text{AND} ;;; x in B$
- $x in A-B iff x in A ;;; text{AND} ;;; x not in B$
- On the premise $A subseteq B$, $;; x in A implies x in B$ (note the converse need not always hold on this one!)
In the case of part (b) in particular, you will show $x in B^c implies x in A^c$ and the reverse, but on the premise $A subseteq B$. That means you can take this latter fact as a given and a tool to use in your proof.
Typically the flow of all these arguments would be in "unraveling" the left-hand side to see what sets $x$ is in, then trying to "wrap it back up" into the identity on the right-hand side.
From there, since $x$ is arbitrary and $x in A implies x in B$, it follows $A subseteq B$ (assuming of course this holds!). Do the same to show $B subseteq A$, and then you have $A = B$.
Of course this is just a broad overview. Hopefully in class or your text, similar examples were given. If not, I imagine there are plenty of other examples you could easily Google to grasp the overall flow, structure, and motivation of such an argument.
P.S. It is also very helpful to have Venn diagrams on-hand, as you probably can see already. They're a good guiding tool for these sorts of proofs. Of course they aren't a substitute for a formal proof, but if you can verify it through Venn diagrams that's like half the difficulty.
answered Jan 21 at 10:24
Eevee TrainerEevee Trainer
7,42821338
$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%2f3081702%2fset-theory-proofs%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$
To show two sets $A,B$ are equal, you show
$$A subseteq B ;;; text{and} ;;; B subseteq A$$
This in turn implies $A = B$.
How would one show this? Typically, you do this in two parts. First, you take $x in A$, then use the definitions of the identities and such to show $x in B$, and similarly start with $x in B$ and show $x in A$.
Some of the identities involved and the implications you'll use. (These are mostly "if and only if" statements, so the left implies the right, and the right implies the left. Usually going left-to-right is when you "unravel" as I speak on later, and right-to-left to "wrap it back up.")
- $x in A iff x not in A^c$
- $x in A^c iff x not in A$
- $x in A cup B iff x in A ;;; text{OR} ;;; x in B$
- $x in A cap B iff x in A ;;; text{AND} ;;; x in B$
- $x in A-B iff x in A ;;; text{AND} ;;; x not in B$
- On the premise $A subseteq B$, $;; x in A implies x in B$ (note the converse need not always hold on this one!)
In the case of part (b) in particular, you will show $x in B^c implies x in A^c$ and the reverse, but on the premise $A subseteq B$. That means you can take this latter fact as a given and a tool to use in your proof.
Typically the flow of all these arguments would be in "unraveling" the left-hand side to see what sets $x$ is in, then trying to "wrap it back up" into the identity on the right-hand side.
From there, since $x$ is arbitrary and $x in A implies x in B$, it follows $A subseteq B$ (assuming of course this holds!). Do the same to show $B subseteq A$, and then you have $A = B$.
Of course this is just a broad overview. Hopefully in class or your text, similar examples were given. If not, I imagine there are plenty of other examples you could easily Google to grasp the overall flow, structure, and motivation of such an argument.
P.S. It is also very helpful to have Venn diagrams on-hand, as you probably can see already. They're a good guiding tool for these sorts of proofs. Of course they aren't a substitute for a formal proof, but if you can verify it through Venn diagrams that's like half the difficulty.
answered Jan 21 at 10:24
Eevee TrainerEevee Trainer
7,42821338
$endgroup$
add a comment |
$begingroup$
To show two sets $A,B$ are equal, you show
$$A subseteq B ;;; text{and} ;;; B subseteq A$$
This in turn implies $A = B$.
How would one show this? Typically, you do this in two parts. First, you take $x in A$, then use the definitions of the identities and such to show $x in B$, and similarly start with $x in B$ and show $x in A$.
Some of the identities involved and the implications you'll use. (These are mostly "if and only if" statements, so the left implies the right, and the right implies the left. Usually going left-to-right is when you "unravel" as I speak on later, and right-to-left to "wrap it back up.")
- $x in A iff x not in A^c$
- $x in A^c iff x not in A$
- $x in A cup B iff x in A ;;; text{OR} ;;; x in B$
- $x in A cap B iff x in A ;;; text{AND} ;;; x in B$
- $x in A-B iff x in A ;;; text{AND} ;;; x not in B$
- On the premise $A subseteq B$, $;; x in A implies x in B$ (note the converse need not always hold on this one!)
In the case of part (b) in particular, you will show $x in B^c implies x in A^c$ and the reverse, but on the premise $A subseteq B$. That means you can take this latter fact as a given and a tool to use in your proof.
Typically the flow of all these arguments would be in "unraveling" the left-hand side to see what sets $x$ is in, then trying to "wrap it back up" into the identity on the right-hand side.
From there, since $x$ is arbitrary and $x in A implies x in B$, it follows $A subseteq B$ (assuming of course this holds!). Do the same to show $B subseteq A$, and then you have $A = B$.
Of course this is just a broad overview. Hopefully in class or your text, similar examples were given. If not, I imagine there are plenty of other examples you could easily Google to grasp the overall flow, structure, and motivation of such an argument.
P.S. It is also very helpful to have Venn diagrams on-hand, as you probably can see already. They're a good guiding tool for these sorts of proofs. Of course they aren't a substitute for a formal proof, but if you can verify it through Venn diagrams that's like half the difficulty.
answered Jan 21 at 10:24
Eevee TrainerEevee Trainer
7,42821338
$endgroup$
add a comment |
$begingroup$
To show two sets $A,B$ are equal, you show
$$A subseteq B ;;; text{and} ;;; B subseteq A$$
This in turn implies $A = B$.
How would one show this? Typically, you do this in two parts. First, you take $x in A$, then use the definitions of the identities and such to show $x in B$, and similarly start with $x in B$ and show $x in A$.
Some of the identities involved and the implications you'll use. (These are mostly "if and only if" statements, so the left implies the right, and the right implies the left. Usually going left-to-right is when you "unravel" as I speak on later, and right-to-left to "wrap it back up.")
- $x in A iff x not in A^c$
- $x in A^c iff x not in A$
- $x in A cup B iff x in A ;;; text{OR} ;;; x in B$
- $x in A cap B iff x in A ;;; text{AND} ;;; x in B$
- $x in A-B iff x in A ;;; text{AND} ;;; x not in B$
- On the premise $A subseteq B$, $;; x in A implies x in B$ (note the converse need not always hold on this one!)
In the case of part (b) in particular, you will show $x in B^c implies x in A^c$ and the reverse, but on the premise $A subseteq B$. That means you can take this latter fact as a given and a tool to use in your proof.
Typically the flow of all these arguments would be in "unraveling" the left-hand side to see what sets $x$ is in, then trying to "wrap it back up" into the identity on the right-hand side.
From there, since $x$ is arbitrary and $x in A implies x in B$, it follows $A subseteq B$ (assuming of course this holds!). Do the same to show $B subseteq A$, and then you have $A = B$.
Of course this is just a broad overview. Hopefully in class or your text, similar examples were given. If not, I imagine there are plenty of other examples you could easily Google to grasp the overall flow, structure, and motivation of such an argument.
P.S. It is also very helpful to have Venn diagrams on-hand, as you probably can see already. They're a good guiding tool for these sorts of proofs. Of course they aren't a substitute for a formal proof, but if you can verify it through Venn diagrams that's like half the difficulty.
answered Jan 21 at 10:24
Eevee TrainerEevee Trainer
7,42821338
$endgroup$
To show two sets $A,B$ are equal, you show
$$A subseteq B ;;; text{and} ;;; B subseteq A$$
This in turn implies $A = B$.
How would one show this? Typically, you do this in two parts. First, you take $x in A$, then use the definitions of the identities and such to show $x in B$, and similarly start with $x in B$ and show $x in A$.
Some of the identities involved and the implications you'll use. (These are mostly "if and only if" statements, so the left implies the right, and the right implies the left. Usually going left-to-right is when you "unravel" as I speak on later, and right-to-left to "wrap it back up.")
- $x in A iff x not in A^c$
- $x in A^c iff x not in A$
- $x in A cup B iff x in A ;;; text{OR} ;;; x in B$
- $x in A cap B iff x in A ;;; text{AND} ;;; x in B$
- $x in A-B iff x in A ;;; text{AND} ;;; x not in B$
- On the premise $A subseteq B$, $;; x in A implies x in B$ (note the converse need not always hold on this one!)
In the case of part (b) in particular, you will show $x in B^c implies x in A^c$ and the reverse, but on the premise $A subseteq B$. That means you can take this latter fact as a given and a tool to use in your proof.
Typically the flow of all these arguments would be in "unraveling" the left-hand side to see what sets $x$ is in, then trying to "wrap it back up" into the identity on the right-hand side.
From there, since $x$ is arbitrary and $x in A implies x in B$, it follows $A subseteq B$ (assuming of course this holds!). Do the same to show $B subseteq A$, and then you have $A = B$.
Of course this is just a broad overview. Hopefully in class or your text, similar examples were given. If not, I imagine there are plenty of other examples you could easily Google to grasp the overall flow, structure, and motivation of such an argument.
P.S. It is also very helpful to have Venn diagrams on-hand, as you probably can see already. They're a good guiding tool for these sorts of proofs. Of course they aren't a substitute for a formal proof, but if you can verify it through Venn diagrams that's like half the difficulty.
answered Jan 21 at 10:24
Eevee TrainerEevee Trainer
7,42821338
edited Jan 21 at 10:30
answered Jan 21 at 10:24
Eevee TrainerEevee Trainer
7,42821338
answered Jan 21 at 10:24
Eevee TrainerEevee Trainer
7,42821338
answered Jan 21 at 10:24
Eevee TrainerEevee Trainer
7,42821338
7,42821338
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%2f3081702%2fset-theory-proofs%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
$begingroup$
You use “double inclusion”, ie you prove that any element in one member of the equality must belong to the other as well.
$endgroup$
– Mindlack
Jan 21 at 10:11
$begingroup$
Note that your (c) should probably be $(A^c)^c = A$.
$endgroup$
– Mees de Vries
Jan 21 at 10:13
$begingroup$
@MeesdeVries You're right. I will fix that. Thank you!
$endgroup$
– Arduin
Jan 21 at 10:14