4 ms·
Well that fear is good because multiplication won't change the cardinality, you have to go exponential.
by Dylan16807 4y ago
Well that fear is good because multiplication won't change the cardinality, you have to go exponential.
- smfjaw 4y agoThat effectively does make it exponential x * x === x^2
- ksarw 4y agoby going exponential, they mean 2^x; x^2 can still be the same "size" as x
- NobodyNada 4y agox^2 is not exponential; it's quadratic. 2^x is an example of an exponential function. The parent comment was alluding to the idea of set cardinality (https://en.wikipedia.org/wiki/Cardinality https://en.wikipedia.org/wiki/Cardinality). Two sets have the same cardinality if you can establish a bijection (a one-to-one mapping) between elements of one set and elements of the other. The set of all natural numbers is said to have a "countably infinite" cardinality. It turns out that for any countably infinite set S, the set S x S is also countably infinite (see Hilbert's hotel: https://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel https://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Gra...). For example, the set of 2-tuples of natural numbers (1, 1), (1, 2), (1, 3), ..., (2, 1), (2, 2), ... is the same size as the set of natural numbers. So in this sense, "endless*endless = endless". Whereas the set of infinitely-long tuples of natural numbers is "uncountably infinite;" it has a cardinality greater than that of the set of natural numbers. Thus, "you have to go exponential"; i.e. "endless^endless".
- danwills 4y agoNot an expert but I thought it needed the 'power set' (set of all subsets) but maybe that's kinda the same as exponentiation in the end?