Talk:Power set

From Wikipedia, the free encyclopedia

WikiProject Mathematics     (Rated Stub-Class)
Mathematics portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	Stub Class	High Priority	Field: Foundations, logic, and set theory
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. An important concept like this deserves more! Geometry guy 21:20, 9 July 2007 (UTC)

Contents 1 other 2 application and use 3 Is there a norm for posting code? 4 ℘ 5 Formal definition of a Power set 6 Notation 7 Finite power set 8 Algorithms 9 Not illuminating?

[edit] other

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

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 and all the real numbers: . 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 : 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:

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

This makes a bijection from A∪B onto interval (0,1). Left and right extensions (that is and ) are quite easy. --CiaPan (talk) 12:25, 6 May 2008 (UTC)

[edit] application and use

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)

[edit] Is there a norm for posting code?

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)

[edit] Formal definition of a Power set

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)

[edit] Notation

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)

[edit] Finite power set

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] ^{< ω} is fairly standard for the set of all finite subsets of A. --Trovatore (talk) 20:11, 4 August 2008 (UTC)

Also . — Carl (CBM · talk) 20:24, 4 August 2008 (UTC)

Yikes! Surely you mean . Steve Checkoway (talk) 07:55, 21 June 2009 (UTC)

[edit] Algorithms

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

[edit] Not illuminating?

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)