Infinitely infinitely many is still infinitely many. N x N has the same cardinality as N. Now if you meant N ^ N then that's actually different. "x" means set product and "^" means function space.

This isn't about cardinality, though, this is about number of steps, which is more properly measured with ordinal numbers. I'm not familiar with the theory of infinite-time Turing machines, but it's at least plausible that there are things you can do with omega^2 steps (or larger countable ordinals) that you couldn't do with only omega steps.

omega == omega^2. They are the same quantity. For every element of omega^2, there is a corresponding unique element of omega.

Actually, no. I just recently read about this.

1 + omega == omega < omega + 1 < omega^2

http://en.wikipedia.org/wiki/Ordinal_number

Weird! Thanks for the link!

Actually you are both right -- omega and omega + 1 (or omega^2) have the same 'number' of elements (there is a one to one correspondence) but the correspondence will not be (can not be) order-preserving. Ordinals are a natural extension of the natural numbers. If you take the natural numbers and add a new element that's bigger than all of them then you get a new structure (called omega + 1) which has the same size as the normal natural numbers, but has one new element which is order-distinguishable from all our normal numbers. Some ordinals, which correspond to a jump in 'size' (like 2^omega) are special and called cardinal numbers.

By N, dkarapetyan presumably means the set of natural numbers, or aleph_0. So it isn't aleph_1. That said, it is also true that aleph_1 x aleph_1 = aleph_1. More generally, any aleph_alpha x aleph_alpha = aleph_alpha, for any ordinal alpha; and if we assume the axiom of choice, then any infinite cardinal A can be written as some aleph_alpha, and hence satisfies A x A = A.

However, ultimately none of this is relevant; number of steps is properly measured with ordinals, not cardinals.