How does one rigorously prove $mathcal{P}({a,b})={emptyset,{a},{b},{a,b}}$












0












$begingroup$


Clearly, every element of ${emptyset,{a},{b},{a,b}}$ is a subset of ${a,b}$, but I do not see how to rigorously prove the reverse implication. Using the formula for the cardinality of a finite set it can be deduced that $mathcal{P}({a,b})$ has $4$ elements, but surely there must be a more elementary way to prove such an elementary fact?






elementary-set-theory







share|cite|improve this question









$endgroup$












  • $begingroup$
    Clarify for me - what exactly is the "reverse implication," here?
    $endgroup$
    – Eevee Trainer
    Dec 7 '18 at 0:45










  • $begingroup$
    I don't think there is much to be shown. A subset of ${a,b}$ clearly has to be one of the sets given.
    $endgroup$
    – Eclipse Sun
    Dec 7 '18 at 0:46










  • $begingroup$
    Just go back to the definition, together with the fact that two sets are equal if and only if they have the same elements. If $X in mathcal{P}({a, b})$, then $X$ is a subset of ${a, b}$. So the elements of $X$ can only consist of $a$ and $b$ and so they must be on the list you wrote.
    $endgroup$
    – T. Bongers
    Dec 7 '18 at 0:46










  • $begingroup$
    @Eevee Trainer How can we be sure that every subset of {a,b} is an element of ${emptyset,{a},{b},{a,b}}$.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 0:46












  • $begingroup$
    @NAnotapplicable ask yourself is $S subseteq {a,b}$, then $|S| leq 2$. If $|S|=0$, then $S=emptyset$, if $|S|=1$, then either $S={a}$ or $S={b}$.
    $endgroup$
    – Anurag A
    Dec 7 '18 at 0:50
















0












$begingroup$


Clearly, every element of ${emptyset,{a},{b},{a,b}}$ is a subset of ${a,b}$, but I do not see how to rigorously prove the reverse implication. Using the formula for the cardinality of a finite set it can be deduced that $mathcal{P}({a,b})$ has $4$ elements, but surely there must be a more elementary way to prove such an elementary fact?






elementary-set-theory







share|cite|improve this question









$endgroup$












  • $begingroup$
    Clarify for me - what exactly is the "reverse implication," here?
    $endgroup$
    – Eevee Trainer
    Dec 7 '18 at 0:45










  • $begingroup$
    I don't think there is much to be shown. A subset of ${a,b}$ clearly has to be one of the sets given.
    $endgroup$
    – Eclipse Sun
    Dec 7 '18 at 0:46










  • $begingroup$
    Just go back to the definition, together with the fact that two sets are equal if and only if they have the same elements. If $X in mathcal{P}({a, b})$, then $X$ is a subset of ${a, b}$. So the elements of $X$ can only consist of $a$ and $b$ and so they must be on the list you wrote.
    $endgroup$
    – T. Bongers
    Dec 7 '18 at 0:46










  • $begingroup$
    @Eevee Trainer How can we be sure that every subset of {a,b} is an element of ${emptyset,{a},{b},{a,b}}$.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 0:46












  • $begingroup$
    @NAnotapplicable ask yourself is $S subseteq {a,b}$, then $|S| leq 2$. If $|S|=0$, then $S=emptyset$, if $|S|=1$, then either $S={a}$ or $S={b}$.
    $endgroup$
    – Anurag A
    Dec 7 '18 at 0:50














0












0








0





$begingroup$


Clearly, every element of ${emptyset,{a},{b},{a,b}}$ is a subset of ${a,b}$, but I do not see how to rigorously prove the reverse implication. Using the formula for the cardinality of a finite set it can be deduced that $mathcal{P}({a,b})$ has $4$ elements, but surely there must be a more elementary way to prove such an elementary fact?






elementary-set-theory







share|cite|improve this question









$endgroup$




Clearly, every element of ${emptyset,{a},{b},{a,b}}$ is a subset of ${a,b}$, but I do not see how to rigorously prove the reverse implication. Using the formula for the cardinality of a finite set it can be deduced that $mathcal{P}({a,b})$ has $4$ elements, but surely there must be a more elementary way to prove such an elementary fact?






elementary-set-theory




elementary-set-theory






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Dec 7 '18 at 0:44









NAnotapplicableNAnotapplicable

32




32












  • $begingroup$
    Clarify for me - what exactly is the "reverse implication," here?
    $endgroup$
    – Eevee Trainer
    Dec 7 '18 at 0:45










  • $begingroup$
    I don't think there is much to be shown. A subset of ${a,b}$ clearly has to be one of the sets given.
    $endgroup$
    – Eclipse Sun
    Dec 7 '18 at 0:46










  • $begingroup$
    Just go back to the definition, together with the fact that two sets are equal if and only if they have the same elements. If $X in mathcal{P}({a, b})$, then $X$ is a subset of ${a, b}$. So the elements of $X$ can only consist of $a$ and $b$ and so they must be on the list you wrote.
    $endgroup$
    – T. Bongers
    Dec 7 '18 at 0:46










  • $begingroup$
    @Eevee Trainer How can we be sure that every subset of {a,b} is an element of ${emptyset,{a},{b},{a,b}}$.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 0:46












  • $begingroup$
    @NAnotapplicable ask yourself is $S subseteq {a,b}$, then $|S| leq 2$. If $|S|=0$, then $S=emptyset$, if $|S|=1$, then either $S={a}$ or $S={b}$.
    $endgroup$
    – Anurag A
    Dec 7 '18 at 0:50


















  • $begingroup$
    Clarify for me - what exactly is the "reverse implication," here?
    $endgroup$
    – Eevee Trainer
    Dec 7 '18 at 0:45










  • $begingroup$
    I don't think there is much to be shown. A subset of ${a,b}$ clearly has to be one of the sets given.
    $endgroup$
    – Eclipse Sun
    Dec 7 '18 at 0:46










  • $begingroup$
    Just go back to the definition, together with the fact that two sets are equal if and only if they have the same elements. If $X in mathcal{P}({a, b})$, then $X$ is a subset of ${a, b}$. So the elements of $X$ can only consist of $a$ and $b$ and so they must be on the list you wrote.
    $endgroup$
    – T. Bongers
    Dec 7 '18 at 0:46










  • $begingroup$
    @Eevee Trainer How can we be sure that every subset of {a,b} is an element of ${emptyset,{a},{b},{a,b}}$.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 0:46












  • $begingroup$
    @NAnotapplicable ask yourself is $S subseteq {a,b}$, then $|S| leq 2$. If $|S|=0$, then $S=emptyset$, if $|S|=1$, then either $S={a}$ or $S={b}$.
    $endgroup$
    – Anurag A
    Dec 7 '18 at 0:50
















$begingroup$
Clarify for me - what exactly is the "reverse implication," here?
$endgroup$
– Eevee Trainer
Dec 7 '18 at 0:45




$begingroup$
Clarify for me - what exactly is the "reverse implication," here?
$endgroup$
– Eevee Trainer
Dec 7 '18 at 0:45












$begingroup$
I don't think there is much to be shown. A subset of ${a,b}$ clearly has to be one of the sets given.
$endgroup$
– Eclipse Sun
Dec 7 '18 at 0:46




$begingroup$
I don't think there is much to be shown. A subset of ${a,b}$ clearly has to be one of the sets given.
$endgroup$
– Eclipse Sun
Dec 7 '18 at 0:46












$begingroup$
Just go back to the definition, together with the fact that two sets are equal if and only if they have the same elements. If $X in mathcal{P}({a, b})$, then $X$ is a subset of ${a, b}$. So the elements of $X$ can only consist of $a$ and $b$ and so they must be on the list you wrote.
$endgroup$
– T. Bongers
Dec 7 '18 at 0:46




$begingroup$
Just go back to the definition, together with the fact that two sets are equal if and only if they have the same elements. If $X in mathcal{P}({a, b})$, then $X$ is a subset of ${a, b}$. So the elements of $X$ can only consist of $a$ and $b$ and so they must be on the list you wrote.
$endgroup$
– T. Bongers
Dec 7 '18 at 0:46












$begingroup$
@Eevee Trainer How can we be sure that every subset of {a,b} is an element of ${emptyset,{a},{b},{a,b}}$.
$endgroup$
– NAnotapplicable
Dec 7 '18 at 0:46






$begingroup$
@Eevee Trainer How can we be sure that every subset of {a,b} is an element of ${emptyset,{a},{b},{a,b}}$.
$endgroup$
– NAnotapplicable
Dec 7 '18 at 0:46














$begingroup$
@NAnotapplicable ask yourself is $S subseteq {a,b}$, then $|S| leq 2$. If $|S|=0$, then $S=emptyset$, if $|S|=1$, then either $S={a}$ or $S={b}$.
$endgroup$
– Anurag A
Dec 7 '18 at 0:50




$begingroup$
@NAnotapplicable ask yourself is $S subseteq {a,b}$, then $|S| leq 2$. If $|S|=0$, then $S=emptyset$, if $|S|=1$, then either $S={a}$ or $S={b}$.
$endgroup$
– Anurag A
Dec 7 '18 at 0:50










2 Answers
2






active

oldest

votes


















1












$begingroup$

Suppose $S in mathcal{P}({a,b})$. Then by the law of excluded middle, we have $a in S vee a notin S$; and similarly, we have $b in S vee b notin S$. This splits into four cases: $(ain S wedge bin S) vee (ain S wedge b notin S) vee (anotin S wedge bin S) vee (anotin S wedge bnotin S)$. I'll illustrate one particular case, where $a in S$ and $b notin S$.



Now, for any $x$, suppose $x in S$. Since $S in mathcal{P}({a,b})$, $S subseteq {a,b}$, so this implies $x in {a,b}$, which is equivalent to $x = a vee x = b$. But in the second case, $x = b$, $x in S$, and $b notin S$ leads to a contradiction. Therefore, $x in S rightarrow x = a$; and conversely, $x = a rightarrow x in S$ by substitution with our assumption $a in S$. In conclusion, we have shown $forall x, x in S leftrightarrow x = a leftrightarrow x in { a }$. By the extensionality axiom, this implies that $S = { a }$, so $S in {emptyset,{a},{b},{a,b}}$.



Combining the cases, we will eventually get a proof of $forall S, S in mathcal{P}({a,b}) rightarrow S in {emptyset,{a},{b},{a,b}}$. For the other direction, $S in {emptyset,{a},{b},{a,b}}$ implies $S = emptyset vee S = {a} vee S={b} vee S={a,b}$. I will leave to you to do a proof by cases that each of these implies $S in mathcal{P}({a,b})$.



Therefore, we have $forall S, S in mathcal{P}({a,b}) leftrightarrow S in {emptyset,{a},{b},{a,b}}$, which by another application of the extensionality axiom implies that $mathcal{P}({a,b}) = {emptyset,{a},{b},{a,b}}$.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Bravo! Exactly what I was looking for.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 1:26










  • $begingroup$
    @NAnotapplicable Out of genuine curiosity, how is this any different than enumeration of the sets in your eyes? During the construction of the cases of consideration, you are forced to explicitly write out every possible subset. The remainder of the proof ends up being even more complicated than the combinatorial argument.
    $endgroup$
    – RandomMathGuy
    Dec 7 '18 at 2:42












  • $begingroup$
    @RandomMathGuy You are right: the answer I selected is indeed more complicated than yours. I prefer it, however, because it relies directly on the definitions of power set, pair set, etc. rather than introducing the more complicated (as I see it) concept of cardinality, which, although undoubtedly useful, did not seem necessary to prove such a simple assertion. My sense of 'mathematical simplicity' is clearly not the same as yours; both answers have their merits and weaknesses. They're both correct though, (and both appreciated), so which one I prefer is a subjective matter. No hard feelings.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 4:20



















1












$begingroup$

I think that you are not going to find a more "elementary" way of working with finite powersets precisely because the powerset operation is axiomatic. The fact that such a set exists is given, you don't have to prove it; thus verifying that a given set is a powerset must boil down to enumerating the elements.



Now, I'm no logician, so I could be wrong. If someone out there has better insight then down-vote this into oblivion.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    But even after enumerating the elements, how can you know that there is not a subset that you missed?
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 0:54










  • $begingroup$
    @NAnotapplicable If you believe the counting argument for the size of the powerset being $2^{|S|}$, then all you have to do is show that all elements are distinct and that there are the right number of them. If you don't believe the counting argument we will need to go back and address something else that is foundational.
    $endgroup$
    – RandomMathGuy
    Dec 7 '18 at 0:56












  • $begingroup$
    Thank you, I do indeed believe the counting argument and your proof is perfectly valid. Nonetheless, it seems to me that there must be a simpler way to prove this.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 0:57












  • $begingroup$
    @NAnotapplicable The issue I'm dancing around is that this is the simple way to prove that a set is a powerset. It is ugly because it is purely computational, but that doesn't make it complicated. I really meant what I wrote; you are dealing with an object that is at the ground floor of ZFC. There is a very good chance that proving a finite set is the powerset of some other set can only be done via enumeration.
    $endgroup$
    – RandomMathGuy
    Dec 7 '18 at 0:59












  • $begingroup$
    Okay then. I admit I'm not fully satisfied but if that really is the simplest way than I guess I never will be... Thanks for your input.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 1:02













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
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3029292%2fhow-does-one-rigorously-prove-mathcalp-a-b-emptyset-a-b-a%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









1












$begingroup$

Suppose $S in mathcal{P}({a,b})$. Then by the law of excluded middle, we have $a in S vee a notin S$; and similarly, we have $b in S vee b notin S$. This splits into four cases: $(ain S wedge bin S) vee (ain S wedge b notin S) vee (anotin S wedge bin S) vee (anotin S wedge bnotin S)$. I'll illustrate one particular case, where $a in S$ and $b notin S$.



Now, for any $x$, suppose $x in S$. Since $S in mathcal{P}({a,b})$, $S subseteq {a,b}$, so this implies $x in {a,b}$, which is equivalent to $x = a vee x = b$. But in the second case, $x = b$, $x in S$, and $b notin S$ leads to a contradiction. Therefore, $x in S rightarrow x = a$; and conversely, $x = a rightarrow x in S$ by substitution with our assumption $a in S$. In conclusion, we have shown $forall x, x in S leftrightarrow x = a leftrightarrow x in { a }$. By the extensionality axiom, this implies that $S = { a }$, so $S in {emptyset,{a},{b},{a,b}}$.



Combining the cases, we will eventually get a proof of $forall S, S in mathcal{P}({a,b}) rightarrow S in {emptyset,{a},{b},{a,b}}$. For the other direction, $S in {emptyset,{a},{b},{a,b}}$ implies $S = emptyset vee S = {a} vee S={b} vee S={a,b}$. I will leave to you to do a proof by cases that each of these implies $S in mathcal{P}({a,b})$.



Therefore, we have $forall S, S in mathcal{P}({a,b}) leftrightarrow S in {emptyset,{a},{b},{a,b}}$, which by another application of the extensionality axiom implies that $mathcal{P}({a,b}) = {emptyset,{a},{b},{a,b}}$.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Bravo! Exactly what I was looking for.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 1:26










  • $begingroup$
    @NAnotapplicable Out of genuine curiosity, how is this any different than enumeration of the sets in your eyes? During the construction of the cases of consideration, you are forced to explicitly write out every possible subset. The remainder of the proof ends up being even more complicated than the combinatorial argument.
    $endgroup$
    – RandomMathGuy
    Dec 7 '18 at 2:42












  • $begingroup$
    @RandomMathGuy You are right: the answer I selected is indeed more complicated than yours. I prefer it, however, because it relies directly on the definitions of power set, pair set, etc. rather than introducing the more complicated (as I see it) concept of cardinality, which, although undoubtedly useful, did not seem necessary to prove such a simple assertion. My sense of 'mathematical simplicity' is clearly not the same as yours; both answers have their merits and weaknesses. They're both correct though, (and both appreciated), so which one I prefer is a subjective matter. No hard feelings.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 4:20
















1












$begingroup$

Suppose $S in mathcal{P}({a,b})$. Then by the law of excluded middle, we have $a in S vee a notin S$; and similarly, we have $b in S vee b notin S$. This splits into four cases: $(ain S wedge bin S) vee (ain S wedge b notin S) vee (anotin S wedge bin S) vee (anotin S wedge bnotin S)$. I'll illustrate one particular case, where $a in S$ and $b notin S$.



Now, for any $x$, suppose $x in S$. Since $S in mathcal{P}({a,b})$, $S subseteq {a,b}$, so this implies $x in {a,b}$, which is equivalent to $x = a vee x = b$. But in the second case, $x = b$, $x in S$, and $b notin S$ leads to a contradiction. Therefore, $x in S rightarrow x = a$; and conversely, $x = a rightarrow x in S$ by substitution with our assumption $a in S$. In conclusion, we have shown $forall x, x in S leftrightarrow x = a leftrightarrow x in { a }$. By the extensionality axiom, this implies that $S = { a }$, so $S in {emptyset,{a},{b},{a,b}}$.



Combining the cases, we will eventually get a proof of $forall S, S in mathcal{P}({a,b}) rightarrow S in {emptyset,{a},{b},{a,b}}$. For the other direction, $S in {emptyset,{a},{b},{a,b}}$ implies $S = emptyset vee S = {a} vee S={b} vee S={a,b}$. I will leave to you to do a proof by cases that each of these implies $S in mathcal{P}({a,b})$.



Therefore, we have $forall S, S in mathcal{P}({a,b}) leftrightarrow S in {emptyset,{a},{b},{a,b}}$, which by another application of the extensionality axiom implies that $mathcal{P}({a,b}) = {emptyset,{a},{b},{a,b}}$.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Bravo! Exactly what I was looking for.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 1:26










  • $begingroup$
    @NAnotapplicable Out of genuine curiosity, how is this any different than enumeration of the sets in your eyes? During the construction of the cases of consideration, you are forced to explicitly write out every possible subset. The remainder of the proof ends up being even more complicated than the combinatorial argument.
    $endgroup$
    – RandomMathGuy
    Dec 7 '18 at 2:42












  • $begingroup$
    @RandomMathGuy You are right: the answer I selected is indeed more complicated than yours. I prefer it, however, because it relies directly on the definitions of power set, pair set, etc. rather than introducing the more complicated (as I see it) concept of cardinality, which, although undoubtedly useful, did not seem necessary to prove such a simple assertion. My sense of 'mathematical simplicity' is clearly not the same as yours; both answers have their merits and weaknesses. They're both correct though, (and both appreciated), so which one I prefer is a subjective matter. No hard feelings.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 4:20














1












1








1





$begingroup$

Suppose $S in mathcal{P}({a,b})$. Then by the law of excluded middle, we have $a in S vee a notin S$; and similarly, we have $b in S vee b notin S$. This splits into four cases: $(ain S wedge bin S) vee (ain S wedge b notin S) vee (anotin S wedge bin S) vee (anotin S wedge bnotin S)$. I'll illustrate one particular case, where $a in S$ and $b notin S$.



Now, for any $x$, suppose $x in S$. Since $S in mathcal{P}({a,b})$, $S subseteq {a,b}$, so this implies $x in {a,b}$, which is equivalent to $x = a vee x = b$. But in the second case, $x = b$, $x in S$, and $b notin S$ leads to a contradiction. Therefore, $x in S rightarrow x = a$; and conversely, $x = a rightarrow x in S$ by substitution with our assumption $a in S$. In conclusion, we have shown $forall x, x in S leftrightarrow x = a leftrightarrow x in { a }$. By the extensionality axiom, this implies that $S = { a }$, so $S in {emptyset,{a},{b},{a,b}}$.



Combining the cases, we will eventually get a proof of $forall S, S in mathcal{P}({a,b}) rightarrow S in {emptyset,{a},{b},{a,b}}$. For the other direction, $S in {emptyset,{a},{b},{a,b}}$ implies $S = emptyset vee S = {a} vee S={b} vee S={a,b}$. I will leave to you to do a proof by cases that each of these implies $S in mathcal{P}({a,b})$.



Therefore, we have $forall S, S in mathcal{P}({a,b}) leftrightarrow S in {emptyset,{a},{b},{a,b}}$, which by another application of the extensionality axiom implies that $mathcal{P}({a,b}) = {emptyset,{a},{b},{a,b}}$.






share|cite|improve this answer









$endgroup$



Suppose $S in mathcal{P}({a,b})$. Then by the law of excluded middle, we have $a in S vee a notin S$; and similarly, we have $b in S vee b notin S$. This splits into four cases: $(ain S wedge bin S) vee (ain S wedge b notin S) vee (anotin S wedge bin S) vee (anotin S wedge bnotin S)$. I'll illustrate one particular case, where $a in S$ and $b notin S$.



Now, for any $x$, suppose $x in S$. Since $S in mathcal{P}({a,b})$, $S subseteq {a,b}$, so this implies $x in {a,b}$, which is equivalent to $x = a vee x = b$. But in the second case, $x = b$, $x in S$, and $b notin S$ leads to a contradiction. Therefore, $x in S rightarrow x = a$; and conversely, $x = a rightarrow x in S$ by substitution with our assumption $a in S$. In conclusion, we have shown $forall x, x in S leftrightarrow x = a leftrightarrow x in { a }$. By the extensionality axiom, this implies that $S = { a }$, so $S in {emptyset,{a},{b},{a,b}}$.



Combining the cases, we will eventually get a proof of $forall S, S in mathcal{P}({a,b}) rightarrow S in {emptyset,{a},{b},{a,b}}$. For the other direction, $S in {emptyset,{a},{b},{a,b}}$ implies $S = emptyset vee S = {a} vee S={b} vee S={a,b}$. I will leave to you to do a proof by cases that each of these implies $S in mathcal{P}({a,b})$.



Therefore, we have $forall S, S in mathcal{P}({a,b}) leftrightarrow S in {emptyset,{a},{b},{a,b}}$, which by another application of the extensionality axiom implies that $mathcal{P}({a,b}) = {emptyset,{a},{b},{a,b}}$.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Dec 7 '18 at 1:17









Daniel ScheplerDaniel Schepler

8,7291620




8,7291620












  • $begingroup$
    Bravo! Exactly what I was looking for.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 1:26










  • $begingroup$
    @NAnotapplicable Out of genuine curiosity, how is this any different than enumeration of the sets in your eyes? During the construction of the cases of consideration, you are forced to explicitly write out every possible subset. The remainder of the proof ends up being even more complicated than the combinatorial argument.
    $endgroup$
    – RandomMathGuy
    Dec 7 '18 at 2:42












  • $begingroup$
    @RandomMathGuy You are right: the answer I selected is indeed more complicated than yours. I prefer it, however, because it relies directly on the definitions of power set, pair set, etc. rather than introducing the more complicated (as I see it) concept of cardinality, which, although undoubtedly useful, did not seem necessary to prove such a simple assertion. My sense of 'mathematical simplicity' is clearly not the same as yours; both answers have their merits and weaknesses. They're both correct though, (and both appreciated), so which one I prefer is a subjective matter. No hard feelings.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 4:20


















  • $begingroup$
    Bravo! Exactly what I was looking for.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 1:26










  • $begingroup$
    @NAnotapplicable Out of genuine curiosity, how is this any different than enumeration of the sets in your eyes? During the construction of the cases of consideration, you are forced to explicitly write out every possible subset. The remainder of the proof ends up being even more complicated than the combinatorial argument.
    $endgroup$
    – RandomMathGuy
    Dec 7 '18 at 2:42












  • $begingroup$
    @RandomMathGuy You are right: the answer I selected is indeed more complicated than yours. I prefer it, however, because it relies directly on the definitions of power set, pair set, etc. rather than introducing the more complicated (as I see it) concept of cardinality, which, although undoubtedly useful, did not seem necessary to prove such a simple assertion. My sense of 'mathematical simplicity' is clearly not the same as yours; both answers have their merits and weaknesses. They're both correct though, (and both appreciated), so which one I prefer is a subjective matter. No hard feelings.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 4:20
















$begingroup$
Bravo! Exactly what I was looking for.
$endgroup$
– NAnotapplicable
Dec 7 '18 at 1:26




$begingroup$
Bravo! Exactly what I was looking for.
$endgroup$
– NAnotapplicable
Dec 7 '18 at 1:26












$begingroup$
@NAnotapplicable Out of genuine curiosity, how is this any different than enumeration of the sets in your eyes? During the construction of the cases of consideration, you are forced to explicitly write out every possible subset. The remainder of the proof ends up being even more complicated than the combinatorial argument.
$endgroup$
– RandomMathGuy
Dec 7 '18 at 2:42






$begingroup$
@NAnotapplicable Out of genuine curiosity, how is this any different than enumeration of the sets in your eyes? During the construction of the cases of consideration, you are forced to explicitly write out every possible subset. The remainder of the proof ends up being even more complicated than the combinatorial argument.
$endgroup$
– RandomMathGuy
Dec 7 '18 at 2:42














$begingroup$
@RandomMathGuy You are right: the answer I selected is indeed more complicated than yours. I prefer it, however, because it relies directly on the definitions of power set, pair set, etc. rather than introducing the more complicated (as I see it) concept of cardinality, which, although undoubtedly useful, did not seem necessary to prove such a simple assertion. My sense of 'mathematical simplicity' is clearly not the same as yours; both answers have their merits and weaknesses. They're both correct though, (and both appreciated), so which one I prefer is a subjective matter. No hard feelings.
$endgroup$
– NAnotapplicable
Dec 7 '18 at 4:20




$begingroup$
@RandomMathGuy You are right: the answer I selected is indeed more complicated than yours. I prefer it, however, because it relies directly on the definitions of power set, pair set, etc. rather than introducing the more complicated (as I see it) concept of cardinality, which, although undoubtedly useful, did not seem necessary to prove such a simple assertion. My sense of 'mathematical simplicity' is clearly not the same as yours; both answers have their merits and weaknesses. They're both correct though, (and both appreciated), so which one I prefer is a subjective matter. No hard feelings.
$endgroup$
– NAnotapplicable
Dec 7 '18 at 4:20











1












$begingroup$

I think that you are not going to find a more "elementary" way of working with finite powersets precisely because the powerset operation is axiomatic. The fact that such a set exists is given, you don't have to prove it; thus verifying that a given set is a powerset must boil down to enumerating the elements.



Now, I'm no logician, so I could be wrong. If someone out there has better insight then down-vote this into oblivion.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    But even after enumerating the elements, how can you know that there is not a subset that you missed?
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 0:54










  • $begingroup$
    @NAnotapplicable If you believe the counting argument for the size of the powerset being $2^{|S|}$, then all you have to do is show that all elements are distinct and that there are the right number of them. If you don't believe the counting argument we will need to go back and address something else that is foundational.
    $endgroup$
    – RandomMathGuy
    Dec 7 '18 at 0:56












  • $begingroup$
    Thank you, I do indeed believe the counting argument and your proof is perfectly valid. Nonetheless, it seems to me that there must be a simpler way to prove this.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 0:57












  • $begingroup$
    @NAnotapplicable The issue I'm dancing around is that this is the simple way to prove that a set is a powerset. It is ugly because it is purely computational, but that doesn't make it complicated. I really meant what I wrote; you are dealing with an object that is at the ground floor of ZFC. There is a very good chance that proving a finite set is the powerset of some other set can only be done via enumeration.
    $endgroup$
    – RandomMathGuy
    Dec 7 '18 at 0:59












  • $begingroup$
    Okay then. I admit I'm not fully satisfied but if that really is the simplest way than I guess I never will be... Thanks for your input.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 1:02


















1












$begingroup$

I think that you are not going to find a more "elementary" way of working with finite powersets precisely because the powerset operation is axiomatic. The fact that such a set exists is given, you don't have to prove it; thus verifying that a given set is a powerset must boil down to enumerating the elements.



Now, I'm no logician, so I could be wrong. If someone out there has better insight then down-vote this into oblivion.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    But even after enumerating the elements, how can you know that there is not a subset that you missed?
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 0:54










  • $begingroup$
    @NAnotapplicable If you believe the counting argument for the size of the powerset being $2^{|S|}$, then all you have to do is show that all elements are distinct and that there are the right number of them. If you don't believe the counting argument we will need to go back and address something else that is foundational.
    $endgroup$
    – RandomMathGuy
    Dec 7 '18 at 0:56












  • $begingroup$
    Thank you, I do indeed believe the counting argument and your proof is perfectly valid. Nonetheless, it seems to me that there must be a simpler way to prove this.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 0:57












  • $begingroup$
    @NAnotapplicable The issue I'm dancing around is that this is the simple way to prove that a set is a powerset. It is ugly because it is purely computational, but that doesn't make it complicated. I really meant what I wrote; you are dealing with an object that is at the ground floor of ZFC. There is a very good chance that proving a finite set is the powerset of some other set can only be done via enumeration.
    $endgroup$
    – RandomMathGuy
    Dec 7 '18 at 0:59












  • $begingroup$
    Okay then. I admit I'm not fully satisfied but if that really is the simplest way than I guess I never will be... Thanks for your input.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 1:02
















1












1








1





$begingroup$

I think that you are not going to find a more "elementary" way of working with finite powersets precisely because the powerset operation is axiomatic. The fact that such a set exists is given, you don't have to prove it; thus verifying that a given set is a powerset must boil down to enumerating the elements.



Now, I'm no logician, so I could be wrong. If someone out there has better insight then down-vote this into oblivion.






share|cite|improve this answer









$endgroup$



I think that you are not going to find a more "elementary" way of working with finite powersets precisely because the powerset operation is axiomatic. The fact that such a set exists is given, you don't have to prove it; thus verifying that a given set is a powerset must boil down to enumerating the elements.



Now, I'm no logician, so I could be wrong. If someone out there has better insight then down-vote this into oblivion.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Dec 7 '18 at 0:51









RandomMathGuyRandomMathGuy

1192




1192












  • $begingroup$
    But even after enumerating the elements, how can you know that there is not a subset that you missed?
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 0:54










  • $begingroup$
    @NAnotapplicable If you believe the counting argument for the size of the powerset being $2^{|S|}$, then all you have to do is show that all elements are distinct and that there are the right number of them. If you don't believe the counting argument we will need to go back and address something else that is foundational.
    $endgroup$
    – RandomMathGuy
    Dec 7 '18 at 0:56












  • $begingroup$
    Thank you, I do indeed believe the counting argument and your proof is perfectly valid. Nonetheless, it seems to me that there must be a simpler way to prove this.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 0:57












  • $begingroup$
    @NAnotapplicable The issue I'm dancing around is that this is the simple way to prove that a set is a powerset. It is ugly because it is purely computational, but that doesn't make it complicated. I really meant what I wrote; you are dealing with an object that is at the ground floor of ZFC. There is a very good chance that proving a finite set is the powerset of some other set can only be done via enumeration.
    $endgroup$
    – RandomMathGuy
    Dec 7 '18 at 0:59












  • $begingroup$
    Okay then. I admit I'm not fully satisfied but if that really is the simplest way than I guess I never will be... Thanks for your input.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 1:02




















  • $begingroup$
    But even after enumerating the elements, how can you know that there is not a subset that you missed?
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 0:54










  • $begingroup$
    @NAnotapplicable If you believe the counting argument for the size of the powerset being $2^{|S|}$, then all you have to do is show that all elements are distinct and that there are the right number of them. If you don't believe the counting argument we will need to go back and address something else that is foundational.
    $endgroup$
    – RandomMathGuy
    Dec 7 '18 at 0:56












  • $begingroup$
    Thank you, I do indeed believe the counting argument and your proof is perfectly valid. Nonetheless, it seems to me that there must be a simpler way to prove this.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 0:57












  • $begingroup$
    @NAnotapplicable The issue I'm dancing around is that this is the simple way to prove that a set is a powerset. It is ugly because it is purely computational, but that doesn't make it complicated. I really meant what I wrote; you are dealing with an object that is at the ground floor of ZFC. There is a very good chance that proving a finite set is the powerset of some other set can only be done via enumeration.
    $endgroup$
    – RandomMathGuy
    Dec 7 '18 at 0:59












  • $begingroup$
    Okay then. I admit I'm not fully satisfied but if that really is the simplest way than I guess I never will be... Thanks for your input.
    $endgroup$
    – NAnotapplicable
    Dec 7 '18 at 1:02


















$begingroup$
But even after enumerating the elements, how can you know that there is not a subset that you missed?
$endgroup$
– NAnotapplicable
Dec 7 '18 at 0:54




$begingroup$
But even after enumerating the elements, how can you know that there is not a subset that you missed?
$endgroup$
– NAnotapplicable
Dec 7 '18 at 0:54












$begingroup$
@NAnotapplicable If you believe the counting argument for the size of the powerset being $2^{|S|}$, then all you have to do is show that all elements are distinct and that there are the right number of them. If you don't believe the counting argument we will need to go back and address something else that is foundational.
$endgroup$
– RandomMathGuy
Dec 7 '18 at 0:56






$begingroup$
@NAnotapplicable If you believe the counting argument for the size of the powerset being $2^{|S|}$, then all you have to do is show that all elements are distinct and that there are the right number of them. If you don't believe the counting argument we will need to go back and address something else that is foundational.
$endgroup$
– RandomMathGuy
Dec 7 '18 at 0:56














$begingroup$
Thank you, I do indeed believe the counting argument and your proof is perfectly valid. Nonetheless, it seems to me that there must be a simpler way to prove this.
$endgroup$
– NAnotapplicable
Dec 7 '18 at 0:57






$begingroup$
Thank you, I do indeed believe the counting argument and your proof is perfectly valid. Nonetheless, it seems to me that there must be a simpler way to prove this.
$endgroup$
– NAnotapplicable
Dec 7 '18 at 0:57














$begingroup$
@NAnotapplicable The issue I'm dancing around is that this is the simple way to prove that a set is a powerset. It is ugly because it is purely computational, but that doesn't make it complicated. I really meant what I wrote; you are dealing with an object that is at the ground floor of ZFC. There is a very good chance that proving a finite set is the powerset of some other set can only be done via enumeration.
$endgroup$
– RandomMathGuy
Dec 7 '18 at 0:59






$begingroup$
@NAnotapplicable The issue I'm dancing around is that this is the simple way to prove that a set is a powerset. It is ugly because it is purely computational, but that doesn't make it complicated. I really meant what I wrote; you are dealing with an object that is at the ground floor of ZFC. There is a very good chance that proving a finite set is the powerset of some other set can only be done via enumeration.
$endgroup$
– RandomMathGuy
Dec 7 '18 at 0:59














$begingroup$
Okay then. I admit I'm not fully satisfied but if that really is the simplest way than I guess I never will be... Thanks for your input.
$endgroup$
– NAnotapplicable
Dec 7 '18 at 1:02






$begingroup$
Okay then. I admit I'm not fully satisfied but if that really is the simplest way than I guess I never will be... Thanks for your input.
$endgroup$
– NAnotapplicable
Dec 7 '18 at 1:02




















draft saved

draft discarded




















































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.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3029292%2fhow-does-one-rigorously-prove-mathcalp-a-b-emptyset-a-b-a%23new-answer', 'question_page');
}
);

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







-

Popular posts from this blog

Le Mesnil-Réaume

Image
Le Mesnil-Réaume Region Normandie Département Seine-Maritime Arrondissement Dieppe Kanton Eu Gemeindeverband Villes Sœurs Koordinaten 49° 58′  N , 1° 27′  O 49.9725 1.4463888888889 Koordinaten: 49° 58′  N , 1° 27′  O Höhe 92–156 m Fläche 5,55 km 2 Einwohner 793 (1. Januar 2016) Bevölkerungsdichte 143 Einw./km 2 Postleitzahl 76260 INSEE-Code 76435 Website http://www.mesnil-reaume.net/ Rathaus (Mairie) und Schule von Le Mesnil-Réaume Le Mesnil-Réaume ist eine französische Gemeinde mit 793 Einwohnern (Stand: 1. Januar 2016) im Département Seine-Maritime in der Region Normandie (vor 2016 Haute-Normandie). Sie gehört zum Arrondissement Dieppe und zum Kanton Eu. Die Einwohner werden Mesnillais genannt. Inhaltsverzeichnis 1 Geographie 2 Bevölkerungsentwicklung 3 Sehenswürdigkeiten 4 Weblinks Geographie | Le Mesnil-Réaume liegt etwa 43 Kilomet
Read more

Bundesstraße 106

Image
Dieser Artikel beschreibt die Bundesstraße 106 in Deutschland. Zur gleichnamigen Straße in Österreich siehe Mölltal Straße. Vorlage:Infobox hochrangige Straße/Wartung/DE-B Bundesstraße 106 in Deutschland Karte Basisdaten Betreiber: Deutschland  Bundesrepublik Deutschland Straßenbeginn: Wismar ( 53° 54′  N , 11° 24′  O 53.900536 11.396875 ) Straßenende: Schwerin ( 53° 36′  N , 11° 24′  O 53.592785 11.404892 ) Gesamtlänge: 40,7 km Bundesland: Mecklenburg-Vorpommern Ausbauzustand: zweistreifig [1] Bundesstraße 106 in Schwerin (Umgehungsstraße) Straßenverlauf Land Mecklenburg-Vorpommern Landkreis Nordwestmecklenburg Ortsumgehung Wismar Wallensteingraben über   Dorf Mecklenburg Wallensteingraben Groß Stieten Bad Kleinen OT Niendorf Bahnstrecke Lübeck–Bad Kleinen Zickhusen Lübstorf Klein Trebbow OT Kirch Stück
Read more

Ida-Boy-Ed-Garten

Image
Die Lage des Ida-Boy-Ed-Gartens, rot markiert Der Ida-Boy-Ed-Garten Der Ida-Boy-Ed-Garten, Blick von der Wakenitzmauer durch das Tor in der Stadtmauer Der Ida-Boy-Ed-Garten ist eine Straße der Lübecker Altstadt. Inhaltsverzeichnis 1 Lage 2 Geschichte 3 Literatur 4 Weblinks Lage | Der etwa 90 Meter lange Ida-Boy-Ed-Garten befindet sich an der nördlichen Spitze der Altstadtinsel, vor dem Burgtor. Die in einem Bogen durch eine Grünanlage hangaufwärts führende Straße verbindet die Wakenitzmauer mit der Burgtorbrücke. Geschichte | Der heutige Ida-Boy-Ed-Garten wurde ursprünglich als Verlängerung der Wakenitzmauer angelegt. 1903 wurde in den erhaltenen Teil der mittelalterlichen Stadtmauer, an dem die Wakenitzmauer bei der Einmündung der Kaiserstraße begann, ein Tor mit einem großen Bogen für die Durchführung der Straße und zwei kleineren seitlichen Öffnungen für Fußgänger gebrochen, um für die neu errichteten Wohnhäuser in diesem Bereich
Read more