Before a once-warm lake starts to freeze, must its temperature be 4°C throughout at some point? This is a problem I just started puzzling over, and I felt this would be a good forum to check my reasoning.  So here are the relevant observations followed by my question:
Water achieves its maximum density at roughly 4°C. That is, water (including ice) at all other temperatures below or above 4°C is less dense. Since matter is ordered from top to bottom by increasing density, any 4°C water in a lake will be found at the bottom.
Temperature is a continuous property, and so the water in a lake must be arranged by temperature as well.  That is, there can be no regions of water with temperature 4° and 6° unless there is a region between them with temperature 5°.
So, my initial puzzlement arose from trying to imagine the temperature arrangement of water with temperatures from 3° to 5°. If 4° water is the most dense, it must be on the bottom of the lake, and both the 3° and the 5° water must be above it. However, if temperature is continuous, there must be 4° water between any 3° and 5° water. So, there is no way for these three temperatures of water to coexist without violating either the ordering of densities or the continuous distribution of temperature.
I suspect the coexistence of these temperatures in water is most likely possible, but it is short-lived.  I imagine some kind of convection current where the water eventually reaches equilibrium at 4°C, but the picture of this is pretty blurry to me.
So does it follow from this that for a relatively warm lake (temps from 10-20°C) to begin to freeze, all the water must reach 4° before any sub-4° temperature is reached? Otherwise, there would be a situation with 3-5° water coexisting. Right?
EDIT:
Here's an extension of this thought that begs for some testing. Since the ordering of densities occurs because of buoyant forces, which occur in a gravitational field, I wonder if the temperature profile of cooling/freezing water is significantly different in anti-gravity.  Based on the above observations, I would expect the temperature barrier at 4°C not to be observed.  Whoa!
 A: The only mechanically static situation is that at bottom of water column temperature is $T_\text{bottom} \le 4^\circ \text{C}$ and at top of the water column temperature is $0^\circ\text{C} \le T_\text{top} \le T_\text{bottom}$, with continuous drop between them.  Of course, there will still be heat transfer due to thermal conductivity of water and ice.  You could easily calculate the thickness of the ice, knowing the temperature of the air and assuming the temperature of the bottom of the sea/lake to be $4^\circ \text{C}$, knowing heat conductivities of ice and water as well as the depth of the water.
In fact this is quite a common situation in the oceans around the Arctic.  This strange property of the water enables life, as water at bottom of the ocean is cooling very slowly (heat transfer due to thermal conductivity is much smaller than heat transfer due to convection), so ice never reaches the bottom of the ocean.
In case of all other distributions of temperatures you shall have heat transfer due to convection too, making circular currents up and down.  This is extremely complex situation and you cannot solve it by simple non-differential calculus.
A: You have hit on the major explanation of the unusual thermal stability of surface-frozen lakes. The deep earth is temperature stable, since the surface seasonal fluctuations can't penetrate the heat by diffusion more than some meters into the deep ground. So the deep ground is at a temperature which is stable all year.
Advection only raises heat to the surface for temperatures higher than 4 degrees, it sinks higher temperature below 4 degrees. So at less than 4 degrees, the lake doesn't achieve thermal equilibrium well, you can only cool the lake by diffusion, so the coldness diffuses from the top of the lake with any advection hindering rather than helping, pushing the cold water up the other way, so freezing only happens at the top, and can only work its way down extremely slowly in a large lake. This makes the lake the same as the ground--- the heat flow is by thermal diffusion with no advection (at least not from the top), and the main body of the lake at a depth of more than a few meters is stuck at close to 4 degrees, the stable bulk temperature.

If you look at this linked paper there is a measured temperature profile in a partly frozen lake on page 297 (reproduced above), and you can see the nearly straight line at slightly over 4 degrees, with significantly higher temperatures only at the very bottom. The warm water at the bottom will have a small advection forcing, heating up the higher layers.
The advection velocity will be very slow for these infinitesimal density differences, but the lake is very big, so even a small density difference leads to very slow average flows. This advection can only mix warm water from the bottom with the middle, and cold water from the top with the middle, keeping the middle at 4 degrees. The situation is extreme in the case of the Apr 1987 measurement in fig 4 of the linked paper, where nearly the entire lake is at a sharp 4 degree straight line, when the top layer of ice is nearly thawed.
