The total number of subsets is $2^n$ for $n$ elements












11












$begingroup$


In my probability book, it says that to count the total number of subsets of n elements is a process of $n$ stages with binary choice of either adding this element to the subset or not to add it. Therefore, the total number is
$$2^n$$



But, for instance, we have 3 elements, according to this formula, there are 2 to the power of 3 elements, namely 8, which are
$${emptyset},A,B,C, AB, AC, BC, ABC$$



However, I have a hard time of imagining the process or N stages binary choice that form this many subsets. Can anyone explain/help me to understand it? I mean, ABC, if we are making the choice of A, put it in or do not put it in, exactly which subset are we choosing to put in or not? Thank you.










share|cite|improve this question









New contributor




commentallez-vous is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$








  • 1




    $begingroup$
    I'm not sure what you were trying to ask. I wrote an answer and other people seem to think it doesn't answer the question. Were you asking how for any finite set, it's possible to count all the subsets of that set or were you asking whether there is a uniform way of defining for all finite sets how to do it for that set?
    $endgroup$
    – Timothy
    yesterday






  • 1




    $begingroup$
    @Timothy I was having trouble understanding this in the process described by Eelvex's answer, but now I understood...thanks!
    $endgroup$
    – commentallez-vous
    yesterday










  • $begingroup$
    I'm confused. Was it my answer that you understood? If so, the fact that my answer got 5 downvotes probably means that people sometimes don't know what confusion the OP has when they ask a question.
    $endgroup$
    – Timothy
    yesterday






  • 1




    $begingroup$
    @Timothy, hi Timothey, sorry I haven't checked your answer yet...and I never gave people down vote...but I'll read it now.
    $endgroup$
    – commentallez-vous
    yesterday
















11












$begingroup$


In my probability book, it says that to count the total number of subsets of n elements is a process of $n$ stages with binary choice of either adding this element to the subset or not to add it. Therefore, the total number is
$$2^n$$



But, for instance, we have 3 elements, according to this formula, there are 2 to the power of 3 elements, namely 8, which are
$${emptyset},A,B,C, AB, AC, BC, ABC$$



However, I have a hard time of imagining the process or N stages binary choice that form this many subsets. Can anyone explain/help me to understand it? I mean, ABC, if we are making the choice of A, put it in or do not put it in, exactly which subset are we choosing to put in or not? Thank you.










share|cite|improve this question









New contributor




commentallez-vous is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$








  • 1




    $begingroup$
    I'm not sure what you were trying to ask. I wrote an answer and other people seem to think it doesn't answer the question. Were you asking how for any finite set, it's possible to count all the subsets of that set or were you asking whether there is a uniform way of defining for all finite sets how to do it for that set?
    $endgroup$
    – Timothy
    yesterday






  • 1




    $begingroup$
    @Timothy I was having trouble understanding this in the process described by Eelvex's answer, but now I understood...thanks!
    $endgroup$
    – commentallez-vous
    yesterday










  • $begingroup$
    I'm confused. Was it my answer that you understood? If so, the fact that my answer got 5 downvotes probably means that people sometimes don't know what confusion the OP has when they ask a question.
    $endgroup$
    – Timothy
    yesterday






  • 1




    $begingroup$
    @Timothy, hi Timothey, sorry I haven't checked your answer yet...and I never gave people down vote...but I'll read it now.
    $endgroup$
    – commentallez-vous
    yesterday














11












11








11


1



$begingroup$


In my probability book, it says that to count the total number of subsets of n elements is a process of $n$ stages with binary choice of either adding this element to the subset or not to add it. Therefore, the total number is
$$2^n$$



But, for instance, we have 3 elements, according to this formula, there are 2 to the power of 3 elements, namely 8, which are
$${emptyset},A,B,C, AB, AC, BC, ABC$$



However, I have a hard time of imagining the process or N stages binary choice that form this many subsets. Can anyone explain/help me to understand it? I mean, ABC, if we are making the choice of A, put it in or do not put it in, exactly which subset are we choosing to put in or not? Thank you.










share|cite|improve this question









New contributor




commentallez-vous is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$




In my probability book, it says that to count the total number of subsets of n elements is a process of $n$ stages with binary choice of either adding this element to the subset or not to add it. Therefore, the total number is
$$2^n$$



But, for instance, we have 3 elements, according to this formula, there are 2 to the power of 3 elements, namely 8, which are
$${emptyset},A,B,C, AB, AC, BC, ABC$$



However, I have a hard time of imagining the process or N stages binary choice that form this many subsets. Can anyone explain/help me to understand it? I mean, ABC, if we are making the choice of A, put it in or do not put it in, exactly which subset are we choosing to put in or not? Thank you.







probability probability-theory permutations combinations






share|cite|improve this question









New contributor




commentallez-vous is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|cite|improve this question









New contributor




commentallez-vous is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this question




share|cite|improve this question








edited yesterday









Asaf Karagila

302k32427757




302k32427757






New contributor




commentallez-vous is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 2 days ago









commentallez-vouscommentallez-vous

1858




1858




New contributor




commentallez-vous is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





commentallez-vous is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






commentallez-vous is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








  • 1




    $begingroup$
    I'm not sure what you were trying to ask. I wrote an answer and other people seem to think it doesn't answer the question. Were you asking how for any finite set, it's possible to count all the subsets of that set or were you asking whether there is a uniform way of defining for all finite sets how to do it for that set?
    $endgroup$
    – Timothy
    yesterday






  • 1




    $begingroup$
    @Timothy I was having trouble understanding this in the process described by Eelvex's answer, but now I understood...thanks!
    $endgroup$
    – commentallez-vous
    yesterday










  • $begingroup$
    I'm confused. Was it my answer that you understood? If so, the fact that my answer got 5 downvotes probably means that people sometimes don't know what confusion the OP has when they ask a question.
    $endgroup$
    – Timothy
    yesterday






  • 1




    $begingroup$
    @Timothy, hi Timothey, sorry I haven't checked your answer yet...and I never gave people down vote...but I'll read it now.
    $endgroup$
    – commentallez-vous
    yesterday














  • 1




    $begingroup$
    I'm not sure what you were trying to ask. I wrote an answer and other people seem to think it doesn't answer the question. Were you asking how for any finite set, it's possible to count all the subsets of that set or were you asking whether there is a uniform way of defining for all finite sets how to do it for that set?
    $endgroup$
    – Timothy
    yesterday






  • 1




    $begingroup$
    @Timothy I was having trouble understanding this in the process described by Eelvex's answer, but now I understood...thanks!
    $endgroup$
    – commentallez-vous
    yesterday










  • $begingroup$
    I'm confused. Was it my answer that you understood? If so, the fact that my answer got 5 downvotes probably means that people sometimes don't know what confusion the OP has when they ask a question.
    $endgroup$
    – Timothy
    yesterday






  • 1




    $begingroup$
    @Timothy, hi Timothey, sorry I haven't checked your answer yet...and I never gave people down vote...but I'll read it now.
    $endgroup$
    – commentallez-vous
    yesterday








1




1




$begingroup$
I'm not sure what you were trying to ask. I wrote an answer and other people seem to think it doesn't answer the question. Were you asking how for any finite set, it's possible to count all the subsets of that set or were you asking whether there is a uniform way of defining for all finite sets how to do it for that set?
$endgroup$
– Timothy
yesterday




$begingroup$
I'm not sure what you were trying to ask. I wrote an answer and other people seem to think it doesn't answer the question. Were you asking how for any finite set, it's possible to count all the subsets of that set or were you asking whether there is a uniform way of defining for all finite sets how to do it for that set?
$endgroup$
– Timothy
yesterday




1




1




$begingroup$
@Timothy I was having trouble understanding this in the process described by Eelvex's answer, but now I understood...thanks!
$endgroup$
– commentallez-vous
yesterday




$begingroup$
@Timothy I was having trouble understanding this in the process described by Eelvex's answer, but now I understood...thanks!
$endgroup$
– commentallez-vous
yesterday












$begingroup$
I'm confused. Was it my answer that you understood? If so, the fact that my answer got 5 downvotes probably means that people sometimes don't know what confusion the OP has when they ask a question.
$endgroup$
– Timothy
yesterday




$begingroup$
I'm confused. Was it my answer that you understood? If so, the fact that my answer got 5 downvotes probably means that people sometimes don't know what confusion the OP has when they ask a question.
$endgroup$
– Timothy
yesterday




1




1




$begingroup$
@Timothy, hi Timothey, sorry I haven't checked your answer yet...and I never gave people down vote...but I'll read it now.
$endgroup$
– commentallez-vous
yesterday




$begingroup$
@Timothy, hi Timothey, sorry I haven't checked your answer yet...and I never gave people down vote...but I'll read it now.
$endgroup$
– commentallez-vous
yesterday










7 Answers
7






active

oldest

votes


















61












$begingroup$

enter image description here




  • "Include A?" is stage 1

  • "Include B?" is stage 2

  • "Include C?" is stage 3.






share|cite|improve this answer









$endgroup$





















    21












    $begingroup$

    Label your $n$ elements so that $X={x_{1},...,x_{n}}$. We're going to form a one-to-one correspondence between the subsets of $X$ and the set of length-$n$ binary strings as follows. Given a binary string
    $$a_{1}cdots a_{n}$$
    imagine that $a_{i}=1$ means "include $x_{i}$ in this subset" and $a_{i}=0$ means "exclude $x_{i}$ in this subset". For example, if $n=4$ then the subset $S={x_{1},x_{3}}$ would be represented as $1010$.



    There are exactly $2^{n}$ possible strings, since each $a_{i}$ has two possible values, and there are $n$ of them. And each string corresponds to one and only one subset of $X$. Therefore there are $2^{n}$ subsets.






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      Thanks pwerth, this is a wonderful and direct view on the process using 1010 as an example.
      $endgroup$
      – commentallez-vous
      2 days ago










    • $begingroup$
      You're welcome, glad to help!
      $endgroup$
      – pwerth
      2 days ago



















    5












    $begingroup$

    Write out all the binary numbers with $3$ digits. Each digit represents one element ($0$ means exclude, $1$ means include):
    $$
    begin{array}{|c|c|}
    text{decimal}&text{binary}&text{subset}\hline
    0&000&{}\
    1&001&{C}\
    2&010&{B}\
    3&011&{B,C}\
    4&100&{A}\
    5&101&{A,C}\
    6&110&{A,B}\
    7&111&{A,B,C}\
    end{array}
    $$

    This is easily extendible to an $n$ element set with $n$ digit binary numbers.






    share|cite|improve this answer











    $endgroup$









    • 1




      $begingroup$
      Note the relationship between the binary numbers and the subset elements: $000 to { }, 001 to {C}, 010 to {B}, 011 to {B,C}, dots$.
      $endgroup$
      – steven gregory
      yesterday












    • $begingroup$
      I believe that this is the same as pwerth's answer.
      $endgroup$
      – Scott
      1 hour ago



















    4












    $begingroup$

    I think, more directly, what the book is saying can be stated as:




    Choosing a subset $U$ of a set $S$ is the same as, for each element $xin S$, choosing whether $x$ is in $U$ or not.




    In particular, there is, at any time, only one set we're considering. So, if $S={A,B,C}$ and we want to choose a subset $U$, we could make the following three choices:
    $$Ain U$$
    $$Bin U$$
    $$Cin U$$
    And we would get $U={A,B,C}$. So, we've constructed a subset by making three binary choices. We could try this process again to make a different subset; for instance, we could decide instead
    $$Anotin U$$
    $$Bnotin U$$
    $$Cin U$$
    And then get $U={C}$. So, we've made a different set of choices and got a different set. So, for each subset, we have to make three choices.






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      Thank you Milo, I think I got it using your explanation with pwerth's. I really appreciate it!
      $endgroup$
      – commentallez-vous
      2 days ago



















    4












    $begingroup$

    The set of subsets of $X$ can be seen as the set of all functions from $X$ to ${0,1}$, denoted ${0,1}^X$.



    For each such function, consider the subset of $X$ consisting of all $xin X$ such that $f(x)=1$.



    This, it turns out, is a $1-1$correspondence.



    As a result, the order of the power set is $mid P(X)mid=mid {0,1}^Xmid=mid{0,1}mid^{mid Xmid}=2^n$.






    share|cite|improve this answer











    $endgroup$





















      4












      $begingroup$

      Proof by induction (on number of elements in the set):



      For $n = 0$, there is exactly $2^0=1$ subset of a set with 0 elements, namely the empty set itself.



      Assuming that any set $U_n$ with $n$ elements has $2^n$ subset, consider a set $U_{n+1}=U_n cup {x}$ (where $x notin U_n$). Which subsets of $U_{n+1}$ exists?




      • The subsets which do not include $x$ are exactly the subsets of $U_n$ (there are $2^n$ such subsets)

      • Any other subset includes $x$, so it is of the form $A cup {x}$, where $A$ is a subset of $U_n$ (because all elements in $U_{n+1}$ except $x$ are also elements of $U_n$), and it's clear that such subset exists (and is unique) for each $A subset U_n$. So, the number of $U_{n+1}$ subsets which include $x$ is also $2^n$.


      So, the total count of $U_{n+1}$ subsets is $2^n+2^n=2^{n+1}$. The proof is complete.






      share|cite|improve this answer









      $endgroup$





















        -5












        $begingroup$

        There is no definable uniform method that works on every single finite set. In Zermelo-Fraenkel set theory, there is no set of all finite sets so there cannot be a function on the set of all finite sets. To prove that there is a uniform way to do so, you need to work in Von Neumann-Berneys-Godel set theory where the axiom of global choice is a theorem and Von Neumann-Berneys-Godel set theory also asserts the existence of functions on proper classes. Zermelo-Fraenkel set theory does describe the statement "There is no set of all finite sets" but does not describe the statement "The class of all finite sets is not a set." However, Von Neumann-Berneys-Godel set theory does describe that statement. In Von Neumann-Berneys-Godel set theory, the axiom of global choice states that there is a class function that assigns to every nonempty set one member of that set. In Zermelo-Fraenkel set theory on the other hand, the axiom of choice is not provable and the axiom of global choice is not even stateable in the formal system of ZF. In ZF, you can't state the statement that there exist a class function that for every finite set picks one way of counting all its subsets. Once I define a way of doing that for every finite ordinal number, it can be shown that for every set, if there exists a bijection from a finite ordinal number to that, there exists a bijection from 2 to the power of that ordinal number to the power set of that set. Now I will define a method of counting for each finite ordinal number all of its subsets. Every finite ordinal number is the set of all smaller finite ordinal numbers. Start with the empty set. For the ordinal number 0, there is only one subset of it, itself. For each finite ordinal number $x$, suppose you have already defined a way to count all subsets of $x$, then count all subsets of $x + 1$ as follows. First count all the subsets of $x$ in exactly the same way then count the objects that can be gotten from them by taking the union of each of them and $text{{x}}$ in the same order. That recursively defines for every finite ordinal number a way to count all of its subsets.






        share|cite|improve this answer











        $endgroup$













        • $begingroup$
          I see that I got a downvote but I don't see what's wrong with this answer. Maybe you don't like it because you're thinking in the contradictory Naive set theory where you can prove the axiom of choice and can also prove that there is a set of all finite sets and therefore you can also prove in Naive set theory that there is a function from the set of all finite sets to the universal set that assings to every finite set one way to count all the elements of its power set.
          $endgroup$
          – Timothy
          yesterday






        • 3




          $begingroup$
          Sorry, I downvoted this too, because this does not actually answer the question. If we consider only finite sets without the possibility that a set can contain itself (which the OP has probably meant), the naive set theory does not lead to paradoxes.
          $endgroup$
          – trolley813
          yesterday






        • 1




          $begingroup$
          I think your answer reached beyond my ability to understand. Probably I have to rephrase my question. But what I meant was exactly the process how those subsets were formed through a n steps binary choice. As you have noticed that Eelvex answer was a good example for me to perceive the process. But I have to say your answer is also quite rigorous given it stems from a point of view in real analysis. But given my math ability, the easier ones are better for me to understand. Still, thanks a lot!
          $endgroup$
          – commentallez-vous
          yesterday










        • $begingroup$
          @commentallez-vous I'm not sure if that's a good idea because it might invalidate the already existing answers. There might exist an edit that doesn't invalidate them but it's probably too hard to figure out what one is so I think it might be better to ask a question to help understand how Zermelo-Fraenkel set theory and Von Neumann-Berneys-Godel set theory work. If the question title is rejected by a Stack Exchange algorithm because it exceeds 150 characters, you could write ZF and NBG for shorthand in the title. Maybe I could make my answer more understandable to you by more clearly
          $endgroup$
          – Timothy
          yesterday










        • $begingroup$
          describing how ZF and NBG work but I'm not sure I'll be able to figure out how to do so even if there is a way. I believe that formally in NBG, the statements "The class of all sets is not a set" and "There is no set of all sets" are distinct but equivalent statements but ZF describes the statement "There is no set of all sets" but does not describe the statement "The class of all sets is not a set" because it doesn't include any statements that refer to proper classes. Sometimes people say "The class of all sets is not a set" when they really mean "There is no set of all sets" in ZF. My
          $endgroup$
          – Timothy
          yesterday











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


        }
        });






        commentallez-vous is a new contributor. Be nice, and check out our Code of Conduct.










        draft saved

        draft discarded


















        StackExchange.ready(
        function () {
        StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3068013%2fthe-total-number-of-subsets-is-2n-for-n-elements%23new-answer', 'question_page');
        }
        );

        Post as a guest















        Required, but never shown

























        7 Answers
        7






        active

        oldest

        votes








        7 Answers
        7






        active

        oldest

        votes









        active

        oldest

        votes






        active

        oldest

        votes









        61












        $begingroup$

        enter image description here




        • "Include A?" is stage 1

        • "Include B?" is stage 2

        • "Include C?" is stage 3.






        share|cite|improve this answer









        $endgroup$


















          61












          $begingroup$

          enter image description here




          • "Include A?" is stage 1

          • "Include B?" is stage 2

          • "Include C?" is stage 3.






          share|cite|improve this answer









          $endgroup$
















            61












            61








            61





            $begingroup$

            enter image description here




            • "Include A?" is stage 1

            • "Include B?" is stage 2

            • "Include C?" is stage 3.






            share|cite|improve this answer









            $endgroup$



            enter image description here




            • "Include A?" is stage 1

            • "Include B?" is stage 2

            • "Include C?" is stage 3.







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered 2 days ago









            EelvexEelvex

            1,114820




            1,114820























                21












                $begingroup$

                Label your $n$ elements so that $X={x_{1},...,x_{n}}$. We're going to form a one-to-one correspondence between the subsets of $X$ and the set of length-$n$ binary strings as follows. Given a binary string
                $$a_{1}cdots a_{n}$$
                imagine that $a_{i}=1$ means "include $x_{i}$ in this subset" and $a_{i}=0$ means "exclude $x_{i}$ in this subset". For example, if $n=4$ then the subset $S={x_{1},x_{3}}$ would be represented as $1010$.



                There are exactly $2^{n}$ possible strings, since each $a_{i}$ has two possible values, and there are $n$ of them. And each string corresponds to one and only one subset of $X$. Therefore there are $2^{n}$ subsets.






                share|cite|improve this answer









                $endgroup$













                • $begingroup$
                  Thanks pwerth, this is a wonderful and direct view on the process using 1010 as an example.
                  $endgroup$
                  – commentallez-vous
                  2 days ago










                • $begingroup$
                  You're welcome, glad to help!
                  $endgroup$
                  – pwerth
                  2 days ago
















                21












                $begingroup$

                Label your $n$ elements so that $X={x_{1},...,x_{n}}$. We're going to form a one-to-one correspondence between the subsets of $X$ and the set of length-$n$ binary strings as follows. Given a binary string
                $$a_{1}cdots a_{n}$$
                imagine that $a_{i}=1$ means "include $x_{i}$ in this subset" and $a_{i}=0$ means "exclude $x_{i}$ in this subset". For example, if $n=4$ then the subset $S={x_{1},x_{3}}$ would be represented as $1010$.



                There are exactly $2^{n}$ possible strings, since each $a_{i}$ has two possible values, and there are $n$ of them. And each string corresponds to one and only one subset of $X$. Therefore there are $2^{n}$ subsets.






                share|cite|improve this answer









                $endgroup$













                • $begingroup$
                  Thanks pwerth, this is a wonderful and direct view on the process using 1010 as an example.
                  $endgroup$
                  – commentallez-vous
                  2 days ago










                • $begingroup$
                  You're welcome, glad to help!
                  $endgroup$
                  – pwerth
                  2 days ago














                21












                21








                21





                $begingroup$

                Label your $n$ elements so that $X={x_{1},...,x_{n}}$. We're going to form a one-to-one correspondence between the subsets of $X$ and the set of length-$n$ binary strings as follows. Given a binary string
                $$a_{1}cdots a_{n}$$
                imagine that $a_{i}=1$ means "include $x_{i}$ in this subset" and $a_{i}=0$ means "exclude $x_{i}$ in this subset". For example, if $n=4$ then the subset $S={x_{1},x_{3}}$ would be represented as $1010$.



                There are exactly $2^{n}$ possible strings, since each $a_{i}$ has two possible values, and there are $n$ of them. And each string corresponds to one and only one subset of $X$. Therefore there are $2^{n}$ subsets.






                share|cite|improve this answer









                $endgroup$



                Label your $n$ elements so that $X={x_{1},...,x_{n}}$. We're going to form a one-to-one correspondence between the subsets of $X$ and the set of length-$n$ binary strings as follows. Given a binary string
                $$a_{1}cdots a_{n}$$
                imagine that $a_{i}=1$ means "include $x_{i}$ in this subset" and $a_{i}=0$ means "exclude $x_{i}$ in this subset". For example, if $n=4$ then the subset $S={x_{1},x_{3}}$ would be represented as $1010$.



                There are exactly $2^{n}$ possible strings, since each $a_{i}$ has two possible values, and there are $n$ of them. And each string corresponds to one and only one subset of $X$. Therefore there are $2^{n}$ subsets.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered 2 days ago









                pwerthpwerth

                2,117413




                2,117413












                • $begingroup$
                  Thanks pwerth, this is a wonderful and direct view on the process using 1010 as an example.
                  $endgroup$
                  – commentallez-vous
                  2 days ago










                • $begingroup$
                  You're welcome, glad to help!
                  $endgroup$
                  – pwerth
                  2 days ago


















                • $begingroup$
                  Thanks pwerth, this is a wonderful and direct view on the process using 1010 as an example.
                  $endgroup$
                  – commentallez-vous
                  2 days ago










                • $begingroup$
                  You're welcome, glad to help!
                  $endgroup$
                  – pwerth
                  2 days ago
















                $begingroup$
                Thanks pwerth, this is a wonderful and direct view on the process using 1010 as an example.
                $endgroup$
                – commentallez-vous
                2 days ago




                $begingroup$
                Thanks pwerth, this is a wonderful and direct view on the process using 1010 as an example.
                $endgroup$
                – commentallez-vous
                2 days ago












                $begingroup$
                You're welcome, glad to help!
                $endgroup$
                – pwerth
                2 days ago




                $begingroup$
                You're welcome, glad to help!
                $endgroup$
                – pwerth
                2 days ago











                5












                $begingroup$

                Write out all the binary numbers with $3$ digits. Each digit represents one element ($0$ means exclude, $1$ means include):
                $$
                begin{array}{|c|c|}
                text{decimal}&text{binary}&text{subset}\hline
                0&000&{}\
                1&001&{C}\
                2&010&{B}\
                3&011&{B,C}\
                4&100&{A}\
                5&101&{A,C}\
                6&110&{A,B}\
                7&111&{A,B,C}\
                end{array}
                $$

                This is easily extendible to an $n$ element set with $n$ digit binary numbers.






                share|cite|improve this answer











                $endgroup$









                • 1




                  $begingroup$
                  Note the relationship between the binary numbers and the subset elements: $000 to { }, 001 to {C}, 010 to {B}, 011 to {B,C}, dots$.
                  $endgroup$
                  – steven gregory
                  yesterday












                • $begingroup$
                  I believe that this is the same as pwerth's answer.
                  $endgroup$
                  – Scott
                  1 hour ago
















                5












                $begingroup$

                Write out all the binary numbers with $3$ digits. Each digit represents one element ($0$ means exclude, $1$ means include):
                $$
                begin{array}{|c|c|}
                text{decimal}&text{binary}&text{subset}\hline
                0&000&{}\
                1&001&{C}\
                2&010&{B}\
                3&011&{B,C}\
                4&100&{A}\
                5&101&{A,C}\
                6&110&{A,B}\
                7&111&{A,B,C}\
                end{array}
                $$

                This is easily extendible to an $n$ element set with $n$ digit binary numbers.






                share|cite|improve this answer











                $endgroup$









                • 1




                  $begingroup$
                  Note the relationship between the binary numbers and the subset elements: $000 to { }, 001 to {C}, 010 to {B}, 011 to {B,C}, dots$.
                  $endgroup$
                  – steven gregory
                  yesterday












                • $begingroup$
                  I believe that this is the same as pwerth's answer.
                  $endgroup$
                  – Scott
                  1 hour ago














                5












                5








                5





                $begingroup$

                Write out all the binary numbers with $3$ digits. Each digit represents one element ($0$ means exclude, $1$ means include):
                $$
                begin{array}{|c|c|}
                text{decimal}&text{binary}&text{subset}\hline
                0&000&{}\
                1&001&{C}\
                2&010&{B}\
                3&011&{B,C}\
                4&100&{A}\
                5&101&{A,C}\
                6&110&{A,B}\
                7&111&{A,B,C}\
                end{array}
                $$

                This is easily extendible to an $n$ element set with $n$ digit binary numbers.






                share|cite|improve this answer











                $endgroup$



                Write out all the binary numbers with $3$ digits. Each digit represents one element ($0$ means exclude, $1$ means include):
                $$
                begin{array}{|c|c|}
                text{decimal}&text{binary}&text{subset}\hline
                0&000&{}\
                1&001&{C}\
                2&010&{B}\
                3&011&{B,C}\
                4&100&{A}\
                5&101&{A,C}\
                6&110&{A,B}\
                7&111&{A,B,C}\
                end{array}
                $$

                This is easily extendible to an $n$ element set with $n$ digit binary numbers.







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited yesterday

























                answered yesterday









                robjohnrobjohn

                265k27303626




                265k27303626








                • 1




                  $begingroup$
                  Note the relationship between the binary numbers and the subset elements: $000 to { }, 001 to {C}, 010 to {B}, 011 to {B,C}, dots$.
                  $endgroup$
                  – steven gregory
                  yesterday












                • $begingroup$
                  I believe that this is the same as pwerth's answer.
                  $endgroup$
                  – Scott
                  1 hour ago














                • 1




                  $begingroup$
                  Note the relationship between the binary numbers and the subset elements: $000 to { }, 001 to {C}, 010 to {B}, 011 to {B,C}, dots$.
                  $endgroup$
                  – steven gregory
                  yesterday












                • $begingroup$
                  I believe that this is the same as pwerth's answer.
                  $endgroup$
                  – Scott
                  1 hour ago








                1




                1




                $begingroup$
                Note the relationship between the binary numbers and the subset elements: $000 to { }, 001 to {C}, 010 to {B}, 011 to {B,C}, dots$.
                $endgroup$
                – steven gregory
                yesterday






                $begingroup$
                Note the relationship between the binary numbers and the subset elements: $000 to { }, 001 to {C}, 010 to {B}, 011 to {B,C}, dots$.
                $endgroup$
                – steven gregory
                yesterday














                $begingroup$
                I believe that this is the same as pwerth's answer.
                $endgroup$
                – Scott
                1 hour ago




                $begingroup$
                I believe that this is the same as pwerth's answer.
                $endgroup$
                – Scott
                1 hour ago











                4












                $begingroup$

                I think, more directly, what the book is saying can be stated as:




                Choosing a subset $U$ of a set $S$ is the same as, for each element $xin S$, choosing whether $x$ is in $U$ or not.




                In particular, there is, at any time, only one set we're considering. So, if $S={A,B,C}$ and we want to choose a subset $U$, we could make the following three choices:
                $$Ain U$$
                $$Bin U$$
                $$Cin U$$
                And we would get $U={A,B,C}$. So, we've constructed a subset by making three binary choices. We could try this process again to make a different subset; for instance, we could decide instead
                $$Anotin U$$
                $$Bnotin U$$
                $$Cin U$$
                And then get $U={C}$. So, we've made a different set of choices and got a different set. So, for each subset, we have to make three choices.






                share|cite|improve this answer









                $endgroup$













                • $begingroup$
                  Thank you Milo, I think I got it using your explanation with pwerth's. I really appreciate it!
                  $endgroup$
                  – commentallez-vous
                  2 days ago
















                4












                $begingroup$

                I think, more directly, what the book is saying can be stated as:




                Choosing a subset $U$ of a set $S$ is the same as, for each element $xin S$, choosing whether $x$ is in $U$ or not.




                In particular, there is, at any time, only one set we're considering. So, if $S={A,B,C}$ and we want to choose a subset $U$, we could make the following three choices:
                $$Ain U$$
                $$Bin U$$
                $$Cin U$$
                And we would get $U={A,B,C}$. So, we've constructed a subset by making three binary choices. We could try this process again to make a different subset; for instance, we could decide instead
                $$Anotin U$$
                $$Bnotin U$$
                $$Cin U$$
                And then get $U={C}$. So, we've made a different set of choices and got a different set. So, for each subset, we have to make three choices.






                share|cite|improve this answer









                $endgroup$













                • $begingroup$
                  Thank you Milo, I think I got it using your explanation with pwerth's. I really appreciate it!
                  $endgroup$
                  – commentallez-vous
                  2 days ago














                4












                4








                4





                $begingroup$

                I think, more directly, what the book is saying can be stated as:




                Choosing a subset $U$ of a set $S$ is the same as, for each element $xin S$, choosing whether $x$ is in $U$ or not.




                In particular, there is, at any time, only one set we're considering. So, if $S={A,B,C}$ and we want to choose a subset $U$, we could make the following three choices:
                $$Ain U$$
                $$Bin U$$
                $$Cin U$$
                And we would get $U={A,B,C}$. So, we've constructed a subset by making three binary choices. We could try this process again to make a different subset; for instance, we could decide instead
                $$Anotin U$$
                $$Bnotin U$$
                $$Cin U$$
                And then get $U={C}$. So, we've made a different set of choices and got a different set. So, for each subset, we have to make three choices.






                share|cite|improve this answer









                $endgroup$



                I think, more directly, what the book is saying can be stated as:




                Choosing a subset $U$ of a set $S$ is the same as, for each element $xin S$, choosing whether $x$ is in $U$ or not.




                In particular, there is, at any time, only one set we're considering. So, if $S={A,B,C}$ and we want to choose a subset $U$, we could make the following three choices:
                $$Ain U$$
                $$Bin U$$
                $$Cin U$$
                And we would get $U={A,B,C}$. So, we've constructed a subset by making three binary choices. We could try this process again to make a different subset; for instance, we could decide instead
                $$Anotin U$$
                $$Bnotin U$$
                $$Cin U$$
                And then get $U={C}$. So, we've made a different set of choices and got a different set. So, for each subset, we have to make three choices.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered 2 days ago









                Milo BrandtMilo Brandt

                39.5k475139




                39.5k475139












                • $begingroup$
                  Thank you Milo, I think I got it using your explanation with pwerth's. I really appreciate it!
                  $endgroup$
                  – commentallez-vous
                  2 days ago


















                • $begingroup$
                  Thank you Milo, I think I got it using your explanation with pwerth's. I really appreciate it!
                  $endgroup$
                  – commentallez-vous
                  2 days ago
















                $begingroup$
                Thank you Milo, I think I got it using your explanation with pwerth's. I really appreciate it!
                $endgroup$
                – commentallez-vous
                2 days ago




                $begingroup$
                Thank you Milo, I think I got it using your explanation with pwerth's. I really appreciate it!
                $endgroup$
                – commentallez-vous
                2 days ago











                4












                $begingroup$

                The set of subsets of $X$ can be seen as the set of all functions from $X$ to ${0,1}$, denoted ${0,1}^X$.



                For each such function, consider the subset of $X$ consisting of all $xin X$ such that $f(x)=1$.



                This, it turns out, is a $1-1$correspondence.



                As a result, the order of the power set is $mid P(X)mid=mid {0,1}^Xmid=mid{0,1}mid^{mid Xmid}=2^n$.






                share|cite|improve this answer











                $endgroup$


















                  4












                  $begingroup$

                  The set of subsets of $X$ can be seen as the set of all functions from $X$ to ${0,1}$, denoted ${0,1}^X$.



                  For each such function, consider the subset of $X$ consisting of all $xin X$ such that $f(x)=1$.



                  This, it turns out, is a $1-1$correspondence.



                  As a result, the order of the power set is $mid P(X)mid=mid {0,1}^Xmid=mid{0,1}mid^{mid Xmid}=2^n$.






                  share|cite|improve this answer











                  $endgroup$
















                    4












                    4








                    4





                    $begingroup$

                    The set of subsets of $X$ can be seen as the set of all functions from $X$ to ${0,1}$, denoted ${0,1}^X$.



                    For each such function, consider the subset of $X$ consisting of all $xin X$ such that $f(x)=1$.



                    This, it turns out, is a $1-1$correspondence.



                    As a result, the order of the power set is $mid P(X)mid=mid {0,1}^Xmid=mid{0,1}mid^{mid Xmid}=2^n$.






                    share|cite|improve this answer











                    $endgroup$



                    The set of subsets of $X$ can be seen as the set of all functions from $X$ to ${0,1}$, denoted ${0,1}^X$.



                    For each such function, consider the subset of $X$ consisting of all $xin X$ such that $f(x)=1$.



                    This, it turns out, is a $1-1$correspondence.



                    As a result, the order of the power set is $mid P(X)mid=mid {0,1}^Xmid=mid{0,1}mid^{mid Xmid}=2^n$.







                    share|cite|improve this answer














                    share|cite|improve this answer



                    share|cite|improve this answer








                    edited 2 days ago

























                    answered 2 days ago









                    Chris CusterChris Custer

                    11.2k3824




                    11.2k3824























                        4












                        $begingroup$

                        Proof by induction (on number of elements in the set):



                        For $n = 0$, there is exactly $2^0=1$ subset of a set with 0 elements, namely the empty set itself.



                        Assuming that any set $U_n$ with $n$ elements has $2^n$ subset, consider a set $U_{n+1}=U_n cup {x}$ (where $x notin U_n$). Which subsets of $U_{n+1}$ exists?




                        • The subsets which do not include $x$ are exactly the subsets of $U_n$ (there are $2^n$ such subsets)

                        • Any other subset includes $x$, so it is of the form $A cup {x}$, where $A$ is a subset of $U_n$ (because all elements in $U_{n+1}$ except $x$ are also elements of $U_n$), and it's clear that such subset exists (and is unique) for each $A subset U_n$. So, the number of $U_{n+1}$ subsets which include $x$ is also $2^n$.


                        So, the total count of $U_{n+1}$ subsets is $2^n+2^n=2^{n+1}$. The proof is complete.






                        share|cite|improve this answer









                        $endgroup$


















                          4












                          $begingroup$

                          Proof by induction (on number of elements in the set):



                          For $n = 0$, there is exactly $2^0=1$ subset of a set with 0 elements, namely the empty set itself.



                          Assuming that any set $U_n$ with $n$ elements has $2^n$ subset, consider a set $U_{n+1}=U_n cup {x}$ (where $x notin U_n$). Which subsets of $U_{n+1}$ exists?




                          • The subsets which do not include $x$ are exactly the subsets of $U_n$ (there are $2^n$ such subsets)

                          • Any other subset includes $x$, so it is of the form $A cup {x}$, where $A$ is a subset of $U_n$ (because all elements in $U_{n+1}$ except $x$ are also elements of $U_n$), and it's clear that such subset exists (and is unique) for each $A subset U_n$. So, the number of $U_{n+1}$ subsets which include $x$ is also $2^n$.


                          So, the total count of $U_{n+1}$ subsets is $2^n+2^n=2^{n+1}$. The proof is complete.






                          share|cite|improve this answer









                          $endgroup$
















                            4












                            4








                            4





                            $begingroup$

                            Proof by induction (on number of elements in the set):



                            For $n = 0$, there is exactly $2^0=1$ subset of a set with 0 elements, namely the empty set itself.



                            Assuming that any set $U_n$ with $n$ elements has $2^n$ subset, consider a set $U_{n+1}=U_n cup {x}$ (where $x notin U_n$). Which subsets of $U_{n+1}$ exists?




                            • The subsets which do not include $x$ are exactly the subsets of $U_n$ (there are $2^n$ such subsets)

                            • Any other subset includes $x$, so it is of the form $A cup {x}$, where $A$ is a subset of $U_n$ (because all elements in $U_{n+1}$ except $x$ are also elements of $U_n$), and it's clear that such subset exists (and is unique) for each $A subset U_n$. So, the number of $U_{n+1}$ subsets which include $x$ is also $2^n$.


                            So, the total count of $U_{n+1}$ subsets is $2^n+2^n=2^{n+1}$. The proof is complete.






                            share|cite|improve this answer









                            $endgroup$



                            Proof by induction (on number of elements in the set):



                            For $n = 0$, there is exactly $2^0=1$ subset of a set with 0 elements, namely the empty set itself.



                            Assuming that any set $U_n$ with $n$ elements has $2^n$ subset, consider a set $U_{n+1}=U_n cup {x}$ (where $x notin U_n$). Which subsets of $U_{n+1}$ exists?




                            • The subsets which do not include $x$ are exactly the subsets of $U_n$ (there are $2^n$ such subsets)

                            • Any other subset includes $x$, so it is of the form $A cup {x}$, where $A$ is a subset of $U_n$ (because all elements in $U_{n+1}$ except $x$ are also elements of $U_n$), and it's clear that such subset exists (and is unique) for each $A subset U_n$. So, the number of $U_{n+1}$ subsets which include $x$ is also $2^n$.


                            So, the total count of $U_{n+1}$ subsets is $2^n+2^n=2^{n+1}$. The proof is complete.







                            share|cite|improve this answer












                            share|cite|improve this answer



                            share|cite|improve this answer










                            answered yesterday









                            trolley813trolley813

                            22014




                            22014























                                -5












                                $begingroup$

                                There is no definable uniform method that works on every single finite set. In Zermelo-Fraenkel set theory, there is no set of all finite sets so there cannot be a function on the set of all finite sets. To prove that there is a uniform way to do so, you need to work in Von Neumann-Berneys-Godel set theory where the axiom of global choice is a theorem and Von Neumann-Berneys-Godel set theory also asserts the existence of functions on proper classes. Zermelo-Fraenkel set theory does describe the statement "There is no set of all finite sets" but does not describe the statement "The class of all finite sets is not a set." However, Von Neumann-Berneys-Godel set theory does describe that statement. In Von Neumann-Berneys-Godel set theory, the axiom of global choice states that there is a class function that assigns to every nonempty set one member of that set. In Zermelo-Fraenkel set theory on the other hand, the axiom of choice is not provable and the axiom of global choice is not even stateable in the formal system of ZF. In ZF, you can't state the statement that there exist a class function that for every finite set picks one way of counting all its subsets. Once I define a way of doing that for every finite ordinal number, it can be shown that for every set, if there exists a bijection from a finite ordinal number to that, there exists a bijection from 2 to the power of that ordinal number to the power set of that set. Now I will define a method of counting for each finite ordinal number all of its subsets. Every finite ordinal number is the set of all smaller finite ordinal numbers. Start with the empty set. For the ordinal number 0, there is only one subset of it, itself. For each finite ordinal number $x$, suppose you have already defined a way to count all subsets of $x$, then count all subsets of $x + 1$ as follows. First count all the subsets of $x$ in exactly the same way then count the objects that can be gotten from them by taking the union of each of them and $text{{x}}$ in the same order. That recursively defines for every finite ordinal number a way to count all of its subsets.






                                share|cite|improve this answer











                                $endgroup$













                                • $begingroup$
                                  I see that I got a downvote but I don't see what's wrong with this answer. Maybe you don't like it because you're thinking in the contradictory Naive set theory where you can prove the axiom of choice and can also prove that there is a set of all finite sets and therefore you can also prove in Naive set theory that there is a function from the set of all finite sets to the universal set that assings to every finite set one way to count all the elements of its power set.
                                  $endgroup$
                                  – Timothy
                                  yesterday






                                • 3




                                  $begingroup$
                                  Sorry, I downvoted this too, because this does not actually answer the question. If we consider only finite sets without the possibility that a set can contain itself (which the OP has probably meant), the naive set theory does not lead to paradoxes.
                                  $endgroup$
                                  – trolley813
                                  yesterday






                                • 1




                                  $begingroup$
                                  I think your answer reached beyond my ability to understand. Probably I have to rephrase my question. But what I meant was exactly the process how those subsets were formed through a n steps binary choice. As you have noticed that Eelvex answer was a good example for me to perceive the process. But I have to say your answer is also quite rigorous given it stems from a point of view in real analysis. But given my math ability, the easier ones are better for me to understand. Still, thanks a lot!
                                  $endgroup$
                                  – commentallez-vous
                                  yesterday










                                • $begingroup$
                                  @commentallez-vous I'm not sure if that's a good idea because it might invalidate the already existing answers. There might exist an edit that doesn't invalidate them but it's probably too hard to figure out what one is so I think it might be better to ask a question to help understand how Zermelo-Fraenkel set theory and Von Neumann-Berneys-Godel set theory work. If the question title is rejected by a Stack Exchange algorithm because it exceeds 150 characters, you could write ZF and NBG for shorthand in the title. Maybe I could make my answer more understandable to you by more clearly
                                  $endgroup$
                                  – Timothy
                                  yesterday










                                • $begingroup$
                                  describing how ZF and NBG work but I'm not sure I'll be able to figure out how to do so even if there is a way. I believe that formally in NBG, the statements "The class of all sets is not a set" and "There is no set of all sets" are distinct but equivalent statements but ZF describes the statement "There is no set of all sets" but does not describe the statement "The class of all sets is not a set" because it doesn't include any statements that refer to proper classes. Sometimes people say "The class of all sets is not a set" when they really mean "There is no set of all sets" in ZF. My
                                  $endgroup$
                                  – Timothy
                                  yesterday
















                                -5












                                $begingroup$

                                There is no definable uniform method that works on every single finite set. In Zermelo-Fraenkel set theory, there is no set of all finite sets so there cannot be a function on the set of all finite sets. To prove that there is a uniform way to do so, you need to work in Von Neumann-Berneys-Godel set theory where the axiom of global choice is a theorem and Von Neumann-Berneys-Godel set theory also asserts the existence of functions on proper classes. Zermelo-Fraenkel set theory does describe the statement "There is no set of all finite sets" but does not describe the statement "The class of all finite sets is not a set." However, Von Neumann-Berneys-Godel set theory does describe that statement. In Von Neumann-Berneys-Godel set theory, the axiom of global choice states that there is a class function that assigns to every nonempty set one member of that set. In Zermelo-Fraenkel set theory on the other hand, the axiom of choice is not provable and the axiom of global choice is not even stateable in the formal system of ZF. In ZF, you can't state the statement that there exist a class function that for every finite set picks one way of counting all its subsets. Once I define a way of doing that for every finite ordinal number, it can be shown that for every set, if there exists a bijection from a finite ordinal number to that, there exists a bijection from 2 to the power of that ordinal number to the power set of that set. Now I will define a method of counting for each finite ordinal number all of its subsets. Every finite ordinal number is the set of all smaller finite ordinal numbers. Start with the empty set. For the ordinal number 0, there is only one subset of it, itself. For each finite ordinal number $x$, suppose you have already defined a way to count all subsets of $x$, then count all subsets of $x + 1$ as follows. First count all the subsets of $x$ in exactly the same way then count the objects that can be gotten from them by taking the union of each of them and $text{{x}}$ in the same order. That recursively defines for every finite ordinal number a way to count all of its subsets.






                                share|cite|improve this answer











                                $endgroup$













                                • $begingroup$
                                  I see that I got a downvote but I don't see what's wrong with this answer. Maybe you don't like it because you're thinking in the contradictory Naive set theory where you can prove the axiom of choice and can also prove that there is a set of all finite sets and therefore you can also prove in Naive set theory that there is a function from the set of all finite sets to the universal set that assings to every finite set one way to count all the elements of its power set.
                                  $endgroup$
                                  – Timothy
                                  yesterday






                                • 3




                                  $begingroup$
                                  Sorry, I downvoted this too, because this does not actually answer the question. If we consider only finite sets without the possibility that a set can contain itself (which the OP has probably meant), the naive set theory does not lead to paradoxes.
                                  $endgroup$
                                  – trolley813
                                  yesterday






                                • 1




                                  $begingroup$
                                  I think your answer reached beyond my ability to understand. Probably I have to rephrase my question. But what I meant was exactly the process how those subsets were formed through a n steps binary choice. As you have noticed that Eelvex answer was a good example for me to perceive the process. But I have to say your answer is also quite rigorous given it stems from a point of view in real analysis. But given my math ability, the easier ones are better for me to understand. Still, thanks a lot!
                                  $endgroup$
                                  – commentallez-vous
                                  yesterday










                                • $begingroup$
                                  @commentallez-vous I'm not sure if that's a good idea because it might invalidate the already existing answers. There might exist an edit that doesn't invalidate them but it's probably too hard to figure out what one is so I think it might be better to ask a question to help understand how Zermelo-Fraenkel set theory and Von Neumann-Berneys-Godel set theory work. If the question title is rejected by a Stack Exchange algorithm because it exceeds 150 characters, you could write ZF and NBG for shorthand in the title. Maybe I could make my answer more understandable to you by more clearly
                                  $endgroup$
                                  – Timothy
                                  yesterday










                                • $begingroup$
                                  describing how ZF and NBG work but I'm not sure I'll be able to figure out how to do so even if there is a way. I believe that formally in NBG, the statements "The class of all sets is not a set" and "There is no set of all sets" are distinct but equivalent statements but ZF describes the statement "There is no set of all sets" but does not describe the statement "The class of all sets is not a set" because it doesn't include any statements that refer to proper classes. Sometimes people say "The class of all sets is not a set" when they really mean "There is no set of all sets" in ZF. My
                                  $endgroup$
                                  – Timothy
                                  yesterday














                                -5












                                -5








                                -5





                                $begingroup$

                                There is no definable uniform method that works on every single finite set. In Zermelo-Fraenkel set theory, there is no set of all finite sets so there cannot be a function on the set of all finite sets. To prove that there is a uniform way to do so, you need to work in Von Neumann-Berneys-Godel set theory where the axiom of global choice is a theorem and Von Neumann-Berneys-Godel set theory also asserts the existence of functions on proper classes. Zermelo-Fraenkel set theory does describe the statement "There is no set of all finite sets" but does not describe the statement "The class of all finite sets is not a set." However, Von Neumann-Berneys-Godel set theory does describe that statement. In Von Neumann-Berneys-Godel set theory, the axiom of global choice states that there is a class function that assigns to every nonempty set one member of that set. In Zermelo-Fraenkel set theory on the other hand, the axiom of choice is not provable and the axiom of global choice is not even stateable in the formal system of ZF. In ZF, you can't state the statement that there exist a class function that for every finite set picks one way of counting all its subsets. Once I define a way of doing that for every finite ordinal number, it can be shown that for every set, if there exists a bijection from a finite ordinal number to that, there exists a bijection from 2 to the power of that ordinal number to the power set of that set. Now I will define a method of counting for each finite ordinal number all of its subsets. Every finite ordinal number is the set of all smaller finite ordinal numbers. Start with the empty set. For the ordinal number 0, there is only one subset of it, itself. For each finite ordinal number $x$, suppose you have already defined a way to count all subsets of $x$, then count all subsets of $x + 1$ as follows. First count all the subsets of $x$ in exactly the same way then count the objects that can be gotten from them by taking the union of each of them and $text{{x}}$ in the same order. That recursively defines for every finite ordinal number a way to count all of its subsets.






                                share|cite|improve this answer











                                $endgroup$



                                There is no definable uniform method that works on every single finite set. In Zermelo-Fraenkel set theory, there is no set of all finite sets so there cannot be a function on the set of all finite sets. To prove that there is a uniform way to do so, you need to work in Von Neumann-Berneys-Godel set theory where the axiom of global choice is a theorem and Von Neumann-Berneys-Godel set theory also asserts the existence of functions on proper classes. Zermelo-Fraenkel set theory does describe the statement "There is no set of all finite sets" but does not describe the statement "The class of all finite sets is not a set." However, Von Neumann-Berneys-Godel set theory does describe that statement. In Von Neumann-Berneys-Godel set theory, the axiom of global choice states that there is a class function that assigns to every nonempty set one member of that set. In Zermelo-Fraenkel set theory on the other hand, the axiom of choice is not provable and the axiom of global choice is not even stateable in the formal system of ZF. In ZF, you can't state the statement that there exist a class function that for every finite set picks one way of counting all its subsets. Once I define a way of doing that for every finite ordinal number, it can be shown that for every set, if there exists a bijection from a finite ordinal number to that, there exists a bijection from 2 to the power of that ordinal number to the power set of that set. Now I will define a method of counting for each finite ordinal number all of its subsets. Every finite ordinal number is the set of all smaller finite ordinal numbers. Start with the empty set. For the ordinal number 0, there is only one subset of it, itself. For each finite ordinal number $x$, suppose you have already defined a way to count all subsets of $x$, then count all subsets of $x + 1$ as follows. First count all the subsets of $x$ in exactly the same way then count the objects that can be gotten from them by taking the union of each of them and $text{{x}}$ in the same order. That recursively defines for every finite ordinal number a way to count all of its subsets.







                                share|cite|improve this answer














                                share|cite|improve this answer



                                share|cite|improve this answer








                                edited yesterday

























                                answered 2 days ago









                                TimothyTimothy

                                296211




                                296211












                                • $begingroup$
                                  I see that I got a downvote but I don't see what's wrong with this answer. Maybe you don't like it because you're thinking in the contradictory Naive set theory where you can prove the axiom of choice and can also prove that there is a set of all finite sets and therefore you can also prove in Naive set theory that there is a function from the set of all finite sets to the universal set that assings to every finite set one way to count all the elements of its power set.
                                  $endgroup$
                                  – Timothy
                                  yesterday






                                • 3




                                  $begingroup$
                                  Sorry, I downvoted this too, because this does not actually answer the question. If we consider only finite sets without the possibility that a set can contain itself (which the OP has probably meant), the naive set theory does not lead to paradoxes.
                                  $endgroup$
                                  – trolley813
                                  yesterday






                                • 1




                                  $begingroup$
                                  I think your answer reached beyond my ability to understand. Probably I have to rephrase my question. But what I meant was exactly the process how those subsets were formed through a n steps binary choice. As you have noticed that Eelvex answer was a good example for me to perceive the process. But I have to say your answer is also quite rigorous given it stems from a point of view in real analysis. But given my math ability, the easier ones are better for me to understand. Still, thanks a lot!
                                  $endgroup$
                                  – commentallez-vous
                                  yesterday










                                • $begingroup$
                                  @commentallez-vous I'm not sure if that's a good idea because it might invalidate the already existing answers. There might exist an edit that doesn't invalidate them but it's probably too hard to figure out what one is so I think it might be better to ask a question to help understand how Zermelo-Fraenkel set theory and Von Neumann-Berneys-Godel set theory work. If the question title is rejected by a Stack Exchange algorithm because it exceeds 150 characters, you could write ZF and NBG for shorthand in the title. Maybe I could make my answer more understandable to you by more clearly
                                  $endgroup$
                                  – Timothy
                                  yesterday










                                • $begingroup$
                                  describing how ZF and NBG work but I'm not sure I'll be able to figure out how to do so even if there is a way. I believe that formally in NBG, the statements "The class of all sets is not a set" and "There is no set of all sets" are distinct but equivalent statements but ZF describes the statement "There is no set of all sets" but does not describe the statement "The class of all sets is not a set" because it doesn't include any statements that refer to proper classes. Sometimes people say "The class of all sets is not a set" when they really mean "There is no set of all sets" in ZF. My
                                  $endgroup$
                                  – Timothy
                                  yesterday


















                                • $begingroup$
                                  I see that I got a downvote but I don't see what's wrong with this answer. Maybe you don't like it because you're thinking in the contradictory Naive set theory where you can prove the axiom of choice and can also prove that there is a set of all finite sets and therefore you can also prove in Naive set theory that there is a function from the set of all finite sets to the universal set that assings to every finite set one way to count all the elements of its power set.
                                  $endgroup$
                                  – Timothy
                                  yesterday






                                • 3




                                  $begingroup$
                                  Sorry, I downvoted this too, because this does not actually answer the question. If we consider only finite sets without the possibility that a set can contain itself (which the OP has probably meant), the naive set theory does not lead to paradoxes.
                                  $endgroup$
                                  – trolley813
                                  yesterday






                                • 1




                                  $begingroup$
                                  I think your answer reached beyond my ability to understand. Probably I have to rephrase my question. But what I meant was exactly the process how those subsets were formed through a n steps binary choice. As you have noticed that Eelvex answer was a good example for me to perceive the process. But I have to say your answer is also quite rigorous given it stems from a point of view in real analysis. But given my math ability, the easier ones are better for me to understand. Still, thanks a lot!
                                  $endgroup$
                                  – commentallez-vous
                                  yesterday










                                • $begingroup$
                                  @commentallez-vous I'm not sure if that's a good idea because it might invalidate the already existing answers. There might exist an edit that doesn't invalidate them but it's probably too hard to figure out what one is so I think it might be better to ask a question to help understand how Zermelo-Fraenkel set theory and Von Neumann-Berneys-Godel set theory work. If the question title is rejected by a Stack Exchange algorithm because it exceeds 150 characters, you could write ZF and NBG for shorthand in the title. Maybe I could make my answer more understandable to you by more clearly
                                  $endgroup$
                                  – Timothy
                                  yesterday










                                • $begingroup$
                                  describing how ZF and NBG work but I'm not sure I'll be able to figure out how to do so even if there is a way. I believe that formally in NBG, the statements "The class of all sets is not a set" and "There is no set of all sets" are distinct but equivalent statements but ZF describes the statement "There is no set of all sets" but does not describe the statement "The class of all sets is not a set" because it doesn't include any statements that refer to proper classes. Sometimes people say "The class of all sets is not a set" when they really mean "There is no set of all sets" in ZF. My
                                  $endgroup$
                                  – Timothy
                                  yesterday
















                                $begingroup$
                                I see that I got a downvote but I don't see what's wrong with this answer. Maybe you don't like it because you're thinking in the contradictory Naive set theory where you can prove the axiom of choice and can also prove that there is a set of all finite sets and therefore you can also prove in Naive set theory that there is a function from the set of all finite sets to the universal set that assings to every finite set one way to count all the elements of its power set.
                                $endgroup$
                                – Timothy
                                yesterday




                                $begingroup$
                                I see that I got a downvote but I don't see what's wrong with this answer. Maybe you don't like it because you're thinking in the contradictory Naive set theory where you can prove the axiom of choice and can also prove that there is a set of all finite sets and therefore you can also prove in Naive set theory that there is a function from the set of all finite sets to the universal set that assings to every finite set one way to count all the elements of its power set.
                                $endgroup$
                                – Timothy
                                yesterday




                                3




                                3




                                $begingroup$
                                Sorry, I downvoted this too, because this does not actually answer the question. If we consider only finite sets without the possibility that a set can contain itself (which the OP has probably meant), the naive set theory does not lead to paradoxes.
                                $endgroup$
                                – trolley813
                                yesterday




                                $begingroup$
                                Sorry, I downvoted this too, because this does not actually answer the question. If we consider only finite sets without the possibility that a set can contain itself (which the OP has probably meant), the naive set theory does not lead to paradoxes.
                                $endgroup$
                                – trolley813
                                yesterday




                                1




                                1




                                $begingroup$
                                I think your answer reached beyond my ability to understand. Probably I have to rephrase my question. But what I meant was exactly the process how those subsets were formed through a n steps binary choice. As you have noticed that Eelvex answer was a good example for me to perceive the process. But I have to say your answer is also quite rigorous given it stems from a point of view in real analysis. But given my math ability, the easier ones are better for me to understand. Still, thanks a lot!
                                $endgroup$
                                – commentallez-vous
                                yesterday




                                $begingroup$
                                I think your answer reached beyond my ability to understand. Probably I have to rephrase my question. But what I meant was exactly the process how those subsets were formed through a n steps binary choice. As you have noticed that Eelvex answer was a good example for me to perceive the process. But I have to say your answer is also quite rigorous given it stems from a point of view in real analysis. But given my math ability, the easier ones are better for me to understand. Still, thanks a lot!
                                $endgroup$
                                – commentallez-vous
                                yesterday












                                $begingroup$
                                @commentallez-vous I'm not sure if that's a good idea because it might invalidate the already existing answers. There might exist an edit that doesn't invalidate them but it's probably too hard to figure out what one is so I think it might be better to ask a question to help understand how Zermelo-Fraenkel set theory and Von Neumann-Berneys-Godel set theory work. If the question title is rejected by a Stack Exchange algorithm because it exceeds 150 characters, you could write ZF and NBG for shorthand in the title. Maybe I could make my answer more understandable to you by more clearly
                                $endgroup$
                                – Timothy
                                yesterday




                                $begingroup$
                                @commentallez-vous I'm not sure if that's a good idea because it might invalidate the already existing answers. There might exist an edit that doesn't invalidate them but it's probably too hard to figure out what one is so I think it might be better to ask a question to help understand how Zermelo-Fraenkel set theory and Von Neumann-Berneys-Godel set theory work. If the question title is rejected by a Stack Exchange algorithm because it exceeds 150 characters, you could write ZF and NBG for shorthand in the title. Maybe I could make my answer more understandable to you by more clearly
                                $endgroup$
                                – Timothy
                                yesterday












                                $begingroup$
                                describing how ZF and NBG work but I'm not sure I'll be able to figure out how to do so even if there is a way. I believe that formally in NBG, the statements "The class of all sets is not a set" and "There is no set of all sets" are distinct but equivalent statements but ZF describes the statement "There is no set of all sets" but does not describe the statement "The class of all sets is not a set" because it doesn't include any statements that refer to proper classes. Sometimes people say "The class of all sets is not a set" when they really mean "There is no set of all sets" in ZF. My
                                $endgroup$
                                – Timothy
                                yesterday




                                $begingroup$
                                describing how ZF and NBG work but I'm not sure I'll be able to figure out how to do so even if there is a way. I believe that formally in NBG, the statements "The class of all sets is not a set" and "There is no set of all sets" are distinct but equivalent statements but ZF describes the statement "There is no set of all sets" but does not describe the statement "The class of all sets is not a set" because it doesn't include any statements that refer to proper classes. Sometimes people say "The class of all sets is not a set" when they really mean "There is no set of all sets" in ZF. My
                                $endgroup$
                                – Timothy
                                yesterday










                                commentallez-vous is a new contributor. Be nice, and check out our Code of Conduct.










                                draft saved

                                draft discarded


















                                commentallez-vous is a new contributor. Be nice, and check out our Code of Conduct.













                                commentallez-vous is a new contributor. Be nice, and check out our Code of Conduct.












                                commentallez-vous is a new contributor. Be nice, and check out our Code of Conduct.
















                                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%2f3068013%2fthe-total-number-of-subsets-is-2n-for-n-elements%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

                                Сан-Квентин

                                8-я гвардейская общевойсковая армия

                                Алькесар