What is the simplest way of proving (to a non-mathematician) that the power set of the set of natural numbers has the same cardinality as the set of the real numbers, i.e. how to construct a bijection from $\mathcal{P}(\mathbb{N})$ to $\mathbb{R}$?
The simplest way of proving that $|\mathcal{P}(\mathbb{N})| = |\mathbb{R}| = c$
13
$\begingroup$
elementary-set-theory
-
4http://en.wikipedia.org/wiki/Continued_fraction – 2012-03-10
-
4It all depends on how mathematical this non-mathematician is. For the less mathematical I honestly think the simplest way would involve using Cantor–Bernstein–Schroeder and phrasing the two halves as "there are no more reals than sets of naturals" and _vice versa_. I think CBS is a theorem that a non-mathematician could be convinced of without too much difficulty; not with anything that would approach mathematical rigour, mind you. Avoiding CBS seems to involve nitty-gritty details that would make the average non-mathematician glassy-eyed, and the heart of the ideas might become lost. – 2012-03-10
-
0I completely agree with Arthur, moreover to the non-mathematician the fact that there are two different sizes of infinity (countable and uncountable) would already make them glassy-eyed and you'd lose them completely. – 2012-03-10
-
0The non-mathematmatician in question is VERY, VERY, VERY MUCH non-mathematical, so that expressions like "arctan (x)" (or even the "tan (x)" itself!) don't shed much of a light to his picture. So I would very much appreciate as little of symbols of any kind as possible - maybe NONE? - and as much convenient "images" as one is capable of providing without reffering to, say, the Bible. Thanks in advance, J. – 2012-03-10
-
0Wrong, Asaf: That there are different sizes of infinity, proven by, say, the diagonal argument, is totaly acceptable, moreover, easy to understand for me. But I do have troubles understanding mathematical symbols and notations. So if there is an explanation that resembles the diagonal agument - which in my eyes is more of a picture than anything else - than that would be the kind of an answer I'm hoping for. – 2012-03-10
-
1@Jan: I am a set theorist. It's not that my research focuses on finding "roots of polynomials" and whatnot. In particular I deal in my M.Sc. with behavior of cardinals in the absence of the axiom of choice. I always enjoy trying explaining those to people, especially other barflies at the local pub. It is *very* baffling to people that there are different sizes of infinity. It is equally baffling when you see it for the first time *with* the full definitions and proofs, people telling you otherwise are likely to lack the actual understanding - and further discussion is just further confusing. – 2012-03-10
-
0Also if you want an under that *you* can understand, this is a **very** different situation than asking "*I have to explain this fact to a bunch of folks in a few days, how should I approach that?*". Mostly because *you* can add to the question what *you* already know and understand on the topic. – 2012-03-10
-
2@Jan Some theorems admit a "proof by picture," where you a give a convincing proof-sketch without actually writing anything down, but most theorems do not have proofs that fall under this category. Something like "There is a bijection between $\mathbb{R}$ and the set of all subsets of $\mathbb{N}$" will almost certainly involve at least a few steps and some non-trivial terminology. That doesn't mean it's complicated (it's just the composition of a few "nice" bijections), it's just not as basic as most ideas encountered in high school. – 2012-03-10
-
0Asaf: Of course, it is ME that is need of a proof. My profession is (german classical) philosophy (mostly Kant and Hegel), but I'm studying Alain Badou now (a french philosopher that talks about ZFC set theory a lot), so I wish to claryfy some basic things. I understand the diagonal argument proving that there is a number that cannot be presented anywhere in the "No infinitely" stretching list of, say, real segments between 0 and 1, etc. but I had another problem: – 2012-03-11
-
0since I was informed, that Cantor could "collect" the set of R only by interpreting it as a power set of N, and since I was also informed that that was his basic motif for the introduction of the "power set" axiom in the first place, I just wanted to know, how can one grasp the mentioned equality without any profound mathematical knowledge - and since the "diagonalization" seemed acceptably cogent to me, I was just wandering if there could be the same case with the equasion of cardinalitys between R and P(N). – 2012-03-11
-
1@Jan: Very good then, you should *edit* the relevant information into the question. What you know and don't know. Sure it is a very general situation right now, and mathematicians strive to solve the most general situation, but first we start with the situation at hand - then we generalize the solution. So please, add the relevant information to the question to reflect that it is *you* who is trying to understand, and not that you need to explain to *someone else*, since you're not mathematically trained I'd consider adding a short list of what you already know about set theory. – 2012-03-11
-
1@Jan: You're studying Badiou?! This might be causing problems later since I know that he also uses the concept of [forcing](http://en.wikipedia.org/wiki/Forcing_%28mathematics%29) in his work (at least in "_Being and Event_", which I guess the original French would be "_L'Être et l'Événement_"). (When I discovered that some philosopher was using set theory in his philosophical work I sought it out, but utterly failed to make sense of it. This is likely due to my lack of any real philosophical background.) – 2012-03-11
-
2@Jan: Diagonal arguments are good for showing that certain things _cannot_ exist (or in rare and subtle cases that things which do exist cannot have certain properties, like the Gödel sentence having a proof). However here you must show that a bijection _does_ exist, so a diagonal argument won't be of avail. Also for technical reasons (as ordered sets $\mathbb R$ and $\mathcal{P}(\mathbb N)$ have fundamentally different properties), such a bijection cannot be entirely "smooth". Which explains what an effortless proof is not possible. – 2012-03-11
-
0@Artur Fischer: I'm not worrying about the "forcing" too much since Badiou explains the general idea in farly siple terms. But the bijection I'm asking for is not explained there so I was simply qurious: If the P(N) is the most obvious way to mathematically discribe the continuum in terms of exemplifying it by N numbers, how can this be done in terms understandable to a non-mathematician, i.e. to me. – 2012-03-11
-
0If you just want to describe $\mathbb{R}$ in terms of $\mathbb{N}$ then it's a COMPLETELY different question. – 2012-03-11
-
0@you: I realy think that such a "describing of R in terms of N" (although I would prefer describing it in terms of P(N)) would be of a great help to me. Could You do it here or should I formulate this as a seperate question? Thanks, J. – 2012-03-12
-
0I can give you a brief description in a comment and see if it's what you're looking for. It's kind of a "call and anser" story. In $\mathbb{N}$, one problem is that most numbers don't have negatives. we fix that with the integers $\mathbb{Z}$, which could be thought of as the smallest set containing $\mathbb{N}$ and the negatives. The next problem is that we don't have inverses: the rationals $\mathbb{Q]$ fix that problem, and can be thought of as the smallest algebraic structure containing $\mathbb{N}$, all it's negatives, and all of the inverses. The final problem is that (continued) – 2012-03-12
-
0$\mathbb{Q}$ still has gaps: numbers like $\sqrt{2}$ and $\pi$ are not in $\mathbb{Q}$, even though we can find rational numbers arbitrarily close to them. In some sense $\mathbb{R}$ is the smallest set containing $\mathbb{Q}$ and all the numbers that can be "approximated in $\mathbb{Q}$". The technical details in rigorously defining $\mathbb{R}$ from $\mathbb{Q}$ are subtle, and probably difficult for high-school level. This is what _I_ think when I hear "describe the continuum in terms of $\mathbb{N}$," maybe not what you meant. – 2012-03-12
-
0@you: Okay, this inclusions of N into Z, Z into Q and of Q (by approximatization) into R, where R is the first uncountable set (of this roe) is quite clear, thanks. But is it possible to do something simmilar with P(N)? To precisize myself: is it possible to intuitively explain why the uncountability of P(N) is not "bigger" nor "smaller" than the uncountability of R? (see cont.) – 2012-03-12
-
0(cont.) Or by putting the question in historical terms: why did Cantor choose the P(N) - and not, say, just some other set - to compare it to R in the first place? What is it about the P(N), that makes it so appealing to make one starting to prove the bijection in question by it? What is it, that makes one (intuitevily) say: "I want to show just how big the R is - so, heck, why don't I just take the P(N) and start from here?!" I hope that the question is now clear enough. – 2012-03-12
-
0Well, by the diagonalization argument we know that $\mathbb{R}$ is "larger" than $\mathbb{N}$, and an argument similar to Russel's Paradox tells us that $\mathcal{P}(\mathbb{N})$ ALSO "larger" than $\mathbb{N}$. So why not compare these two objects? – 2012-03-12
-
0@you: Well, that is what I do know, and the means for showing it are simple enough (1. to get a hold on the diagonalisation argument is realy easy, and 2. the set of all the "outer" (not-contained) representations of P(N) in N cannot have an adquate representation in N); okay. But are there similar nonmathematical means to show that both of these uncountable infinities are of the "same size"? – 2012-03-12
-
0The standard ways of showing that two sets $A$ and $B$ have the "same size" are 1)give a bijection between $A$ and $B$, and 2) Schroeder-Bernstein theorem, which says "$|A|\leq |B|$ and $|B|\leq|A|$ $\implies\ |A|=|B|$", or in other words it suffices to give one-to-one maps both ways or onto maps both ways. If you would like a nonmathematical way of showing two uncountably infinite sets have the same size, I ask: what do "uncountable" and "same size" mean, nonmathematically? – 2012-03-12
-
0Khmmm, I'd say you've got a point there... Well, I was wandering if one could go one in pretty much the same way as with the proofs provides for the notions, applied with 1. ("uncountability") the (non-)relation between R and N, shown by the diagonalization, and 2., ("same size") one-to-one correspondence between the natural and even (or odd, or squared, etc.) numbers... All in all I'd say that it was exactly this supposition that drowe me in posing the question in the first place. (see cont.) – 2012-03-13
-
0(cont.) But since: 1., no argument of this (realy simple) kind was provided in this site (although there were some nice tries), 2. Marc van Leeuwen (see above) stated that "ordered sets R and P(N) have fundamentally different properties", and 3. I belive You, mathematicians, - I guess finally, the answer to my question would be that it is simply PRINCIPALLY IMPOSSIBLE to demonstrate such an answer in a manner that could be as simple as showing the correspondence of N to one of its subsets (i.e. evens, odds, etc.)? (see cont.) – 2012-03-13
-
0(cont.) But still further on: since, 1., N cannot be put into the one-to-one correspondence with EACH of it's subsets - i.e. at least not with those that are self-referential (the set of all the "outer" (not-contained) representations of P(N) in N cannot have an adquate representation in N) -, since 2., the diagonal arg. is basically of the same (self-referential) kind, and 3., since both of these arguments combined show ONLY that both P(N) and R are non-countable, but not that they are of the same size: (see cont.) – 2012-03-13
-
0(cont.): Then, finaly, I guess the main argument for the impossibility of the intuitive answer to my question would be that there just ain't no way to intuitively grasp still larger incountable set as R (implied that diagonalization counts as intuitive enough to devide the cardinalities of N and R), thus showing the way to divide it from the uncountability of R (and of P(N)). Or is there? – 2012-03-13
-
0First let me remark that there is a simple way to show that every infinite subset of $\mathbb N$ can be put in one-to-one correspondence with $\mathbb N$. Each and every one of them. It can also be shown that $\mathbb N$ cannot be bijected with its *power set*. These two are not very difficult to see and understand. I have to admit that I have absolutely no idea what does that mean for a set to be "self referential" and what is "the set of all the 'outer' representations of P(N) in N". – 2012-03-13
-
0I also have to say that if you plan on making set theory based arguments without studying some set theory first... well, that's just wrong in so many levels. – 2012-03-13