User martin lackner - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T03:36:18Z http://mathoverflow.net/feeds/user/1330 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/4589/is-there-a-non-self-referencing-non-computable-function/4685#4685 Answer by Martin Lackner for Is there a non self-referencing non-computable function? Martin Lackner 2009-11-08T21:56:28Z 2009-11-08T21:56:28Z <p>A nice example for a function that fits your description (I think), is the Busy-Beaver function. The definition is rather natural (at least for an uncomputable function) and the uncomputability proof is not using any "tricks". See the Wikipedia entry (<a href="http://en.wikipedia.org/wiki/Busy_beaver" rel="nofollow">http://en.wikipedia.org/wiki/Busy_beaver</a>) for details.</p> http://mathoverflow.net/questions/3528/is-there-a-formula-phi-s-t-phi-and-not-phi-have-a-stronger-consistency Is there a formula phi s.t. phi and not-phi have a stronger consistency? Martin Lackner 2009-10-31T10:46:02Z 2009-11-05T15:39:38Z <p>Let &Sigma; be an axiom system. Can there be a formula &phi;, s.t. </p> <ul> <li>Con(&Sigma;) does not imply Con(&Sigma; + &phi;) AND</li> <li>Con(&Sigma;) does not imply Con(&Sigma; + not &phi;)</li> </ul> <p>If yes, can you give me an example for ZFC?</p> http://mathoverflow.net/questions/3528/is-there-a-formula-phi-s-t-phi-and-not-phi-have-a-stronger-consistency/3850#3850 Answer by Martin Lackner for Is there a formula phi s.t. phi and not-phi have a stronger consistency? Martin Lackner 2009-11-02T21:12:52Z 2009-11-02T21:12:52Z <p>Now that I know the answer, I've found my own simple proof. Probably it's interesting to someone else, so I post it:</p> <p>I want to show that Con(&Sigma;) is equivalent to ( Con(Σ + φ) OR Con(Σ + not φ) )</p> <p>Proof: Con(Σ + φ) OR Con(Σ + not φ) iff</p> <p>( Σ doesn't prove [φ -> FALSE] ) OR ( Σ doesn't prove [not φ -> FALSE] ) iff</p> <p>Σ doesn't prove [(not φ -> FALSE) AND (φ -> FALSE)] iff</p> <p>Σ doesn't prove [FALSE], which is Con(Σ).</p> http://mathoverflow.net/questions/3528/is-there-a-formula-phi-s-t-phi-and-not-phi-have-a-stronger-consistency Comment by Martin Lackner Martin Lackner 2009-11-05T15:39:07Z 2009-11-05T15:39:07Z You're right - I will change it. Thanks for pointing that out.