This is the Realm of Simply Beautiful Art

12:18 PM

@user400188 Many thanks. Hope you are doing well. :)

12:45 PM

Functional analysis book came in the mail. Looking forward to sinking into that soon.

3 hours later…

3:39 PM

@shredalert: Hey you're back! How are you? Sorry it's nearly time for me to go off, but I guess I'll see you again soon. =)

I have read about incompleteness theorem only from articles which are written for laymen and not from a proper book on logic. Can you give a reference which is rigorous yet accessible to starters?

Or even a link to some of your answers on this website will help

May be I will switch to SBA room for this kind of discussion

Sure I can move these messages over now.

← 4 messages moved from C.R.U.D.E.

@ParamanandSingh I guess it depends on your background. Are you familiar with programming?

Programming as in computer programming

3:44 PM

Yep.

I am familiar with it

Basically I earn my living as a software developer

A: What are the prerequisites for studying mathematical logic?

Normally mathematical references on the incompleteness theorems don't invoke programming concepts, so a lot of the technical details are there simply because they have to 'reinvent the wheel'.

But if you already understand programming and the fact that programs are strings that can be inputs to programs, then you are perfectly equipped to understand more elegant proofs of the incompleteness theorems.

From my profile under "introduction to logic" you will find mathematically-oriented texts, which you may not want to wade through, except for Peter Smith's book, which I highly recommend (perhaps it's because I have fond memories of it as the first book that I understood properly).

But for those familiar with computing there is another link to "incompleteness theorems" where I basically give entire proofs of them except for Godel's key lemma.

The two posts are:

I think for starting material you can't beat P.D. Magnus' book forall x, which clearly explains the intuitions behind logic culminating in Fitch-style natural deduction. (I described a programming-inclined variant here.) After that you can read Stephen Simpson's Mathematical Logic lecture notes a...

A: In Godel's first incompleteness theorem, what is the appropriate notion of interpretation function?

I've always interpreted this notion in the following way. $ \def\eq{\leftrightarrow} \def\t{\text} \def\pa{\t{PA}} \def\th{\t{Th}} \def\prf{\t{Proof}} \def\prov{\t{Prov}} \def\box{\square} \def\nn{\mathbb{N}} \def\str#1{{``\text{#1}\!"}} $ Formal system interpretation Take any formal systems...

The second post is based on a delightful computability-based argument that I first read about from the linked blog post but I made it thoroughly rigorous and fully generalized to every conceivable formal system.

I will get hold of that book, and also continue this discussion further. But right now something has cropped up here which takes precedence over chat. I will be back after some time. Bye

Sure take care!

You can read the blog post first to get a intuitive grasp of the argument, and then go to my rigorous version after that. I purposely left out Godel's key lemma since it's actually not the core reason for incompleteness; it's only necessary when the system we're dealing with is too weak to natively reason about finite strings. Of course, it was important for Godel because he wanted to show that basic arithmetic is essentially incomplete, and that is the link to finite strings.

Q: Formal systems and total programs

4:06 PM

However, the core reason for incompleteness is not really the nature of arithmetic, unlike what I myself had previously thought. Some people might think that induction is the culprit, but PA− is also essentially incomplete (cannot be extended to a complete implementable formal system). After seeing that, some people like myself might think that perhaps it's the interaction of addition and multiplication. Not so.

TC (theory of concatenation) is basically the following:
1. Closure of strings under concatenation
2. Associativity of concatenation on strings
3. Existence of at least two distinct strings
4. Given any strings a,b,c,d such that a+b=c+d, there is a string x such that either ( a+x=c and b=x+d ) or ( a=c+x and b+x=d ).

TC is essentially incomplete.

So string concatenation alone is sufficient to generate incompleteness, and not surprisingly it's via being able to reason about program execution (encoding a Turing machine running on a tape as a single string) correctly. That really is the key, and it does not matter whether you can do it via string manipulation as in TC or via Godel coding and decoding as in PA.

That's all I have to say for the moment. Feel free to ask further here or in the logic chat-room! =)

@SimplyBeautifulArt: You may be interested in the question I just asked, as the function defined there is a fast-growing function f that grows faster than any function that is provably total in the chosen system S. f is provably total under the assumption that S is Π2-sound.

In this question I will work in ACA. Take any formal system $S$ with a proof verifier program that interprets classical arithmetic. Then $S$ is (arithmetically-)consistent iff some specific program $c$ (that searches for a proof of "$0=1$" over $S$) does not halt. So consistency corresponds direc...

xD Can't absorb this stuff at school

4:32 PM

@user21820 Feeling way better. Hope you are well! I'm on a bit of a break. Will be more active soon.

o/ @SimplyBeautifulArt

@shredalert o/

@shredalert That's always wonderful to hear

@SimplyBeautifulArt what you been up to?

@shredalert School I guess? Boringness and all that

@user21820 : I found your concatenation theory thing easier to handle. I will also read the attached pdf for the proof, but the explanation in terms of Turing machine is pretty accessible to me

@user21820 @ParamanandSingh @shredalert I'm not sure if my memory is correct, but was there something someone once said in here concerning the concept that some things can't be proven without induction?

5:37 PM

@SimplyBeautifulArt There are quite a lot of things that depend on induction to be proved. Quite a few things which rely on induction just to be defined.

@shredalert Hm, okay

@SimplyBeautifulArt Any reason in particular why you ask?

6:07 PM

@shredalert Something about induction in the main chat yesterday

3 hours later…

8:46 PM

@SimplyBeautifulArt The idea of inf and sup are also a part of those intuitive concepts that can't really be defined in a non-circular way.

8:58 PM

@shredalert Hello! o/

o/ @amWhy

Hope you're getting treatment sorted out soon @amWhy

@shredalert Yeah... I've got an MRI scheduled for next week; depending on the results, I'll either need surgery (worst case scenario), or I will be referred to a pain clinic to receive shots (cortisol), in the affected areas. Which is not the greatest of scenarios, either, but would spare me, hopefully, from going under the knife!

Hoping for the best; feeling much better than last week, or the week before, so that's good. But x-rays do reveal a compression fracture in one of the vertebrae, as well as some bone spurs, which help explain the three primary points of pain. Any way. @shredalert How are you doing? When do you start classes?

9:16 PM

@amWhy got an exam on the 9th of September. No classes until October after that.

@amWhy I hope it's a best case scenario. Wishing you a speedy recovery.

@shredalert Good for the later start of classes (later than what I know); what exam? Ahh, okay. Good luck, but I'm quite confident that you'll nail it.

@amWhy mechanics mostly.

@amWhy I'll need to refresh my brain on the content soon.

@shredalert Are you pursuing an engineering degree, @shredalert, or physics/math?

@amWhy physics/math. Will be heading to bed soon. Hope to catch up soon. :)

@shredalert Sleep well!! (Think logic, math, logic, math, as you fall off to sleep!)