Difference between revisions of "User:IssaRice/Computability and logic/Some important distinctions and equivalences in introductory mathematical logic"

This page lists some important distinctions in introductory mathematical logic and computability theory. Bizarrely, most books won't even mention these distinctions, so you will probably be very confused at the start as you inevitably conflate these ideas.

Term Distinction Further reading
• completeness: semantically complete (complete logic; the topic of the completeness theorem) vs negation-complete (complete theory; the topic of the first incompleteness theorem)
• decides: decidable set/relation vs deciding a sentence vs a theory being decidable vs deciding every sentence vs a logic being decidable (decidability of logic has several equivalent formulations; this is the topic of the Entscheidungsproblem)
• soundness: sound logic (soundness theorem) vs sound theory
• truth in all interpretations (validity) vs truth in the intended interpretation (natural reading, standard interpretation): see User:IssaRice/Computability and logic/Intended interpretation versus all interpretations
• structure vs interpretation vs model: synecdoche problem
• interpretation: there's interpretation in the "structure" sense and also interpretation in the sense of embedding one theory inside another theory (e.g. doing arithmetic with sets)
• theory vs axioms: synecdoche problem
• language vs logic vs formal system vs system
• proves logically vs proves in a particular theory: each theory adds some non-logical axioms that allows it to prove things that aren't logically valid
• $\models$: when a set of sentences comes before the symbol vs when a structure comes before the symbol: see User:IssaRice/Computability and logic/Models symbol
• deciding (corresponding to computable total functions) vs recognizing (semi-deciding, computably enumerating; corresponding to computable partial functions)
• algorithm vs program vs index vs Godel number
• algorithm vs function computed by algorithm: see User:IssaRice/Computability and logic/Function versus algorithm
• expresses vs captures (strong capture, weak capture): see User:IssaRice/Computability and logic/Expresses versus captures
• primitive recursive vs (general, μ) recursive
• $\Delta_0 = \Sigma_0 = \Pi_0$ vs $\Delta_1 = \Sigma_1 \cap \Pi_1$
• $\Sigma_n$ formulas vs relations vs sets
• enumerating vs computably enumerating

More speculative:

• different kinds of diagonalization?

There are also some important equivalences to keep in mind:

• Turing computable = computable = recursive = unbounded loops
• Primitive recursive = bounded loops
• computably enumerating = semi-deciding
• computably enumerating in order = deciding
• diagonalization lemma = rogers fixed point theorem
• Kleene's T predicate, godel beta function, Prf(m,n)
{"ft_lang_label":"__label__en","ft_lang_prob":0.8472453,"math_prob":0.95422924,"size":3818,"snap":"2019-43-2019-47","text_gpt3_token_len":820,"char_repetition_ratio":0.14472994,"word_repetition_ratio":0.28355387,"special_character_ratio":0.19250917,"punctuation_ratio":0.10526316,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99621254,"pos_list":[0,1,2,3,4,5,6,7,8],"im_url_duplicate_count":[null,null,null,7,null,7,null,7,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-10-18T08:59:22Z\",\"WARC-Record-ID\":\"<urn:uuid:c5f56cc5-f4d3-4657-ac5c-168e85049f18>\",\"Content-Length\":\"27911\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:695c356b-4e3d-4931-8d91-d0db5f9d3cdc>\",\"WARC-Concurrent-To\":\"<urn:uuid:710b87c2-64cb-477b-a9b2-0a894da7305b>\",\"WARC-IP-Address\":\"96.126.114.7\",\"WARC-Target-URI\":\"https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/Some_important_distinctions_and_equivalences_in_introductory_mathematical_logic&diff=prev&oldid=1647\",\"WARC-Payload-Digest\":\"sha1:KHWYSTEP2TUM2IP26W37KI3TGJHNOYDF\",\"WARC-Block-Digest\":\"sha1:LACEIWLZMLB7P3P2OLAWVW42SI4GCA3K\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-43/CC-MAIN-2019-43_segments_1570986679439.48_warc_CC-MAIN-20191018081630-20191018105130-00205.warc.gz\"}"}