The crux of the matter is in step (9), where you state that Lim(H) = H. I don't see why this is true, and the justification you give "via (2)" is not illuminating to me. Why does x ∈ H imply x ∈ lim(H)? You use a complex argument, that I don't fully understand, to conclude that " Therefore G may be decomposed uniquely into an unrefinable, denumerable union of separated subsets G' with distinct right- and left-handed boundary points." Isn't the decomposition of G into sets with a single element such a decomposition? If not, what do you mean by saying a collection of sets is "separated"? Andy On Sun, Nov 20, 2016 at 1:27 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
<< Denote by Lim(S) the set of accumulation points of set S ; and define the height ht(S) to be the minimum n such that Lim^n(S) = { } is empty. Question: is ht(G) necessarily finite for every grunch G ? >>
Three weeks or so ago, I posed this supplementary to Dan's grunch puzzle; la grippe promptly gripped, and has only just relented sufficiently to permit preparing the answer (11) below. The argument is surprisingly delicate --- perhaps it might be simplified --- so paragraphs are numbered for ease of reference, elision, refutation, general derision etc.
The discussion employs set operators ∈ (member of), ⋃ (union), ⋂ (intersection), ⊂, ⊆ (proper/subset), since such symbols are apparently becoming more widely available to mail browsers. Please complain if still unable to decipher!
Fred lunnon
____________________________________________________________
(0) Given some real set S , define Lim(S) to be the set of accumulation points of S .
(1) Every x ∈ S can be classified as just one of: `ambidextrous' if all neighbourhoods of x contain y,z ∈ S with y < x < z ; else `left-handed' if all neighbourhoods of x contain y ∈ S with y < x ; else `right-handed' if all neighbourhoods of x contain z ∈ S with x < z ; else `isolated' if none of the above.
(2) Define a grunch to be any closed and bounded set of rational numbers. For any grunch G : G is denumerable since its points are rational; G is compact since closed and bounded; Lim(G) is also a grunch; Lim(G) ⊆ G .
*(3)* Required to prove that Lim(G) ⊂ G properly for nonempty grunch G . Assume that on the contrary G = Lim(G) ; then ---
(4) Via (2) every x ∈ G is an accumulation point of G , so no x is isolated.
(5) Gaps in G occur only between consecutive left- and right-handed points; otherwise some neighbour intrudes between them. Therefore G may be decomposed uniquely into an unrefinable, denumerable union of separated subsets G' with distinct right- and left-handed boundary points.
(6) Each G' is a grunch such that G' = Lim(G') also.
(7) Having no gaps, G' is dense: every x ∈ G' is ambidextrous except its boundaries!
(8) Via (6), G' is rational; but via (7) and compactness, G' includes all real numbers between its bounds. Via contradiction G' does not exist, so G is empty, proving (3) QED.
(9) Define the `omega-limit' of G , H == G ⋂ Lim(G) ⋂ ... ⋂ Lim^n(G) ⋂ ... For grunch G , via (2) H = Lim(H) ; so via (3), H = { } is empty.
(10) Assume G is a grunch with Lim^n(G) nonempty for all natural n . Using (3), for each n choose some x_n ∈ Lim^n(G) - Lim^{n+1}(G) ; then let x be some accumulation point of the infinite set {x_n} ⊆ G . Via compactness, x ∈ Lim^n(G) for all n , so x ∈ H ; and H is nonempty, contradicting (9).
*(11)* Hence assumption (10) was false: for any grunch G , the height ht(G) == min( n | Lim^n(G) = { } ) is finite.
(12) The following sequence of examples is instructive. For each n , denote by G(n) the dyadic rationals in the unit interval with at most n bits nonzero: formally, F(n) = { 2^(i_1) + ... + 2^(i_n) | 0 > i_1 > ... > i_n } ; G(n) = { 0 } ⋃ F(1) ⋃ ... ⋃ F(n) .
(13) Easily G(n) is a grunch, with Lim(G(n+1)) = G(n) , ht(G(n)) = n+1 .
(14) As n -> oo , the omega-limit H is the entire unit interval, expressed in binary; so as indicated by the proof of (3), extending its height to infinity crunches the grunch into continuity.
Fred lunnon, Maynooth 20/11/16
____________________________________________________________
On 10/28/16, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Rats --- I did get there, but too late (reinvigorated by a post-prandial snooze, combined with further editorial sanction ...) To restore my bruised ego, I shall propose a supplementary.
Denote by Lim(S) the set of accumulation points of set S ; and define the height h(S) to be the minimum n such that Lim^n(S) = { } is empty.
Question: is h(S) necessarily finite for every grunch S ?
Fred Lunnon
On 10/28/16, Dan Asimov <asimov@msri.org> wrote:
Yes, that's it. Nice solving! Fred ... and Andy.
The puzzle was on an old Putnam exam, from those halcyon days when they didn't feel compelled to ask questions about the integer of the year A.D. in which the test was administered.
—Dan
On Oct 28, 2016, at 10:06 AM, Andy Latto <andy.latto@pobox.com> wrote:
On Fri, Oct 28, 2016 at 10:29 AM, Dan Asimov <dasimov@earthlink.net> wrote:
So far, no one has submitted a correct solution.
The only thing I see missing from Fred's construction is that the sequence x_i might converge to an irrational > 0, rather than converging to 0.
But this is easily patched up. Choose x_{i+1} rational in (0, x_i/2) and not in H_{i+1}. This must be possible because H_{i+1} cannot contain all the rationals in this interval, since if it did and was closed, it would have to contain an irrational. Now the x_i are guaranteed to converge to 0 so the {x_i} with 0 added is a grunch that is not contained in any H_i.
>> On 10/27/16, Dan Asimov <asimov@msri.org <mailto:asimov@msri.org>> >> wrote: >>> Puzzle: Define a grunch to be any closed and bounded >>> subset of the real line R consisting entirely of rational numbers. >>> >>> True or false: There is a countable set of grunches such that >>> every grunch is a subset of one of them. >>> >>> Prove your answer.
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com