Is the cardinality of the set of numbers between 0 and 1 greater than aleph null?

[wind moat]

So I understand that for an infinite set to be countable it must correspond one to one with the set of natural numbers. But it doesn’t seem like this is the case with the infinity between 0 and 1. We can consider 0.1 to be the first, 0.01 the second, 0.001 the third and so on, but then we never get to 0.11, 0.2, 0.12, etc.

[obsidian leaf]

1. Wait patiently for a helper to come along.
2. Once someone helps you, say thank you and close the thread with:

+close

3. Feel free to nominate the person for helper of the week in #helper-nominations

[wind moat]

Is the cardinality of the set of numbers between 0 and 1 greater than aleph null?

[normal yacht]

Well, consider f(x) = (2x - 1)/√(1 - (2x - 1)^2). It bijectively maps the numbers in the interval (0, 1) to real numbers. That should tell you what the cardinality of (0, 1) is.

(and of any other interval, really)

[wind moat]

Never thought about it this way but it makes more sense now

[normal yacht]

It's a good way to compare cardinalities.
If you can make a bijection between two sets, then their cardinality is the same.

[rancid geyser]

note that a function from the naturals to a strict subset of some set doesn't prove it's uncountably infinite

ex. N -> P

[mortal cape]

@wind moat Hi! I'm glad the above answer shed a bit of light! However, if one wants to be a tad bit pedantic, the above answer by LordDarpinger shows that (0,1) has the same cardinality as the real numbers, but does not necessarily show why this must be strictly larger than the cardinality of the natural numbers. Are you familiar with this argument? If so, great, that should answer your question! If not, I'd be happy to help you explore some ideas that might perhaps lead you to a proof of that (or I can tell you the proof if you'd prefer that, though the former does allow for some room for improvement in problem solving!)

[wind moat]

A proof of why the cardinality of the real numbers are larger than natural numbers?

[mortal cape]

Yup!

A priori, we don't know that they have different cardinalities until proven

(as a note, the proof is not terribly difficult, but pedagogically speaking this fact should not be assumed without knowing such a proof)

[wind moat]

Yea sure, what’s the thought process?

[mortal cape]

so i think intuitively, you perhaps can see that this is true. Could you vocalize some of the reason for why you might think this?

[wind moat]

Basically my reasoning in the original comment at the top

[mortal cape]

So you are on the right path with your aforementioned comment, but an issue here is that you've only picked one counting and showed it didn't work. One could similarly argue that the cartesian product of the natural numbers with itself is NOT countable because you can try (1,1), (1,2), (1,3) etc etc, and you'd never get to (2,1)

However, we know that this cartesian product should be countable, because we CAN pick a way to count these, it just might not have been our first thought

So this leads us to the next part of our thought process:

"To show that the real numbers form an infinite set that is NOT countably infinite, we have to somehow show that no matter how we count, we reach a contradiction"

How would we proceed from here?

In other words, if we know that our proof has to work for an arbitrary method of counting, what do you think our starting point should be?

[wind moat]

There’s a lot here for me to unpack. What would be the way of counting the Cartesian product of natural numbers?

[mortal cape]

No worries! Sorry if I kinda rushed ahead

Can I assume that you know what the Cartesian product of N with itself is?

[wind moat]

It’s fine. I’m glad that you’re willing to help. Isn’t just all possible ordered pairs (a, b) of the natural numbers?

[mortal cape]

yes exactly!

now let me perhaps provide a visual of this set

Now, behold my perfect artistic skills matched by no man

so now that we can kinda visualize/organize this entire set, we can rephrase the question of "is this countable" somewhat differently!

we can look at this and say "ok, can i point to these elements can count them off one by one in a pattern that is both infinitely repetitive/reasonable, while still being able to hit every number"

so essentially, from my previous example a few minutes ago, if we tried to "count" these by saying (1,1) is first, (1,2) is second, (1,3) is third, and sso on and so forth

this is a pattern thats infinitely repetitive, but we would never "count" up to (2,1) since we'd just keep going on infinitely in the first row and never stop

so far so good?

[wind moat]

Yea if you count in a zig zag pattern it seems to work

[mortal cape]

exactly!!

thats what shows that this set is countable

this means, more explicitly, that perhaps theres a way to "formalize" what you just said as an actual function from the natural numbers to this set!

because what you've just given me is a way to be like "if i give you a natural number, can you tell me which element it corresponds to?"

for example if i randomly picked the natural number 9, you have a way of counting it off in the zig zag you mentioned, and giving me the 9th element

that's a function, and it turns out to be a bijective! (Not hard to see why it's bijective, but perhaps this might be a good thought exercise)

So we now see how we can check if something is countable!

I am unsure if you are familiar with quantifiers, but essentially, recall that a definition of a set S being countable is as follows:

S is countably infinite if there exists a function f:N---> S such that f is a bijection

and so, if we want to claim that the real numbers are NOT such a set, we would have to prove the negation!

In other words, we need to prove that "For every function f : N---> R, f is not a bijection"

I'll pause here to give you a chance to comment/digest!

[wind moat]

What’s the ‘:’? I’m reading this as “A function f such that N entails S”.

[mortal cape]

the colon is part of a conventional way to define functions

a function has a domain and a codomain, and so

if X and Y are sets, and X is the domain of the function, with Y being the codomain, we can represent the function by writing f: X--> Y

this is technically needed as part of the definition of a function!

For instance, if i simply wrote f(x)=2x, this is actually not a well-defined function

The domain could be all real numbers (as it usually is), or it could be the natural numbers, or even some finite set!

[wind moat]

Is codomain just a subset of the domain?

[mortal cape]

it's not actually!

Let me perhaps take another step back to make sure we're on the same page for functions

First, how familiar are you with quantifiers?

(Apologies, I do not know the courses with which you have familiarity in terms of being completely mathematically precise)

[wind moat]

I’ve only really used them in a logical sense. Like ∀, ∃, □, ◇…

[mortal cape]

great! Can I assume familiarity with those?

[wind moat]

Yea

[mortal cape]

ok fantastic

lemme get on my PC real quick so I can type some stuff out

I'm new to the server and unsure if it has a LaTeX bot

[rancid geyser]

we love the latex bot

[mortal cape]

While I do that, I want to first either introduce or recall a quick definition.

If A is a set, we can define a "relation on A" as a subset of A x A

Bringing this further, if A and B are sets, we can define a "relation from A to B" as a subset of A x B

[rancid geyser]

(hate the latex bot)

[mortal cape]

oh fantastic! ty @rancid geyser

We say that for any 2 sets A and B, a relation f from A to B is a function if:

[reef ridge]

luddeus

[mortal cape]

(As a reminder just in case of unfamiliarity, the ! means unique)

Within this definition, we then define A to be the domain of the function f, and B to be the codomain of f

let me know if I'm still making sense!

[wind moat]

I’m pretty sure I’m following so far

[mortal cape]

ok great! so essentially, the codomain need not be a subset of the domain, but can be an entirely unrelated set

it's essentially just where your outputs of the function are

for instance, I can construct the set X={Alice, Bob, Charlie} and Y={Red, Blue, Green} and I can just get a function f: X---> Y

where f(Alice)= Red, f(Bob) = Blue, and f(Charlie) = Green, and this is a perfectly valid function!

so in our original case, the idea is we want to investigate ALL possible functions f: N---> R, where N is the set of natural numbers, and R is the set of real numbers, and ask the question of "can i show why this can NEVER be a bijection"

and so here, problem solving techniques kind of hint that if i need to show something for EVERY possible iteration, this means I can pick an arbitrary iteration and this should work!

So what does this mean?

Well to formalize, this then gives us the start of a proof!

Let f:N--> R be a function from N to R. What does this mean? Well, it means that f(1) is a real number, f(2) is a real number, and so on and so forth```

So far so good? @wind moat Let me know if you want more clarification on the process itself or if you'd just like me to continue! I'm totally cool with w/e you prefer, but I definitely don't wanna take the lazy route and just reveal the solution if you want to explore this as well without knowing the answer 🙂

[wind moat]

How does “f:N—>R” read? I’m understanding it but I don’t know how to articulate it. “f(x)” would just be “f of x” for example. I did a quick Google search because it seems like codomain is just range but it seems there’s a minor difference.

[mortal cape]

there's a fairly distinct difference, but this comes from just "definining" things a certain way

we haven't technically defined range yet in the above statements!

so all we know now is what the codomain is

range is techncially a name given for something else that we would say is the "image of the domain"

The notation "f:N---> R" can be read as "f is a function from N to R" but really, it is simply notation and the definition given above is complete, and tells you what this is!

One thing to realize in math is that to really be mathematically precise about anything, we have to provide formal definitions, and these definitions can be used to provide notation that could honestly be whatever you want! That being said, there are standard conventions that help with readability, this being one of those conventions

so for example, in calculus courses, pretty much every function you are talking about is a function from R to R, but you never explicitly say this

So if I want to talk about the function f(x)=2x, I technically have to define it as follows, given the above definition:

$\text{Let} f:\mathbb{R}\rightarrow\mathbb{R}\text{ such that } \forall x\in\mathbb{R},\ (x,2x)\in f$

[reef ridge]

luddeus

[mortal cape]

This might not LOOK like standard notation for a function, but this is simply because of the definition we provided for "what a function is" above, and when you normally say "f(x)=2x", this statement above is technically what you mean!

[wind moat]

Yea this makes sense

[mortal cape]

I know we're a bit off topic, but just to close up a minithread you opened, the image is defined as:

$\text{Let X and Y be sets. Let }f:X\rightarrow Y \text{ be a function. Let } S\subseteq X\ Im(S):={f(x):\ x\in S}$

oh sorry one sec im being a bit dense atm

[reef ridge]

luddeus

[mortal cape]

In other words, if you take all the elements of S, "plug it in" to the function f, and collect all the outputs into a set, what you get is the image

the range is then the image of the domain!

so for example, we can construct a function f:R---> R, where f(x)=x^2

The codomain is R, simply by definition

However, the range is [0. infinity), not R, and so the range is not the codomain

But I digress a bit! Lemme know if everything makes sense, though, and if so we can go back to the original discussion 🙂

[wind moat]

I’m caught up now.

[mortal cape]

ok great!

So let's go back to where we stopped off earlier. We now go back to the following

Let f:N--> R be a function from N to R. What does this mean? Well, it means that f(1) is a real number, f(2) is a real number, and so on and so forth```

In fact, we can make this even easier, let's just talk about the set (0,1) !

You showed earlier that (0,1) and R have the same cardinality, so lets take a function from f:N---> (0,1) instead, if thats ok!

(totally arbitrary, the argument is just a lot simpler if you use the set (0,1), and you've already shown this has the same cardinality as R

So we modify the above slightly

Let f:N--> (0,1) be a function from N to R. What does this mean? Well, it means that f(1) is in (0,1), f(2) is in (0,1), etc etc```

[wind moat]

Wait what do you mean here? Wouldn’t the elements of (0,1) be ‘{}, {0}, {1}’?

[mortal cape]

no, that would be {0,1}

By (0,1) from the original post, you mean the open interval from 0 to 1

which is

[wind moat]

Oh

Ok

Makes sense

[reef ridge]

luddeus

[mortal cape]

{0,1} is a finite set with 2 elements, so it wouldn't play into the discussion, as finiteness is in its own little category!

But by this, any number is (0,1) we know can be written by its decimal expansion in base 10 as, for example, something like

0.12345, or 0.34234238, or 0.42349283429348124124109241024124019....

there might even be infinitely many digits

but they coudl be anything of this form, right?

[wind moat]

yea

[mortal cape]

So now, since we know f is some function from N---> (0,1)

lets say, for example

f(1) = 0.234234293419....

f(2)= 0.02934293547`1020...

f(3) = 0.928357629387129384....

f(4) = 0. 3497563945712938759....

and so on and so forth

this goes on for EVERY natural number

but WAIT

lets follow this pattern

let's take the first digit of f(1), the 2nd digit of f(2), the 3rd digit of f(3), and so on and so forth, and let's add 1 to each of this (if it's 9, change it to 0 instead"

lemme draw this rq

and im gonna keep repeating this pattern forever. the result is a real number. Are we agreed here?

[wind moat]

Yea I’m following

[mortal cape]

ok but heres the issue

notice that

based on how I constructed this number, it straight up CANNOT be f(n) for some n

right?

cuz for every n, this number is different from f(n) in the n^th digit!

and notice that no matter WHAT numbers i had picked from f(1), f(2) etc etc etc

same thing holds

so ive found a real number that is NOT an output of any natural number, so this function cannot be surjective, and thus cannot be bijective!

This essentially shows that such a bijection cannot exist between N and (0,1)

and so (0,1) MUST have a cardinality greater than the cardinality of N

[wind moat]

Yea I see now. Going through this makes a lot more sense.

[mortal cape]

If you're curious about this, this is called "Cantor's Diagonalization Argument" in case you wanna look this up on wikipedia or other texts

but I mainly wanted to ping you and mention this because while the previous answer was a true statement, it wasn't t echnically an answer to your question

[rancid geyser]

now prove this is a real number being produced!!!!

/joke

[mortal cape]

ofc great for humour purposes, but technically also a good question mathematically speaking 😉

[wind moat]

I’ll check it out and read tomorrow. I actually need to go right now it’s pretty late for me. Thanks for going through all of this with me. I’ll look more into it tomorrow.

[mortal cape]

Of course! Please feel free to ping or DM if you have further questions!

[mortal cape]

Exercise Left For Student

😉

[wind moat]

Wouldn’t it just be a real number simply from it not being imaginary

[rancid geyser]

there are some processes which seem to produce real numbers but actually don't

hackenbush, for example,

you can assign values to things but you end up having to assign values that are not real numbers (nor complex numbers)

that is my understanding at least

very minimal understanding

[mortal cape]

Hackenbush only results in things that aren't complex if you start with inputs that already aren't complex

I'm not quite sure what you mean by processes that seem to produce real numbers but dont

[mortal cape]

There are ideas of values that are neither real nor complex (although we mostly work with complex numbers, and real numbers are just a subset of complex numbers)

But that would not apply here

You have to specifically construct such sets to be able to use them

[unique quartz]

I assume they're referring to the surreal numbers

[rancid geyser]

yis

[unique quartz]

If you assign a value to (finite) positions of blue-red Hackenbush such that a single blue stalk has value 1, a single red stalk value -1, and the value of combining two positions is the sum of the values of the positions, you end up assigning a dyadic rational (fraction with a denominator of 2ⁿ for some n) to each position such that the number is positive if blue is winning, negative if red is winning, and zero in equal positions (when the first player to move loses)

Now say you add green stalks, that can be taken by either player; what is the value of a Hackenbush game containing a single green stalk? In such a position, the first player to move wins, so its an equal position and hence can't be positive or negative, but it also can't be 0 (because that's when the first player to move loses)

so we just define a new number "∗" with this property

the result of taking this approach (of defining numbers as the values you can assign to a game state) is a coherent number system called the "surreal numbers"

(we also consider infinitely large Hackenbush games)

[unique quartz]

it's funny I see this mentioned now, because I just got the first book of Winning Ways today