Wikipedia:Reference desk/Archives/Mathematics/2006 July 7

Humanities Science Mathematics Computing/IT Language Miscellaneous 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 at one of the pages linked to above.

< July 6 Mathematics desk archive July 8 >

Set theory and epistemology

Hi guys... I was wondering why is set theory said to be 'beyond logic' can someone explain this to me please? Is it because logic itself is a set? is it because anything that can be, is a set or is in a set?...but then again, isn't that part of our logic?...unless the subject isn't settled yet...like I think it is.--Cosmic girl 19:43, 7 July 2006 (UTC)

Where is your reference that set theory is said to be 'beyond logic?' ...IMHO (Talk) 19:47, 7 July 2006 (UTC)

I would say that set theory is not reducible to logic (in the sense, say, that Frege thought it was). That is, it's synthetic rather than analytic. Is that what you mean, or do you mean something stronger, say that set theory is not amenable to the methods of logic? --Trovatore 20:17, 7 July 2006 (UTC)

Here is my source: http://www.rbjones.com/rbjpub/philos/maths/faq031.htm I mean that set theory can aply to many kinds of logic... is that possible?...meaning thus, that set theory is way more general than logic.--Cosmic girl 02:23, 8 July 2006 (UTC)

(Corrected header spelling to "epistemology".) I could not find a statement that set theory is "beyond logic" on that page, only a question about the epistemological implications if that view is adopted. Seeing philosophers around mathematics or physics makes me nervous, like seeing small children playing with sharp knives. Games about foundations have little impact on most working mathematicians. We do know that we have a choice of which rock to stand on and which to pick up, so to speak. It is overly simplistic to claim that set theory is beyond logic, or that logic is beyond set theory. In fact, it is too simplistic to speak of either set theory or logic in the singular, because we have choices of set theories and choices of logics. Further confusing the discussion is the difference between how a philosopher conceives of logic and what a mathematician means.

What every trained mathematician does know is Gödel's incompleteness theorems. An "executive summary" is that there is a difference between truth and provability. (But see the article for details.) Some might thus consider arithmetic "beyond logic". --KSmrq^T 06:40, 8 July 2006 (UTC)

Do you mean by 'beyond logic' that logic is dependent on arithmetic?.--Cosmic girl 19:53, 10 July 2006 (UTC)

Number theory question

Anyone know if there's a proven non-trivial limit to the number of consecutive composites each a multiple of some prime <= p(n), expressed in terms of p(n)? This limit is certainly less than the primorial of p(n) and I can show (by a constructive method) that it is at least 2*p(n-1) - 1. I also know for at least some values of n it is somewhat larger than 2*p(n). It seems there might be some way to prove a limit of the form C*p(n) for some ridiculously large C. If anyone has seen anything like this, please let me know. -- Rick Block (talk) 20:07, 7 July 2006 (UTC)

hey, I probably can't help you, but out of curiostiy does consecutive just mean like 77, 78, 79, etc? How could each such composite number be the multiple of the same prime? Or do you mean "a multiple of some prime" but not the same one, in which case isn't the word "composite" enough to say that?? Thank you. 82.131.184.144 22:20, 7 July 2006 (UTC).

Yes, consecutive, but a multiple of any of the primes less than p(n). For example, for n=3 the question is how many consecutive numbers are there that are each a multiple of 2,3, or 5 (the answer is 5). There's a pattern to the arrangement of multiples and non-multiples of length primorial of p(n) (which gets large in a hurry). Using Π(p(n)) to mean the primorial, ( x * Π(p(n)) ) + 1 is not a mulitple of any of the primes up to p(n), so the trivial limit is Π(p(n)). -- Rick Block (talk) 22:59, 7 July 2006 (UTC)

I think it's always the next higher prime minus two, but I don't have a proof. —Keenan Pepper 03:01, 8 July 2006 (UTC)

Thanks, but I know it's not this. Consider [2,3,5,7,11]. There's a sequence of 13 starting at 114 which are all multiples of one of these primes. Given the set of primes through p(n) I can construct a sequence very much like this one of length 2*p(n-1) - 1. If you're curious, the construction is to pick a multiple of Π(p(n-2)) such that one less is a multiple of p(n-1) and one more is a multiple of p(n) (such an arrangement is guaranteed to exist by the Chinese remainder theorem). The chosen multiple of Π(p(n-2)) is the center of a sequence of length 2*p(n-1) - 1 which are multiples of at least one of the primes through p(n). -- Rick Block (talk) 18:12, 8 July 2006 (UTC)

Oh whoops, I misinterpreted you to mean all its prime factors are below a certian limit, when you mean just one of them. Right? —Keenan Pepper 21:02, 8 July 2006 (UTC)

So you're talking about sequence A058989, right? —Keenan Pepper 21:06, 8 July 2006 (UTC)

Yes, I'm talking about sequence A058989. I'm aware of the Weissman conjecture. I had independently conjectured this, and ultimately found the discussion on yahoo's primenumber group about it (including Phil Carmody's counterexamples). -- Rick Block (talk) 23:55, 8 July 2006 (UTC)

I don't know whether this counts as non-trivial, but I can shove the upper bound down some. Take p(n) and Π(p(n)) to be the areas I'm trying to find gaps in. max(a,b,c) will indicate the largest of what's in the parentheses, eg max(1,2,3)=3. ZSpan(x) and Span(x) will be as Phil Carmody described them. A "prime candidate" indicates a number that is not divisible by any p(x<=n).

1) First, the most obvious: p(n+1) is guaranteed to be fairly close to p(n). Certainly closer than Π(p(n)), but the tightest bound I've heard of puts at least one prime between any number x and 2x. Anyway, close, which cuts the gap between 2 and Π(p(n)) down a bit. So, Span(n) <= max(ZSpan(n), Π(p(n))-ZSpan(n)).

2) Of course, since Π(p(n)) is divisible by all p(x<=n), Π(p(n))-p(n+1) is not divisible by any, so Span(n) <= max(ZSpan(n), Π(p(n))-2*ZSpan(n)). (I'm ignoring the details of +-1, to get the idea across.)

3) Now, at the center of the full pattern, at Π(p(n))/2, there is a number divisible by all p(x<=n) except 2. Moving outwards from it a distance a in either direction, you'll find prime candidates fanned out at 2^a for 1<2^a<2*p(n+1). I'll call the largest such a A, which is equal to floor(log₂p(n+1)). There are of course many prime candidates just beyond that, but they're much more difficult to locate. So, Span(n) <= max(ZSpan(n), Π(p(n))/2-ZSpan(n)-2^A, 2^a-1). The last is to take into account the largest gap in the fan. However, since it's defined as being less than p(n+1), I guess it can be left out in this case.

4) A similar system will work for any division of Π(p(n)) by one of its factors p(x<=n) (eg Π(p(n))/5, 2*Π(p(n))/5, 3*Π(p(n))/5, 4*Π(p(n))/5 or Π(p(n))/7, 2*Π(p(n))/7...6*Π(p(n))/7). The density of the fan around each decreases substantially, however, as p(x) increases, and for any p(x)>2 each of the p(x)-1 centerpoints given by this system is guaranteed to have at least one prime candidate exactly adjascent to it.

5) Getting into division by two primes at once (Π(p(n))/15, Π(p(n))/21, Π(p(n))/22 etc.) or more makes the fan significantly more dense in general, since a is at not only 1 (sometimes) and powers of each prime, but at combinations of their powers. However, as the number of primes gets higher, I can't quite guarantee there will always be a prime candidate right nearby. However, by following the trend downwards, it's pretty clear that although a multiple of a recent prime may not be the right answer, it's in the ballpark.

6) Now, I'd like to see if you can help with an extension of that. It seems to me that the multiples of p(n) that aren't multiples of p(x<n) tend to have quite a few other prime candidates between them. I'm not certain of that, though, and don't see how to prove it. If someone can, though, then any gap in n is the sum of at most two gaps in n-1, so Span(n)<=2Span(n-1). I tested out the theory that this is the case on the values of Span(x) I can find (2, 4, 6, 10, 14, 22, 26, 34, 40, 46, 58, 66, 74, 90, 100, 106, 118, 132, 152, 174, 190, 200, 216, 234), and the proportion of each to the one before is less than 2 (except for 4/2, which is equal to 2 and demonstrates my point nicely). In fact, the proportions seem to get closer to 1 the farther out I go, ending with 234/216≈1.08. This is consistent with what I would expect, but nowhere near proof. I eagerly await your response. Black Carrot 20:25, 11 July 2006 (UTC)

I numbered your points for reference.

1) That there is a prime between n and 2*n is Bertrand's postulate. There are tighter bounds that have been proven, I think current is close to between n and n + ~sqrt(n) (it's actually +n to some exponent a little larger than 1/2). And, yes, Span(n) <= max(ZSpan(n), Π(p(n))-ZSpan(n)), but ZSpan(n) is so small compared to Π(p(n)) that this really isn't much different from saying Span(n) <= Π(p(n)).

2) Agreed (but again, Zspan(n) << Π(p(n)) ).

3) I follow the fan out from Π(p(n))/2 with prime candidates at Π(p(n))/2 +/- 2^a (these are really numbers that are relatively prime to p(x<=n) ), but I think there are some notation issues here. Specifically, I think the "prime candidates" are at Π(p(n))/2 +/- 2^a for 1<= a <= A, where A is floor(log₂Π(p(n))/2)). I think this leads to a potential span of length 2^A - 2^(A-1), which I believe simplifies down to Π(p(n))/4. So I think we end up with Span(n) <= max(ZSpan(n), Π(p(n))/4). It's certainly the case that Π(p(n))/4 is far larger than Zspan(n), so I think we're at Span(n) <= Π(p(n))/4.

4) Agreed, and this leads to Span(n) <= Π(p(n))/p(n), i.e. Span(n) <= Π(p(n-1)), and some other more complicated (and smaller) terms which I don't have time at the moment to figure out. They're terms of the form p(i)^A - p(i)^(A-1) where p(i)^A is a piece of Π(p(n))/p(i).

5) In general, I think this means we can't really say anything about these cases. Specifically, if we divide Π(p(n)) by any two primes it might well be the case that the adjacent numbers are divisible by the two primes we've divided by.

6) I think that this boils down to a claim that there's always a "prime candidate" (with respect to primes p(x<=n+1) ) in any span of length 2*p(n+1). I don't know how to prove this (it may well be true). Note that even if this is true and, therefore, Span(n)<=2Span(n-1), we end up with Span(n) <= 2ⁿ. On the other hand, if there's always a "prime candidate" (with respect to primes p(x<=n+1) ) in any span of length 2*p(n+1), because p(n+1) <= 2*p(n) we have Span(n) <= 4*p(n).

If you'd like to continue this conversation (which I would be quite happy to do), I think we're distinctly in the realm of original research which means we should take it out of Wikipedia (my "email this user" link is enabled). The original question was "has anyone seen anything like this", and I'm starting to suspect the answer is no. -- Rick Block (talk) 15:19, 12 July 2006 (UTC)

BTW - there's a formula for the number of "prime candidates" in one iteration of the full pattern, which is ${\prod (p(i)-1)}$ from 1 <= i <= n. Since no more than two of these can occur in every 6 consecutive integers, and the pattern is symmetric about the midpoint, it's true that $span(n)<=({\prod p(i)})/2-3/2*{\prod (p(i)-1)}$. -- Rick Block (talk) 16:49, 12 July 2006 (UTC)

Also note, although it is perhaps not particularly useful for a proof, the "average" span is ${\prod p(i)}/{\prod (p(i)-1)}$, which grows pretty slowly (less than 9 for p(25) = 97). -- Rick Block (talk) 19:24, 12 July 2006 (UTC)