I don't think having a startIndex and endIndex makes a type automatically countable.
Range has startIndex and endIndex, but 0.5..<1.5 (which is basically the set [0.5, 1.5) in interval notation) isn't countable.
EDIT: 0.5..<1.5 is only one instance of Range<Double>. It would be a better argument to present that Range<Double> models the power set of real numbers, which is uncountable.
Do you want to know the ultimate uncountable type? Here it is:
class Foo { init() {} }
Yep, that's this simple. You can have a set of instances of this type that has any cardinality (assuming you already have a set of that cardinality. For example:
for _ in Irrational.allCases {
Foo()
}
You just created uncountable number of instances of Foo. You might say that it's cheating, and all of them are the same, but each new instance is distinguishable from one another (for example with === or ObjectIdentifier) so they are different instances.
If our machine supports hypertask, that is. Well, it can store infinite bytes, so adding a few more features wouldn't hurt.
Then what you talking about is "size of [Int] with fixed arbitrary number of elements N", not the size of [Int] itself.
By definition, a set S is countable if and only if each member of S can map to a different natural number without running out of all natural numbers, i.e. if there is an injection from S to the ℕ. One reasonable interpretation is that, given an arbitrary member of a countable set, one can figure out what the next member of the same set is. This is because given an arbitrary natural number, one can always find the next natural number. If this interpretation is correct, then we can define a Countable protocol like this:
protocol Countable {
var next: Self { get }
}
If a type is countable, then it must be able to conform to this protocol. For example,
extension Int: Countable {
var next: Self { self + 1 }
}
extension Void: Countable { // Let's pretend that void can be extended
var next: Self { () }
// There is only 1 possible value,
// so we can just map all natural numbers to the same value.
}
With the exception of Never:
extension Never: Countable {
var next: Never { fatalError() }
// This is the edge case.
// Never is basically an empty set.
}
I'm not sure if this Countable protocol is fool-proof, or if it adds much to the discussion, but hopefully in some way it helps clarify things.
As I've shown above, [Int] size is at least not smaller than the size of Double, that's proven (I've found a subset of String and [Int] with 1 to 1 correspondence to every member of Double). You saying that Double is uncountable and [Int] is countable, but countable is strictly smaller than uncountable, that's a contradiction. So, either Double is countable (finite memory case) or [Int] is uncountable (infinite memory case).
All types are countable sets, even on theoretical machines with infinite memory. Types are inhabited only by values that can be produced by some program, and there are countably infinite such programs.
Whether a type is enumerable by some program is a totally different question.
As amusing as this thread seems to have become, mind if I ask how any of it is of practical use? What actually prompted the question in the first place? @wowbagger, when you asked it, were you trying to design some API or functionality when this came up? Was it some sort of homework question or academic challenge? Or is it really just pure abstract mathematical curiosity?
If you were actually hoping for help with something (the point of the “Using Swift” category), then please share more of what it is you are trying to solve, so that we can get back to trying to help you with the underlying issue.
This would be the set of all finite sequences of integers, which is still countable, no? Just like there are no infinitely long Strings, there are no infinitely long Arrays.
Def not the only one.
It was a combination of API design and curiosity.
I was trying to calculate degrees of separation between values of Strideable types, and realised it would only make sense if the values are in a subset of a countable set. I could define degrees of separation between values of BinaryInteger types, and not any other types, so I got curious in general.
I didn't expect this thread to get this long, to be honest.
The union you wrote is only a union of finite subsets of the naturals. For instance, {2, 4, 6, 8, ...} is not contained in any of the terms of the union, but it is contained in the power set. Same goes for any infinite subset of the naturals.
Hi,
I was interpreting the original idea for degrees of separation as solving for the number of T.Stride between a start and an end.
Binary integers have an intrinsic stride of 1, so it’s easy to use that.
For IEEE floats, the distance between each value varies depending where on the number line you are—the intrinsic stride between valid values is less near 0 and more out near the positive and negative ends. I might have misunderstood.
I feel like there is probably a way to characterize the IEEE float distance between two floats, but it would be a function, not a number, or something like the ratio between the density of the number line at one point and the density of the number line at the other point, scaled by the floating point distance.
But maybe I’m misunderstanding what you meant and stating the obvious, that happens a lot to me.
—Dan
This is exactly what I wanted to do at first.
For floating point values, I completely ignored the IEEE standard. I treated them as truncated real numbers, which is what all floating point types intended to model (imprecisely). I think there is also the problem that a number can have multiple equivalent representations, if taking the IEEE standard into account. For example, 0.3 can be represented as 3×10⁻¹, 30×⁻², 300×10⁻³, and so on.
IIRC, that's only true for ±0, and the family of NaN.
Also, we have greatestFiniteMagnitude and nextDown, sooo...
You're right, restricting String and [Int] to finite length does make sense. My reasonings are based on assumption that it can be infinite, but that probably is not true 
The diagonal argument is about an infinite sequence of infinite sequences of bits. A single infinite sequence of bits is countable, like naturals are.