"Nice! I've never seen an ex..."

https://arbital.com/p/2wt

by Alexei Andreev Mar 27 2016


Nice! I've never seen an example like this before, and it's actually kind of surprising. It seems to imply that 2^N is qualitatively different than N or N^2, but I'm not sure how to phrase it. (And I wonder if there is a relationship between that and P=NP problem.)


Comments

Jason Gross

Thanks!

A^B is the set of functions from B to A. So 2^N is powerset of N (a function f from N to {0, 1} says, for each element of N, whether or not that element is in the subset defined by f), which is isomorphic to the reals. Perhaps this should go somewhere in one or more of the versions. I don't know any connection between this and P=NP (although I suppose it could be behind the exponential bounds on various things).

Patrick Stevens

A summary of the relevant cardinal arithmetic, by the way (in the presence of choice): $$~$\aleph_{\alpha} + \aleph_{\alpha} = \aleph_{\alpha} = \aleph_{\alpha} \aleph_{\alpha}$~$$ while $$~$2^{\aleph_{\alpha}} > \aleph_{\alpha}$~$$