# power set

• Jan 18th 2013, 09:36 PM
jojo7777777
power set
1. Is the power set P({1, {1,2}}) has an element {{ }, {1,2}} ?
2. Is R2⊆R3 false simply because of the different dimensions?
3. What is P(P(R2))? If I view P(R2) as any possible set of points in the Cartesian plane?
• Jan 18th 2013, 10:09 PM
Deveno
Re: power set
1. no. {1,{1,2}} is a set which has 2 elements: 1, and {1,2}. its power set is:

{Ø, {1}, {{1,2}}, {1, {1,2}} }

the set {Ø,{1,2}} is not any of these 4 elements. <--this is a set with 2 elements and the only element of P({1,{1,2}}) that has 2 elements is {1,{1,2}}, and 1 is not an element of {Ø,{1,2}}, so these two sets can't be equal.

2. it depends on your viewpoint.

strictly speaking, R2 is not a subset of R3, since a (non-empty) subset of R3 consists of vectors (x,y,z) all of which have 3 coordinates. elements of R2 have only two coordinates (a type-mismatch).

however, there are subspaces of R3 isomorphic (as vector spaces, and thus as sets) to R2:

one can verify that (x,y) -->(x,y,0) defines an injective map of R2 into R3, the image of which behaves in almost every respect "just like R2".

in various algebra fields, one often replaces "equal" to "equal up to isomorphism" (which is an equivalence relation, albeit one usually over a proper CLASS, not a set), because "isomorphic objects" behave the same as far as algebra is concerned.

one CAN take the same view with sets: regarding the set {a,b,c} as "essentially the same" as {a,b,d} (they both have 3 elements)...in this context a set-isomorphism is just a bijection.

BUT...obviously, this can lead to problems if one is looking at P({a,b,c,d}), for example.

this problem is a bit worse than it might appear: consider the following distinct sets:

A = {Ø, {Ø}, {Ø,{Ø}}, {Ø,{Ø,{Ø}}},.....} if we call Ø = 0, and {0} = 1, and {0,1} = 2, this can be seen as one way to construct natural numbers.

B = {Ø, {Ø}, {{Ø}}, {{{Ø}}}, .......} this starts out the same, but now 2 = {1}, 3 = {2}, etc. this is an alternate way to construct natural numbers.

but shouldn't the natural numbers be one set or the other? which is it?

another way would be to let natural numbers be "ur-elements", things which are like "atoms" that can inhabit sets, but are not sets themselves. this is probably the way sets were first thought of (later, it was decided this was "excess baggage"). the problem with doing this, however, is that it lets us do mathematics perfectly fine, but leaves us wondering what {Ted,Bob,Alice} might mean (i'm not an expert, but i believe that logicists address this by making such things part of a "background alphabet", whatever THAT means. explain one term, you get another...i find myself wondering if we even ever know what we are talking about at all...but that's another can of worms).

short answer to #2: if you're talking to a set-theorist, it's false. if you're talking to a topologist (or algebraist) it's true (up to some isomorphism, of course).
• Jan 20th 2013, 09:56 AM
jojo7777777
Re: power set
I'm endlessly grateful to you for providing such a professional help!

If you allow me, I would like to ask a few questions:
1.
Quote:

BUT...obviously, this can lead to problems if one is looking at P({a,b,c,d}), for example.
Does the problem in this example is that for P({a,b,c,d}) the sets- {a,b,c}, {a,b,d} are distinct while at the same time they are "essentially the same" (set isomorphism)?

2. If natural numbers are "ur-elements" then they don't need to be constructed (like was done in sets A and B)?

3. Let me restate the third question in the original post: If P(R^2) contains every imaginable function and every imaginable black-white image (where the black points belong to the subset and the white points do not), will P(P(R^2)) mean something?

• Jan 20th 2013, 11:50 AM
Deveno
Re: power set
the answer to your third question is easier if we consider just a two-point set, instead of R: S = {0,1}.

now SxS = {(0,0),(0,1),(1,0),(1,1)},

so P(SxS) = {Ø, {(0,0)}, {(0,1)}, {(1,0)}, {(1,1)}, {(0,0),(0,1)},{(0,0),(1,0)}, {(0,0),(1,1)}, {(0,1),(1,0)}, {(0,1),(1,1)}, {(1,0),(1,1)}, {(0,0),(0,1),(1,0)}, {(0,0),(0,1),(1,1)}, {(0,0),(1,0),(1,1)},{(0,1),(1,0),(1,1)}, SxS}

this can be visualized as every black and white coloring of a 2x2 grid, for example: {(0,0),(1,1)} would be:

BW
WB

so P(P(SxS)) would be "collections of colorings", one element of P(P(SxS)) might be "all colorings with 3 squares black" (there are 4 of these).

one can identify an element of P(RxR) as a "region" of RxR (such a region may be highly disconnected, of course, composed of many "islands" (isolated points)). P(P(RxR)) has elements which are "collections of regions" (for example, one element might be:

"all regions where the entire third quadrant is white").

the level of abstraction in talking of P(P(RxR)) is already quite high, since R itself is defined as a certain subset of P(Q), and Q is an equivalence on ZxZ* and Z is an equivalence on NxN

(so an integer is an element of P(NxNxNxN), and a rational number is an element of P(ZxZ*xZxZ*), and thus an element of P(P(NxNxNxN)xP(NxNxNxN)xP(NxNxNxN)xP(NxNxNxN)), so we are already "three power sets deep" just to talk about real numbers, and then talking about P(P(RxR)) is "two more power sets deep". such a set (the various collections of regions in the plane) is QUITE large, some might say TOO large, we cannot even begin to explore it).

to give an example of just how complicated this really is, consider the real number -3/4:

-3/4 = sup({x in Q: 4x < -3}), and as a rational number:

-3/4 = [(-3,4)] = [([(0,3)]),([(4,0)])] <--the square brackets "equivalence class" hide just how large this set is, we can also write:

-3/4 = [(-6,8)] = [([(4,10)]),([(20,12)])], for example.

our arithmetical notation helps us out a bit, here: all i am really saying is:

(0-3)/(4-0) = (4-10)/(20-12), or as one might have said long ago:

"3 to the left done 20 times, and then undone 12 times is equal and opposite to: 4 to the left, then 10 to the right performed twice twice".

**********************

yes, P(P(S)) is ALWAYS "meaningful" but usually one has to "expand the context". the history of mathematics is rife with such "enlarging of context". counting (reckoning) did not allow for "negative numbers" (negative sheep don't exist), but giving them meaning allowed subtraction to be meaningful in contexts it wasn't before. for a long time, it was thought "the integers were big enough for everything" (rational numbers can be thought of as "comparing integers"), but the pythagorean theorem put an abrupt end to that. then, numbers constructible with rule and compass were thought to be "big enough for everything", but that notion, too, was laid to rest in the 19-th century. cantor's famous "diagonal argument" shows that there ISN'T any "big enough for everything": the power set of an infinite countable set is uncountable, and the power set of THAT is "even bigger".

it never ends....for every way of constructing a "limit cardinal", there lies another larger cardinal beyond it, and so it must be...for if one set contained everything, we would have a nasty self-referential paradox.

a word about "=" (equals). we almost never mean, when we write A = B, that A and B are exactly the same. what we usually mean is there is some "evaluation function" E, for which E(A) = E(B).

for example, when we write x + 3 = 6, we don't mean "x + 3" and "6" are the same polynomial. we mean:

there is some number a such that for f(x) = x + 3, and g(x) = 6, f(a) = g(a) (and this number is a = 3). in this case E is the function: polynomials-->numbers given by: E(f(x)) = f(a).

you are correct, "ur-elements" don't NEED to be defined (but they are usually specified before-hand. this is like setting "the topic of discussion"). sometimes this is more useful than it seems: it is well-nigh impossible, in plane geometry, to define what a point, or a line IS (and it turns out that NOT doing so is beneficial..."geometries can be more than we first thought"). there are several "versions" of "set-theory with ur-elements", and most of them are considered "non-standard" (the set theory proposed by Zermelo and modified by Fraenkel is seen as "robust enough and complete enough for most mathematics").

naively (and thus imprecisely), whenever we talk about a "bunch" of things, we usually don't want to talk about "all" of them. we want to talk about the "interesting ones". if we are using set-notation to distinguish which ones are the interesting ones, it would be comforting to know that this makes SENSE, that is, given any collection (think: set here), we want to have all the "sub-collections" (think: subsets here) available to us. power sets let us do that. this lets us "forget about the background" (where these "interesting things 'live' ") and focus instead on "properties of interesting things". we aren't typically interested in EVERY subset of the plane, all at once, but rather CERTAIN subsets of the plane, which mean something to us (like a circle, or curve, or graph of a function). so a power set is like a library, which hold all the books, even those we never want to read.
• Jan 23rd 2013, 12:21 PM
jojo7777777
Re: power set
I am grateful to you for your invaluable help!

Sorry for asking again, but for making things a bit more clear for me:
1. What does "*" mean in the expression "ZxZ*"?
2. How an integer is an element of P(NxNxNxN), how do the negative integers come in?
3.
Quote:

...since R itself is defined as a certain subset of P(Q)...
is that a general statement (if so, how irrational numbers may be found there), or it refers to the first sentence of your answer?

Thanks again
• Jan 23rd 2013, 01:33 PM
Deveno
Re: power set
1. in this case Z* is just an abbreviation for Z\{0}.

2. we construct the integers from the natural numbers like so:

we define the equivalence relation ~ on NxN by: (k,m) ~ (k',m') if k+m' = k'+m...the general idea is to think of k as "the positive part" and m as "the negative part".

having done so, we need a way to add these equivalence classes of pairs of numbers, which we do like so:

[(k,m)] + [(k',m')] = [(k+k',m+m')]. it is clear that this addition is associative and commutative. it is not so clear it is well-defined, however:

if (r,s) ~ (k,m) and (r',s') ~ (k',m'), then r+m = s+k, and r'+m' = s'+k', so:

(r+r')+(m+m') = (r+m)+(r'+m') = (s+k)+(s'+k') = (s+s')+(k+k'), so (r+r',s+s')~(k+k',m+m').

note that [(n,n)] serves as an identity:

[(k,m)] + [(n,n)] = [(k+n,m+n)] = [(k,m)], since (k+n)+m = (m+n)+k. for a natural number k, we define the integers as:

k = [(k+1,1)]
-k = [(1,k+1)]
0 = [(k,k)]

if one starts with the natural numbers including 0, you can simplify this to:

k = [(k,0)]
-k = [(0,k)]
0 = [(0,0)].

one can go on to define multiplication as:

[(k,m)]*[(k',m')] = [(kk'+mm',km'+k'm)]

for example: [(3,5)]*[(7,4)] = [(21+20,12+35)] = [(41,47)]

which is a fancy way of saying: [(0,2)]*[(3,0)] = [(0,6)], that is (-2)*3 = -6.

it is tedious to verify that this multiplication is also well-defined (that is depends only on the equivalence classes, and not the representatives (k,m)), and distributive over addition, but it can be done.

3. there are various ways of constructing the real numbers. the easiest to see R as a subset of P(Q), is to use dedekind cuts (a cut is a partition of Q into two subsets, every element of one set is less than every element of the other).

it is convenient just to consider "one side" of the cuts, usually the left side. it is also convenient to stipulate that the left cut have no greatest member, such as:

{x in Q: x < 2}.

cuts whose complements in Q have a smallest number are called rational numbers, cuts whose complements in Q have no smallest member are called irrational numbers. this definition takes some getting used to.

another way to define the reals is as "infinite decimals". this is a three-part process:

a) first we define the integer part. since integers are rational, this can be regarded as "the first element of a set of rational numbers that defines a real"

b) next, we define "the decimal part". this is a real number between 0 and 1 (we "copy this structure" in-between integers). specifically, we create a sequence of rationals:

$\displaystyle \left\{\frac{a_1}{10},\frac{a_2}{100},\dots\frac{a _k}{10^k},\dots\right\}$

c) finally, we state that sequences that end in an infinite strings of 9's are equivalent to the same sequence before the first 9 of the infinite string, except that the last non-9 digit is increased by 1. so, for example:

0.239999999999..... = 0.2400000000..... = 0.24

and that sequences which end in an infinite string of 0's are equivalent to a finite string with the trailing 0's omitted. there are several difficulties associated with using this definition, most notable of which is the impossibility of defining arithmetical operations, for example:

0.1235038926..... + 0.8764961073..... = ???? if there is no rhyme or reason to the digits, we may never know when to stop "carrying the 1", so we cannot even compute the FIRST digit past the decimal. nevertheless, we can "approximately" add and multiply.

another common construction of real numbers is as equivalence classes of rational cauchy sequences. each sequence is a collection of rational numbers, so is an element of P(Q). in all fairness, this is actually a partition of a distinguished subset of P(Q), but i do believe you get the idea: we are talking about a subset of QN, which is "roughly" the same size as P(Q), there is a theorem which goes:

|P(Q)| ≤ |QN| ≤ |P(Q)|

(actually the theorem is, for the set of functions from A to B, which has cardinality |B||A|, that if one of A or B is infinite:

max(|B|,|P(A)|) ≤ |B||A| ≤ max(|P(A)|,|P(B)|) but if A = N, the natural numbers, and B = Q, the rationals, then |Q| < |P(Q)|, and |P(N)| = |P(Q)|.

a sequence of rational numbers is, after all, just a function f:N-->Q).

ironically, irrational numbers are "hard to get a hold of", even though they out-number the rationals by a LOT. the main reason for this, is that every way we can think of to define one can be stored as a finite algorithm, and the set of all possible algorithms we can devise is at best, countably infinite. imagine you are told you can do "anything you want to". well, you may have uncountably infinite choices, but as soon as you pick one, you've drastically reduced the possibilities. ultimately though, most of this has no practical bearing on the math we actually DO, we don't do "all the math that's possible" just what we can see through the key-hole.
• Jan 26th 2013, 10:04 AM
jojo7777777
Re: power set
Your replies are precious to my understanding...Thank you very much!