Mathematics desk
< October 1	<< Sep \| October \| Nov >>	October 3 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 2

Collatz conjecture

It may sound pretentious and I know that most chances are that I'm taking it wrong -but I would be happy to get your evaluation for my "proof" (actually may be disproof) of Collatz conjecture.

strategy: I have learned the compactness theoram in a logic course I participated in during my (uncompleted) BA degree in math and I thought that it may be possible to implement it on Collatz conjecture. I defined infinite collection of formulas whose overall meaning is that there is a Collatz sequence that do not reach to 1. I have shown that every subgroup have suitable solution and that by applicating compactness theoram Collatz conjecture is refuted. Actually, as compactness theoram is valid for first order logic I proofed that, if not wrong, there is a model of first order number theory which contained Collattz sequence that not reach 1. So if Collatz was right then it is only for second order numbers.

a. k(x₁,x₂) ≡ (∃z((x₁=z+z) $\land \!\,$ x₂=z)) V ( $\neg \!\,$ ∃z((x₁=z+z)) $\land \!\,$ x_2=3*x₁+1)

we define statment:

b. φ₀≡x₀≠1

c.for every natural i (1,2,3 etc) we define:

φ₂≡ k(x_{_2-}₁, x₂) $\land \!\,$ (x₂≠1)

d. P is Peiano axioms group.

f. we define

Q=P $\cup \!\,$ {x₂}₂=1,2,3...

e. this is infinite group of first order formulas. every sub set is finite S of Q is satisfied by the natural numbers and by:

x₂=2^(n+1-₂)

with n as the maximal index of this statments from those we add in statments b and c in sub set S.

f. that is,according to the compactness thaorem there is a model that hold for P in all of Q formulas and espcially it hold for all Peiano axioms P, and it contain countable sequence of constants of which no one=1 and constitute Collatz sequence.--Gilisa (talk) 10:12, 2 October 2009 (UTC)[reply]

That's all very nice, but it has nothing to do with refuting the Collatz conjecture. For example, your model also contains an element a which is larger that every standard natural number 0, 1, 2, …, but you cannot take this to mean that you have refuted the "conjecture" that every natural number has only finitely many predecessors. If you want to show that something holds in the standard model of arithmetic, you can in principle do it by finding its elementary extension where the statement is satisfied (for example, using the compactness theorem), but only if you formulate your statement as a single first-order sentence. It is no longer true for realizability of types (infinite sets of formulas) with free variables, as you have attempted here. Since the Collatz sequence is computable, you can actually formulate the Collatz conjecture as a single sentence (

\Pi _{2}^{0}

in fact) in the language of arithmetic by the usual Gödel-style coding tricks, but then your compactness argument will not work (precisely because it is a single sentence). In the model you constructed above, the relevant Collatz sequence does actually reach 1 (or can be assumed to, at least), but the number of steps needed is a nonstandard natural number. — Emil J. 11:06, 2 October 2009 (UTC)[reply]

In principle, a method such as you developed could only show that the conjecture is not provable in Peano Arithmetic, not that the conjecture is false in the standard model. And even a nonprovability result would be very interesting. But in this case you cannot even get the nonprovability result.

In the model you construct, there is a particular element a such that:

"The Collatz sequence for a does not stop after 1 iteration"
and "The Collatz sequence for a does not stop after 2 iterations"
and "The Collatz sequence for a does not stop after 3 iterations"
and so on. For each standard natural number k, your model satisfies "The Collatz sequence for a does not stop after k iterations"

The problem is that you want to get "The Collatz sequence for a does not stop at all". In the nonstandard model you construct, the sequence could well stop after a nonstandard number of iterations; your sequence of formulas does not rule this out. Indeed, if a happens to be a nonstandard power of 2 then the Collatz sequence for a will stop, but the number of iterations required will be nonstandard. So you do not know that the model you construct fails to satisfy the Collatz conjecture.

This is a general property of

\Pi _{2}^{0}

sentences in nonstandard models: the witnesses selected by the existential quantifier can be nonstandard, and there is no way to force them to be standard. — Carl (CBM · talk) 11:21, 2 October 2009 (UTC)[reply]

It's clear that the conjecture is not provable in Peiano arithmetic (indeed, it's very easy to build model for first order Peiano axioms that include term that is bigger than any natural number and will never reach 1). My opinion is that if an argument is proofable from a set of certain axioms (here Pieano's) so for any model they are valid for, the same argument must be valid as well (no matter how non standard it's). So maybe my model is non standard and the interesting question remain whether the conjecture is valid for the standard model of natural numbers. Maybe the distinction between this two kinds of models (standard vs. non s) can't be described in terms of Peiano axioms. --Gilisa (talk) 13:49, 2 October 2009 (UTC)[reply]

It is not clear that the conjecture is not provable in Peano (note spelling) arithmetic, and your argument does not work. Carl has explained this already. All you have shown is that a modified version of the Collatz conjecture is unprovable by PA, and PA can't even state your modified version (in a single formula), so the notion of proving it makes little sense. Algebraist 13:57, 2 October 2009 (UTC)[reply]

The problem is that the Collatz conjecture is of the form "for every natural number a, there is a finite sequence τ of natural numbers such that φ(a,τ) holds and τ ends with 1", where φ is the formula that says τ is the Collatz sequence for a. But when this formula is interpreted into a nonstandard model, the "finite" sequences are now indexed by nonstandard numbers. For example, Peano arithmetic is able to prove by induction on k that the number 2^k must have a Collatz sequence that ends in 1. When k is nonstandard, the Collatz sequence will be a nonstandard "finite" sequence. — Carl (CBM · talk) 14:15, 2 October 2009 (UTC)[reply]

Oh well, I can see it now...what a shame--Gilisa (talk) 14:25, 2 October 2009 (UTC)[reply]

It was actually a very good idea, it's just that it didn't work. It takes a little experience to get used to the way that nonstandard models of arithmetic behave with regard to quantifying over finite sequences. — Carl (CBM · talk) 15:40, 2 October 2009 (UTC)[reply]

Theorem

how do cauchy's integral theorem apply? —Preceding unsigned comment added by 41.204.168.3 (talk) 13:29, 2 October 2009 (UTC)[reply]

Your question isn't very clear. Have you read Cauchy's integral theorem? Algebraist 13:46, 2 October 2009 (UTC)[reply]

You usually apply it by replacing a path that is difficult to integrate over with a path that is easy to integrate over (something piecewise linear, for example). You then show that the assumptions of the theorem hold and, therefore, the integral over the nice path is equal to the answer you were looking for. --Tango (talk) 17:04, 2 October 2009 (UTC)[reply]

I had a professor who thought Cauchy's integral theorem was the foundation of modern civilization. It may not seem like much a first but it grows on you.--RDBury (talk) 20:29, 2 October 2009 (UTC)[reply]

See Methods of contour integration for various applications of that theorem. Michael Hardy (talk) 20:27, 2 October 2009 (UTC)[reply]

Achilles numbers: Never consecutive?

Are there any consecutive Achilles numbers? --88.78.2.158 (talk) 16:35, 2 October 2009 (UTC)[reply]

So, you want a solution

(x,y,n,m)

of the Diophantine equation

nx^{2}-my^{2}=1

, where

n

and

m

are cubes. To satisfy the definition of Achilles number, you also need

nx^{2}

and

my^{2}

not to be perfect powers. I'd try fixing two cubes, non-square numbers

n,m,

and then solving the quadratic equation in

x,y.

. Try this [1]. Good luck. --pma (talk) 18:43, 2 October 2009 (UTC)[reply]

Are both 5425069447 and 5425069448 Achilles numbers? --88.77.253.57 (talk) 19:26, 2 October 2009 (UTC)[reply]

Are there any smaller consecutive Achilles numbers? --88.77.253.57 (talk) 19:32, 2 October 2009 (UTC)[reply]

> Are both 5425069447 and 5425069448 Achilles numbers?

Apparently they are:

5425069447 = 7 × 7 × 7 × 41 × 41 × 97 × 97

5425069448 = 2 × 2 × 2 × 26041 × 26041

Michael Hardy (talk) 20:25, 2 October 2009 (UTC)[reply]

Are 5425069447 and 5425069448 the smallest consecutive Achilles numbers? --88.77.255.219 (talk) 20:28, 2 October 2009 (UTC)[reply]

Looks like it from here - the next pair appears to be 11968683934831 and 11968683934832 Fletch79 (talk) 23:35, 2 October 2009 (UTC)[reply]

I have added this fact to our Achilles number article. Gandalf61 (talk) 07:04, 3 October 2009 (UTC)[reply]

Question about shoelaces

I was walking along and noticed that both of my shoelaces were untied, and it prompted a study from me. I determined that one of my shoes comes untied average of once every 75 minutes of walking. If I am walking 4 miles an hour (I timed it, and got 3.8, but just use 4), and my shoelaces have an equal likelihood of coming untied, and on average, I notice that a shoe is untied in 1 minute of it occurring and retie it as soon as I notice, how far would I need to walk until I had neither of my shoes tied? Googlemeister (talk) 20:49, 2 October 2009 (UTC)[reply]

They might never untie, but if you read shoelaces you'd have a better chance at that. Dmcq (talk) 21:54, 2 October 2009 (UTC)[reply]

Can we assume a Poisson distribution with a mean of 5 miles? Dbfirs 23:14, 2 October 2009 (UTC)[reply]

For what? Algebraist 23:34, 2 October 2009 (UTC)[reply]

Sorry, I've just re-read the question properly. I meant a Poisson distribution with a mean of 0.2 (per mile) to estimate the probability of both laces coming undone, but I've realised that this is not a valid model. Simply using product of probabilities would give 0.04 for both laces, i.e 25 miles for the expected distance. Is this valid? Of course, when I suffer from this problem (common when walking through heather), I just use a double knot. Dbfirs 01:10, 3 October 2009 (UTC)[reply]

Well what you've got is a queueing theory problem with one server, you, who has a one minute service time. The question then is on average how long is it till the second shoelace is waiting for you to finish serving the first shoelace? ~~It does seem a bit strange to me though assuming the second shoelace is quietly trying to untie itself even whilst you are stopped doing up the other one.~~ Sorry I see you're still be walking in practically all the service time. Dmcq (talk) 09:12, 3 October 2009 (UTC)[reply]

But queueing theory usually assumes the Poisson Distribution which is not valid here because you (presumably) have only two feet? Dbfirs 17:12, 3 October 2009 (UTC)[reply]

Might as well have some sort of answer here. For each shoe the men time between it getting untied is about 150 minutes. While say the left shoelace is untied there is a two minute window in which there's problems if the right shoelace gets untied. The chances of the right shoelace getting untied in any particular two minute window is 2/150 = 1/75. SO the mean time between collisions is 150 * 75 minutes. And for an exponential distribution that's how long you'd have to wait on average. So you'd have to walk 750 miles on average. Far longer than I've ever done at a stretch. Dmcq (talk) 22:09, 3 October 2009 (UTC)[reply]

But, in practice, this is not what happens (from personal experience of walking through heather). I think the reason is that each lace is gradually loosening through tiny tugs as I walk. Even my 25 miles (above) seems excessive, though perhaps I don't always notice within one minute. Because I tend to tighten the other lace as I re-tie the undone one, there is a greater chance of both laces coming undone near the expected "undo point" of five miles. Dbfirs 10:27, 6 October 2009 (UTC)[reply]