User pa - MathOverflow

Are there any recommended texts that cover Turing Tilings?

2011-07-12T16:01:20Z

I have read the original paper by Wang, as well as a paper by Boas [1996] entitled 'the Convenience of Tilings', but wanted to know if there were any other texts that people could recommend that include sections on Turing Tilings?

Secondarily to this, I would very much like to hear of any attempts to include Oracle computations in Turing Tilings...

Answer by PA for Subsystems of Peano arithmetic and incompleteness theorem

2011-06-18T08:31:52Z

This answers to this question may be of use - http://mathoverflow.net/questions/65626/can-any-formal-system-prove-its-own-consistency

In short, it states that $PA$ is too strong to prove its own consistency, Presburger arithmetic (see Neel Krishnaswami's answer in the link) is too weak (although it is consistent). Other sub-systems like $I\Sigma_1$ can't prove their own consistency. $PA^-$ (PA without induction) I'm not sure about, but I wouldn't expect it to prove its own consistency.

But Paseman's comment is probably most accurate!

An inconsistent sub-system could, but I don't think that's what you're after... ;)

http://mathoverflow.net/questions/9864/presburger-arithmetic http://www.cs.albany.edu/~dew/m/jsl1.pdf http://en.wikipedia.org/wiki/Presburger_arithmetic

Proofs that use Infinite/Finite Priority Injury Method

2011-06-15T23:50:20Z

Can anyone point me to any proofs (pref. interesting ones!) that make good (or bad) use of the Finite or Infinite Priority Injury Argument?

Edit: I would suppose that my question could be put this way too. Are priority injury method proofs limited to recursion theory, or have they been used elsewhere?

Motivation: It's a technique that crops up a lot in recursion/computability theory, especially in the Friedberg-Muchnik theorem. As a development of normal Priority Arguments (set up by Kleene and Post), I wish to explore any interesting, or just additional, formulations.

As I said, I'm familiar with 'Movable Marker' proofs, and with 'Priority Method' proofs, and I'm looking for proofs that make use of the injury side of the method.

For those who are unsure; the priority injury method utilises the notion that for a set of requirements that we have to meet, $R_{2e}$ for one side and $R_{2e+1}$ on the other side of our computation, we define the 'use' of each side, and then choose a witness $x$ s.t. $A(x)\neq \Phi^B_i (x)$, where $A$ and $B$ are the sets that we're trying to make incomparable in the Friedberg-Muchnik theorem. The key point is that we allow ourselves to finitely/infinitely injure the requirements that have been satisfied before so that we can satisfy a stronger requirement - it is this technique that I'm interested to see further examples of...

Any proofs considered!

With thanks, M.

Answer by PA for undergraduate logic textbook

2011-06-15T07:49:18Z

[Apologies, but I can't vote nor comment]

@Andrew & @Mark - Just read the 3rd and 4th chapters (that is, the ones that overlap with my current research) and yes, the book by Wolf is excellent! (Preview is on Google Books) I can secondarily recommend it! The start of each chapter is verbose, and scant in technical detail, but it fleshes out the ideas very nicely and succinctly. Also, it reads like most lecturers talk - then you turn around and see just how much ground and technical detail HAS been covered, and I have to say, I was very impressed. If you don't choose it as a textbook, then most certainly secondary/pre-course reading! There are a few typos (one in a definition... :-S ), but the survey of the subjects, without getting bogged down in detail that those starting out don't appreciate nor necessarily need, is excellent.

Answer by PA for undergraduate logic textbook

2011-06-14T20:07:38Z

Kaye, R., 'Mathematics of Logic' is a good first-year text. Also consider Boolos 'Computability and Logic', but this could get in the way if you have a particular way of teaching CS/computability topics.

I prefer these to the Mendelson - which I found a bit confusing for the sake of formal accuracy. Kaye, by example, avoids too much technical jargon, and keeps to the ideas in play, building to a completeness theorem.

Hope this helps!

Answer by PA for Logic in mathematics and philosophy

2011-06-14T14:57:49Z

[I would like to vote up David Corfield's answer - but don't yet have the reputation. Also, having a taught philosophical logic in seminars and now studying mathematical logic, I don't understand what the term 'epistemic' logic mean in reference to mathematics - also, I don't know much about provability theory - so please vote down this answer if it is rubbish]

Here's my threppence... In terms of teaching, the motivations for students are usually qutie different. Many philosophy departments teach logic, but not for the same reasons that CS or mathematics departments teach it. For philosophers, Logic is a 'toolkit' for developing arguments, structuring them properly and getting a cohesive thread that can be read and understood by other philosophers.

Beyond this, philosophical logic develops into a number of descriptive and analytical disciplines (analytical, here, in the philosophical sense, opp. to continental philosophy), such as theory of mind, ontology, etc. etc. As such, teaching logic in philosophy depts. has its own challenges, as it is discouraged to be completely abstract, which makes concepts like Ex Falso Quodlibet quite challenging for students to understand.

Mathematical logic looks a lot more at what logical/non-logical symbols you have, how they relate to each other at what theorems are provable ($\phi \vee \neg \phi$) or un-provable (also called undecidable; $\phi \wedge \neg\phi$), and this is done by many means - model theory, recursion/computability theory, etc. etc., and theorem results give exact boundaries and thresholds for mathematical and logical systems. That said, most research seems to be in PA or fragments of PA (such as $PA^-$, $I\Sigma_1$ or $I\Sigma_n$ - the first of which is usually enough to do most mathematics, certainly all that we get from secondary school).

When considering truth, Tarski's 1969 paper on formal language states clearly that formal languages do have a way of expressing truth, which is not naturally inherent in natural language. In addition, the strength of a system is also well defined (Strength of T = {$ \phi : T \vdash \phi^\ast $}, where $\phi^\ast$ is a translation of $\phi$ into the language of T).

As to what philosophical models have influenced mathematics? I'm not sure exactly what to say. The only think that you normally get from mathematicians is derision of 'philosophical rubbish'! Which isn't very helpful to you... ;)

[Finally, thanks to @grshutt for the interviews - they are quite interesting indeed!]

Answer by PA for Propositional logic and first order logic textbook

2011-06-13T15:55:04Z

I'm suprised that no one has yet mentioned Boolos 'Computability and Logic'. The first 100 pages are pretty solid computability theoyr, and then follows Meta-logic, with an especially good précis on first-order logic that emphasizes the difference between a Language, an theory, and logical/non-logical symbols. Worth a gander, espeically if you're interested in CS related logic.

Robert Sores 'Recursively Enumerable Sets and Degrees' is another good place to start for recursion theory, as well as general logic. His approach is very clear (if a little assuming that you're following everything at once) and the first 120pp are very informative on recursively enumerable sets (now usually called computably enumerable). But for undergraduates, I'd go with the Boolos...

Note of warning - Mendelson's book Introduction to Mathematical Logic I found confusing when starting out - this was confirmed by supervisors/colleagues.

I hope this helps!

Comment by PA

2011-06-16T22:40:56Z

Many thanks! I shall look it up!

Comment by PA

2011-06-16T12:44:57Z

Many thanks @Quinn.Culver - that post looks interesting! Answers the question as I had hoped. The use of random strings and oracles is unusual - not something I had thought of in the way they write. Additionally, the comments are interesting (and quite philosophical at points).

Comment by PA

2011-06-16T12:36:31Z

@Carl - correct for both counts.

Comment by PA

2011-06-16T07:13:19Z

François - the other notes are also very informative! But do you know of any other places where finite priority injury methods are used?

Comment by PA

2011-06-16T06:43:04Z

...contd. in FM-theorem, we say that r.e. sets $A$ and $B$ exist s.t. $A \mid_T B$. I want to use this technique to solve some other problems, but wanted to gain some 'field experience' by researching what other problems have this as aprt of their solution. François Many thanks for the links! Some of these I had seen before (Lerman's papers on iterated trees of priority frameworks esp.). But some of the others should prove most useful. And yes, I had been informed of another book by Soare. Apologies for causing people problems... I had only hoped for informative results...

Comment by PA

2011-06-16T06:35:08Z

I have read Soare's book - I was wondering where else this technique has been used. I've also read Soare's papers on the subject, amongst Googling for examples (relatively unsuccessfully) and asking people as I meet them. I would like to think that this is asked with some research done... A normal - that is non-injured - priority argument is used in the construction of non-r.e. degrees (in fact, it's in Soare's book, p. 93). Two separate sets of requirements $R_e$ and $S_e$, are satisfied to resolve that there are incomparable degrees....

Comment by PA

2011-06-15T07:01:07Z

From what I have read (which is quite a bit) I haven't found many textbooks that treat logic in the way it is researched/studied today. Unfortunately, this means that writing your own notes seems to be the norm! Then again, there's probably a lot of monographs waiting to be fleshed out! Every cloud, silver lining...

Comment by PA

2011-06-14T20:21:00Z

I would have thought that the theorem on Slide 5 would satisfy a bijective condition that could be 'scaled up' for uncountable structures... I only considered it to possibly be of help. Clearly wrong. @Ioannis Souldatos - ignore.

Comment by PA

2011-06-14T18:42:53Z

correction - I think that I may be wrong about the 'person of the Empty Set' - I can't remember the axioms off the top of my head, but I hope that the message is clear...