Talk:Power set

This  level-5 vital article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics High‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics High This article has been rated as High-priority on the project's priority scale.

"The power set of the set of natural numbers for instance can be put in a one-to-one correspondence with the set of real numbers (by identifying an infinite 0-1 sequence with the set of indices where the ones occur)."

The actual bijection should be more complicated. This one doesn't work because both 0.01111111111111... and 0.1 represent the same number (1/2), but they refer to different sets {x ∈ N: x>0} and {0}. The nicest thing is that in this very case they are the complement of each other! (anon forgot to sign)

That's right. Oleg Alexandrov 18:06, 1 Apr 2005 (UTC)

Huh? I don't get it. I'm not a math pro, but the bijection actually sounds fine to me. What I don't understand specifically in you argument is, how does 0.1 represent 1/2 and not 1/10? I take that the bijection was proposed with 0-1 sequences built as real numbers in decimal notation. Again, I'm not an expert, so I'm really asking this not to question your knowledge, but to learn more. Thanks. LodeRunner 16:43, 24 October 2005 (UTC)Reply

That gives you a bijection between the powerset of N and the set of all reals (between 0 and 1) that have decimal expansions containing only the digits 0 and 1. That's by no means all the reals (even between 0 and 1). --Trovatore 16:56, 24 October 2005 (UTC)Reply

Ah, I see. I misread the original sentence as trying to point out that the cardinality of the reals was >= than that of the power set of the naturals (I focused on what it proved instead of what it was saying it proved). Thanks for the clarification! LodeRunner 21:47, 26 October 2005 (UTC)Reply

In fact, there must be a bijection between the powerset of ${\displaystyle \mathbb {N} }$ and all the real numbers: ${\displaystyle \sharp {\mathcal {P}}(\mathbb {N} )=2^{\sharp \mathbb {N} }=2^{\aleph _{0}}=\aleph _{1}=\sharp \mathbb {R} }$. Rotring 14:48, 20 May 2006 (UTC)Reply

Please, do not use sharp sign for number sign! Not "harmonious". (Sorry.) Zaslav 10:00, 22 March 2007 (UTC)Reply

Well, here you're assuming the continuum hypothesis, which may not be true (in fact, among set theorists who think it's a meaningful question whether it's true or not, more think it's not true than that it is). But you don't need CH to show that there's a bijection between the reals and the powerset of the naturals; you can find one explicitly, by finding injections both ways (not difficult) and then applying the methodology of the Schröder–Bernstein theorem. --Trovatore 05:26, 11 June 2006 (UTC)Reply

Split all sequences into two sets: the set A of those containing infinite number of zeros and the other one, B with sequences which have a finite number of zeros and an infinite 111... tail. Map (f) the set A onto the interval D=[0,1) by adding a '0.' prefix to each sequence and applying the binary expansion. Of course f is a bijection.

Next order the B set into a sequence X. This can be done in two steps with complement sequences. Step one: map (g) sequences into ${\displaystyle \mathbb {N} }$: in each sequence in B replace every 0 with 1 and every 1 with 0, append 1 on the beginning, truncate trailing zeros and read result as binary numbers. Step two: order initial sequences by those numbers.

Then inject X into D: define a sequence in D, say:

${\displaystyle Y=(y_{i})_{i\in \mathbb {N} }={\begin{cases}0&i=1\\{\tfrac {1}{i}}&i>1\end{cases}}}$

separate them to free every other place and plug X items into freed places:

${\displaystyle {\mbox{sequence}}\mapsto {\begin{cases}f({\textrm {sequence}})&{\textrm {if}}\left\{{{\text{sequence is in A and}} \atop f({\textrm {sequence}})\notin \{{\text{values of }}Y\}}\right.\\y_{2i}&{\textrm {if}}\left\{{{\text{sequence is in A and}} \atop f({\textrm {sequence}})=y_{i}}\right.\\y_{2i+1}&{\textrm {if}}\left\{{{\text{sequence is in B and}} \atop {\textrm {sequence}}=x_{i}}\right.\end{cases}}}$

This makes a bijection from A∪B onto interval (0,1). Left and right extensions (that is ${\displaystyle A\cup B\to {\mathcal {P}}(\mathbb {N} )}$ and ${\displaystyle (0,1)\to \mathbb {R} }$) are quite easy. --CiaPan (talk) 12:25, 6 May 2008 (UTC)Reply

if P(A) denotes the power set of A, then are the following statements true? "P(A inter B) = P(A) inter P(B)" "P(A U B) = P(A) U P(B)" —Preceding unsigned comment added by 142.157.70.17 (talk) 06:39, 5 October 2009 (UTC)Reply

The first will be true but not the second. The powerset is a set of sets so a union of two powersets does not do any sort of union between individual elements of each powerset. The Wikipedia:Reference desk/Mathematics is usually the best place to ask straight questions which aren't related to possible problems or improvements in an article. Dmcq (talk)

I think it would be very useful for someone to include

1. the reason the power set was developed
2. the way power sets are used in practice or in higher math
3. and how the power set relates to other topics

unfortunately, i don't know enough about power sets to even begin to write about these things. I would personally be appreciative of anyone wanting to add those. Fresheneesz 01:55, 4 November 2005 (UTC)Reply

You raise excellent points. Unfortunately I probably won't get to them soon. Anyone else who's interested might point out the way the set of all real numbers can be coded up by the powerset of the naturals, and might discuss how, without the powerset axiom, we can't prove the existence of uncountable sets. See also Hartogs number. --Trovatore 03:00, 4 November 2005 (UTC)Reply

Hi: I've checked the FAQ and wandered through various help-type pages w/o success. I just finished writing Microsoft Excel-based Visual Basic for Application code to generate the power set (and subsets) for a set S.

Is there any documented guideline on adding such code to the wikipedia and if so the style/form for doing so?

Thanks.Tusharm 22:11, 7 November 2005 (UTC)Reply

My intuitive reaction is it doesn't really belong in this article. The thrust of this article is set-theoretic, which means the primary interest is infinite sets; no offense intended, but I doubt your program really works for those :-). But more generally, it's specific to a programming language, and I think that's not really the right thing for an article about an abstract concept. Maybe you could put it on Wikisource or Wikicommons, and put a link there from this article. --Trovatore 22:40, 7 November 2005 (UTC)Reply

Thanks for the comments. I'd reached the same conclusion (though not through the same reasoning vis-a-vis infinite sets {grin}) about the appropriateness of adding language-specific code here.Tusharm 14:59, 9 November 2005 (UTC)Reply

There is a really elegant recursive algorithm for computing power sets that could be posted in pseudo code:

   BEGIN CODE
   power_set(set)
   if set equals empty_set return empty_set
   else return {first(set) + power_set(rest(set)),power_set(rest(set))}
   END CODE

Of course it can be optimized (power_set need not be calculated twice if you want to make it procedural)

The + operation here prepends an item to every element of the set of sets it is passed.

The first function returns the first element of its argument

The rest function returns every element but the first element of the argument.

This function is O(2^n) where n is the number of elements in the original set.

I don't think it's possible to do better that this, but I don't know if that has been proven. — Preceding unsigned comment added by 76.172.74.74 (talk) 27 June 2007 (UTC)

I think its O(n^2) in time, the recursion tree has n nodes and it does at most n work at each level. It is possible there is some replicated work in this solution.... — Preceding unsigned comment added by 128.97.68.234 (talk) 27 June 2007 (UTC)

℘ (U+2118 SCRIPT CAPITAL P) redirects here, but it seems to also be used for Weierstrass's elliptic functions. Should there be a disambig page at ℘ instead? --Abdull 20:22, 7 June 2006 (UTC)Reply

Would be a good idea I would think. Oleg Alexandrov (talk) 05:13, 8 June 2006 (UTC)Reply

I think it should be removed from here altogether and dump the disambig page. ℘ is really only used for the power set by people who don't know how to get a script looking P in LaTeX any other way. (At least, that has been my experience with it.) It's simply not the right symbol. Steve Checkoway (talk) 07:54, 21 June 2009 (UTC)Reply

I agree that this is a LaTeX error and doesn't belong here. I have never seen any published work using \wp for the power set. I have therefore removed it. JordiGH (talk) 16:27, 7 July 2022 (UTC)Reply

This seems to have crept back into the page. Apparently in December 2022: [1]. I don't see any citation supporting the use of ℘ for powerset. I'm also not a mathematician. But I am going to WP:BEBOLD and remove it again.

Perhaps the other user meant to add 𝓅. Dingolover6969 (talk) 23:12, 22 September 2024 (UTC)Reply

This page needs a formal definition of a power set. Perhaps P(S)={x\subseteq S}. InformationSpace 03:21, 12 February 2007 (UTC)Reply

I don't see the need, as long as the definition is correct and clear. This is not a set-theoretical treatise (or is it?). Zaslav 10:03, 22 March 2007 (UTC)Reply

I suggest the notation {0,1}^S be de-emphasised. It is technically incorrect, since it really means a set of functions. Yes, they are equivalent, but they are not the same, and often that is important. I removed it from the introduction, but not from the special notation section since it may be used sometimes in the literature. Zaslav 10:07, 22 March 2007 (UTC)Reply

My office mate and I have both independently needed to use the notion of the set of all finite subsets of a set, and I was surprised there didn't seem to be an article on it or a mention of it in this article. PlanetMath suggests a convention on notation for it. Is there notation for it that is as standard as for ordinary power sets? Somebody want to incorporate this notion into this and/or another article? --pfunk42 (talk) 20:04, 4 August 2008 (UTC)Reply

There's no notation that's as standard, no. But I think ${\displaystyle [A]^{<\omega }}$ is fairly standard for the set of all finite subsets of A. --Trovatore (talk) 20:11, 4 August 2008 (UTC)Reply

Also ${\displaystyle {\mathcal {P}}_{fin}(A)}$. — Carl (CBM · talk) 20:24, 4 August 2008 (UTC)Reply

Yikes! Surely you mean ${\displaystyle {\mathcal {P}}_{\mathit {fin}}(A)}$. Steve Checkoway (talk) 07:55, 21 June 2009 (UTC)Reply

Based on the notation for subsets of limited cardinality in the article, we already effectively have a notation for this: ${\displaystyle {\mathcal {P}}_{\aleph _{0}}(A)}$. But is there a prose name? "Finite power set" might work as an informal term to tell some people what you mean, but it's inaccurate - unless A is finite, then both the power set and this subset are in fact infinite sets. — Smjg (talk) 15:50, 14 March 2015 (UTC)Reply

Hello. In my view, the section "Algorithms" was too long, making the article a little unbalanced. (In my experience, the field of "algorithms for computing powersets" is tiny in the general subject of "powersets".) I have removed the illustration of the algorithm, because the description of the algorithm is clear and sufficient. I apologise in advance to J R Spriggs, who undid my earlier action, perhaps with good reason. Another thing: it would be good if someone could provide a reference for the algorithm (I can't find one). Sam (talk) 10:23, 30 October 2008 (UTC)Reply

Someone put an implementation for the algorithm on the page. As discussed above, it doesn't really belong. I've moved the source code here until a more appropriate place for it is found. Sam (talk) 09:25, 14 April 2009 (UTC)Reply

function powerset($set) {
  $c = sizeof($set);

  if ($c == 0) {
    // sets of cardinality = 0

    // power set of empty set is the empty set
    return array(array());
  } elseif ($c == 1) {
    // sets of cardinality = 1

    // get set element 
    list ($a,) = $set;

    // return power set (for sets of cardinality = 1):
    // {{},{a}}
    return array(array(), array($a)); 
  } elseif ($c == 2) {
    // sets of cardinality = 2
    
    // get set elements    
    list ($a, $b,) = $set;

    // return power set (for sets of cardinality = 2):
    // {{}, {a}, {b}, {a,b}}
    return array(array(), array($a), array($b), array($a,$b)); 
  } else {
    // sets of n-cardinality 

    // split set S in sets H an T, such that:
    // S : {Element 1, Element 2, ..., Element n} -> 
    //   H : {Element 1},
    //   T : {Element 2, ..., Element n}
    $hd = array(array_shift($set));
    // Note that variable $set now .contains T
    
    // return powerset of S as cartesian product of power sets of T and H 
    return cjoin (powerset($hd), powerset($set));
  }
}

// returns the cartesian product of sets $a and $b
function cjoin($a, $b) {
  $out = array();

  for ($x=0;$x < sizeof($a);$x++) {
    for ($y=0;$y < sizeof($b);$y++) {
      $out[] = array_merge($a[$x], $b[$y]); 
    }
  }
  
  return $out;
}

Since the bit vector approach is more efficient, why is there any interest at all in the other approach, which seems like doing it the hard way for no apparent reason? --Vaughan Pratt (talk) 06:22, 4 April 2010 (UTC)Reply

Concerning the representation of Boolean algebras as subalgebras of power-set Boolean algebras, what is the intended meaning of the strange parenthetical remark "though this is not always a particularly illuminating representation of an infinite Boolean algebra"? That there exist unilluminating representations, or that there exist Boolean algebras that have no illuminating representation, or that there exist people who don't always find such representations illuminating? If the first then what does this have to do with Boolean algebras? Do there exist any algebraic structures which have no unilluminating representations? If the second, what's an example? Every example I could think of has a representation as a field of sets that I found illuminating. If the third, again what does this have to do with Boolean algebras, this has to be true for every kind of algebraic structure. --Vaughan Pratt (talk) 13:08, 8 May 2009 (UTC)Reply

I didn't write it, and I don't mind removing it. My guess is that they are saying that because of the nature of the representing algebra (it's a subset of a powerset algebra of ultrafilters, after all), the representation may not be very useful for obtaining results about the original Boolean algebra. But this is just part of the nature of the representation, so the parenthetical remark seems to be mostly useless. I can think of parallel case in other areas where there are general representations, but they are not very often useful. — Carl (CBM · talk) 13:25, 8 May 2009 (UTC)Reply

First, the sentence: "For example, the power set of the set of natural numbers can be put in a one-to-one correspondence with the set of real numbers" may need either further justification, or deletion. (I am not an expert.) But it seems to me that that assertion is assuming the continuum hypothesis to be "true", which of course is not the case, since it can neither be proven nor disproven in ZFC.

Second, the sentence: "Cantor's diagonal argument shows that the power set of a set (whether infinite or not) always has strictly higher cardinality than the set itself" I find hard to believe. I suspect that it is just wrong. Cantor's diagonal argument SPECIFICALLY shows that the cardinality of the real numbers is larger than the cardinality of the rational numbers. There is no way that this diagonalization argument can be applied to "higher orders of infinity", is there? No one has ever even demonstrated that "higher orders of infinity" exist, much less applied the diagonal argument to the higher orders. Cantor's diagonal argument shows that you cannot even list (potentially list) the real numbers. So how can you apply a diagonal argument to a list that cannot even exist? Am I wrong about this? Somebody who knows what he/she is talking about needs to address this. Worldrimroamer (talk) 19:15, 26 July 2009 (UTC)Reply

As to the first paragraph, no, this is completely different from CH. CH asserts that the reals may be put into one-one correspondence with the countable ordinals.

As to the second: The argument goes through for any set; for any set A, there is no function from A onto P(A). If you don't believe P(A) exists in the first place, you won't find this claim to have much content, but the argument is valid whether or not you think the result is meaningful. --Trovatore (talk) 19:22, 26 July 2009 (UTC)Reply

Trovatore, excuse me please if I'm annoying you, but I write this only because I care about the educational value of Wikipedia. CH says (postulates) that there is no set whose cardinality is strictly between that of the integers and that of the real numbers. Also, aside from "countably infinite" (i.e., the integers, rationals, etc.) there is also the term "at most countable". The point I'm making is that the paragraph in question needs to be expanded upon for educational purposes.

How can the reals be put into 1-to-1 correspondence with ANYTHING countable? This is wrong by trivial definition, isn't it? This is my problem with the article.

And, second, If it is true, as you say, that: "The argument goes through for any set; for any set A, there is no function from A onto P(A)", there should be a reference to the mathematical validity of that claim. It is a quite non-trivial point, and I DO NOT doubt for a second that you know what you're talking about, but I just saying that I think it should be documented, for educational purposes. In fact, I, personally, would be very interested to see why the comment about "any set A" and "and A onto P(A)" is true. I've never seen it (except for P(N) where N is the set of natural numbers), and I am very fascinated by the whole issue. Again, I am NOT questioning your knowledge of the subject, I'm just saying I think these issues should be addressed. I think wiki should expound upon it.

Thank you for your attention to my comments. Worldrimroamer (talk) 00:49, 27 July 2009 (UTC)Reply

The powerset of the natural numbers can be mapped bijectively onto the Cantor set which is a subset of the real numbers. The real numbers can be mapped one-to-one into the interval (0,1) of the reals which can be mapped one-to-one into the powerset of the natural numbers by interpreting each such real as an ω-sequence of binary digits (choosing the sequence which ends in all zeros where there is an ambiguity) and regarding these functions as the indicator functions of subsets of the natural numbers (n∈S <-> 1 is the coefficient of 2^-(n+1) in the binary expansion of the real). Using the Cantor–Bernstein–Schroeder theorem, one gets that the powerset of the natural numbers can be placed into a one-to-one correspondence with the real numbers. Obviously this argument does not use either the continuum hypothesis or the axiom of choice.

See Cantor's diagonal argument#General sets for a very simple proof that no set can be mapped onto its powerset. JRSpriggs (talk) 04:07, 27 July 2009 (UTC)Reply

The article follows "For example, the power set of the set of natural numbers can be put in a one-to-one correspondence with the set of real numbers" immediately with "(see cardinality of the continuum)". The article also has "Cantor's diagnonal argument" as a hyperlink in "Cantor's diagonal argument shows that the power set of a set (whether infinite or not) always has strictly higher cardinality than the set itself". The hyperlinks are meant to be followed if one has difficulties whilst reading those statements. Afterwards pressing the back button on the browser gets back to this original article. The articles are not and cannot be self contained - that would defeat a lot of the purpose of Wikipedia as an internet encyclopaedia. If you dispute a statement there should be a reference or a link where you can check. If there is no such link or reference or it doesn't back up what's said then you have a dispute with the content of the article. However here the dispute as far as I can see is over facts supported by links without as far as I can see checking up the links in the first place. Dmcq (talk) 07:53, 27 July 2009 (UTC)Reply

To Worldrimroamer:
You asked

"How can the reals be put into 1-to-1 correspondence with ANYTHING countable?"

Of course they can't−and they are not put in such correspondence. The paragraph in question does not say:

"the set of natural numbers can be put in a one-to-one correspondence with the set of real numbers"

but rather

"the power set of the set of natural numbers can be put in a one-to-one correspondence with the set of real numbers"

that is "the set of all subsets of ${\displaystyle \mathbb {N} }$", which may be equivalently represented as the set of all binary sequences. See the section #other above and #About the "Real numbers" section - 2 in the Cantor's diagonal argument's talk page for examples of such bijection. --CiaPan (talk) 15:49, 7 April 2010 (UTC)Reply

User:AMenteLibera wrote <<Please add demonstration - one can be found in the italian wiki at Insieme delle parti>> in the section Power set#Properties. I think that request is more appropriate here on the talk page. There is a sketch argument already, in the footnote -- is that enough? or should we include a proof... ComputScientist (talk) 18:08, 4 November 2011 (UTC)Reply

I've just added to the properties section a somewhat colloquial explanation why the cardinality is exponential. It is true that the very next section gives essentially the same information. But that pre-existing presentation is much more technical than the version I inserted, and I think that readers with less mathematical sophistication will, despite their lack of expertise, be interested to know why it's exponential.

Nevertheless, the article does contain at this moment two successive versions of the same information that are merely expressed at distinct levels of technical detail. How do others think we should proceed?—PaulTanenbaum (talk) 14:51, 5 April 2012 (UTC)Reply

The topology of the pointwise convergence is not convenient for the power set. The good topology is the following: a sequence of sets ${\displaystyle (A_{n})}$ converges to ${\displaystyle A}$ if and only if ${\displaystyle \cap _{N}\cup _{n\geq N}A_{n}=A}$. Alain-yves.thomas (talk) 17:12, 9 July 2012 (UTC) — Preceding unsigned comment added by Alain-yves.thomas (talk • contribs) 04:11, 7 July 2012 (UTC)Reply

I removed this section

Since any family of functions X^Y from Y to X might be topologized establishing the so-called function space, the same can be done with the power set 2^S identified as {0,1}^S. This particular type of function space is often called a hyperspace and the topology on the power set is referred to as hypertopology.

The (unreferenced) article on function space does not define a topology, and a hypertopology is stated to be defined on the closed sets of a topological space. In other words, this paragraph is sufficiently incoherent to warrant removal. Is there a decent reference for any of this? Deltahedron (talk) 22:57, 21 January 2013 (UTC)Reply

I don't know of a decent reference, but this paper on hit-and-miss hypertopologies shows how power sets are used to define hypertopologies. Mark viking (talk) 00:34, 22 January 2013 (UTC)Reply

Without a decent reference there's really nothing more to say. The paragraph as it stood makes no sense and there's no reference we can use to rewrite it. Deltahedron (talk) 07:28, 22 January 2013 (UTC)Reply

What is the source of the "Subsets of limited cardinality" section?

Should not ${\displaystyle {\mathcal {P}}_{\kappa }(S)}$ mean the set of subsets of S of cardinality less than or equal to κ?

Is ${\displaystyle {\mathcal {P}}_{\leq \kappa }(S)}$ also a commonly used notation?

utapyngo (talk) 08:43, 21 November 2012 (UTC)Reply

why is this included in the "binary operations" section of Template:Set_theory? Adavies42 (talk) 22:06, 17 December 2012 (UTC)Reply

Good catch — I've removed it. --Trovatore (talk) 22:08, 17 December 2012 (UTC)Reply

The Power Set describes the set generated by the Kleene star operation, but neither page references the other. I suggest making the relationship explicit. SMesser (talk) 21:47, 1 December 2014 (UTC)Reply

The Kleene star is the set of ordered finite sequences made with elements from a given set. The powerset is the set of unordered subsets, and they don't have to be finite. It's true that the operations have some things in common, but I don't immediately see any relationship so compelling that it burns to be stated here. (I wouldn't oppose adding it to "see also".) --Trovatore (talk) 15:51, 2 December 2014 (UTC)Reply

We may as well mention binary trees, hexadecimal numbers and 32bit CPUs here, because, lets face it, 2^n appears everywhere. Good idea would be linking to 2^n article, and from there linking to all the relevant articles about powers of two, including binomial stuff.

-NikitaSadkov (talk) 00:13, 17 October 2018 (UTC)Reply

1. analyze set theories of physics (nowadays are impossible because physics is incomplete, but add links on the subject)
2. after you add set theories of physics; as a metalogical elaboration of cosmogony through the prism of set theory (even that is not possible nowadays; but add all the links; not here; make a page. Don't blame me for writing here and not on the non-existing page.)

Zero doesn't exist (the average of some set or some qualities can be zero, but not any specific material something). The null set exists. The universe exists.

It makes no sense to start with cosmogony. Mention set theories of physics. — Preceding unsigned comment added by 2A02:587:4115:1000:4005:4380:AB99:AB8C (talk) 23:07, 18 July 2019 (UTC)Reply

Part of the first sentence reads identifying the powerset of S with the set of all functions from S to a given set of two elements. It does not become clear what function means in this respect and in which relation the given set of two elements stands to the set S. Using the example from the article with a set S={x,y,z} and its power set P(S)={{},{x},{y},{z},{x,y},{x,z},{y,z},{x,y,z}} containing 8 elements, how would this power set be identified with the set of all functions from S to a set of two elements, for example, {a,b}? Arbitrarily many functions from S to {a,b} can be defined, not only 8. Thanks for indicating the point where I got it wrong. --193.222.161.35 (talk) 09:25, 25 July 2019 (UTC)Reply

Nope, there are exactly eight functions from your S to arbitrary {a, b} :

• a constant function equal a: {(x,a), (y,a), (z,a)} ;
• a function which is b at x only: {(x,b), (y,a), (z,a)} ;
• a function which is b at y only: {(x,a), (y,b), (z,a)} ;
• a function which is b at z only: {(x,a), (y,a), (z,b)} ;
• a function which is a at z only: {(x,b), (y,b), (z,a)} ;
• a function which is a at y only: {(x,b), (y,a), (z,b)} ;
• a function which is a at x only: {(x,a), (y,b), (z,b)} ; and finally
• a constant function equal b: {(x,b), (y,b), (z,b)} .

Replace 'b' with '1' or with 'the argument belongs to a subset' and 'a' with '0' or 'not b', and you'll see each function defines exactly one subset of your three-element set S; that is, exactly one element of your eight-element power-set P(S). --CiaPan (talk) 10:55, 25 July 2019 (UTC)Reply

OK, thanks. This answers, at least for me, the question about the functions. The powerset is actually not identified with the set of all functions from S to a two-element-set but it is identified with the set of graphs of all functions from S to a two-element-set. --193.222.161.35 (talk) 12:20, 25 July 2019 (UTC)Reply

Assuming the codomain is known (and it is, in this case) the graphs are in an obvious one-to-one correspondence to the functions, so the distinction is insignificant. --CiaPan (talk) 12:28, 25 July 2019 (UTC)Reply

I noticed that the article tends to use the markup {{mathcal|P}} for the power set-P, which renders as P. However, this doesn't look anything like the LaTeX equivalent: ${\displaystyle {\mathcal {P}}}$ (for me). The wikicode version simply looks like a funny sans-serif roman P. I've been meaning to deal with stuff that uses {{mathcal}} for a while now, but haven't gotten around to it. WP:VPT or WT:WPM might be a better place for this, but I thought I'd just try quick sense if other people have the same issue before going elsewhere. –Deacon Vorbis (carbon • videos) 14:36, 27 October 2019 (UTC)Reply

The two mathcal P's look similar on my system; the main difference is that the wikicode one has a horizontal stroke at the bottom, which is not present in the latex one. They are certainly recognizable as the same symbol. --JBL (talk) 13:28, 18 December 2019 (UTC)Reply

In the current version Special:PermaLink/986826045 there is a note in the lead section, defined with <ref group=note>. It got its number 1. in the note group, but it's displayed right above a 1. reference defined with the default group – see Special:PermaLink/986826045#Notes.

That's because both reflists are inserted in the same Notes section. I would like to split the section into Notes and References, but the References section exists already and it contains bibliography!

How should I clean up that mess? --CiaPan (talk) 09:49, 3 November 2020 (UTC)Reply

Solved by splitting the Notes section into Notes & Reference and renaming previous References section to Bibliography: Special:Diff/986874963. --CiaPan (talk) 14:33, 3 November 2020 (UTC)Reply

An editor is edit warring for including a Python implementation in the article. Such an implementation in a specific programming language is clearly discouraged by MOS:MATH#Algorithms, since there is no algorithm in this article.

Moreover, if one would want to include an algorith for generating the power set of a given finite set, this implementation is definitively not convenient, since the algorithm is hidden behind features of a specific library extending Python. In particular, there is no way to know whether the algorithm has the expected computational complexity, which is the following: the time complexity must be linear in the output size; the used memory must be linear in the input size, if the storage of the output is not counted (output streaming).

So, I'll revert this Python implementation again. D.Lazard (talk) 12:23, 1 January 2024 (UTC)Reply

User pushing the WP:OR python implementation is currently blocked after edit-warring (WP:3RR) violation. If the edit-warring behavior continues, an alternative is WP:RFP. If Tzv06887 wishes to make a case for inclusion on the talk page, then they are welcome to do so after their block expires, but per WP:NOR it appears unlikely to me that this material is due in the article. Russ Woodroofe (talk) 18:27, 3 January 2024 (UTC)Reply

To be honest the OR is probably the least of the problems with it. A language-specific implementation — particularly one that gives no clue as to the algorithm, but just calls an external library — is never going to fly here, even if you can source it.

It wouldn't be completely out of bounds to discuss including pseudocode for an algorithm for powersets of finite sets. I still would probably be against it, because I think of this as a math article and mainly focused on powersets of infinite sets. But it would be within the realm of plausibility. --Trovatore (talk) 20:26, 3 January 2024 (UTC)Reply

Even for power sets of finite sets, a pseudo code would be completely out of the scope of this article. Indeed, such an algorithm depends strongly on the method used for representing the subsets of a set. For example, if the subsets of a set with n elements are represented by their indicator function (more precisely, the sequence of the values of their indicator function), then the power set consists of set of all binary representations of the integers from 0 to ${\displaystyle 2^{n}-1.}$ In other words, the algorithm consists of counting in base two. D.Lazard (talk) 22:52, 3 January 2024 (UTC)Reply

The section Power object begins with this sentence:

"A set can be regarded as an algebra having no nontrivial operations or defining equations."

But the word "algebra" (even an algebra of sets) has multiple distinct meanings.

It would be better if the type of algebra were mentioned.

I hope someone knowledgeable on this topic can elaborate on this point, so that this sentence becomes less mysterious.

(I have no idea what kind of "algebra" can have no nontrivial operations or defining equations. I suspect few people dp.)

"The power set of a set S, together with the operations of union, intersection and complement, is a σ-algebra over S"

This is incorrect, in general. A σ-algebra requires sequences to converge. Not true in, for example, ℝ. Skewray (talk) 18:22, 22 November 2025 (UTC)Reply

Really not sure what you're getting at here, but no, this is not true. You can find the definition of σ-algebra at its article, and you can easily check that ${\displaystyle {\mathcal {P}}(\mathbf {R} )}$ satisfies that definition. --Trovatore (talk) 20:35, 22 November 2025 (UTC)Reply

You are correct. I am referencing a book on measure theory in English, but written by a Frenchman. I was thrown by a highly misleading sentence.

Are we supposed to blast this entire conversation, or leave it here for posterity? Skewray (talk) 17:43, 23 November 2025 (UTC)Reply

Usually we just leave them. Sometimes someone else comes with the same assertion and it's useful to point to the precedent. I don't really think that will happen this time but you never know. --Trovatore (talk) 22:50, 23 November 2025 (UTC)Reply