Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[silverspawn]

Any specific number should be reached at some point by adding more subgroups with this property, right? No matter how your infinite sum looks like.

[Witherweaver]

Isn't it more direct to just take an arbitrary natural number K and ask if it can be expressed in the form described?

[Watno]

Say first is that all even numbers have the property.
Next, all numbers 4n+1 have the property.
Next, all numbers 8n+3 have the property.
Next, all numbers 16n+7 have the property.
Next, all numbers 32n+15 have the property.

And so on.  You can represent this as 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + ..., which is one.

You can't.

[sudgy]

However, if you have a sequence of subsets of of N that covers N, and you prove a statement for each such subset, it holds for all natural numbers.

Even if it requires an infinite number of subsets?

[Witherweaver]

If not, then yeh answer is obviously no.  Take the property to be "not X", where X is something not of that form.

[SirPeebles]

However, if you have a sequence of subsets of of N that covers N, and you prove a statement for each such subset, it holds for all natural numbers.

Even if it requires an infinite number of subsets?

Yes. Let n be an arbitrary natural number. Since our collection subsets covers N, we know that n belongs to one of our subsets. But we've proved that every element of the subset has our property. So n has the property.

[Watno]

However, if you have a sequence of subsets of of N that covers N, and you prove a statement for each such subset, it holds for all natural numbers.

Even if it requires an infinite number of subsets?

Yes.
If a statement holds for all elements of each set of a family of sets, it holds for each element of the union as well.

[scott_pilgrim]

You could just start by proving that any natural number can be written as (2^k)n+2^(k-1)-1, and then prove that if a number can be written like that, then it has that property.  That should make it obvious that every natural number has that property, without thinking about infinite unions.

[Watno]

Aren't you implicitely thinking about infinite unions when you do that?

[scott_pilgrim]

Aren't you implicitely thinking about infinite unions when you do that?

Probably, but I think it might be a more intuitive way of thinking about it for some people.

[sudgy]

You could just start by proving that any natural number can be written as (2^k)n+2^(k-1)-1, and then prove that if a number can be written like that, then it has that property.  That should make it obvious that every natural number has that property, without thinking about infinite unions.

The problem that I have though isn't in the form of 2^kn+2^k-1-1.  I just used that as an example.  The problem I have is of the form 2^kn + c, where c takes on a whole bunch of values that don't seem to have any rhyme or reason.  (I've found a way to compute c, but it's really really complicated).  However, the number of c's that work for a specific k seems to be easier to find, so I was looking for another way to do it.  My idea was to use the number of c's for a given k (let's call it c_k) divided by 2^k (this fraction is basically the fraction of natural numbers it includes) and summing them up:

(c_k1)/(2^k₁) + (c_k2)/(2^k₂) + (c_k3)/(2^k₃) + (c_k4)/(2^k₄) + ...

Also, when I say a fraction of the natural numbers, say a/b, I'm saying that if you picked b consecutive natural numbers, there would be a of them.


So how would I prove that the union of all of these subsets is the natural numbers?

[Witherweaver]

But again it depends on the property if not every natural number can be written as n*2^k + c_k.

If every natural number can be written this way, and every number of this form has property P, then certainly every natural number has property.  However, if there is a natural number N that cannot be expressed as n*2^k + c_k for any n, k, then certainly there is a property P that does not translate from the subset to all naturals.  The trivial property is "m has property P if m is not equal to N".

[Cuzz]

You could just start by proving that any natural number can be written as (2^k)n+2^(k-1)-1, and then prove that if a number can be written like that, then it has that property.  That should make it obvious that every natural number has that property, without thinking about infinite unions.

The problem that I have though isn't in the form of 2^kn+2^k-1-1.  I just used that as an example.  The problem I have is of the form 2^kn + c, where c takes on a whole bunch of values that don't seem to have any rhyme or reason.  (I've found a way to compute c, but it's really really complicated).  However, the number of c's that work for a specific k seems to be easier to find, so I was looking for another way to do it.  My idea was to use the number of c's for a given k (let's call it c_k) divided by 2^k (this fraction is basically the fraction of natural numbers it includes) and summing them up:

(c_k1)/(2^k₁) + (c_k2)/(2^k₂) + (c_k3)/(2^k₃) + (c_k4)/(2^k₄) + ...

Also, when I say a fraction of the natural numbers, say a/b, I'm saying that if you picked b consecutive natural numbers, there would be a of them.


So how would I prove that the union of all of these subsets is the natural numbers?

I may be misunderstanding, but you need some measurement of the overlap of these subsets. Trivial example: Let P be the property "N is even or N = 2k for some natural number k." 1/2 of all natural numbers are even, and 1/2 are of the form 2k for some natural number k. 1/2 + 1/2 =1 but certainly not all natural numbers have property P.

[Polk5440]

summing them up:

I reading into things and thinking you might need this: Remember, if you have two sets A and B, the number of elements in A or B = number of elements in A + number of elements in B - number of elements in A and B.

[sudgy]

In this case, none of the elements in the sets overlap.

[SirPeebles]

sudgy, I haven't read your request too closely, but here is an example to watch out for:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...

and so forth. Each natural number eventually turns red except for 1.

[sudgy]

sudgy, I haven't read your request too closely, but here is an example to watch out for:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...

and so forth. Each natural number eventually turns red except for 1.

Now I'm curious, what's the difference between this example and my earlier one that makes mine include all the numbers while yours doesn't?  I'm not just talking about how yours is 2^kn+2^k-1+1 while mine is 2^kn+2^k-1-1, but I'm more looking for something that says why mine covers the natural numbers while yours doesn't.

[Haddock]

sudgy, I haven't read your request too closely, but here is an example to watch out for:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...

and so forth. Each natural number eventually turns red except for 1.

Now I'm curious, what's the difference between this example and my earlier one that makes mine include all the numbers while yours doesn't?  I'm not just talking about how yours is 2^kn+2^k-1+1 while mine is 2^kn+2^k-1-1, but I'm more looking for something that says why mine covers the natural numbers while yours doesn't.

This should be fairly clear, no?  Powers of 2 start at 1, so adding 1 will definitely mean you miss something, while subtracting is not a threat.

Indeed, if you add a large enough constant you're pretty much always going to miss some early numbers.  This is the main problem with the question, to some extent. 

If you can't prove that your set of sequences covers everything, you're likely at the very least to miss finitely many numbers at the start. 

For certain sequences you could prove that you cover almost all naturals, I'm sure.  The "almost all" would sometimes mean "all but finitely many", and sometimes mean something more measure-theoretically complex.

It really does depend on the sequences in question.

[Cuzz]

Also, when I say a fraction of the natural numbers, say a/b, I'm saying that if you picked b consecutive natural numbers, there would be a of them.

Can you state this condition more carefully using quantifiers?

[sudgy]

Also, when I say a fraction of the natural numbers, say a/b, I'm saying that if you picked b consecutive natural numbers, there would be a of them.

Can you state this condition more carefully using quantifiers?

I'm more of an amateur mathematician (that's why I ask so many questions here), and haven't really heard of quantifiers before, but I'll try to state it a bit more formally.

A subset S of N contains a fraction a/b of N iff for all subsets T of N with length b containing consecutive integers, the size of T ∩ S is a.

[Haddock]

Also, when I say a fraction of the natural numbers, say a/b, I'm saying that if you picked b consecutive natural numbers, there would be a of them.

Can you state this condition more carefully using quantifiers?

I'm more of an amateur mathematician (that's why I ask so many questions here), and haven't really heard of quantifiers before, but I'll try to state it a bit more formally.

A subset S of N contains a fraction a/b of N iff for all subsets T of N with length b containing consecutive integers, the size of T ∩ S is a.

I can say fairly confidently that that's not going to be a good definition.  There are too many edge cases.  Your example with arithmetic progressions is OK because they're nice evenly laid-out sequences.  In general, that's not what a mathematician would mean if they said S was a proportion a/b of the naturals.

That said, for your question specifically your definition might be OK, since you're only working with arithmetic progressions.  In that picture, you just need to know how much overlap there is between the progressions.  (I suspect there'll be too much overlap, but I haven't looked closely at your specific sequences)

[Witherweaver]

I feel like the only natural definition of a subset A being a proportion X of its superset B is |A|  = X*|B|, where |.| is some measure and 0 \leq X \leq 1.  When |B| is an infinite ordinal, I think these operations still make sense; maybe it should be |B|= Y*|A|, where Y >= 1. (If |.| is the usual cardinality and B is the natural numbers, |B| is the first infinite ordinal, and X can only be 0 or 1 depending on if A is finite or not.)

[Haddock]

I feel like the only natural definition of a subset A being a proportion X of its superset B is |A|  = X*|B|, where |.| is some measure and 0 \leq X \leq 1.  When |B| is an infinite ordinal, I think these operations still make sense; maybe it should be |B|= Y*|A|, where Y >= 1. (If |.| is the usual cardinality and B is the natural numbers, |B| is the first infinite ordinal, and X can only be 0 or 1 depending on if A is finite or not.)

This might be a valid definition but it is not the only natural one, at least not for subsets of the naturals (or subsets of any countable ordered set).

The definition I have seen (and/or used) most often for subsets of N is (variants of) the following:

X (a subset of N) has density d if
Limsup (|X intersect {1,...,N}| / N) = d,
the limsup being taken as N --> infinity.

See https://en.wikipedia.org/wiki/Natural_density

[Witherweaver]

I feel like the only natural definition of a subset A being a proportion X of its superset B is |A|  = X*|B|, where |.| is some measure and 0 \leq X \leq 1.  When |B| is an infinite ordinal, I think these operations still make sense; maybe it should be |B|= Y*|A|, where Y >= 1. (If |.| is the usual cardinality and B is the natural numbers, |B| is the first infinite ordinal, and X can only be 0 or 1 depending on if A is finite or not.)

This might be a valid definition but it is not the only natural one, at least not for subsets of the naturals (or subsets of any countable ordered set).

The definition I have seen (and/or used) most often for subsets of N is (variants of) the following:

X (a subset of N) has density d if
Limsup (|X intersect {1,...,N}| / N) = d,
the limsup being taken as N --> infinity.

See https://en.wikipedia.org/wiki/Natural_density

That makes sense, right.  My way doesn't let you usefully compare subsets of naturals very well, since the relative measure is either 0 or 1.

[Cuzz]

I feel like the only natural definition of a subset A being a proportion X of its superset B is |A|  = X*|B|, where |.| is some measure and 0 \leq X \leq 1.  When |B| is an infinite ordinal, I think these operations still make sense; maybe it should be |B|= Y*|A|, where Y >= 1. (If |.| is the usual cardinality and B is the natural numbers, |B| is the first infinite ordinal, and X can only be 0 or 1 depending on if A is finite or not.)

This might be a valid definition but it is not the only natural one, at least not for subsets of the naturals (or subsets of any countable ordered set).

The definition I have seen (and/or used) most often for subsets of N is (variants of) the following:

X (a subset of N) has density d if
Limsup (|X intersect {1,...,N}| / N) = d,
the limsup being taken as N --> infinity.

See https://en.wikipedia.org/wiki/Natural_density

And for this definition, the thing sudgy is trying to show is most certainly false because you could always remove some infinite set of density 0. But I don't know how helpful that is.