You are not missing anything. It is true, that every cube contains a rational point, but most squares (or circles) have no rational point. Hence only aleph-zero many cubes.
OTOH, you can divide any cube further to the infinite number of disjunct cubes. Infinitely many times.
Now, if you can organize these divisions in such a way, that those infinities build up to more than aleph-zero cubes, the ZF is down.
I don’t say it’s possible, it just looks like slightly probable, due to the infinite divisibility of cubes. Which can be misleading, but maybe not.
I thought you wanted a set of cubes whose volumes don’t intersect with each other. (Then this set can’t be uncountable because each volume contains a rational point.) I don’t understand what you mean by replacing cubes… Can you explain the problem once again?
Assumed, that the ZF is consistent, you are right, of course. The fact, that there are rational points inside every cube, and that those cubes have no common volume, only common surfaces (lines, points) perhaps—is enough to state that there are at most aleph-zero of them.
But, if the ZF is not consistent, there may be a way to encode every real number between 0 and 1 with some peculiar cubic subdivision of 3D space.
You can easily encode every real between 0 and 1 via dividing (even a finite volume of) 3D space into disjunct 2D circles.
Perhaps, just perhaps, it is possible to replace those circles with cubes and spheres, given the infinite volume you have.
People have attacked the consistency of ZF with much more powerful tools and failed. Your attack wouldn’t sound promising to these people, because it already sounds unpromising to me. Each further minute of your time spent on this problem would be a failure of rationality.
If you want another problem that’s really fun, prove or disprove that every division of the square into triangles of equal area will have an even number of triangles :-)
Strongly agree. This problem [EDITED to add: I mean Thomas’s, not cousin_it’s] sounds about as much worth working on as one that says: “Can you find positive integers x,y,z such that x^3+y^3=z^3? If so, ZF is broken!” No, you can’t; the proof isn’t all that difficult (though harder than the one for Thomas’s cube-division question); the fact that the answer is no unless ZF is broken is just another way of saying “the answer can be proved to be no”. I am not much interested in searching for solutions to problems that have been proved to have no solutions.
Well, it hasn’t been proved, that this problem has no solution.
If you ask me, at least since the invention of the Yablo’s paradox, the ZF is mortally wounded. But that’s just me and some others. Or better, some others and me.
I am only probing around, if there is a way to reformulate this paradox in some different contexts.
If you ask me, at least since the invention of the Yablo’s paradox, the ZF is mortally wounded.
Well, there’s nothing revolutionary about that. If you don’t like ZF, then make up your own set of rules. I can show you how to create a different set theory in every topos.
ZF is not some authority that says what is true and what is not. It’s simply a model that people have found very useful in the foundation of mathematics, which has then blossomed into a discipline of its own.
Yablo’s paradox does not lead to any problem in ZF and there’s no reason to expect any version of it would.
The situation you’re in now is as pure a test of LW rationality as you’ll ever come across. Saving people from mistakes like yours, which defend themselves by feeding on your wishes, is pretty much why LW exists. Read the crackpot offer post. All the tools you need are right here.
Sometimes you win the lottery too, but that doesn’t mean buying lottery tickets is a good idea. You must evaluate your chance, not just say there’s a chance. For this problem you have both inside view (comments from people who know math) and outside view (examples of math cranks) saying your chance is very low.
For what it’s worth, I’m treating this conversation as a test. How much chance does rationality have against a strong desire, in a situation that’s 100% in favor of rationality, and is there any way for it to avoid losing.
What makes you think, that the next Monday I will still remember this problem?
I will come with another crackpottery, or even some problem you are going to solve, as it has happened already.
And I also don’t see the necessity to actually find a crack in the ZF or to immediately find a solution for a problem posted? The problem you have presented a few days ago, it was several years before its solution. I’ve Googled it.
Most problems posted worldwide are too trivial to even bother. Some are interesting to play with. Some are just too tough.
There’s a well known puzzle called duck and fox. A duck starts at the center of a circular pond and can swim with speed 1. On the shore there’s a fox who can run with speed 4. Can the duck reach the shore without getting caught by the fox?
As it is, the puzzle is pretty easy. But if you generalize it to multiple foxes that can use coordinated strategies (say, with speeds 2 and 3) it becomes much harder. If anyone can find a necessary and sufficient condition on fox speeds that allow the duck to escape, even for just two foxes, that’d be really cool.
I don’t think it’s equivalent. The duck can move freely inside the circle, while the fox can only stay on the circumference. Anyway, try to solve the 2 and 3 case.
Imagine a rating system for movies where Bob the reviewer watches a movie and declares “this is in the top three movies I will see this year”. Then he watches another movie and says “this is in the top two movies I will see this year”. Then he watches another movie and says “this is in the top two movies I will see this year”. Then he watches another movie and says “this is in the top three movies I will see this year”. But with this last statement his credibility is gone, because he’s claimed that four movies will be in the top three or better. Thus we will say that the “longest credible prefix” of the list [3,2,2,3] is [3,2,2].
The puzzle is to write an algorithm that accepts a list of integers and returns the length of its longest credible prefix, whose asymptotic complexity is as good as possible. (I have found an answer that’s extremely fast, but no proof that it’s fastest.)
I can do time O(n^2), where n is the length of the list. Perhaps the “extremely fast” algorithm you have is O(n log n)? Surely O(n) must be impossible.
Just to check we are formalizing in the same way, do you agree that O(n) is a lower bound? Because the list [1,2,...,n] has longest credible prefix of length n, but if we reduce any of the first n-1 elements by 1 then the length of the longest credible prefix is reduced. So we at least have to spend O(n) time looking at the first n-1 elements.
“this is in the top three movies I will see this year”
He can’t say that. He doesn’t even know how many movies he is going to see.
If he knows, that he is going to watch another N movies this year, he can only say “this is in the top N+1 movies I will see this year”. If that was the best movie so far.
The problem statement should be taken on face value, not argued with. But if you’re interested in the motivation, I was trying to design a review system that wouldn’t suffer from score inflation and payola (“every decent movie is 4 stars out of 5”). The problem you see is in fact the whole point. If you don’t feel confident enough that a movie will be in your top 3, say that it will be in your top 10. Your lack of confidence is an important signal of your true beliefs about the movie and viewers deserve to know it :-)
You mean, you can’t divide 3D space into cubes, such that they have no common volume, and that there would be more than aleph-zero cubes?
Yes, his proof is well based on the fact that every cube has to contain a rational point not shared with other cubes. Because there are only aleph-zero such rational points in an infinite 3D space, there may be at the most aleph-zero such cubes.
That’s fine.
But what if, God forbid it, it’s also possible to code every real number with a cubic subdivision of that space?
Then we’ve proved A (as cousin_it has done) and proved NOT A.
We can’t have it.
Just as we can’t have a true and the same time false sentences in Yablo’s paradox.
“You mean, you can’t find three positive integers, cube them, and have the sum of two equal to the third? Yes, the proof is well based on the method of infinite descent. That’s fine. But what if, God forbid it, it’s also possible to find three positive integers with that property? Then we’ve proved A and proved NOT A. Just as in Yablo’s paradox.”
Yablo’s paradox gives no more reason to expect blatant contradictions in cousin_it’s cardinality argument than in Fermat’s infinite descent proof. What you’re saying is, in effect: Because of Yablo’s paradox, we can’t trust that mathematical reasoning is consistent, and if something has been proved impossible then we should see that as an opportunity to find contradictions in mathematics.
Well, if that’s how you want to proceed, good luck to you. But I’ll be betting the other way.
(Just for the avoidance of doubt: 1. Yablo’s paradox is not a contradiction in ZF. 2. There is nothing ZF-specific about the cardinality argument cousin_it gives, which I’m pretty sure goes through just fine in, say, NFU. 3. There is also nothing ZF-specific about Yablo’s paradox.)
As I said: if you want to look there, go ahead. I just think you’re going to fail, and the reason I think you’re going to fail is that there is a proof that you’ll fail.
You protest that this problem is not important for you, and I think I remember you saying something similar the last time you brought up your opinion that ZF, or the very notion of infinity, or whatever it was, is likely inconsistent. For something not important to you, you seem to want to discuss it a lot.
I don’t want to look there more than quite briefly. So don’t be so worried for me.
If I will ever want to climb these hills, it will be on the motorbike, so to speak.
Math problems are a perfect toy for my real interests. Not by itself my highest interest.
Having said that, yes, I believe that the ZF is broken, yes. But it’s not more important than the fact that the rules of chess are broken.
In fact, this last observation, is much more shocking and worrying. One may easily expect, that those simple rules of chess are rock solid, but they aren’t. And one may easily expect, that something as rich as all the mathematics coming out of the ZF can easily have issues.
The current official rules of chess—which I think are here—are perfectly clear that an en passant capture is a thing the opponent does on the next move and doesn’t mean that the pawn “never reached” the square it was moved to. They are also perfectly clear that castling occurs only on a player’s first rank. (And, just to add one you didn’t mention, that a pawn can promote only to a piece of the same colour.)
At some times in the past, the rules of chess have been drafted carelessly enough to have consequences that were clearly not intended by their drafters nor expected by ordinary chess players. Perhaps they are now, though I don’t know of any such consequences of the present rules.
The “holes” in the laws of chess—at least, those found so far—have generally been extremely simple, and not many people have actively explored the exact consequences of the rules. If there were errors in, say, the axioms of ZF set theory that are as simple as the ones there have been in the rules of chess, they would surely have been caught by now. (Consider e.g. Frege’s system, a hole in which was found by Russell before he’d even finished publishing it; or the original version of Quine’s ML, a hole in which was found by two people independently within a couple of years of publication. ZF has been looked at a lot more than either of those, for longer.)
I’m not claiming to know that ZF is consistent. I don’t know that ZF is consistent. No one does. But if it is inconsistent, I would be flabbergasted if its inconsistency were found by the sort of thing you’re proposing here, where you find a really easy proof that something is impossible and suggest looking for counterexamples.
In the position you’ve linked, it goes like this. White plays Bg2+. He calls it checkmate but of course it isn’t. Black plays d5#. This is checkmate. The fact that white can (or could, if it got him out of check) capture the pawn on d5 en passant doesn’t meant it never really got to d5; the rules are perfectly clear that a White capture en passant is a thing that happens (if it does) on White’s following move. The etymology of the term is neither here nor there. White cannot, in fact, now play cxd6 e.p. because that move doesn’t get him out of check. And despite White’s fanciful interpretation of how the game rules, an e.p. capture does not, in fact, have any sort of retroactive effect. Of course Black’s pawn got to d5; it is already there.
This is true, as long as white has no pawn intersecting power. Which today is a defacto standard. And “en passant” isn’t “en passant”, but “as if en passant, but only after the taken pawn has occupied some other field than the one his slayer occupies know”.
This should be make clear, or things are vague, ill-defined.
I think you are complaining that the official rules of chess merely define the rules of chess, and don’t also take care to offer explicit contradictions for every confused notion someone reading them impressionistically might arrive at.
There is nothing in those rules to imply or even suggest that either player has “pawn intersecting power”, if by that cryptic phrase (perhaps you mean “intercepting” but the meaning is still obscure) you mean some sort of retroactive interference with a previous move. It’s true that the rules also don’t explicitly deny that—in the same way as they don’t explicitly deny (say) that if you push the same pawn three times in a row then you get to remove one of your opponent’s pieces. They don’t need to, because neither is something a reasonable person would expect on reading the rules.
“En passant” is merely a technical term. It is not necessary for the rules to say explicitly “even though the term comes from the French for ‘in passing’, the pawn completes its move and is then removed only by the capture next move” because that is obvious from the actual rules as stated. Just as it is not necessary for them to say explicitly “even though the term ‘checkmate’ comes from words meaning ‘king dead’, checkmate is achieved as soon as the king is in check and has no way to escape; actually capturing the king is not required”. Or “even though the players are called white and black, it is not necessary for the actual players to be white and black respectively”. Or “even though the knight in some sense represents a man on a horse, a knight’s move can pass over intervening pieces representing things that would be too high for a real horse to jump over”.
There is nothing ill-defined here (at least, not so far as the example you’ve given tells us; there might be errors or omissions I haven’t noticed).
I would be happy to bet my $100 against your $10 that none of the 10 most widely used chess engines takes a different view of this situation from the one I describe. … Well, actually I wouldn’t, because the nuisance of agreeing details and testing chess engines and so on greatly outweighs the value to me of $10, but in principle I would.
I don’t really see that this would “decide who is right”, though; if people had been writing chess engines back when the rules failed to stipulate that castling has to be horizontal or that promotions have to be to pieces of your own colour, I bet they would mostly have implemented those features in the “expected” way. If there are subtle omissions in the present-day rules, they probably aren’t reflected in actual chess engine code.
The question is, how their rules of engagement looks like. Especially, what is the mechanism dealing with the en passant? Is it plain like in the FIDE’s rules?
I don’t think so.
They are different. You see, pure mathematics is like a program in Python written on a sheet of paper. You actually don’t know, if it would run or not.
The same goes for the game rules. Humans do out-negotiate from most situation if not all, but that doesn’t mean that the rules of the game (in this case chess) are without a problem.
I’m not sure I understand your question about “their rules of engagement”. But I took a look at one chess engine’s source. This is Robert Hyatt’s “Crafty”, which at one time was one of the leading engines (others have overtaken it now). Many things are represented as 64-bit bitmaps. Here, accordingly, is its special code for e.p. captures.
First, in a function called GenerateCaptures there is a line that says this:
target = Occupied(enemy) | EnPassantTarget(ply);
Everything from “|” inclusive to ”;” exclusive would be omitted if there were no e.p. captures. Second, there is some special-cased code for generating moves when in check (since of course you then only need to consider moves that might get you out of check). Here’s the relevant code:
Without e.p. captures this would be simplified in fairly obvious ways. Third, as well as generating moves there is some code for validating moves (I haven’t looked at how it’s used, but I guess it’s just for verifying that an opponent’s move is legal; I’m not sure why it isn’t good enough to generate all legal moves and see if the given move is among them, since it’s hard to see how efficiency would matter for this). Here’s the relevant bit:
and this thing needs initializing, setting when a pawn advances two squares, incorporating (since e.p. status is a sometimes-important feature of a position) into the hash function used when storing previously-examined positions, and various bits of bookkeeping (e.g., in the tree search it is convenient to “flip” the position, interchanging the roles of black and white, and the e.p. status is one of the things that needs swapping over). And that’s it.
None of this (of course) involves any sort of reverse-causation where an e.p. capture causes the captured pawn never to have reached the square it nominally moved to. And, aside from the fact of being formalized in computer code, it all seems to me pretty much exactly as clear-cut as in the FIDE rules.
I had a quick look at the source of Stockfish, one of today’s top engines. It seemed fairly similar in complexity, except that Stockfish seems to take some notice of e.p. status in its analysis, which means there’s e.p.-related code that isn’t strictly needed merely because the rules are what they are.
You don’t actually know, if it [sc. mathematics] would run or not.
I think you know as well as you do for many pieces of software that have been run. After all, pure mathematics is used all the time by pure mathematicians, and less directly by physicists, engineers, etc. There might be bugs, but so might there be in software that has been used for years.
[EDITED to fix some code-formatting errors and remark that the remaining ones are probably unfixable because AFAIK there’s no good way to stop spaces at the starts of lines being eaten.]
The first is this about chess. How the rules of chess are defined for chess engines, are they really just a copy of what the official FIDE rules are, and how this is going to play out for some crucial positions.
I argue, that the human rules are a bit vogue and that some engines are very likely well designed, but their rules are a bit different. At least more complete.
The second is about mathematics, how likely everything is consistent there. Very unlikely, if you ask me. But almost certainly very likely all is okay, if I ask you. Even if there are paradoxes, they are so very well hidden, that no surface scanning is going to find one. The ZF has been scrutinized quite deeply and all is okay. That’s your view if I understand you correctly.
The third is about math and software. You are saying, that a lot of mathematics is constantly used by a lot of programs and that program bugs are somewhat a problem, but that there is almost certainly no math bugs.
Here we disagree again. I think there might be some unseen math bugs, too. Probably not in finite simple mathematics, but maybe even there. But quite possibly when things get really complicated.
Perhaps I will not refer to another problem involving infinities here. Just to avoid some unnecessary disputes.
Why is this particular puzzle relevant to ZF? If we had provided contradictory solutions to any of your previous puzzles then that would also doom ZF, no?
It just MIGHT be relevant to the ZF. Writing down every real from the interval (0,1) onto the Euclidian plane using some (arbitrarily resizable) Lucida console or whatever font, (in an abstract way, of course), would be enough to have the consistency crisis in the ZF.
You can do this in a finite volume amount of 3D space, using flat 2D font. But that’s okay, regarding ZF, because most numbers written this way, covers no rational point when in 3D space.
You don’t need to actually write them down in a font, you can instead represent every real from the interval (0,1) with just some small circle or square, or with whatever shape with an area, and they also should not overlap. And with all that, the ZF is done.
But you don’t need to use every real from (0,1), just say aleph-middle of them.
What is aleph-middle? It’s some Cohen’s cardinality between aleph-zero and aleph-one, you can always postulate.
This MIGHT be feasible. If it is, it’s enough. I don’t know, if it’s feasible, let alone how exactly.
Then, you don’t even need finite area shapes, you need shapes with at least one rational point.
Then, those shapes MAY overlap. Just not in that rational point, but everywhere else.
I wouldn’t be too much surprised, if someone comes with such a construction. With all the necessary rigor, of course.
If we had provided contradictory solutions to any of your previous puzzles then that would also doom ZF, no?
Yes, but I don’t find those likely to have two opposite simple solutions. At least not less than extremely complicated. Which is practically useless. We could never have agreed about something that complicated.
I think all this means is that you find this proof less obvious than some other proofs. That’s fair enough, but finding something difficult to grasp doesn’t mean it’s likely to be wrong.
The way it looks to me: no, it’s not feasible, it’s plainly not feasible, for exactly the reason cousin_it gives; you might as well be asking for three positive integers with x^3+y^3=z^3. (Actually, even more so; I find the cardinality argument here clear at a glance, but Euler’s infinite-descent argument intricate and requiring sustained concentration. But, again, the fact that I can’t just look at it and immediately see why there are no solutions in no way calls into question the proof that there are no solutions.)
Yablo’s paradox cannot be formulated in ZF because it uses the idea of truth. If you reformulate it so that every sentence says that the rest of the sentences can be disproven, all of the sentences will be false, but there will be no proof in ZF of this for any of them. This simply shows that ZF is not (and cannot be) complete, not that there is anything wrong with it.
It is not necessary that the YP is “formulated in ZF”.
It’s enough that ZF yields some byproduct, like countably infinite sets, which are used to make (in this case a semantic) paradox.
Then something must be wrong either with ZF, either with the semantics which allows YP formulation. Possibly with both, but at least with one of them.
If the list of Yablo’s sentences is a finite one, then the last statement of the list is just true. And all those before the last are false and no paradox there.
This doesn’t mean, that something is necessary wrong with ZF, only likely. There might be a problem solely with the semantics which permits Yablo’s sequence. Still possible.
But the YP formulation is a very elementary one. There might be others, equally elementary. I didn’t say they are, but that they might be. The “infinite geometry” looks suspicious to me.
There are countably infinite lists in ZF. That doesn’t make the general fact that in some situations you can produce a paradox with a countably infinite list, a reason to think you can do that in ZF. You might as well argue, “We can produce paradoxes in natural language. So maybe we can do it in mathematics too.”
And maybe you could have made that argument, before people tried it. As others have pointed out, many people have looked for contradictions in ZF for a very long time, and none have been found. There is no reason to think there are any.
Each cube contains a rational point, so there’s at most a countable number of cubes. Or am I missing something?
You are not missing anything. It is true, that every cube contains a rational point, but most squares (or circles) have no rational point. Hence only aleph-zero many cubes.
OTOH, you can divide any cube further to the infinite number of disjunct cubes. Infinitely many times.
Now, if you can organize these divisions in such a way, that those infinities build up to more than aleph-zero cubes, the ZF is down.
I don’t say it’s possible, it just looks like slightly probable, due to the infinite divisibility of cubes. Which can be misleading, but maybe not.
I’m sorry, didn’t you say that the cubes must have no common volume?
I said so, yes. But you can replace a cube with its smaller parts.
Infinitely many cubes instead of just one.
I thought you wanted a set of cubes whose volumes don’t intersect with each other. (Then this set can’t be uncountable because each volume contains a rational point.) I don’t understand what you mean by replacing cubes… Can you explain the problem once again?
Assumed, that the ZF is consistent, you are right, of course. The fact, that there are rational points inside every cube, and that those cubes have no common volume, only common surfaces (lines, points) perhaps—is enough to state that there are at most aleph-zero of them.
But, if the ZF is not consistent, there may be a way to encode every real number between 0 and 1 with some peculiar cubic subdivision of 3D space.
You can easily encode every real between 0 and 1 via dividing (even a finite volume of) 3D space into disjunct 2D circles.
Perhaps, just perhaps, it is possible to replace those circles with cubes and spheres, given the infinite volume you have.
Perhaps, just perhaps, the ZF is broken.
People have attacked the consistency of ZF with much more powerful tools and failed. Your attack wouldn’t sound promising to these people, because it already sounds unpromising to me. Each further minute of your time spent on this problem would be a failure of rationality.
If you want another problem that’s really fun, prove or disprove that every division of the square into triangles of equal area will have an even number of triangles :-)
https://en.wikipedia.org/wiki/Monsky%27s_theorem
Strongly agree. This problem [EDITED to add: I mean Thomas’s, not cousin_it’s] sounds about as much worth working on as one that says: “Can you find positive integers x,y,z such that x^3+y^3=z^3? If so, ZF is broken!” No, you can’t; the proof isn’t all that difficult (though harder than the one for Thomas’s cube-division question); the fact that the answer is no unless ZF is broken is just another way of saying “the answer can be proved to be no”. I am not much interested in searching for solutions to problems that have been proved to have no solutions.
Well, it hasn’t been proved, that this problem has no solution.
If you ask me, at least since the invention of the Yablo’s paradox, the ZF is mortally wounded. But that’s just me and some others. Or better, some others and me.
I am only probing around, if there is a way to reformulate this paradox in some different contexts.
Well, there’s nothing revolutionary about that. If you don’t like ZF, then make up your own set of rules. I can show you how to create a different set theory in every topos.
ZF is not some authority that says what is true and what is not. It’s simply a model that people have found very useful in the foundation of mathematics, which has then blossomed into a discipline of its own.
Yablo’s paradox does not lead to any problem in ZF and there’s no reason to expect any version of it would.
The situation you’re in now is as pure a test of LW rationality as you’ll ever come across. Saving people from mistakes like yours, which defend themselves by feeding on your wishes, is pretty much why LW exists. Read the crackpot offer post. All the tools you need are right here.
Everybody want to save other people from the mistakes they (other people) do. Sometimes, that’s a mistake.
Sometimes you win the lottery too, but that doesn’t mean buying lottery tickets is a good idea. You must evaluate your chance, not just say there’s a chance. For this problem you have both inside view (comments from people who know math) and outside view (examples of math cranks) saying your chance is very low.
For what it’s worth, I’m treating this conversation as a test. How much chance does rationality have against a strong desire, in a situation that’s 100% in favor of rationality, and is there any way for it to avoid losing.
What makes you think, that the next Monday I will still remember this problem?
I will come with another crackpottery, or even some problem you are going to solve, as it has happened already.
And I also don’t see the necessity to actually find a crack in the ZF or to immediately find a solution for a problem posted? The problem you have presented a few days ago, it was several years before its solution. I’ve Googled it.
Most problems posted worldwide are too trivial to even bother. Some are interesting to play with. Some are just too tough.
What’s your problem?
There’s a well known puzzle called duck and fox. A duck starts at the center of a circular pond and can swim with speed 1. On the shore there’s a fox who can run with speed 4. Can the duck reach the shore without getting caught by the fox?
As it is, the puzzle is pretty easy. But if you generalize it to multiple foxes that can use coordinated strategies (say, with speeds 2 and 3) it becomes much harder. If anyone can find a necessary and sufficient condition on fox speeds that allow the duck to escape, even for just two foxes, that’d be really cool.
It’s another puzzle of a toreador chased by the bull in a circular arena. Both have the same speed.
Is there a way for the toreador to always stay in front of the bull?
Spoiler: Yes, it is.
I don’t think it’s equivalent. The duck can move freely inside the circle, while the fox can only stay on the circumference. Anyway, try to solve the 2 and 3 case.
I didn’t say it’s equivalent, just another puzzle. Took years before the solution came, decades ago.
But I don’t see much sense into digging for old solved or unsolved problems.
Invent one!
Here’s one I invented recently.
Imagine a rating system for movies where Bob the reviewer watches a movie and declares “this is in the top three movies I will see this year”. Then he watches another movie and says “this is in the top two movies I will see this year”. Then he watches another movie and says “this is in the top two movies I will see this year”. Then he watches another movie and says “this is in the top three movies I will see this year”. But with this last statement his credibility is gone, because he’s claimed that four movies will be in the top three or better. Thus we will say that the “longest credible prefix” of the list [3,2,2,3] is [3,2,2].
The puzzle is to write an algorithm that accepts a list of integers and returns the length of its longest credible prefix, whose asymptotic complexity is as good as possible. (I have found an answer that’s extremely fast, but no proof that it’s fastest.)
I can do time O(n^2), where n is the length of the list. Perhaps the “extremely fast” algorithm you have is O(n log n)? Surely O(n) must be impossible.
O(n log n) would be nice, but you can do even better :-)
Just to check we are formalizing in the same way, do you agree that O(n) is a lower bound? Because the list [1,2,...,n] has longest credible prefix of length n, but if we reduce any of the first n-1 elements by 1 then the length of the longest credible prefix is reduced. So we at least have to spend O(n) time looking at the first n-1 elements.
Yes, O(n) is a lower bound.
He can’t say that. He doesn’t even know how many movies he is going to see.
If he knows, that he is going to watch another N movies this year, he can only say “this is in the top N+1 movies I will see this year”. If that was the best movie so far.
The problem statement should be taken on face value, not argued with. But if you’re interested in the motivation, I was trying to design a review system that wouldn’t suffer from score inflation and payola (“every decent movie is 4 stars out of 5”). The problem you see is in fact the whole point. If you don’t feel confident enough that a movie will be in your top 3, say that it will be in your top 10. Your lack of confidence is an important signal of your true beliefs about the movie and viewers deserve to know it :-)
I’ll pass. Maybe somebody else will solve this problem of yours. Too vague for me.
Of course it’s been proved that the problem has no solution. cousin_it already sketched a proof.
You mean, you can’t divide 3D space into cubes, such that they have no common volume, and that there would be more than aleph-zero cubes?
Yes, his proof is well based on the fact that every cube has to contain a rational point not shared with other cubes. Because there are only aleph-zero such rational points in an infinite 3D space, there may be at the most aleph-zero such cubes.
That’s fine.
But what if, God forbid it, it’s also possible to code every real number with a cubic subdivision of that space?
Then we’ve proved A (as cousin_it has done) and proved NOT A.
We can’t have it.
Just as we can’t have a true and the same time false sentences in Yablo’s paradox.
“You mean, you can’t find three positive integers, cube them, and have the sum of two equal to the third? Yes, the proof is well based on the method of infinite descent. That’s fine. But what if, God forbid it, it’s also possible to find three positive integers with that property? Then we’ve proved A and proved NOT A. Just as in Yablo’s paradox.”
Yablo’s paradox gives no more reason to expect blatant contradictions in cousin_it’s cardinality argument than in Fermat’s infinite descent proof. What you’re saying is, in effect: Because of Yablo’s paradox, we can’t trust that mathematical reasoning is consistent, and if something has been proved impossible then we should see that as an opportunity to find contradictions in mathematics.
Well, if that’s how you want to proceed, good luck to you. But I’ll be betting the other way.
(Just for the avoidance of doubt: 1. Yablo’s paradox is not a contradiction in ZF. 2. There is nothing ZF-specific about the cardinality argument cousin_it gives, which I’m pretty sure goes through just fine in, say, NFU. 3. There is also nothing ZF-specific about Yablo’s paradox.)
You and cousin_it want to assure me, that there is nothing to see here, therefore nobody should even bother to look.
Fine, don’t.
How important is that problem for me? Not very. Like 100 chess games.
As I said: if you want to look there, go ahead. I just think you’re going to fail, and the reason I think you’re going to fail is that there is a proof that you’ll fail.
You protest that this problem is not important for you, and I think I remember you saying something similar the last time you brought up your opinion that ZF, or the very notion of infinity, or whatever it was, is likely inconsistent. For something not important to you, you seem to want to discuss it a lot.
For the record.
I don’t want to look there more than quite briefly. So don’t be so worried for me.
If I will ever want to climb these hills, it will be on the motorbike, so to speak.
Math problems are a perfect toy for my real interests. Not by itself my highest interest.
Having said that, yes, I believe that the ZF is broken, yes. But it’s not more important than the fact that the rules of chess are broken.
In fact, this last observation, is much more shocking and worrying. One may easily expect, that those simple rules of chess are rock solid, but they aren’t. And one may easily expect, that something as rich as all the mathematics coming out of the ZF can easily have issues.
But the chess?
As the vertical castling, wasn’t bad enough!
Probably it’s “nothing to see here” for you also at this chess thing.
I beg to differ.
The current official rules of chess—which I think are here—are perfectly clear that an en passant capture is a thing the opponent does on the next move and doesn’t mean that the pawn “never reached” the square it was moved to. They are also perfectly clear that castling occurs only on a player’s first rank. (And, just to add one you didn’t mention, that a pawn can promote only to a piece of the same colour.)
At some times in the past, the rules of chess have been drafted carelessly enough to have consequences that were clearly not intended by their drafters nor expected by ordinary chess players. Perhaps they are now, though I don’t know of any such consequences of the present rules.
The “holes” in the laws of chess—at least, those found so far—have generally been extremely simple, and not many people have actively explored the exact consequences of the rules. If there were errors in, say, the axioms of ZF set theory that are as simple as the ones there have been in the rules of chess, they would surely have been caught by now. (Consider e.g. Frege’s system, a hole in which was found by Russell before he’d even finished publishing it; or the original version of Quine’s ML, a hole in which was found by two people independently within a couple of years of publication. ZF has been looked at a lot more than either of those, for longer.)
I’m not claiming to know that ZF is consistent. I don’t know that ZF is consistent. No one does. But if it is inconsistent, I would be flabbergasted if its inconsistency were found by the sort of thing you’re proposing here, where you find a really easy proof that something is impossible and suggest looking for counterexamples.
According to the rules of chess you have linked, it is perfectly clear to you, who wins in the game I have linked.
Black or white?
It is not perfectly clear to me. It’s kind of “ill defined”.
Black wins because White’s last move is not a legal move, since it doesn’t get White out of check. As gjm said, there is nothing vague about this.
In the position you’ve linked, it goes like this. White plays Bg2+. He calls it checkmate but of course it isn’t. Black plays d5#. This is checkmate. The fact that white can (or could, if it got him out of check) capture the pawn on d5 en passant doesn’t meant it never really got to d5; the rules are perfectly clear that a White capture en passant is a thing that happens (if it does) on White’s following move. The etymology of the term is neither here nor there. White cannot, in fact, now play cxd6 e.p. because that move doesn’t get him out of check. And despite White’s fanciful interpretation of how the game rules, an e.p. capture does not, in fact, have any sort of retroactive effect. Of course Black’s pawn got to d5; it is already there.
This is true, as long as white has no pawn intersecting power. Which today is a defacto standard. And “en passant” isn’t “en passant”, but “as if en passant, but only after the taken pawn has occupied some other field than the one his slayer occupies know”.
This should be make clear, or things are vague, ill-defined.
I think you are complaining that the official rules of chess merely define the rules of chess, and don’t also take care to offer explicit contradictions for every confused notion someone reading them impressionistically might arrive at.
There is nothing in those rules to imply or even suggest that either player has “pawn intersecting power”, if by that cryptic phrase (perhaps you mean “intercepting” but the meaning is still obscure) you mean some sort of retroactive interference with a previous move. It’s true that the rules also don’t explicitly deny that—in the same way as they don’t explicitly deny (say) that if you push the same pawn three times in a row then you get to remove one of your opponent’s pieces. They don’t need to, because neither is something a reasonable person would expect on reading the rules.
“En passant” is merely a technical term. It is not necessary for the rules to say explicitly “even though the term comes from the French for ‘in passing’, the pawn completes its move and is then removed only by the capture next move” because that is obvious from the actual rules as stated. Just as it is not necessary for them to say explicitly “even though the term ‘checkmate’ comes from words meaning ‘king dead’, checkmate is achieved as soon as the king is in check and has no way to escape; actually capturing the king is not required”. Or “even though the players are called white and black, it is not necessary for the actual players to be white and black respectively”. Or “even though the knight in some sense represents a man on a horse, a knight’s move can pass over intervening pieces representing things that would be too high for a real horse to jump over”.
There is nothing ill-defined here (at least, not so far as the example you’ve given tells us; there might be errors or omissions I haven’t noticed).
Yes, you are right.
Otherwise we don’t agree at all about this.
But there is a way to decide who is right here. By reviewing some chess engine code, how this instance is handled.
There, rules of the chess are explicitly written down. It would be interesting to see how this is handled and what are the rules.
I would be happy to bet my $100 against your $10 that none of the 10 most widely used chess engines takes a different view of this situation from the one I describe. … Well, actually I wouldn’t, because the nuisance of agreeing details and testing chess engines and so on greatly outweighs the value to me of $10, but in principle I would.
I don’t really see that this would “decide who is right”, though; if people had been writing chess engines back when the rules failed to stipulate that castling has to be horizontal or that promotions have to be to pieces of your own colour, I bet they would mostly have implemented those features in the “expected” way. If there are subtle omissions in the present-day rules, they probably aren’t reflected in actual chess engine code.
I think, chess engines probably do it right.
The question is, how their rules of engagement looks like. Especially, what is the mechanism dealing with the en passant? Is it plain like in the FIDE’s rules?
I don’t think so.
They are different. You see, pure mathematics is like a program in Python written on a sheet of paper. You actually don’t know, if it would run or not.
The same goes for the game rules. Humans do out-negotiate from most situation if not all, but that doesn’t mean that the rules of the game (in this case chess) are without a problem.
I’m not sure I understand your question about “their rules of engagement”. But I took a look at one chess engine’s source. This is Robert Hyatt’s “Crafty”, which at one time was one of the leading engines (others have overtaken it now). Many things are represented as 64-bit bitmaps. Here, accordingly, is its special code for e.p. captures.
First, in a function called GenerateCaptures there is a line that says this:
Everything from “|” inclusive to ”;” exclusive would be omitted if there were no e.p. captures. Second, there is some special-cased code for generating moves when in check (since of course you then only need to consider moves that might get you out of check). Here’s the relevant code:
Without e.p. captures this would be simplified in fairly obvious ways. Third, as well as generating moves there is some code for validating moves (I haven’t looked at how it’s used, but I guess it’s just for verifying that an opponent’s move is legal; I’m not sure why it isn’t good enough to generate all legal moves and see if the given move is among them, since it’s hard to see how efficiency would matter for this). Here’s the relevant bit:
Finally, of course that thing EnPassantTarget needs to be defined. Its definition is simple:
This is basically a wrapper around this:
and this thing needs initializing, setting when a pawn advances two squares, incorporating (since e.p. status is a sometimes-important feature of a position) into the hash function used when storing previously-examined positions, and various bits of bookkeeping (e.g., in the tree search it is convenient to “flip” the position, interchanging the roles of black and white, and the e.p. status is one of the things that needs swapping over). And that’s it.
None of this (of course) involves any sort of reverse-causation where an e.p. capture causes the captured pawn never to have reached the square it nominally moved to. And, aside from the fact of being formalized in computer code, it all seems to me pretty much exactly as clear-cut as in the FIDE rules.
I had a quick look at the source of Stockfish, one of today’s top engines. It seemed fairly similar in complexity, except that Stockfish seems to take some notice of e.p. status in its analysis, which means there’s e.p.-related code that isn’t strictly needed merely because the rules are what they are.
I think you know as well as you do for many pieces of software that have been run. After all, pure mathematics is used all the time by pure mathematicians, and less directly by physicists, engineers, etc. There might be bugs, but so might there be in software that has been used for years.
[EDITED to fix some code-formatting errors and remark that the remaining ones are probably unfixable because AFAIK there’s no good way to stop spaces at the starts of lines being eaten.]
We have 3 somewhat separated questions here.
The first is this about chess. How the rules of chess are defined for chess engines, are they really just a copy of what the official FIDE rules are, and how this is going to play out for some crucial positions.
I argue, that the human rules are a bit vogue and that some engines are very likely well designed, but their rules are a bit different. At least more complete.
The second is about mathematics, how likely everything is consistent there. Very unlikely, if you ask me. But almost certainly very likely all is okay, if I ask you. Even if there are paradoxes, they are so very well hidden, that no surface scanning is going to find one. The ZF has been scrutinized quite deeply and all is okay. That’s your view if I understand you correctly.
The third is about math and software. You are saying, that a lot of mathematics is constantly used by a lot of programs and that program bugs are somewhat a problem, but that there is almost certainly no math bugs.
Here we disagree again. I think there might be some unseen math bugs, too. Probably not in finite simple mathematics, but maybe even there. But quite possibly when things get really complicated.
Perhaps I will not refer to another problem involving infinities here. Just to avoid some unnecessary disputes.
Why is this particular puzzle relevant to ZF? If we had provided contradictory solutions to any of your previous puzzles then that would also doom ZF, no?
It just MIGHT be relevant to the ZF. Writing down every real from the interval (0,1) onto the Euclidian plane using some (arbitrarily resizable) Lucida console or whatever font, (in an abstract way, of course), would be enough to have the consistency crisis in the ZF.
You can do this in a finite volume amount of 3D space, using flat 2D font. But that’s okay, regarding ZF, because most numbers written this way, covers no rational point when in 3D space.
You don’t need to actually write them down in a font, you can instead represent every real from the interval (0,1) with just some small circle or square, or with whatever shape with an area, and they also should not overlap. And with all that, the ZF is done.
But you don’t need to use every real from (0,1), just say aleph-middle of them.
What is aleph-middle? It’s some Cohen’s cardinality between aleph-zero and aleph-one, you can always postulate.
This MIGHT be feasible. If it is, it’s enough. I don’t know, if it’s feasible, let alone how exactly.
Then, you don’t even need finite area shapes, you need shapes with at least one rational point.
Then, those shapes MAY overlap. Just not in that rational point, but everywhere else.
I wouldn’t be too much surprised, if someone comes with such a construction. With all the necessary rigor, of course.
Yes, but I don’t find those likely to have two opposite simple solutions. At least not less than extremely complicated. Which is practically useless. We could never have agreed about something that complicated.
I think all this means is that you find this proof less obvious than some other proofs. That’s fair enough, but finding something difficult to grasp doesn’t mean it’s likely to be wrong.
The way it looks to me: no, it’s not feasible, it’s plainly not feasible, for exactly the reason cousin_it gives; you might as well be asking for three positive integers with x^3+y^3=z^3. (Actually, even more so; I find the cardinality argument here clear at a glance, but Euler’s infinite-descent argument intricate and requiring sustained concentration. But, again, the fact that I can’t just look at it and immediately see why there are no solutions in no way calls into question the proof that there are no solutions.)
Yablo’s paradox cannot be formulated in ZF because it uses the idea of truth. If you reformulate it so that every sentence says that the rest of the sentences can be disproven, all of the sentences will be false, but there will be no proof in ZF of this for any of them. This simply shows that ZF is not (and cannot be) complete, not that there is anything wrong with it.
It is not necessary that the YP is “formulated in ZF”.
It’s enough that ZF yields some byproduct, like countably infinite sets, which are used to make (in this case a semantic) paradox.
Then something must be wrong either with ZF, either with the semantics which allows YP formulation. Possibly with both, but at least with one of them.
If the list of Yablo’s sentences is a finite one, then the last statement of the list is just true. And all those before the last are false and no paradox there.
This doesn’t mean, that something is necessary wrong with ZF, only likely. There might be a problem solely with the semantics which permits Yablo’s sequence. Still possible.
But the YP formulation is a very elementary one. There might be others, equally elementary. I didn’t say they are, but that they might be. The “infinite geometry” looks suspicious to me.
Once again, as others have already told you, Yablo’s paradox cannot generate any sort of paradox whatsoever in ZF.
I told the others, that the countably infinite sets MIGHT be infected, since a finite list of Yablo sentences DOESN’T yield a paradox.
While a countably infinite list of Yablo sentences—DOES yield the mentioned paradox.
AFAIK, the infinities come out of ZF. Don’t they?
There are countably infinite lists in ZF. That doesn’t make the general fact that in some situations you can produce a paradox with a countably infinite list, a reason to think you can do that in ZF. You might as well argue, “We can produce paradoxes in natural language. So maybe we can do it in mathematics too.”
And maybe you could have made that argument, before people tried it. As others have pointed out, many people have looked for contradictions in ZF for a very long time, and none have been found. There is no reason to think there are any.