Talk:Power set

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, High-importance)
WikiProject Mathematics
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.
Mathematics rating:
C Class
High Importance
 Field: Foundations, logic, and set theory

other[edit]

"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 {xN: 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)
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)
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)
In fact, there must be a bijection between the powerset of \mathbb{N} and all the real numbers: \sharp\mathcal{P}(\mathbb{N}) = 2^{\sharp\mathbb{N}} = 2^{\aleph_0} = \aleph_1 = \sharp\mathbb{R}. Rotring 14:48, 20 May 2006 (UTC)
Please, do not use sharp sign for number sign! Not "harmonious". (Sorry.) Zaslav 10:00, 22 March 2007 (UTC)
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)
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 \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:
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:
\mbox{sequence}\mapsto\begin{cases}
f(\textrm{sequence}) & \textrm{if } \left\{ {\textrm{sequence\ is\ in\ A\ and} \atop f(\textrm{sequence}) \notin \{\textrm{values\ of\ } Y\}}\right. \\
y_{2i} & \textrm{if } \left\{ {\textrm{sequence\ is\ in\ A\ and} \atop f(\textrm{sequence}) = y_i}\right. \\
y_{2i+1} & \textrm{if } \left\{ {\textrm{sequence\ is\ in\ B\ and} \atop \textrm{sequence} = x_i}\right. 
\end{cases}
This makes a bijection from AB onto interval (0,1). Left and right extensions (that is A\cup B \to \mathcal P(\mathbb N) and (0,1) \to \mathbb R) are quite easy. --CiaPan (talk) 12:25, 6 May 2008 (UTC)
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)
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)

application and use[edit]

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)

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)

Is there a norm for posting code?[edit]

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)

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)
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)
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) in space where n is the number of elements in the original set. 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....

[edit]

(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)

Would be a good idea I would think. Oleg Alexandrov (talk) 05:13, 8 June 2006 (UTC)
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)

Formal definition of a Power set[edit]

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

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)

Notation[edit]

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)

Finite power set[edit]

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)

There's no notation that's as standard, no. But I think [A]^{<\omega} is fairly standard for the set of all finite subsets of A. --Trovatore (talk) 20:11, 4 August 2008 (UTC)
Also \mathcal{P}_{fin}(A). — Carl (CBM · talk) 20:24, 4 August 2008 (UTC)
Yikes! Surely you mean \mathcal{P}_{\mathit{fin}}(A). Steve Checkoway (talk) 07:55, 21 June 2009 (UTC)
Based on the notation for subsets of limited cardinality in the article, we already effectively have a notation for this: \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)

Algorithms[edit]

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)

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

Not illuminating?[edit]

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)

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)

Huhh???[edit]

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)

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)

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)

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 (nS <-> 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)
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)
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 \Bbb 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)

Request for demonstration[edit]

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)

Redundance about cardinality?[edit]

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)

About the section: Topologization of power set (This section requires expansion. (April 2010))[edit]

The topology of the pointwise convergence is not convenient for the power set. The good topology is the following: a sequence of sets (A_n) converges to A if and only if \cap_N\cup_{n\ge N}A_n=A. Alain-yves.thomas (talk) 17:12, 9 July 2012 (UTC) — Preceding unsigned comment added by Alain-yves.thomas (talkcontribs) 04:11, 7 July 2012 (UTC)

I removed this section
Since any family of functions XY from Y to X might be topologized establishing the so-called function space, the same can be done with the power set 2S 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)
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)
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)

Notation for powersets of limited cardinality[edit]

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

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

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

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

binary operation?[edit]

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

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

Link to Kleene Star page[edit]

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)

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)