Talk:Power set

From Wikipedia, the free encyclopedia

WikiProject Mathematics
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

Contents

[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 \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 A∪B 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)

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

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