I'm not sure I disagree with anything p4wn3r says, but I'd like to say something in defence of constructivism: constructive systems are particularly noteworthy in the Curry-Howard correspondence. Many interesting type systems are no more powerful than intuitionist logic, and only constructive results are of interest to these type systems.
That said, there's an interesting result which shows that call/cc's type corresponds to Peirce's Law, from which classical logic follows. It then follows that if your system doesn't have a call/cc-like primitive baked in, you can't have a well-typed implementation of it from the simply typed lambda calculus.
Well, the formal system itself must be definable with a finite amount of information (or else it's not definable in practice; we cannot read an infinite definition in order to know all of its axioms. A formal system with an infinite definition would not be very useful.)
I can immediately define an uncountable set of formal systems: choose a real number in [0,1), call it r. Then formal system r consists of the countable set of definitions which define a number r+i, for integer i.
For any one of those formal systems, almost all real numbers are undefinable within the system. But all real numbers are definable in exactly one of those formal systems.
Without a formal system like this, you can end up with paradoxes by defining numbers like "the smallest positive real number without a definition".
The example is a bit unfortunate. Unlike the integer case, the subset of positive undefined reals doesn't need to have a minimum. It does have an infimum, but the infimum doesn't need to be a member of the set, and could be a defined number.
Good catch, you're perfectly right here. And in fact if we take our formal system to be algebraic numbers, the smallest non-algebraic positive real number doesn't exist. Hmm. I'm pretty certain one *can* make a paradox here, but it's proving harder to achieve than I thought. I think you could use the axiom of choice and say "an arbitrary undefined number" but that's somehow unsatisfying, and also I feel I'm getting above my pay grade (I'm a computer scientist really, not a mathematician).
I just find it fascinating that there exist real numbers that cannot be expressed in any way.
The set of all real numbers that can be expressed with a finite definition is countable (pretty much by definition). Since this doesn't cover all real numbers (because they are uncountable), this means that there are real numbers that cannot be expressed in any way (because you can't literally write an infinite expression to define it).
In fact, the set of real numbers that cannot be expressed in any way is larger than the set of numbers that can.
I think that's fascinating.
This reasoning is pretty good, but to make it work you have to firm up what you mean by "definition", which will normally require you to define some sort of formal system for defining things; polynomials are an example of such a system, which defines algebraic numbers. Without a formal system like this, you can end up with paradoxes by defining numbers like "the smallest positive real number without a definition".
What you end up with is a statement closer to "In any formal system for creating finite definitions of real numbers, almost all real numbers are undefinable." Which is still fascinating, but leaves open the possibility that any particular real number undefiniable in a particular formal system might have a definition within another formal system.
This is all very closely related to Gödel's incompleteness theorem and Russell's paradox.
Without loss of generality, assume that the ratio is expressed in simplest form. So we have long side length L, short side length S, and gcd(L,S) = 1. Also assume that the long cushions are aligned with the x-axis.
Consider the long cushions first: at each bounce, the ball will go in the pocket if the total distance (scalar distance, not vector displacement) travelled in the x-axis ≡ 0 (mod L). At each bounce on the L-cushion, the x-axis distance travelled increases by S. Since gcd(L,S) = 1, this condition will first be met when the total distance travelled is L×S, after L - 1 bounces on the long cushions (not counting the ball finally being potted as a bounce).
A similar argument shows that there will be S - 1 bounces on the short cushions.
The total is therefore L + S - 2, once L and S have been expressed as the simplest ratio.
If the long cushion is an irrational number times the length of the short cushion, the ball will never be potted. (Of course, we're assuming pointlike balls and perfect pockets here, not to mention perfect cushions.)
They're now advertising a commentary live stream, Monday 14th 20:00 CEST twitch.tv/dabigbooi if you're interested. I won't be able to tune in at that time, but damn I bet it'll be interesting.
You can't simply "square both sides". That's not a valid operation (that keeps the equality). You have to multiply both sides by the same number, and you did not do that there.
You know, I read your question and decided not to answer it for one reason: it was horribly worded, in such a way that "pie" would be just as reasonable an answer as any. You are doing it again.
Please be civil. Relativity is a difficult subject; it can be difficult for those new to it to distinguish between questions which are meaningful but bizarre and those which are completely meaningless. An example of a meaningless and yet intuitively sensible question is "what speed is the Earth *really* travelling at?"
Your response is in general good: there is little else to be done than to point out where the question is meaningless or underspecified, and ask for clarification -- but use of words such as "horrible" and "mangled" can make this thread feel like a less safe place for people to ask questions.
So the original problem could be made slightly "harder" by phrasing it as: "Prove that every natural number can be written as the sum of unique, non-consecutive fibonacci numbers."
This is related to the numerical base phinary: using the golden ratio as a number base (as opposed to an integer as in binary or decimal), you can come up with a representation of any integer using only digits 0 and 1 and never using the sequence 11.
There is a close relationship between the fibonacci numbers and the golden ratio: the ratio between consecutive fibonacci numbers (1/1, 2/1, 3/2, 5/3, 8/5 etc) asymptotically approaches the golden ratio; and the formula for the fibonacci numbers uses the golden ratio.
You can easily lower the upper bound to 5 by ommiting the weight of value 1. You could only compare to even values, but if unknown weigth X is heavier than known weights Y and Y+2, X is obviously Y + 1.
This wasn't quite what I had in mind; but I suppose according to the problem as stated, you could do that. You can do better than 5, though, and even get an exact weighing rather than inferring from multiple inexact weighings.
The proof is based on contructing an algorithm to generate such a decomposition, proving the algorithm always picks unique fibonacci numbers, and proving it always terminates. It is a greedy algorithm, which is an algorithm which works by trying to take the biggest piece available at each stage. Making change for an amount of money is generally done by a greedy algorithm. Greedy algorithms don't always work for all problems, but for this problem, it works perfectly.
The algorithm-based proof operates "top down" because you start from a target number N and reduce the problem to a smaller problem of finding a decomposition for (N-Fn). (Note that N and n are different numbers; sorry about that. K would have been a better choice.) thatguy's proof is related but it's "bottom up" because it starts by proving a base case for 1 and proves each subsequent case by induction: the inductive step is "if it works for numbers < Fn, it will work for numbers < Fn+1".
I suspect my proof feels more natural to me because I'm a computer scientist by training, and I was thinking in terms of algorithms & termination; proof by induction feels like a more mathematics-style proof.
Interestingly, this algorithm will either only use even-indexed or odd-indexed fibonacci numbers.
If that observation is correct, would it mean that every natural number can be written as the sum of unique even-index or odd-indexed fibonacci numbers?
Hmm, actually now I think I was wrong about that. If the algorithm picks Fn then it won't pick Fn-1; but there's nothing to stop it picking Fn-3. I guess there's a weaker statement: the algorithm won't pick two consecutive fibonacci numbers.
I can at least give an upper bound. If you use weights of powers of 2, then with 6 weights you can represent any value between 1 and 63 as a "binary number" using the weights.
I don't know, however, if when using 1-40 in particular, some other scheme would allow 5 weights to be used.
As you suspect, there is more to this problem. There are more configurations of weights in the scales than you have considered so far.
Prove that every natural number can be written as a sum of unique (ie. non-repeated) fibonacci numbers.
Proof sketch: use a greedy algorithm.
Proof: for a given number N. Find the greatest fibonacci number less than or equal to N; call this Fn. Now, N < Fn+1 = Fn-1+Fn, so N-Fn < Fn-1. Therefore, the algorithm can be repeated while only ever using strictly smaller fibonacci numbers, maintaining the uniqueness constraint. The algorithm terminates because N gets strictly smaller with each step while remaining a natural number; and because for every N ≥ 1 there is a Fn ≤ N (because F1 = 1); and because the natural numbers are well-ordered by <.
Interestingly, this algorithm will either only use even-indexed or odd-indexed fibonacci numbers.
On a similar note: Suppose you have a two-pan balance. What is the minimum number of weights you need to measure items of every integer weight from 1 to 40?
I think that's a very good response. I'm tempted to go in two directions with it.
First, I could say, "Good example. But it's real."
It's definitely not real, based on our knowledge of electrons. There is no "thing" that is actually moving in the direction of conventional current.
Second (and this is more my inclination), I could try to invoke Occam's razor. If Benjamin Franklin had happened to decide that amber gains a positive charge and glass is left with a negative charge when they are rubbed together, we wouldn't have this problem today. We flipped a coin a few centuries ago and got the "wrong" result.
This is what makes it an interesting example. As you point out, there are two largely equivalent theories, with conventional current and counter-conventional current. Both make the same essential predictions. Both claim the existence of a concept called "current" and that it moves in a direction; but they disagree on the direction it moves. We now know that current is caused by the motion of charged particles, and that these particles are (almost) always negatively charged.
Actually, it gets even more interesting when you consider electric current flowing through an ionic solution in electrolysis -- then there are two types of charge carrier, the positive ions and the negative ions, and the conventional current somehow combines the action of both types of particle flowing in opposite directions. I guess in this light, conventional current is an aggregate quantity rather than the flow of a single type of particle.
This whole debate is the subject of scientific realism (the position that scientific theories describe the real world) versus anti-realism (entities which can't be directly observed, like electrons and quarks, don't really exist, even if they are useful) versus instrumentalism (scientific theories should be judged based on the quality of their predictions, rather than their correspondence or otherwise to reality). It's interesting, although it can be overlaboured sometimes.
I'm very interested, however, in where you draw the line. What is something that you consider useful but not "real"?
I'm going to suggest an answer: conventional current. That is, the classical notion that current flows from a positive terminal to a negative terminal. We now know that the current-carrying particles are themselves negatively charged, and they flow from negative to positive1. But you can get a long way in predictive power with a theory that assumes current flows from positive to negative. It's incredibly useful -- but is it real? The fact that we now know of the existence of electrons puts an interesting spin2 on it. Suppose we hadn't discovered electrons: would conventional current be more real than it is now that we have discovered them?
1Yes, you also get holes in p-type semiconductors; but really it's still electrons carrying the charge
2A spin of ½ (ho ho).
There's a similar result about the fact that the wind is always calm somewhere. No matter what the pattern of wind is globally, there is always a point at which there is no wind.
EDIT: I think I got it. First: show that the equal temperature contour joins a point with its opposite: this can be done by a symmetry argument because f(point opposite x) = -f(x), so the contour will join two symmetrical halves of the sphere and each point opposite a point on the contour will itself be on the contour.
I think this doesn't cover the case where there are disjoint zero contours.
I never claimed that the contour was the only zero contour (there may well be others); but the symmetry argument demonstrates that there is a unique zero contour which splits the sphere into two equally-sized regions, and that this zero contour must be invariant under transforming each point to its opposite. Even if other zero contours exist, only one can have this property -- the other contours are transformed into different contours on the opposite side by this transformation. (If there were two contours with this property, they would necessarily cross)
Let b(θ, t) be the half-great-circle on the sphere going from latitude 90° (at t=0) to latitude -90° (at t=1) along the longitude angle θ. Then h(b(0°, t)) is a path on two-dimensional space from a point (r,s)≠(0,0) to the point (-r,-s), not through (0,0). Likewise, h(b(180°, t)) also goes from (r,s) to (-r,-s), but on the "opposite side" of h(b(θ, t)). The argument is then that, as θ ranges from 0° to 180°, h(b(θ,t)) undergoes a "continuous deformation", and that is not possible without going through (0,0).
This is good, too. I'm not sure I understand the formalization (what does φ(t) mean?) but the proof sketch is good enough for me.
Prove that there are always two points on opposite sides of Earth with the exact same temperature.
There is actually a two-parameter version of the question (e.g. Prove that there exist two points on opposite sides of the Earth with the exact same temperature and elevation.)
Ooh I wasn't sure until you gave this hint.
Let T1 be the minimum temperature on the sphere and T2 be the maximum temperature. Now consider the function f(lat,long) of temperature at a point, minus the temperature at the opposite point on the globe. f is positive in a region around T2, and negative in a region around T1. Because f is a sum of two continuous functions, it is itself a continuous function, and so there must be a zero contour. Any point on this contour has the property that it has the same temperature as the opposite side of the sphere.
Now, for the two-variable version: the same argument shows that there exists a contour line of equal antipodean elevation. But I'm not sure how to demonstrate that these contours must cross. I have a feeling that you need to show at least one contour exists which connects two points on opposite sides of the earth for each variable; two such contours in different variables would have to cross. But I'm not sure how to show that.
EDIT: I think I got it. First: show that the equal temperature contour joins a point with its opposite: this can be done by a symmetry argument because f(point opposite x) = -f(x), so the contour will join two symmetrical halves of the sphere and each point opposite a point on the contour will itself be on the contour.
Then perform the same argument on elevation, but constrained to the contour line: form the function g(x) = elevation at x minus elevation at point opposite x. At maximum elevation, this function is positive, at minimum elevation, it's negative, therefore there must be a zero on the contour. This point has equal temperature and elevation to the point opposite.
By the time you get to "computable", there isn't much left to consider (99.9999...% of the real numbers we care about are computable).
While this is true, it is also true that almost all numbers are not computable and not definable -- precisely because the set of computable (or definable) numbers is countable.
So if you were to randomly pick a real number (say from the uniform distribution from 0 to 1, though the particular distribution hardly matters), you will almost surely (ie with probability 1) get an undefinable, noncomputable, trancendental, irrational number.
Is there some kind of relationship between undefinable numbers and transcendental numbers, or is the definition of "undefinable number" pretty much arbitrary?
As the article states, the set of definable numbers contains all algebraic numbers. If algebraic => definable, then by contrapositive, undefinable => trancendental; so all undefinable numbers are trancendental.
But some trancendental numbers are definable -- including e and pi.
One thing caught my eye in that article:
Wikipedia wrote:
the set of all definable numbers is countably infinite (because the set of all logical formulas is)
No further argument for this claim seems to be given. It seems obvious at first, but in fact I'm not so sure.
For instance, one would hastily think that the set of all possible infinite combinations of digits is countably infinite (because they are just combinations of symbols from a finite set). However, that's not so, and Cantor's diagonal argument (which the article refers to immediately after) demonstrates this.
If the set of all possible combinations of digits is uncountably infinite (as per Cantor's diagonal argument), then why isn't the set of all possible logical formulas as well?
I think the point of disagreement between you and the article is that the article assumes a formula can't contain an infinite number of symbols; it has to be finite. I think this is a reasonable assumption.
(We may sometimes deal with infinite sums, but the only ones that we can actually understand are the ones which have some sort of pattern, and therefore can be expressed in a finite number of symbols using sigma notation.)
A polygon has vertices with integer coordinates (in 2 dimensions) and integer length edges. Show that the perimeter is an even integer.
I want to try a slightly different tack for the proof, though it uses much of the same ideas:
If all edges are rectilinear, the perimeter is an even integer.
If there is at least one diagonal edge, you can transform the polygon by replacing the diagonal with two rectilinear edges, while preserving the parity of the perimeter. This is because for diagonal length z and rectilinear sides x and y, z has the same parity as x + y by pythagoras.
Therefore, any polygon can be transformed into a rectilinear polygon with the same parity. Since all rectilinear polygons have even parity, all polygons have even parity.