Countable types

wowbagger · 2020-08-26T15:16:41.425Z

Adding to the list, Void (1 possible value) and Never (0 possible value) are countable.

zienag · 2020-08-26T16:41:01.270Z

wtedst:

likewise, all tuples and arrays of integers or enumerations are countable — even if you assume them to be infinitely large,

all strings are countable because they are a countable array of characters from a countable alphabet,

wtedst:

So the only ones that aren't are those that have a Float or a Double within them

Nope.

Those are contradictory statement. Simple rule can be imagined to correspond every real number to array of integer or string:

12.345678....
[1, 2, -1, 3, 4, 5, 6, 7, 8, ...]
"12.345678..."

So, the size of [Int] or String is at least not less than the size of Double. If size of Double is already uncountable, so the size of [Int] and String are uncountable too.

cukr · 2020-08-26T17:10:06.594Z

There is a lot of confusion, because some people say Foo when they mean an instance of Foo, and some people say Foo when they mean a set of all of the possible instances of Foo

wowbagger · 2020-08-26T17:26:24.348Z

wtedst:

by having a startIndex and endIndex

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.

cukr · 2020-08-26T17:52:09.864Z

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.

Lantua · 2020-08-26T17:56:59.462Z

cukr:

You just created uncountable number of instances of Foo .

If our machine supports hypertask, that is. Well, it can store infinite bytes, so adding a few more features wouldn't hurt.

zienag · 2020-08-26T18:19:33.970Z

Then what you talking about is "size of [Int] with fixed arbitrary number of elements N", not the size of [Int] itself.

wowbagger · 2020-08-26T18:31:28.003Z

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.

zienag · 2020-08-26T18:42:26.967Z

wtedst:

That is, [Int] and String form a countable set of values even on a computer with infinite memory by having a startIndex and endIndex , for instance

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

John_McCall · 2020-08-26T19:22:53.517Z

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.

SDGGiesbrecht · 2020-08-26T19:46:09.378Z

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.

Jumhyn · 2020-08-26T19:47:11.158Z

wtedst:

The same talk goes about [Int] — if you let Int itself be infinitely large and you have no upper bound on the length of the array, then [Int] actually does model the power set of natural numbers, which is uncountable.

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.

Lantua · 2020-08-26T19:47:22.654Z

wtedst:

I'm curious of other people find this thread super funny because this whole discussion is very mathematically imprecise, so whatever we are doing here makes very little sense without much stricter definitions

Def not the only one.

wowbagger · 2020-08-26T19:52:37.713Z

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.

Jumhyn · 2020-08-26T20:06:57.699Z

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.

dfsweeney · 2020-08-26T20:09:26.000Z

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

wowbagger · 2020-08-26T20:30:30.006Z

dfsweeney:

I was interpreting the original idea for degrees of separation as solving for the number of T.Stride between a start and an end.

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.

Lantua · 2020-08-27T00:04:19.058Z

wowbagger:

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⁻³

IIRC, that's only true for ±0, and the family of NaN.

Also, we have greatestFiniteMagnitude and nextDown, sooo...

zienag · 2020-08-27T10:07:26.123Z

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

salutis · 2020-08-30T21:20:27.871Z

wowbagger:

I believe an infinite sequence of bits is uncountable, as per Cantor's diagonal argument.

The diagonal argument is about an infinite sequence of infinite sequences of bits. A single infinite sequence of bits is countable, like naturals are.