Okay, here's a classic. I'm sure the geniuses round here will be quick to spot the flaw in this proof but I still like it.
Theorem: all horses are of the same colour.
Proof:
1: Let us first assume that any set of N horses is a set of horses all of the same colour. Call this set A.
2: Let us remove one horse from this set, to leave a set of N-1 horses. Call this set B. This set of horses is all of the same colour, and is of the same colour as the set A.
3: Now let us add another, different horse to this set. It is another set of N horses, so by the assumption in step 1, it is a set all of the same colour. It is of the same colour as the set B, and therefore of set A.
4: Now add the horse to set C that was taken out of set A in step 1, and call it set D. Since it is of the same colour as the horses in set C, D is a set of N+1 horses all of the same colour.
5: Any set of N+1 horses contains a subset of N horses, so any set of N+1 horses can be formed this way from sets of N horses. Thus if any N horses all have the same colour, then any N+1 horses are all of the same colour.
6: Now let N=1. It is self-evident that, when N=1, every horse in the set has the same colour, since any horse is the same colour as itself.
7: If all sets of N horses are of the same colour for N=1, then, by repeatedly applying the result of step 5, any N horses have the same colour for N=2, N=3, N=4... for all positive integers N.
8: Let N be the total number of horses in the world. All the horses in the world are of the same colour. QED.
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.
Here is a probability mess:
A parser for a fictional bytecode format has gotten desyncronized. Given a certain distribution (your answer should work no matter what it is) between instructions with various lengths, how many instructions on average need to be decoded before the parser resynchronizes by dumb luck?
4: Now add the horse to set C that was taken out of set A in step 1, and call it set D. Since it is of the same colour as the horses in set C, D is a set of N+1 horses all of the same colour.
I'm not sure that you mean what you've written there. No set was taken out of A in step 1, that's step 2. You haven't defined a set C anywhere, did you mean the one created in step 3?
I'd reject that "proof" based on the convoluted structure and the handwaving alone. If you have to reorder a proof until it makes sense, it's not a proof.
But your well disguised attempt at an induction falls flat, anyway. You've proven it for N = 1, you've proven the step from N to N + 1 for N >= 2, but you haven't proven it for N = 2. Your step isn't valid from 1 to 2, because you're talking about the color of an empty set of horses, which you haven't defined.
Here is a probability mess:
A parser for a fictional bytecode format has gotten desyncronized. Given a certain distribution (your answer should work no matter what it is) between instructions with various lengths, how many instructions on average need to be decoded before the parser resynchronizes by dumb luck?
I don't think it can be answered by that alone.
How is the length of an instruction encoded? If it's encoded in the first byte, we need to calculate the actual chances for that encoding to appear in the later bytes of the instructions.
If it's encoded as "first bit = 0: instruction ends here, first bit = 1: another byte follows.", it'll resynchronize at the next symbol.
Other encoding schemes yield different results.
How did it get desyncronized? Did you pick a random instruction, then a random byte except the first? Or did you just pick a random byte and start from there? The latter would make it more likely to start in a longer instruction.
Also, what happens if the parser gets an invalid (or unknown) instruction? Is there any immediate data inside the bytecode, and what's its distribution? I'd assume that unknown instructions are just skipped, and there's no immediate data.
That's right Bobo the King. There is one bit of neatening I can do to the proof. For the section where you discuss Pythagorean triples, you don't even need to invoke the formula for generating them. All you need to do is reason thus:
If x^2 + y^2 = z^2, then either:
x and y are both even, z is even
x is odd, y is even, z is odd
x is even, y is odd, z is odd
And in each case x+y-z is even.
Actually, my post originally said, "By a quick parity argument, it can be seen that either all three sides are even, or one leg is even while the other leg and hypotenuse are odd," which matches what you've written.
Unfortunately, we both overlooked the possibility that x and y might both be odd while z is even. Looking back, however, I see this doesn't affect the proof, so... uh... we're both right?
Hypothesis: All natural numbers are interesting.
Proof by contradiction: Let's assume that not all natural numbers are interesting. This means that there exists a natural number n which is the smallest uninteresting natural number. However, that fact is in itself interesting (it would be interesting to know which uninteresting natural number is the smallest one). Therefore no such n exists.
Unfortunately, we both overlooked the possibility that x and y might both be odd while z is even.
Technically, that's not possible. If x and y are odd, then x^2 and y^2 are 1 mod 4, so x^2+y^2 is 2 mod 4 and cannot be a square.
It's true that it doesn't affect your proof though. That being said, rhebus's proof above is a simple proof, and one that seems most intuitive.
No it's not.
I've honestly never understood the point or merit of these sort of hypotheses. There's also the one about whether the set containing all sets contains itself (IMO: yes, otherwise it doesn't contain all sets. If this is not allowed, then no such set exists).
It always feel like you are making an assumption (there exist boring numbers) and then saying that assumption must be wrong (this makes them interesting), as such your assumption must be wrong. While I get that this is pretty much what proof by contradiction means, you normally at least deduce something from your assumption.
Sorry for ranting, continue your mathses.
I've honestly never understood the point or merit of these sort of hypotheses. There's also the one about whether the set containing all sets contains itself (IMO: yes, otherwise it doesn't contain all sets. If this is not allowed, then no such set exists).
It always feel like you are making an assumption (there exist boring numbers) and then saying that assumption must be wrong (this makes them interesting), as such your assumption must be wrong. While I get that this is pretty much what proof by contradiction means, you normally at least deduce something from your assumption.
The point of these types of paradoxes is to point out (in jest) how ill-definedness wreaks havoc in mathematics, not to claim that these statements are somehow inherently useful (which they are obviously not).
I for one would be interested in knowing what the smallest uninteresting natural number is. Therefore you are wrong.
I've honestly never understood the point or merit of these sort of hypotheses.
It's this thing called "humor". You might have heard of it.
A slightly more semi-serious question: Can you generalize the proof for all rational numbers and all real numbers?
(Since rational numbers are countable, my intuition would be that yes. However, real numbers are a much harder beast.)
It's this thing called "humor". You might have heard of it.
I seem to have the same problem now that you sometimes have: seeming far more on the offense than you actually are. I'm not saying you're not allowed to indulge in applying (semi-)serious math to "silly" problems, I'm just curious as to why. FractalFusion's answer was precisely what I was asking for (and thank you for that).
Warp wrote:
A slightly more semi-serious question: Can you generalize the proof for all rational numbers and all real numbers?
(Since rational numbers are countable, my intuition would be that yes. However, real numbers are a much harder beast.)
I think we can fairly trivially generalize the proof to any set containing the natural numbers, by looking for the "smallest natural number that is not interesting".
A slightly more semi-serious question: Can you generalize the proof for all rational numbers and all real numbers?
Here's one for rational numbers. (Don't take me seriously.)
Warp's Theorem states that all natural numbers are interesting (see proof). An interesting number divided by another interesting number must surely result in an interesting number! And putting a minus sign on an interesting number also results in an interesting number. Therefore all rational numbers are interesting!
(Or a number n is "interesting" if it gives the unique smallest value of f(n) on some subset of the rational numbers where f is a given bijection between rationals and natural numbers. Warp's argument follows.)
As for real numbers, here's a not-so-valid argument that there exist uninteresting real numbers. An interesting number ought to be a definable number. Conversely, we can accept the notion that a definable number is an interesting number. Yet there are only countably many definable numbers. Therefore there exist uncountably many undefinable, and therefore uninteresting, real numbers.
Or just: "The set of real numbers is too large for anyone to care about all of them." Uncountability wins again.
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?
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.)
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.
Exactly. Any set of words of finite length over a finite alphabeth is countable. The reals are uncountable precisely because they contain every word of infinite length; cantor's diagonalization doesn't work otherwise. He constructs a symbol of infinite length not included in the enumeration, then he shows that said symbol belongs to the enumerated set. With finite words, you can do the first part, but the resulting symbol wouldn't belong to the initial set, so there's no contradiction.
Assuming finite proofs is not just a reasonable assumption, it's a requirement for any useful definition of "definable number". Otherwise, every real number could be defined by its infinite decimal expansion, which would make the definable numbers a rather boring set.
Is there some kind of relationship between undefinable numbers and transcendental numbers, or is the definition of "undefinable number" pretty much arbitrary?
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.
There is actually another notion of definable (or "interesting", if you will) called "arithmetical":
http://en.wikipedia.org/wiki/Arithmetical_number
Basically "arithmetical" in the article means "definable on Peano arithmetic" and "definable" in its article means... well, I don't know, but I assume "definable on ZFC".
Anyway, all these notions are hardly useful, and are merely the result (and not the cause) of the anthropic principle; basically, the natural result of asking "Which numbers are interesting?"
By the way:
Natural numbers ⊆ Integers ⊆ Rational numbers ⊆ Algebraic numbers ⊆ Computable numbers ⊆ Arithmetical numbers ⊆ Definable numbers
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).
Where do irrational and transcendental numbers fit?
By definition, irrational means not rational, and transcendental means not algebraic. They don't exactly fit into the hierarchy above. Of course, by the contrapositive, a number that is transcendental is necessarily irrational.
Warp wrote:
Any examples of non-computable numbers?
Constants related to the halting problem, like Chaitin's constant, are not computable numbers. Even if such a constant were to be given its first n digits, no algorithm can generate all of its remaining digits.
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.
As long as we're on this topic and I'm putting off work, I'd like to ask a fairly simple question.
Why do we care about irrational (or transcendental, or definable...) numbers? I'm a physicist by training and I've never cared if the number I am working with is rational or not (much like I've never cared whether I use a less-than or less-than-or-equal-to sign). There are some really elegant theorems concerning different classes of numbers, but at the end of the day, is any of it important? I genuinely want to know if anyone uses this stuff for even moderately practical purposes.
Why do we care about irrational (or transcendental, or definable...) numbers?
I'm sure there are many, many reasons to care about them, but one particular example that comes to mind is that understanding them helps us answer questions like "can you square a circle?" (Answer: No, because pi is transcendental.)
FractalFusion wrote:
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).
That got me thinking that using percentages with infinite sets can be a bit... misleading.
For example, consider the question: "How many % of all natural numbers have the digit '3' in their decimal representation? How many % do not?"
It's trivial to see that there are infinitely many natural numbers whose decimal representation do not have the digit '3' in their decimal representation. Yet when you do the calculation you end up with the (somewhat unintuitive result) that 0% of natural numbers do not have that digit, and 100% of them do.
This is because infinities mess up things...
