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












3














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.

























    3














    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.























      3












      3








      3







      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.











      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




      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






      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 4 hours ago









      commentallez-vouscommentallez-vous

      1305




      1305




      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.






















          4 Answers
          4






          active

          oldest

          votes


















          7














          enter image description here




          • "Include A?" is stage 1

          • "Include B?" is stage 2

          • "Include C?" is stage 3.






          share|cite|improve this answer





























            4














            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





















            • Thanks pwerth, this is a wonderful and direct view on the process using 1010 as an example.
              – commentallez-vous
              4 hours ago










            • You're welcome, glad to help!
              – pwerth
              4 hours ago



















            1














            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





















            • Thank you Milo, I think I got it using your explanation with pwerth's. I really appreciate it!
              – commentallez-vous
              4 hours ago



















            1














            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























              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

























              4 Answers
              4






              active

              oldest

              votes








              4 Answers
              4






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes









              7














              enter image description here




              • "Include A?" is stage 1

              • "Include B?" is stage 2

              • "Include C?" is stage 3.






              share|cite|improve this answer


























                7














                enter image description here




                • "Include A?" is stage 1

                • "Include B?" is stage 2

                • "Include C?" is stage 3.






                share|cite|improve this answer
























                  7












                  7








                  7






                  enter image description here




                  • "Include A?" is stage 1

                  • "Include B?" is stage 2

                  • "Include C?" is stage 3.






                  share|cite|improve this answer












                  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 3 hours ago









                  EelvexEelvex

                  965518




                  965518























                      4














                      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





















                      • Thanks pwerth, this is a wonderful and direct view on the process using 1010 as an example.
                        – commentallez-vous
                        4 hours ago










                      • You're welcome, glad to help!
                        – pwerth
                        4 hours ago
















                      4














                      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





















                      • Thanks pwerth, this is a wonderful and direct view on the process using 1010 as an example.
                        – commentallez-vous
                        4 hours ago










                      • You're welcome, glad to help!
                        – pwerth
                        4 hours ago














                      4












                      4








                      4






                      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












                      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 4 hours ago









                      pwerthpwerth

                      1,807411




                      1,807411












                      • Thanks pwerth, this is a wonderful and direct view on the process using 1010 as an example.
                        – commentallez-vous
                        4 hours ago










                      • You're welcome, glad to help!
                        – pwerth
                        4 hours ago


















                      • Thanks pwerth, this is a wonderful and direct view on the process using 1010 as an example.
                        – commentallez-vous
                        4 hours ago










                      • You're welcome, glad to help!
                        – pwerth
                        4 hours ago
















                      Thanks pwerth, this is a wonderful and direct view on the process using 1010 as an example.
                      – commentallez-vous
                      4 hours ago




                      Thanks pwerth, this is a wonderful and direct view on the process using 1010 as an example.
                      – commentallez-vous
                      4 hours ago












                      You're welcome, glad to help!
                      – pwerth
                      4 hours ago




                      You're welcome, glad to help!
                      – pwerth
                      4 hours ago











                      1














                      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





















                      • Thank you Milo, I think I got it using your explanation with pwerth's. I really appreciate it!
                        – commentallez-vous
                        4 hours ago
















                      1














                      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





















                      • Thank you Milo, I think I got it using your explanation with pwerth's. I really appreciate it!
                        – commentallez-vous
                        4 hours ago














                      1












                      1








                      1






                      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












                      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 4 hours ago









                      Milo BrandtMilo Brandt

                      39.4k475139




                      39.4k475139












                      • Thank you Milo, I think I got it using your explanation with pwerth's. I really appreciate it!
                        – commentallez-vous
                        4 hours ago


















                      • Thank you Milo, I think I got it using your explanation with pwerth's. I really appreciate it!
                        – commentallez-vous
                        4 hours ago
















                      Thank you Milo, I think I got it using your explanation with pwerth's. I really appreciate it!
                      – commentallez-vous
                      4 hours ago




                      Thank you Milo, I think I got it using your explanation with pwerth's. I really appreciate it!
                      – commentallez-vous
                      4 hours ago











                      1














                      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




























                        1














                        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


























                          1












                          1








                          1






                          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














                          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 hours ago

























                          answered 4 hours ago









                          Chris CusterChris Custer

                          11k3824




                          11k3824






















                              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.





                              Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                              Please pay close attention to the following guidance:


                              • Please be sure to answer the question. Provide details and share your research!

                              But avoid …



                              • Asking for help, clarification, or responding to other answers.

                              • Making statements based on opinion; back them up with references or personal experience.


                              To learn more, see our tips on writing great answers.




                              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

                              Lallio

                              Image
                              Coordenadas: 45° 40' N 9° 38' E Lallio      Comuna    Lallio Localização de Lallio na Itália Coordenadas 45° 40' N 9° 38' E Região Lombardia Província Bérgamo Área - Total 2 km² Altitude 216 m População  - Total 3 826     • Densidade 1 913 hab./km² Outros dados Comunas limítrofes Bergamo, Dalmine, Stezzano, Treviolo Código ISTAT 016123 Código cadastral E422 Código postal 24040 Prefixo telefônico 035 Website www.comune.lallio.bg.it Lallio é uma comuna italiana da região da Lombardia, província de Bérgamo, com cerca de 3.826 habitantes. Estende-se por uma área de 2 km², tendo uma densidade populacional de 1913 hab/km². Faz fronteira com Bergamo, Dalmine, Stezzano, Treviolo. [ 1 ] [ 2 ] [ 3 ] Demografia | Variação demográfica do município entre 1861 e 2011 [ 3 ] Fonte : Istituto Nazionale di Statistica (ISTAT) - Elabor...
                              Read more

                              Unable to find Lightning Node

                              Image
                              2 I have successfully installed and synced my lightning node (Raspiblitz). I see my public ip on port 8333 has 8 conns. However, when I check my node on 1ml.com my node is not found. I did forward port 8333 and 9735 on my router. Should I connect to a peer or create a channel before my node is visible for the outside? lightning-network lightning-network-daemon share | improve this question asked 1 hour ago Bart DV Bart DV 31 3 add a comment  |  ...
                              Read more

                              Futebolista

                              Image
                              Ronaldo primeiro jogador a ser eleito por três vezes o melhor jogador do mundo pela FIFA. Ronaldinho Gaúcho atuando pelo Barcelona onde foi duas vezes eleito o melhor jogador do mundo pela FIFA. Kaká atuando pelo Milan onde foi eleito em 2007 o melhor jogador do mundo pela FIFA. Lothar Matthäus primeiro jogador a ser eleito o melhor jogador do mundo pela FIFA em 1991 pela Inter de Milão. Neymar durante partida contra a Escócia, em 27 de março de 2011. Crianças praticando futebol. Robinho, futebolista brasileiro, em 15 de novembro de 2006. Atletas do Chelsea, da Inglaterra. A venda de camisas com nome e número dos jogadores é uma grande fonte de arrecadação. Jürgen Klinsmann atuou como jogador e foi treinador da Alemanha. Estádio de futebol, principal local onde laboram os jogadores. O jogador de futebol , ou Futebolista , é um atleta profissional de futebol, e cuja prática do desporto coletivo é fundamental. Estes trabalhadores sã...
                              Read more