3 ms·
why is that "unsound"? what's wrong with an unwritable natural? Almost all reals are unwritable.
by lupire 5y ago
why is that "unsound"?
what's wrong with an unwritable natural?
Almost all reals are unwritable.
- dogecoinbase 5y agoSoundness in this sense (sigma_1 soundness) is defined by equivalency to the standard model (specifically, all sentences provable in the system must be provable in the standard model).
- dwohnitmok 5y agoIt is defined by equivalency to a standard model. Whether there is a single standard model is a philosophical question (which granted most, but not all, set theorists tend to agree with). Hence sigma_1 soundness is from a purely mathematical point of view a relative statement.
- rssoconnor 5y agoMostly because it implies that some Turing machines halt that actually do not halt. That is unless you are willing to accept that a Turing machine can halt in some number of steps that is beyond any number that can be written. And I don't mean can't be written in the sense that we don't have enough paper. Just cannot be written in principle at all by our notation for numbers.
- bryan0 5y agoBut isn’t this what the busy beaver numbers are? Numbers that we cannot write for arbitrary n but they do exist?
- rssoconnor 5y agoI think this is a great question. The difference here is that with busy beaver numbers, e.g. BB(101) we can, presumably, write their values with our notation; it's just that we often cannot prove that any particular value written in our notation does indeed denote the value for that function. So if we write 100000...0000 with an unholy number of 0s there, it might be the value of BB(101), in particular we might not be able to prove that it isn't. On the other hand, for a non-standard number, c, it is definitely the case that 100000...0000 is not c, because, whatever c is, it is strictly greater than 100000...0000, or any other number we can write down. And thus when it comes to proofs about the termination of Turing machines that do not actually terminate, the unsound system is claiming that some machine terminates, but it doesn't terminate in 1 step, nor 2 steps, nor 3 steps, nor ... nor 100000...0000 steps, nor 100000...0001 steps, nor 100000...0002 steps, nor .... However, regarding the BB(101), the (presumably) sound systems we use such as PA, or ZFC, do not claim that BB(101) isn't 100000...0000. They just may not be able to prove anything one way or the other.
- thaumasiotes 5y agoDo they exist? I thought there was an independence theorem for the specific values of almost all busy beaver numbers.
- rssoconnor 5y agoThey exist in that it is easy to prove "for ALL x there EXISTS y such that (there EXISTS a Turing machine with at most x states M such that (there EXISTS some n such that M prints y 1's and halts after n steps) AND (for ALL Turing machines with at most x states M, if (there EXISTS some n such that M halts after n steps) then (M prints no more than y 1's after n steps))". I expect you can prove this in systems as weak as Primitive Recursive Arithemetic. It is true though that various (decidable) proof systems are unable to prove that the Busy Beaver function has any specific value beyond a certain point. However, where that cut-off is varies from proof system to proof system, with stronger proof systems being able to prove more an more values of the Busy Beaver function. Maybe you find it weird that we can prove (Exists x. P x) without being able to prove P n for any particular numeral n? Welcome to the strange world of classical (i.e. non-constructive) mathematics.
- thaumasiotes 5y ago> It is true though that various (decidable) proof systems are unable to prove that the Busy Beaver function has any specific value beyond a certain point. Isn't the result stronger than that though? The value of BB(30) might be X. Or it might be Y. Neither value would cause any problems. Thus, "the value" doesn't exist. There is no value that is the value of BB(30).
- rssoconnor 5y agoYes, what you are saying is indeed the case in the sense that if BB(30)=n for some particular numeral n is independent of whatever proof system we are focusing on, for the sake of argument let's say ZFC, (though 30 feels a a bit on the low side for ZFC), then we can consistently add BB(30)=n or BB(30)≠n as axioms to the system, the same way to can for any other independent statement. And there will be arbitrary large values of n that are independent, so we could add BB(30)=n or we could add BB(30)=m or so forth for any numerals i so long as BB(30)=i is independent of ZFC (or whatever axiom system we are considering). But! that does not mean that all these systems are sound, for if you add the incorrect value as an axiom, specifically if you add anything but the smallest value 'm' such that BB(30)=m is independent of ZFC, then you are in a similar situation to adding ¬Con(ZFC) whereby you only have non-standard models. They way this works is that, suppose BB(30)=m for some particular m is independent of ZFC, but BB(30) is not actually equal to m. What we will find is that there is some Turing machine M and some non-standard natural number q such that, while M doesn't actually halt in reality, according to some non-standard model it does halt in 'q' number of steps, and, in this model, when it does halt, it leaves 'm' 1's on the output tape. That said, your comment did push me towards the limits of my comfort zone, so it might be helpful to double check what I'm saying. I don't see how it could be any other way though.
- ummonk 5y agoWhy is that wrong? If you actually ran a Turing machine for a number of steps that is beyond any number that can be written, maybe it would halt.
- rssoconnor 5y agoBy number that cannot be written, I don't mean cannot be written due to lack of paper; I mean a value that there is no notation for. You cannot run a machine for "that many" steps because such a value is unreachable by steps. Non-standard models have a set of values that begin with a copy of the actual natural numbers, followed by some ordered set of copies of the integers in the sense that any values "beyond" the initial natural numbers have an infinite number of successors and an infinite number of predecessors, like integers do. By counting in steps it is not possible to move from a value in the initial natural number fragment to one of these non-standard values, because there are an infinite number of values in between them that you would be required to step through.
- ummonk 5y ago> By number that cannot be written, I don't mean cannot be written due to lack of paper; I mean a value that there is no notation for. That's true for most real numbers in ordinary mathematics too, so if you accept the existence of those numbers, no reason why you can't do the same for the natural numbers in these non-standard models. > You cannot run a machine for "that many" steps because such a value is unreachable by steps. Non-standard models have a set of values that begin with a copy of the actual natural numbers, followed by some ordered set of copies of the integers in the sense that any values "beyond" the initial natural numbers have an infinite number of successors and an infinite number of predecessors, like integers do. By counting in steps it is not possible to move from a value in the initial natural number fragment to one of these non-standard values, because there are an infinite number of values in between them that you would be required to step through. Yes...
- dwohnitmok 5y agoThis is not unsound in the usual sense of "logical soundness" (which applies to logical systems such as first-order logic, rather than specific theories in the system such as ZFC). This is unsound in that it runs counter to certain philosophical commitments, namely that there should be some tangible, physical realization of all the natural numbers (although if you really go far in that direction you end up with ultrafinitism, which most set theorists would find unpalatable, so the philosophical implications of all this are rather tricky).
- ummonk 5y agoAs you allude, it's rather ridiculous to make certain philosophical commitments but only apply them to natural numbers. I think ordinary finitism will do fine though, no need to go to ultrafinitism.
- pavpanchekha 5y agoI wonder what you mean by "what's wrong with an unwritable natural"... It is sound to assume one! And it doesn't make any true mathematical facts false. But of course it's sound to assume many silly things. But why assume those things? The reality is that mathematicians didn't first come up with the Peano axioms and then study the interesting consequences of them. Both as a matter of history and also as a matter of why most mathematicians do math, mathematicians first came up with numbers, and only later came up with axioms that allow them to do rigorous reasoning about them. The same is actually true of almost all math—real numbers were invented to do rigorous reasoning about calculus, which by that point had been around for a century plus; set theory likewise. In other words, if the goal is to come up with any old consistent set of axioms, you can assume an unwritable natural number, that's fine, go ahead. But if your goal is to study natural numbers—which, like, I have a lot of experience with natural numbers in my day to day life, I'm pretty sure I could write all of them if I had enough time and space and so on—then you want to study natural numbers, not some other weird things where there are unwritable weird things.
- ummonk 5y ago"But of course it's sound to assume many silly things. But why assume those things?" This goes to the parent comment's point about real numbers though. It's silly to assume unwritable real numbers. Why do we do so?