[ home ] [ math / cs / ai / phy / as / chem / bio / geo ] [ civ / aero / mech / ee / hdl / os / dev / web / app / sys / net / sec ] [ med / fin / psy / soc / his / lit / lin / phi / arch ] [ off / vg / jp / 2hu / tc / ts / adv / hr / meta / tex ] [ chat ] [ wiki ]

/math/ - Mathematics

[ Post a reply ]

Name
Email
Subject	Preview Post
Comment
Preview
Verification	Instructions: Press the Get Captcha button to get a new captcha Find the correct answer and type the key in TYPE CAPTCHA HERE Press the Publish button to make a post Incorrect answer to the captcha will result in an immediate ban.
File
Password	(For file deletion.)


25 Dec 2021	Mathchan is launched into public

3 / 1 / 3 / ?

File: ‎image_two_grids.jpeg ( 318.43 KB , 1920x1080 , 1693178750553.jpeg )

Listing all k-tuples! aether_1729 August 27, 2023 (Sun) 23:25:54 No. 481

Do you know of any interesting ways to list all possible

k

-tuples of nonnegative integers in order? Or in other words, do you know a function

f(n)

such that for every

(a, b)

with integers

a, b \ge 0

, there exists an

n \ge 0

with

f(n) = (a, b)

? Well, I do! I'll be showing my way.

First you create a grid with two axes which you start numbering starting at 0. The square in the

p

th row and

q

th column will have the tuple

(p - 1, q - 1) = (a, b)

. Not

(n, m)

because we start at 0. Now, we draw a line that connects the squares like in the left grid of the image attached (translucent, red line). The line creates this one-dimensional sequence of 2-tuples:

(0, 0) \rightarrow (0, 1) \rightarrow (1, 0) \rightarrow (2, 0) \rightarrow (1, 1) \rightarrow (0, 2) \rightarrow (0, 3) \rightarrow (1, 2) \rightarrow (2, 1) \rightarrow (3, 0) \rightarrow (4, 0) \rightarrow \dots

You should notice the pattern. Like that, I've listed all 2-tuples.

We define

f_k(n)

as our function that maps

\lbrace 0, 1, 2, \ldots \rbrace

to the set of all

k

-tuples of nonnegative integers.

We can extend this to 3-tuples. But without using a 3-dimensional grid. We make a similar grid (right side of image), this time the upper axis is for the third element in the tuple and the left axis is just the sequence of 2-tuples I listed before for the 1st and 2nd elements of the 3-tuple.

Using that method, we get this for

k = 3

f_3(0) = (0, 0, 0)\\ f_3(1) = (0, 0, 1)\\ f_3(2) = (0, 1, 0)\\ f_3(3) = (1, 0, 0)\\ f_3(4) = (0, 1, 1)\\ f_3(5) = (0, 0, 2)\\ \ \ \ \vdots

A slightly less intuitive pattern...

Of course, you can generalize this method to get the formula:

f_{k+1}(n) = f_k(b(n)) \cup s(n)

. The union symbol is used here to append

s(n)

to to the

k

-tuple

f_k(b(n))

b(n)

refers to the first element of

f_2(n)

and

s(n)

refers to the second. Also, it isn't particularly hard to prove that these functions indeed do return every possible tuple.

I find this formula beautiful. Correct me in case you find mistakes!

Anonymous August 28, 2023 (Mon) 09:33:50 No. 483 >>484

This method is the same for demonstrating the numerability of rational numbers, but it presents a mistake.
I explain it. Natural numbers are defined by Peano's axioms, actually they are defined for recursion (second axiom), i.e. 7 does not exist without 6.
In first black line of the table you have already the naturals in order.
Now if we stop this method in some numbers, we'll see that it exist a number but the inferior number does not exist yet. e.g. If we stop in (1,1), we'll have (2,0)=(1,0,0)>(1,1)=(0,1,1)
The same is true in numerability, if we stop in 2/3, we'll have defined 1/4 without 4, but rationals are defined by naturals.

aether_1729 August 28, 2023 (Mon) 11:01:04 No. 484 >>485

>>483 I know that a similar method is used to prove that the set of rationals and naturals have the same cardinality except you remove all the duplicates. But I'm not quite sure what you mean by

(2, 0) = (1, 0, 0) > (1, 1) = (0, 1, 1)

. Could you elaborate?

Anonymous August 28, 2023 (Mon) 11:51:42 No. 485

>>484
Of course, you ask to us: "Do you know of any interesting waves to list all possible k-tuples of possible nonnegative integers in order?" In effect it exists, it is sufficient to change the base of natural numbers. e.g. For k-tuple in base two until

f(2^k-1)

you have the k-tuple in order f(0))(0,...,0,0,0), f(1)=(0,...,0,0,1), f(2)=(0,...,0,1,0), f(3)=(0,...,0,1,1), f(4)=(0,...,1,0,0), f(5)=(0,...,1,0,1), etc here you can see that (1,0,0)>(0,1,1) where a>b means a comes after b.
If, otherwise, you fixed k and you need numbers bigger than

f(2^k -1)

you can change base into base n for number until

f(n^k -1)

. e.g. k=2, number until f(125), n≥12 you obtain: (for n=12) f(0)=(0,0), f(1)=(0,1), f(2)=(0,2), f(3)=(0,3),..., f(10)=(0, A), f(11)=(0, B), f(12)=(1,0), f(13)=(1,1), f(14)=(1,2),...,f(125)=(A,5)

3 / 1 / 3 / ?