The Math Thread

[ískallin]

whoah... This is confusing...
(cough)nerds(cough)

It must be me thats stupid. Or is it anyone else?

[Petek]

I don't understand your objection to my solution.

There are uncountably many real numbers between 0 and 1. Each such number corresponds to a decimal expansion of the form 0.a_1 a_2 a_3 ... , where each a_i is an integer equal to 0, 1, 2, ..., or 9. (There is a slight ambiguity whether the decimal expansion is finite, or ends with 999..., but this doesn't affect the argument).

Thus, there are uncountably many sets of integers {a_1, a_2, a_3, ...} where each a_i is one of the integers 0, 1, ..., 9. Any two such sets have a finite intersection since each set consists of a subset of {0, 1, ..., 9}.

Petek

[KrazyHorse]

Originally posted by Petek
I don't understand your objection to my solution.

There are uncountably many real numbers between 0 and 1. Each such number corresponds to a decimal expansion of the form 0.a_1 a_2 a_3 ... , where each a_i is an integer equal to 0, 1, 2, ..., or 9. (There is a slight ambiguity whether the decimal expansion is finite, or ends with 999..., but this doesn't affect the argument).

Thus, there are uncountably many sets of integers {a_1, a_2, a_3, ...} where each a_i is one of the integers 0, 1, ..., 9. Any two such sets have a finite intersection since each set consists of a subset of {0, 1, ..., 9}.

Petek

What don't you understand? There is a difference between a sequence and a set. Your solution involves an uncountable number of sequences of integers and a finite number of sets of integers.

The question asked for an uncountable set of subsets of the integers, not an uncountable set of sequences of the integers. You have provided the latter, not the former.

[KrazyHorse]

{0,1,1}={0,1} in terms of sets.

[Petek]

Originally posted by KrazyHorse


What don't you understand? There is a difference between a sequence and a set. Your solution involves an uncountable number of sequences of integers and a finite number of sets of integers.

The question asked for an uncountable set of subsets of the integers, not an uncountable set of sequences of the integers. You have provided the latter, not the former.

OK, I understand now. Thanks for the correction.

Petek

[KrazyHorse]

Now, technically you could raise the same objection to my solution, but it only applies when two sequences converge to rationals (say you have R1 = 1, R2 = 2, qn = 2,1,1,1,..., vn = 1,2,2,2,2,....). In this case the set {qn} and the set {vn} are identical (namely {1,2}). However, we can avoid this by making all of our sequences strictly monotonically increasing. This ensures that we never double count. You could also note that the irrationals are uncountable and simply restrict yourself to them. In either case, we force all sets {qRn} to always be infinite, with a finite intersection between any two sets, showing that {qR1n} dne {qR2n} (assuming R1 dne R2)

[Peter Triggs]

I think this is simpler:

Let C be the set of real numbers between 0 and 1. Define

U = { {x} : x in C }

so that U is the set of unit sets of members of the continuum. Then U is uncountable since C is. But the intersection of any two members of U is empty, hence (trivially) finite.

Edit: Oops, well it would be except that I just reread the question and we're supposed to have sets of integers.

[KrazyHorse]

Find uncountably many sets of integers such that the intersections of any two of them is finite.

[KrazyHorse]

Though if you've managed to find a bijection between the integers and the reals I'm sure the fields prize commitee would be happy to hear about it....

[Lul Thyme]

Re: Re: The Math Thread

Originally posted by Petek


Does this work?

Consider

{a_1, a_2, a_3, ... : 0 <= a_i <= 9}

That is, the set of all sequences of integers whose elements are between 0 and 9.

These sequences obviously correspond to real numbers between 0 and 1 (by looking at the decimal representation .a_1 a_2 a_3 ...), and hence represent an uncountable collection. However, the intersection of any two such sequences is finite, because the elements of any two such sequences are contained in {0, 1, ... , 9}.

Well, the question asked for uncountably many sets,
you gave ONE set containing uncountably many elements, which weren't even integers as the question asked.
So didn't answer the question obviously.

EDIT: KH beat me to it.

[Lul Thyme]

Originally posted by Petek
Assuming that my previous reply is correct, here's another challenge:

Given any integer N, show that some integer multiple of N consists entirely of the digits 0 and 1.

For example,

2 x 5 = 10
3 x 37 = 111
4 x 25 = 100

etc.

Let x(N) be the number we're looking for.

Write N=N'*gcd (10,N); so gcd(N',10)=1.

Use Euler's totient theorem so that
10^(phi(N'))=1 (mod N')
So take x(N')=sum_{i=1}^N' (10^(phi(N'))i).
Clearly x(N') is divisible by N' and also of the required form.

Now take x(N)=x(N')*lcm(10,N).
Clearly x(N) is divisible by N and also of the required form.

[Lul Thyme]

Originally posted by KrazyHorse
Got it.

For every real number R there exists a sequence of rational numbers qn such that lim(n->inf)qn = R.

Now, any two distinct real numbers (R1 and R2) are separated by a distance |R1-R2| = d > 0 and have corresponding sequences qn and vn (respectively). Since qn converges to R1 there exists M1 s.t |R1 - qn| < d/2 when n>M1. Similarly, there exists M2 s.t. |R2-vn| < d/2 when n>M2. Therefore, if qm = vn either m I. Represent the aforementioned converging sequence of rationals to a real R as {qRn}. Our uncountable set of subsets is the union over all R of {b(qRn}}

Btw, when I go in reply with quote your message I can see it, but most of your proof doesn't appear for me.
Can somebody confirm this?

This is what I see
"For every real number R there exists a sequence of rational numbers qn such that lim(n->inf)qn = R.

Now, any two distinct real numbers (R1 and R2) are separated by a distance |R1-R2| = d > 0 and have corresponding sequences qn and vn (respectively). Since qn converges to R1 there exists M1 s.t |R1 - qn| < d/2 when n>M1. Similarly, there exists M2 s.t. |R2-vn| < d/2 when n>M2. Therefore, if qm = vn either m I. Represent the aforementioned converging sequence of rationals to a real R as {qRn}. Our uncountable set of subsets is the union over all R of {b(qRn}} "

[civman2000]

A somewhat more elegant (IMHO) solution to Petek's problem: consider the numbers 1, 11, 111, 1111, etc mod n. By the pigeonhole principle, two of them must be congruent mod n; the difference is then a multiple of n consisting of 0s and 1s.

[KrazyHorse]

Btw, when I go in reply with quote your message I can see it, but most of your proof doesn't appear for me.
Can somebody confirm this?

Sorry. I think it was trying to parse some of my < symbols as html tags. I think it's fixed now.