What is the Collatz Problem and how can it be solved?

[Organic]

Matt,

It is also can be written as: {10... ,1100... ,11110000... ,...}

... means that each 0 1 starting repeats on itself forever.

 

[matt grime]

But is my characterization equivalent to yours?

 

[Hurkyl]

I think he's looking at the set of columns, and assuming it's obvious that when he writes "..." he means "repeat that string of digits indefinitely"

 

[matt grime]

Originally posted by Organic
Matt,

It is also can be written as: {10... ,1100... ,11110000... ,...}

... means that each 0 1 starting repeats on itself forever.

the array you wrote out - clearly it satisfies every row is eventually 1 continually (ie every entry in row r is 1 after point reading right to left - the point changing as r changes) therefore it corresponds to sets whose complement is finite. The cofinite sets again. now what about them.

 

[matt grime]

I don't understand it. I've proved one diagram corresponds only to the finite subsets, another corresponds only to the cofinite subsets, their union is not the power set, that organic doesn't know the meaning of the terms he uses, as proven by the fact that he thinks it's ok for a bijection not to be injective. what more do i need to do?

 

[Hurkyl]

Matt's talking about the rows, not the columns. I think we all agree there is a bijection between the set of columns and N.

 

[matt grime]

Originally posted by Organic
Matt,

What is finite in {10... ,1100... ,11110000... ,...} set?

I'm not saying anything there is a finite set. it's the same proof as before that you don't understand.

take the row at position r. let us examine what set it corresponds to in the power set.

now the c'th column starts with 2^c 1s doesn't it? that is the pattern of the columns.the c'th entry in row r is the r'th entry in column c. Now, 2^c>c and if c>r we see the r'th entry in column c is a 1.

therefore all entries after the r'th in row r are 1.look at the finite portion of the diagram - notice how everything above the diagonal is a 1? that's just what we've proved above.

and what that tells us is that the element in the power set correspoding to that row r contains every element in N greater than r. thus it's complement only contains some subset of the numbers 1,2,..r.

Sets like this are called cofinite.

This is the same method of proof that shows the other list only contained elements in ther power set that had a finite number of elements in them because there the any row eventually becomes zero by the same argument. thus you've only enumerated the finite and cofinite sets and none of the (uncountable) remaining sets.The cut off point is different in each row but that doesn't matter, which is what i think you thought i meant earlier - that there was a vertical line you could draw in the diagram and all to the left of the vertical line is 0 (or 1) I am not saying that and i don't need to say that.

read the above proof carefully, and try and understand we're just formally stating that everythin above the diagonal is a 1 (in this case and 0 in the other diagram)

 

[matt grime]

also note i am not saying a row is finite, but that a row corresponds to a cofinite (or finite in the old case) element in the power set of N

 

[Organic]

Matt and Hurkyl,

What is finite in {10... ,1100... ,11110000... ,...} set?

This set is bijective to N.

Now, let us go back to look at this set like this:

      3 2 1 0
     2 2 2 2
     ^ ^ ^ ^
     | | | |
     v v v v
[b]{[/b]...,1,1,1,1[b]}[/b] 
 ...,1,1,1,0  
 ...,1,1,0,1  
 ...,1,1,0,0  
 ...,1,0,1,1  
 ...,1,0,1,0  
 ...,1,0,0,1  
 ...,1,0,0,0  
 ...,0,1,1,1  
 ...,0,1,1,0  
 ...,0,1,0,1  
 ...,0,1,0,0  
 ...,0,0,1,1  
 ...,0,0,1,0  
 ...,0,0,0,1  
 ...,0,0,0,0  
 ...

By taking the n-th notation from each member we can build a list of unique sequences which its magnitude=2^aleph0.

 

[matt grime]

n'th notation from what?

did you even bother to try to understand that argument? No i didn't think so.

we aren't saying the set of columns is finite. why would we? have you even read the proof i just offered? attempted to understand what it said? or did you just presume to know it was wrong? It isn't.

 

[Organic]

Matt, if you write this: "n'th notation from what?" it is simply shows us that you did not read carefully what I write to you and to Hurkyl, so here it is again.



{10... ,1100... ,11110000... ,...} set is bijective to N.

By taking the n-th notation from each member we can build a list of unique sequences which its magnitude=2^aleph0:

      3 2 1 0
     2 2 2 2
     ^ ^ ^ ^
     | | | |
     v v v v
[b]{[/b]...,1,1,1,1[b]}[/b] 
 ...,1,1,1,0  
 ...,1,1,0,1  
 ...,1,1,0,0  
 ...,1,0,1,1  
 ...,1,0,1,0  
 ...,1,0,0,1  
 ...,1,0,0,0  
 ...,0,1,1,1  
 ...,0,1,1,0  
 ...,0,1,0,1  
 ...,0,1,0,0  
 ...,0,0,1,1  
 ...,0,0,1,0  
 ...,0,0,0,1  
 ...,0,0,0,0  
 ...

 

[matt grime]

i've read and reread that post and you don't explain what the n'th notation is.

the indvidual words make sense but not when put together like that

what is a notation, what is the nth one? you didn't state what they are.

which members are you taking these notations from? members of rows, columns, power sets, N?

so illuminate it for the stupid round herenow have you actually read my proof that any row in the diagram corresponds to a confinite element of the power set?

we;ve got this diagram enumerating the cofinite sets, what's the point you're trying to make

 

[Organic]

Matt,

First, thank you for reading an rereading.


{10... ,1100... ,11110000... ,...} set is bijective to N.

The n-th notation of each member is:

n-th 1 2 3 . .  1 2 3 . . . .  1 2 3 . . . . . . . .  1 2 3
    {1 0 . . . ,1 1 0 0 . . . ,1 1 1 1 0 0 0 0 . . . ,. . .}

By taking the n-th notation from each member we can build a list of unique sequences which its magnitude=2^aleph0:

      3 2 1 0
     2 2 2 2
     ^ ^ ^ ^
     | | | |
     v v v v
[b]{[/b]...,1,1,1,1[b]}[/b]<--> n-th 1
 ...,1,1,1,0 <--> n-th 2
 ...,1,1,0,1 <--> n-th 3 
 ...,1,1,0,0 <--> n-th 4 
 ...,1,0,1,1 <--> n-th 5 
 ...,1,0,1,0 <--> n-th 6 
 ...,1,0,0,1 <--> n-th 7 
 ...,1,0,0,0 <--> n-th 8 
 ...,0,1,1,1 <--> n-th 9 
 ...,0,1,1,0 <--> n-th 10
 ...,0,1,0,1 <--> n-th 11
 ...,0,1,0,0 <--> n-th 12
 ...,0,0,1,1 <--> n-th 13
 ...,0,0,1,0 <--> n-th 14
 ...,0,0,0,1 <--> n-th 15
 ...,0,0,0,0 <--> n-th 16
 ...

 

[matt grime]

ok got it. you take the n'th element in each column as the elements in the nth row.

That does not give you "2^aleph-0" possibilities, there are exactly as many rows as there are natural numbers. How can you claim that there are 2^aleph-0 rows. Why? What set of cardinality 2^aleph-0 is it in bijection with and how?

 

[Organic]

Matt,

A Binary Tree with infinitely many nodes has a width of magnitude aleph0 and a length of 2^aleph0.

Simple as that.

 

[matt grime]

That would depend on how you defined binary tree - the rooted binary tree with countably infinite branch set has only a countable number of nodes - it is the countable union of finite sets.

Besides that has nothing to do with this issue.

Of course you don't think that binary tree means what it really means.

So what is your binary tree? You seem to think it is a Cantor set. There fore you seem to think that the rows of your matrix are in bijection with a cantor set. How? Please demonstrate? As I can prove that a cantor set is not in bijection with N, that the rows are in bijection with N, don't you think that that is a little problematic. So please exhibit this notional bijection with the Cantor set. Or explicitly state what your binary tree is. This will all involve taking (inverse/direct) limits in the correct sense, but of course you know all about thatedit: and seeing as you don't think there are an uncountable number of points in the real line, don't you think taking an uncountable subset is wrong? It is conceptually impossible in your world, and if you're in mine you need to prove all your assertions.

 

[Hurkyl]

Fun fact.

A (balanced) binary tree with infinitely many nodes has zero leaves.

 

[Organic]

Matt and Hurkyl,

Besides that has nothing to do with this issue (the Binary Tree).

Let us take again our set:

      3 2 1 0
     2 2 2 2
     ^ ^ ^ ^
     | | | |
     v v v v
[b]{[/b]...,1,1,1,1[b]}[/b]<--> n-th 1
 ...,1,1,1,0 <--> n-th 2
 ...,1,1,0,1 <--> n-th 3 
 ...,1,1,0,0 <--> n-th 4 
 ...,1,0,1,1 <--> n-th 5 
 ...,1,0,1,0 <--> n-th 6 
 ...,1,0,0,1 <--> n-th 7 
 ...,1,0,0,0 <--> n-th 8 
 ...,0,1,1,1 <--> n-th 9 
 ...,0,1,1,0 <--> n-th 10
 ...,0,1,0,1 <--> n-th 11
 ...,0,1,0,0 <--> n-th 12
 ...,0,0,1,1 <--> n-th 13
 ...,0,0,1,0 <--> n-th 14
 ...,0,0,0,1 <--> n-th 15
 ...,0,0,0,0 <--> n-th 16
 ...

Now let us make a little redundancy diet

      3 2 1 0
     2 2 2 2
     ^ ^ ^ ^
     | | | |
     v v v v
...  1-1-1-1 <--> n-th 1
     \  \ \0 <--> n-th 2
      \  0-1 <--> n-th 3 
       \  \0 <--> n-th 4 
       0-1-1 <--> n-th 5 
        \ \0 <--> n-th 6 
         0-1 <--> n-th 7 
          \0 <--> n-th 8 
 ... 0-1-1-1 <--> n-th 9 
     \  \ \0 <--> n-th 10
      \  0-1 <--> n-th 11
       \  \0 <--> n-th 12
       0-1-1 <--> n-th 13
        \ \0 <--> n-th 14
         0-1 <--> n-th 15
          \0 <--> n-th 16
 ...

and we got

      3 2 1 0
     2 2 2 2
     ^ ^ ^ ^
     | | | |
     v v v v
          /1 <--> n-th 1
         1 
        / \0 <--> n-th 2
       1   
       /\ /1 <--> n-th 3 
      /  0
     /    \0 <--> n-th 4 
 ... 1    
     \    /1 <--> n-th 5 
      \  1 
       \/ \0 <--> n-th 6
       0  
        \ /1 <--> n-th 7
         0
          \0 <--> n-th 8
          
          /1 <--> n-th 9 
         1
        / \0 <--> n-th 10
       1  
       /\ /1 <--> n-th 11
      /  0 
     /    \0 <--> n-th 12
 ... 0    
     \    /1 <--> n-th 13
      \  1
       \/ \0 <--> n-th 14
       0  
        \ /1 <--> n-th 15
         0
          \0 <--> n-th 16
 ...

 

[matt grime]

Full credit to him, it takes some doing to talk about binary trees (uniquely path connected), even drawing them so they appear to be what you I might think, and then after much pressing claim it is actually a Cantor Set (totally disconnected), and further that as this is TD he can do whatever he damn well pleases. (Despite the fact it was your decision to move it here, Hurkyl, and that he wanted to post it in the maths forum.) That's some cheek

 

[matt grime]

And is that supposed to demonstrate a bijection with the Cantor set? How?

If it helps, a Cantor set is in bijection with the set of base 3 expansions of all reals between 0 and 1 with no 2 in their expansions, with the obivious dyadic representations identified.

 

[Organic]

Matt and Hurkyl,

      3 2 1 0
     2 2 2 2
     ^ ^ ^ ^
     | | | |
     v v v v
          /1 <--> n-th 1
         1 
        / \0 <--> n-th 2
       1   
       /\ /1 <--> n-th 3 
      /  0
     /    \0 <--> n-th 4 
 ... 1    
     \    /1 <--> n-th 5 
      \  1 
       \/ \0 <--> n-th 6
       0  
        \ /1 <--> n-th 7
         0
          \0 <--> n-th 8
          
          /1 <--> n-th 9 
         1
        / \0 <--> n-th 10
       1  
       /\ /1 <--> n-th 11
      /  0 
     /    \0 <--> n-th 12
 ... 0    
     \    /1 <--> n-th 13
      \  1
       \/ \0 <--> n-th 14
       0  
        \ /1 <--> n-th 15
         0
          \0 <--> n-th 16
 ...

 

[Organic]

Matt,

Please look at http://www.mathacademy.com/pr/prime/articles/cantset/

Cantor set is a hybrid of base 2 and base 3 ratios.

Therefore it is easy to show that 2^aleph0 is Cantor set where Cantor set is a Binary Tree:

                ?
__________________________________

      1                    0
_____________        _____________

  1       0            1       0
_____   _____        _____   _____

1  0    1  0         1  0    1  0  
__ __   __ __        __ __   __ __

 

[matt grime]

And? That is not a bijection from the (countable) set of rows corresponding to cofinite elements the power set of N to the Cantor Set, or any thing that has cardinality 2^aleph-0It tells you how to superimpose a binary tree onto another picture. that does not define a bijection. Nor does it imply that the binary tree is 'uncountable' (what aspect of it is uncountable in your opinion)

 

[matt grime]

Organic, I know what a Cantor set is.
You claimied the binary tree was a Cantor set in this thread earlier. It isn't. One wonders what you think a Cantor set is, or a binary tree.

Or why that defines a bijection.

 

[Organic]

Matt,

You forget my proof |R|>|N| but both N and R are countable.

 

[matt grime]

Evidently you don't understand the maths.

The Cantor set is not a binary tree. You have your own odd definition for binary tree, don't you. Care to explain what it is?

The cantor Set is the ***limit*** of that process.

So how does being able to draw a rooted binary tree on top of some other diagram provide you with a bijection with the Cantor set?

 

[Organic]

Matt,

Cantor set is a hybrid of base 2 and base 3 ratios.

Therefore Cantor set can be a base 2 fractal and base 3 fractal.

Your Cantor set is disjoint because you don't look at it from the complex level.

 

[Hurkyl]

Full credit to him, it takes some doing to talk about binary trees (uniquely path connected), even drawing them so they appear to be what you I might think, and then after much pressing claim it is actually a Cantor Set (totally disconnected), and further that as this is TD he can do whatever he damn well pleases. (Despite the fact it was your decision to move it here, Hurkyl, and that he wanted to post it in the maths forum.) That's some cheek

You're right. He's dropped the attitude he had for a while that caused me to start moving his posts over here in the first place.



Anyways, Organic, the trick to the "binary tree" construction of the Cantor set is that it's not enough; it only generates the points in the Cantor set with terminating decimal expansions. In order to get the whole Cantor set, you have to take the (topological) closure of this set of points.


Given a set S, the closure of S is the set of all points that are limits of sequences of elements of S. For example, the closure of (0, 1) is [0, 1]. (the sequence 0.1, 0.01, 0.001, 0.0001, ... is entirely in (0, 1), and the limit is 0, so 0 is in the closures of (0, 1))

 

[Organic]

Hurkyl,

You can't contradict it.

{10... ,1100... ,11110000... ,...} set is bijective to N.

The n-th notation of each member is:

n-th 1 2 3 . .  1 2 3 . . . .  1 2 3 . . . . . . . .  1 2 3
    {1 0 . . . ,1 1 0 0 . . . ,1 1 1 1 0 0 0 0 . . . ,. . .}

By taking the n-th notation from each member we can build a list of unique sequences which its magnitude=2^aleph0:

      3 2 1 0
     2 2 2 2
     ^ ^ ^ ^
     | | | |
     v v v v
[b]{[/b]...,1,1,1,1[b]}[/b]<--> n-th 1
 ...,1,1,1,0 <--> n-th 2
 ...,1,1,0,1 <--> n-th 3 
 ...,1,1,0,0 <--> n-th 4 
 ...,1,0,1,1 <--> n-th 5 
 ...,1,0,1,0 <--> n-th 6 
 ...,1,0,0,1 <--> n-th 7 
 ...,1,0,0,0 <--> n-th 8 
 ...,0,1,1,1 <--> n-th 9 
 ...,0,1,1,0 <--> n-th 10
 ...,0,1,0,1 <--> n-th 11
 ...,0,1,0,0 <--> n-th 12
 ...,0,0,1,1 <--> n-th 13
 ...,0,0,1,0 <--> n-th 14
 ...,0,0,0,1 <--> n-th 15
 ...,0,0,0,0 <--> n-th 16
 ...

If by closure you mean:

The collection of all points such that every neighborhood of these points intersects the original set in a nonempty set.

The result of this definition cannot be but at least Binary Tree where each point of it is a connaction (an intersection) with at least three neighbors (one above it and two below it).

 

[Hurkyl]

The problem is that each of the
10101010...
11001100...
11110000...
...

are only aleph0 long.

 

[Organic]

Hurkyl,

It is 2^aleph0 long because it "grows" in geometric series and not arithmetic series.

<---arithmetic series
      3 2 1 0
     2 2 2 2
     ^ ^ ^ ^
     | | | |
     v v v v
[b]{[/b]...,1,1,1,1[b]}[/b]<--> n-th 1      geometric series 
 ...,1,1,1,0 <--> n-th 2      |
 ...,1,1,0,1 <--> n-th 3      |
 ...,1,1,0,0 <--> n-th 4      |
 ...,1,0,1,1 <--> n-th 5      |
 ...,1,0,1,0 <--> n-th 6      |
 ...,1,0,0,1 <--> n-th 7      |
 ...,1,0,0,0 <--> n-th 8      |
 ...,0,1,1,1 <--> n-th 9      |
 ...,0,1,1,0 <--> n-th 10     |
 ...,0,1,0,1 <--> n-th 11     |
 ...,0,1,0,0 <--> n-th 12     |
 ...,0,0,1,1 <--> n-th 13     |
 ...,0,0,1,0 <--> n-th 14     |
 ...,0,0,0,1 <--> n-th 15     |
 ...,0,0,0,0 <--> n-th 16     |
 ...                          V

 

[Hurkyl]

The problem is that the geometric growth only exists in the finite realm. You have to do some other operation (such as take a limit, or a nested union) to transfer to the infinite case, and in this case, that operation doesnt' catapault you to 2^aleph0.

 

[Organic]

Hurkyl,

Forget about the word "growth".

I am talking about infintley long arithmetic series = aleph0
and infinitely long geometric series = 2^aleph0.

More than that both serieses are depended.

 

[Hurkyl]

There is no ω-th term in a geometric sequence, nor in an arithmetic sequence. An infinitely long geometric (or arithmetic) sequence has aleph0 terms, one for each finite ordinal.

 

[Organic]

Hurkyl,

Thank you, it is just something that I used to explain Matt my point of view in some particular case.

So here it is with no -th things:

<---arithmetic series
      3 2 1 0
     2 2 2 2
     ^ ^ ^ ^
     | | | |
     v v v v
[b]{[/b]...,1,1,1,1[b]}[/b]   geometric series 
 ...,1,1,1,0                  |
 ...,1,1,0,1                  |
 ...,1,1,0,0                  |
 ...,1,0,1,1                  |
 ...,1,0,1,0                  |
 ...,1,0,0,1                  |
 ...,1,0,0,0                  |
 ...,0,1,1,1                  |
 ...,0,1,1,0                  |
 ...,0,1,0,1                  |
 ...,0,1,0,0                  |
 ...,0,0,1,1                  |
 ...,0,0,1,0                  |
 ...,0,0,0,1                  |
 ...,0,0,0,0                  |
 ...                          V