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


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


Jason Gross


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}$~$$