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

  • Thread starter Thread starter Organic
  • Start date Start date
Click For Summary
The discussion centers on the Collatz problem and the implications of fixing the variable k within its mathematical framework. Participants debate whether k should be considered fixed or variable, with arguments suggesting that treating k as fixed leads to contradictions in the proof structure. The concept of decidability is also scrutinized, with claims that the Collatz problem is undecidable due to its reliance on the axioms of infinity and the inherent symmetry of the Binary Tree. The conversation highlights the complexity of proving the Collatz conjecture and the necessity of clarifying terms like "out of range" and "fixed" in mathematical discourse. Ultimately, the participants emphasize the need for rigorous definitions and logical consistency in mathematical proofs related to the Collatz problem.
  • #31
But youu don't produce any explanation of generating these trees, or what they are!

Please answer these simple question.

1. The diagram labelled collatz sequence macro tree. What is it, how are you generating it, what are the blue dots.

2. Why is the phrase 'any n in Collatz sequence has a 1-1 and onto with {}...' there? It is meaningless in the English langauage an mathematically.


3. You speak of 'this binary tree' that stands at the 'base of N' implying it is unique - you've drawn at least 3 of them, so it isn't unique. What is it?
I asked it it is the infinite bifurcating diagram with two outgoing edges at each vertex, and one incoming (except at the initial vertex where there are no incident edges), you didn't answer.



4. You still speak of 'Collatz sequence' with no article, definite otherwise. What do you mean by this?


5. It is customary in writing a proof of a conjecture (or whatever it is you are now claiming) to state what the conjecture says. Why isn't a statement of what you are trying to prove included?

6. The theory doesn't change; a different theory may replace it, supersede it or just be developed in tandem. If one wants to do anything requiring set theory, then ZF(C) is the current vogue. Ok, this isn't a question.
 
Physics news on Phys.org
  • #32
In fact, just state what it is you are trying to prove, so that you at least demonstrate you know what the Collatz Conjecture says. That doesn't mean post a link to some Wolfram site, just in plain English explain what it is that you understand the Conjecture to say. Perhaps then we might even see what you mean by 'Collatz sequence'
 
  • #33
Matt,
1. The diagram labelled collatz sequence macro tree. What is it, how are you generating it, what are the blue dots.
Don't you see the similarity of these sub branches in maco and micro Binary Trees?

These sub branches defined in the micro tree, but fits to the macro tree, where Collatz sequence (marked by the blue dots) was first defined.
2. Why is the phrase 'any n in Collatz sequence has a 1-1 and onto with {}...' there? It is meaningless in the English langauage an mathematically.
I translated it from Hebrew, any way you can use "bijection" instead.
. You speak of 'this binary tree' that stands at the 'base of N' implying it is unique - you've drawn at least 3 of them, so it isn't unique. What is it?
Where did i draw 3 of them? In the base of the Von Neumann Hierarchy
there is exactly one and only one Binary Tree.
I asked it it is the infinite bifurcating diagram with two outgoing edges at each vertex, and one incoming (except at the initial vertex where there are no incident edges), you didn't answer.
I don't undestand your question.
4. You still speak of 'Collatz sequence' with no article, definite otherwise. What do you mean by this?
I don't understand what you write here too.
5. It is customary in writing a proof of a conjecture (or whatever it is you are now claiming) to state what the conjecture says. Why isn't a statement of what you are trying to prove included?
Thank you, I'll do it tonight.
6. The theory doesn't change; a different theory may replace it, supersede it or just be developed in tandem. If one wants to do anything requiring set theory, then ZF(C) is the current vogue. Ok, this isn't a question.
No you no me can know what exactly happen when some mutation takes place in some real or theoretical system.
 
  • #34
there is one and only one binary tree? ok, what is it?

is it the infinite continuation of the finite depth tree you have drawn under the title collatz sequence macro tree?

that is is it the one that goes

x
0 1
01 01
01 01 01 01
...
.
.


off 'to infinity' where you can't say what x is? you'll have to imagine the branches drawn in, and try and justify it correctly - html is a pain.


As for just saying 'Collatz sequece'

A sequence is a function from some set, S, to N, that is you can think of it as sequence

(a_1,a_2,a_3...) a_i in S


so what is 'collatz sequence'?

*a* collatz sequence can be defined, i suppose, by setting a_1 to be some integer, r, and obtaining the next term by the collatz iteration. However there is no unique collatz sequence - a different r defines a different sequence, so which one of these are you talking about? or is it something else entirely.

the conjecture states that given any r, the above defined sequence eventually reaches 1.

that will do for now
 
Last edited:
  • #35
Matt,

Sorry about my Math language, which is very poor as you already know.

By sequence I mean the tree of Collatz sequences for example:

http://michael.cleverly.com/funstuff/3x+1/collatz2.jpg


The blue dots in my diagrams are equivalent to this tree.

Any magenta branch in the macro tree goes directly to 1.
 
Last edited by a moderator:
  • #36
Ok, I'm beginning to see the picture.


1. The binary tree is what i said it is - the infinite thing above. At the k'th level you number the nodes from 1 to 2^k using binary expansions (this means by the way that the only consistent choice for the initial node is 1). You then superimpose those green lines and blue dotsby saying join dot r with dot t iff at least one of the following hold:

r=2t
t=2r
r=3t+1
t=3r+1

ok.

What youve observed is that at any level, it must be that there is a number that is sent outside that level to the next one, for instance you need to construct level k+1 and higher to indicate all th points where 2^k - 1 gets sent/can come from



let's address what you are claiming this implies.

In order to provide a proof of the Collatz conjecture in ZF, one must have all the Natural numbers. However it is in the assumption of the Collatz conjecture that the naturals exist and are a set in ZF. If we are not assuming the axiom of infinity, then the natural numbers do not form a set in the theory we are using, and hence Collatz is undefined in that theory. However, all the axiom of infinity states is that the natural numbers form a set, it does not imply the Collatz conjecture s true. The truth of the Collatz conjecture is not therefore equivalent to the axiom of infinity.

We must presume the axiom of infinity is in our set theory to define the Collatz conjecture, that is all.

the naturals exist, whether or not you chose to call them a set and do so independently of the set theory you use, there is nothing in what you've written to suggest that the assumption the naturals form a set is equivalent to Collatz being true or not.


I think the key here is your views on axiomatic set theory and the natural numbers, nothing to do with Collatz. The axiom of infinity just states that the naturals are an (inductive) set in ZF(C).
 
Last edited:
  • #37
Matt,

You are close so maybe in this post you will understand my proof.

Please pay attention to the fact that only Collatz-like sequences take you always from some n to another n in the micro tree.

If you combine all these "movements" to one direction (let us choose the positive direction) then by collatz-like sequences you get the "If n exists then (at least) n+1 exists" which is equivalent to ZF axiom of infinity.
 
Last edited:
  • #38
But, Organic, the Collatz Iteration is defined on N already, that is all the n's in N 'exist' already. You're finding problems where there aren't any, and in particular you still seem to think that the axiom of infinity is what makes N exist, when that isn't what it states. The axioms of a group say do not force idnetity elements to exist, do they?
 
  • #39
Matt,

Can N exists without the axiom of infinity?

Please show me how you can say that there are inifinitly many n's in N without the axiom of infinity?
 
Last edited:
  • #40
yes, they do exist without the axiom of infinity. This is what I've been attempting to explain since the year dot (English phrase meaning from the very beginning) all the axioms of *a* set theory do is tell you what collections of things constitute sets. It as an attempt to put the theory of sets onto a firm footing so that we can avoid things like the Russell paradox - the collection of all sets that do not contain themselves 'exists' but it is not a set (in ZFC). If you take all the other axioms of ZF(C) apart from the axiom of infinity, then there is no way to force the Natural numbers to be a set - that is it is not possible to deduce the existence of an infinite set from the other axioms alone.

There is some philosophical debate as to what one means by 'exist', but the fact that the greeks were able to talk about the natural numbers (and the rationals etc) without knowing the axiom of infinity should tell you something! The existence philosophy boils down to 'is there some higher plane where '1' genuinely exists in the same way that the computer in front of you exists, or is it that we force it to exist in this universe and it is purely an invention of this universe' this is the so-called idea of the platonic realm. Actually that wasn't a very good example, but if you want to learn about it try looking up the word 'qualia' which is the idea that oneness is some higher concept independent of 1, and that 1 is just some realization of it. But please don't think you can use that to do anytihng with 'infinity' with because, as we established earlier, the idea that 'infinity' exists is a myth, infinite is just 'not finite' which has associated implications, and useful properties.
 
Last edited:
  • #41
Just seen the edit.


Suppose that there are only finitely many natural numbers ( a natural number is one obtained by adding 1 repeatedly), then let M be the largest. M+1 is a natural number by definition, and strictly larger than M. This isn't the axiom of infinity. Don't like that one?

Clearly 2 is a natural number, so M>1 if it exists, yet then M*M > M # so M can't exist.

The axiom of infinity means that there is an infinite set, that is all.
 
  • #42
Matt,

By saying: "yes, they do exist without the axiom of infinity."

You maybe use a vary deep platonic realm.

Well, I do not accept your platonic point of view, because without the axiom of infinity all you have is the empty set by the empty set axiom.
 
  • #43
No, they exist by induction, they form a set in ZF by the axiom of infinity. If you want a set theoretic proof for these things try the peano postulates.

I suppose saying they exist inductively sounds wrong doesn't it?


We can count, we know what 1 dog is, 2 dogs, etc, the counting things are natural numbers, we get them by adding 1 repeatedly. Now the question is can we form the SET of natural numbers? Well, the collection of natural numbers exists, and is clearly infinite, that they are a set in ZF is useful, and exactly the reason why the axiom of infinity is there, in ZF they for an inductive set. That's all, I'm not appealing to any platonic realm, only that we can count and have labels for this counting. Are you getting this yet? That it is whether or not we can call it a set, that's all? You can define classes of arbitrary things, they just don't turn out to behave as sets morally ought to if our logic is to be consistent. Set theory is just a formalization of what we know ought to be true, in a way that makes it consistent - the class of sets that do not contain themselves is not a set, yet it still exists.

I knew I'd regret telling you abuot the platonic realm. You already seem to have misunderstood what was admittedly a bad explanation of it; the explainer must take the blame.
 
Last edited:
  • #44
Peano postulates and ZF axoim of infinity are the same induction.
 
Last edited:
  • #45
Peano just puts the naturals on a well founded set theory footing. Induction is there, it is independent of the Axiom of infinity, which after all requires induction, to demonstrate that there is actually an infinite set.


The natural numbers exist, that they form a set is all we are saying with the axiom of infinity.
 
  • #46
Without this induction you can have one and only one element.

This induction does not define the internal structure made by Von Neumann.

My proof combines between Von Neumann recursive method and the ZF induction.

By this recursive(micro)-inductive(macro) point of view we can check the invariant symmetry that exists in the base of the examined elements.
 
  • #47
Originally posted by Organic
Matt,

By saying: "yes, they do exist without the axiom of infinity."

You maybe use a vary deep platonic realm.

Well, I do not accept your platonic point of view, because without the axiom of infinity all you have is the empty set by the empty set axiom.

But how can the empty set exist? By your logic it can't. Because the existence of the empty set in your logic requires the axiom of the empty set, which requires the empty set to exist... oh no, your circular reasoning goes horribly wrong! Have you read anything that talks about set theory at all, ever? Get a book from the library, you might learn something. And when you understand it, try again.
 
  • #48
OF course if you don't like that, then how about this (which i noted earlier but you ignored)

if one wants to prove that Collatz iterations of all natural numbers reach one, then you must be presuming that the natural numbers all already exist to even define the Conjecture, so there can be no issue in presuming they exist to prove it. Anyway, you haven't proved anything, well apart from that you don't know what you're talking about, yet still feel confident enough to tell me I'm wrong about everything.
 
  • #49
Nothing circular here.

The axiom of the empty set and the empty set are the same.

The axiom of infinity use this axiomatic existence as its input and using induction to define its pruducts.

Von Neumann Hierarchy uses the same axiomatic existence as its input and using recursion to define its products.

My proof combines between Von Neumann recursive method and the ZF induction.

By this recursive(micro)-inductive(macro) point of view we can check the invariant symmetry that exists in the base of the examined elements.
 
  • #50
You think the axiom of the empty set is the empty set? Wow, that's a new one. You know you really ought to learn some maths, Organic if you're going to persist in this.

Erm, there is no such thing as ZF induction as far as I'm aware. Please post some reference for this.

Inducion is a mathematical technique, using the existence of the 'inductive' set that the axiom of infinity requires, one can construct an infinite set. And? How does this bear any relation to anything here?

At least accept that the existence of the Natural numbers is implicit in the statement of the Collatz conjecture. Therefore assuming their existence in the proof is acceptable!


That you do not seem to understand the ideas of set theory can be left alone - go and get a book and learn about them. The axiom of infinity does not state the naturals exist, it states that there must be an infinite set.
 
  • #51
Let me put it this way, the ZF axiom of the empty set uses x
where x is something and then it says that for any x(=something),
x(=something) not in some set X.

This is nothing but a negative and complicated way to say positively and simply: "there exist set X with no elements" notated as {}.

ZF induction is my mistake, it has to be the ZF axiom of infinity induction.

You don't see the invariant symmetry that exists in both Von Neumann
recursion(micro level) and Collatz sequences (macro level).

The ZF axiom of infinity products (if n exists then n+1 exists implies N members) are in the level of the macro tree, where Collatz sequences exists, therefore we cannot distinguish between them and the Collatz sequences because in the macro level they are the same elements.

Eech n in the induction macro level has its own internal unique structure produced by Von Neumann recursion.


When we examine the invariant Binary tree that stands in the basis of both Collatz sequences and Von Neumann recursion, then and only then we can see that Collatz sequences and ZF axiom of infinity are the same iteration.
 
  • #52
Oh. My. God. For the god knows how many'th time, what is the ZF axiom of infinity induction?. You are the only person I have ever known use it, Google for the phrase. You and responses to you were the only hits the last time I did it.

There is the axiom of infinity which states there must be a set W satisfying a certain property: if y is in W then y u {y} is in W. There is absolutely no mention of induction there. Now, using induction we can conclude that there is a set which does not have finite cardinality. That's it. It is not the ZF axiom of infinity induction.

For some reason you seem to think that it is the axioms of ZF that force things to exist. Exercise: just using the axioms, how do you see that the class of all continuous Real valued functions on a compact hausdorff topological space exists?

The class exists, independently of ZFC. Which is just a formal attempt to put the theory of sets onto a firm mathematical footing. These things all exist albeit in some mathematical sense anyway.

Read a book on set theory, please, I'm begging you.
 
  • #53
Matt,

Don't you see that "if y is in W then y u {y} is in W" is exactly the same as "if n is in N then n+1 is in N"?

"if n is in N then n+1 is in N" is an induction.

Please look at the other things that I wrote in the previous post.

Thank you.
 
Last edited:
  • #54
You are missing the subtle point about what the word induction means here, in particular it is properly the principle of mathematical induction which states that, suppose P(r) is a set of statements indexed by N. Then if P(n) => P(n+1) and P(1) is true, it follows P(r) is true for all r in N. What ever short hand you may have for it, and whatever the superficial similarity, the axiom of infinity that if y is in W, then yu{y} is in W is not the principle of mathematical induction. Using the principle of mathematical induction one concludes that the axiom of infinity states there is a set whose cardinality is not finite. Roughly speaking the set theory one uses must have an inductive set. These are subtle issues, but you're lack of precision with mathematical language causes you to say things that are wrong, often very wrong - you have said repeatedly that a set is equal to an inequality for instance. This is a common error you commit - saying that two different things are equal or the same.

In particular if n is in N then n+1 is in N is an 'inductive step' in a proof by induction.

Yes there are similarities, and that is how the axiom of infinity comes to be in the form it is - there are equivalent formulations (inductive sets).

Anyway, enough of this. Back to the main point.

Your proof. what stage is at at now. It is on at least its third rewrite isn't it. Each time you insist it is a proof, and each time you have to rewrite it cos you realisze you've made another mistake, and each time you're as certain that it is a proof. How about relabelling it as an idea cos you don't seem to understand what a proof is.
 
  • #55
1) I rewrote it because i saw that you don't understand it.

2)"if n is in N then n+1 is in N" is not an 'inductive step' but an induction forced by an axiom (the ZF axiom of infinity).

3) Please this time read what is below and write your remarks:

Let me put it this way, the ZF axiom of the empty set uses x
where x is something and then it says that for any x(=something),
x(=something) not in some set X.

This is nothing but a negative and complicated way to say positively and simply: "there exist set X with no elements" notated as {}.

If you don't see the invariant symmetry that exists in both Von Neumann recursion(micro level) and Collatz sequences (macro level) then you can't understand my proof.

The ZF axiom of infinity products (if n exists then n+1 exists implies N members) are in the level of the macro tree, where Collatz sequences exists, therefore we cannot distinguish between them and the Collatz sequences because in the macro level they are the same elements.

Eech n in the induction macro level has its own internal unique structure produced by Von Neumann recursion.


When we examine the invariant Binary tree that stands in the basis of both Collatz sequences and Von Neumann recursion, then and only then we can see that Collatz sequences and ZF axiom of infinity are the same iteration.
 
Last edited:
  • #56
OK, let's ignore the infinity stuff, cos it is implicit in the definition of the Conjecture that we are proving it for all n in N.

Right, now you put the collatz tree in some sort of bijection with the binary tree. However, as each integer n occurs an infinite number times in the labelling on the binary tee, how are you deciding which one you want?

Seeing as you tend not to see things like this, here's a proof of that assertion. let r be fixed, the number 2^r-1 occurs on the k'th level for every k > r. So which of those are you picking?

I say some sort of bijection cos I don't see what is in bijection with what clearly. what are the two sets that are in bijection?
 
  • #57
The Binary Tree is in bijection with itself, or if you like macro tree (the induction level) is in bijection with the micro tree (the internal recursion level).
 
  • #58
So, something is in bijection with itself? Stop presses. You claimed something about the n being in bijection with {} or something, please repost that.
 
  • #59
  • #60
Some comments for all:

You belong to a community that express its ideas by words, I don't.

In my opinion, there is nothing in the tools themselves that determines if some idea is mathematical or not.

It's not the tools, it's how you use them. Mathematics can be done with pictures, but you have to use them the same way you use words and formulas; by following rules of deduction that let you deduce new pictures from old pictures.

The tricky thing is that pictoral arguments say absolutely nothing about things that get described by words and formulas unless you provide a mapping between picture world and word/formula world.

Sometimes when I've done "proofs" via deductions of pictures, I was only looking for results in picture-land and I was happy. Other times, I was working in word/formula-land and I carfeully constructed a picture-land that had a correspondence back to word/formula land so that my picture proofs really do translate into facts in word/formula-land.


In order to provide a proof of the Collatz conjecture in ZF, one must have all the Natural numbers. However it is in the assumption of the Collatz conjecture that the naturals exist and are a set in ZF.

It takes a bit of effort, but you can state the Collatz conjecture in ZF without ever mentioning N, thus the Collatz conjecture can be defined even if you deny the existence of N.

Of course, it does require you to define the term "natural number", but that can be done without the axiom of infinity. You just don't get the convenience of having a set of all natural numbers.


"If n exists then (at least) n+1 exists" which is equivalent to ZF axiom of infinity.

The axiom of infinity states (accepting your slight abuse of notation):

"There is a set, S, such that if n is in S, then n + 1 is in S".

Please try to understand the difference.


The statement "If n exists then (at least) n+1 exists" would be better said as "For any n, there exists a set we write as n+1". This fact is guaranteed by the axioms of the sum set and the axiom of the pair set:

Given n:
The axiom of the pair set proves the set {n} exists.
The axiom of the pair set proves the set {n, {n}} exists.
The axiom of the sum set proves that n U {n} exists
and "n U {n}" is what is really meant in set-theory land, not "n + 1"



Can N exists without the axiom of infinity?

The answer to this statement (interpreted mathematically) is yes.

ZF is an incomplete theory; to the best of my knowledge, the statement "N exists" is independant from the axioms of ZF without the axiom of infinity.

Thus N can exist without the axiom of infinity.


Please show me how you can say that there are inifinitly many n's in N without the axiom of infinity?

Without the axiom of infinity, I can prove that there does not exist a finite set that contains all of the natural numbers. Here's the sketch:

Suppose F is a set of all natural numbers. The function f(n) = n + 1 is a 1-1 mapping from F onto a proper subset of itself. Therefore F is infinite.

Therefore, no finite set can contain all natural numbers.


Peano postulates and ZF axoim of infinity are the same induction.

Nothing in the Peano postulates say anything about sets. ZF does nothing but postulate the existence of a set with a given property. Induction is a mathematical technique for proof and thus cannot be one or more axioms. None of the three things mentioned in your sentence can be the same.


Without this induction you can have one and only one element.

Tell me how many sets you want proved exist and I'll do it for you without any form of induction. I'll do two sets for you, as a freebie.

{} exists by the axiom of the empty set.
{{}} exists by the axiom of the pair set.

{} is unequal to {{}} because {} is in {{}} but {} is not in {}.

Thus, I've proven two sets, {} and {{}} exist.


The axiom of the empty set and the empty set are the same.

The axioms of a mathematical theory are not the objects of that mathematical theory.
 

Similar threads

Undergrad Breakthrough in 3n+1 Problem: Collatz Conjecture
  • · Replies 7 ·
Replies
7
Views
5K
Undergrad Can this method be used to prove the Collatz Conjecture?
  • · Replies 3 ·
Replies
3
Views
2K
How Can Complementary Logic Enhance Dimensional Visualization?
  • · Replies 8 ·
Replies
8
Views
7K
How Does Complementary Logic Redefine Mathematical Infinity?
  • · Replies 211 ·
8
Replies
211
Views
24K
Is the Collatz Conjecture's Behavior Predicted by Binary Representations?
  • · Replies 1 ·
Replies
1
Views
3K
Similar to Collatz Problem (Please Read)
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad Stable solutions to simplified 2- and 3-body problems?
  • · Replies 6 ·
Replies
6
Views
3K
Complex function open set, sequence, identically zero, proof
  • · Replies 6 ·
Replies
6
Views
2K
What is the relationship between symmetry and the Collatz problem?
  • · Replies 16 ·
Replies
16
Views
5K
Undergrad What type of problems do you like the most?
  • · Replies 4 ·
Replies
4
Views
2K