display all the ideas for this combination of texts
31 ideas
| 10616 | Second-order arithmetic can prove new sentences of first-order [Smith,P] |
| Full Idea: Going second-order in arithmetic enables us to prove new first-order arithmetical sentences that we couldn't prove before. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 23.4) | |
| A reaction: The wages of Satan, perhaps. We can prove things about objects by proving things about their properties and sets and functions. Smith says this fact goes all the way up the hierarchy. |
| 10076 | The 'range' of a function is the set of elements in the output set created by the function [Smith,P] |
| Full Idea: The 'range' of a function is the set of elements in the output set that are values of the function for elements in the original set. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 02.1) | |
| A reaction: In other words, the range is the set of values that were created by the function. |
| 10605 | Two functions are the same if they have the same extension [Smith,P] |
| Full Idea: We count two functions as being the same if they have the same extension, i.e. if they pair up arguments with values in the same way. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 11.3) | |
| A reaction: So there's only one way to skin a cat in mathematical logic. |
| 10075 | A 'partial function' maps only some elements to another set [Smith,P] |
| Full Idea: A 'partial function' is one which maps only some elements of a domain to elements in another set. For example, the reciprocal function 1/x is not defined for x=0. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 02.1 n1) |
| 10074 | A 'total function' maps every element to one element in another set [Smith,P] |
| Full Idea: A 'total function' is one which maps every element of a domain to exactly one corresponding value in another set. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 02.1) |
| 10612 | An argument is a 'fixed point' for a function if it is mapped back to itself [Smith,P] |
| Full Idea: If a function f maps the argument a back to a itself, so that f(a) = a, then a is said to be a 'fixed point' for f. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 20.5) |
| 10615 | The Comprehension Schema says there is a property only had by things satisfying a condition [Smith,P] |
| Full Idea: The so-called Comprehension Schema ∃X∀x(Xx ↔ φ(x)) says that there is a property which is had by just those things which satisfy the condition φ. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 22.3) |
| 10595 | A 'theorem' of a theory is a sentence derived from the axioms using the proof system [Smith,P] |
| Full Idea: 'Theorem': given a derivation of the sentence φ from the axioms of the theory T using the background logical proof system, we will say that φ is a 'theorem' of the theory. Standard abbreviation is T |- φ. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 03.4) |
| 10602 | A 'natural deduction system' has no axioms but many rules [Smith,P] |
| Full Idea: A 'natural deduction system' will have no logical axioms but may rules of inference. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 09.1) | |
| A reaction: He contrasts this with 'Hilbert-style systems', which have many axioms but few rules. Natural deduction uses many assumptions which are then discharged, and so tree-systems are good for representing it. |
| 10613 | No nice theory can define truth for its own language [Smith,P] |
| Full Idea: No nice theory can define truth for its own language. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 21.5) | |
| A reaction: This leads on to Tarski's account of truth. |
| 10078 | An 'injective' ('one-to-one') function creates a distinct output element from each original [Smith,P] |
| Full Idea: An 'injective' function is 'one-to-one' - each element of the output set results from a different element of the original set. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 02.1) | |
| A reaction: That is, two different original elements cannot lead to the same output element. |
| 10077 | A 'surjective' ('onto') function creates every element of the output set [Smith,P] |
| Full Idea: A 'surjective' function is 'onto' - the whole of the output set results from the function being applied to elements of the original set. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 02.1) |
| 10079 | A 'bijective' function has one-to-one correspondence in both directions [Smith,P] |
| Full Idea: A 'bijective' function has 'one-to-one correspondence' - it is both surjective and injective, so that every element in each of the original and the output sets has a matching element in the other. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 02.1) | |
| A reaction: Note that 'injective' is also one-to-one, but only in the one direction. |
| 10070 | If everything that a theory proves is true, then it is 'sound' [Smith,P] |
| Full Idea: If everything that a theory proves must be true, then it is a 'sound' theory. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 01.1) |
| 10086 | Soundness is true axioms and a truth-preserving proof system [Smith,P] |
| Full Idea: Soundness is normally a matter of having true axioms and a truth-preserving proof system. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 03.4) | |
| A reaction: The only exception I can think of is if a theory consisted of nothing but the axioms. |
| 10596 | A theory is 'sound' iff every theorem is true (usually from true axioms and truth-preservation) [Smith,P] |
| Full Idea: A theory is 'sound' iff every theorem of it is true (i.e. true on the interpretation built into its language). Soundness is normally a matter of having true axioms and a truth-preserving proof system. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 03.4) |
| 10598 | A theory is 'negation complete' if it proves all sentences or their negation [Smith,P] |
| Full Idea: A theory is 'negation complete' if it decides every sentence of its language (either the sentence, or its negation). | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 03.4) |
| 10597 | 'Complete' applies both to whole logics, and to theories within them [Smith,P] |
| Full Idea: There is an annoying double-use of 'complete': a logic may be semantically complete, but there may be an incomplete theory expressed in it. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 03.4) |
| 10069 | A theory is 'negation complete' if one of its sentences or its negation can always be proved [Smith,P] |
| Full Idea: Logicians say that a theory T is '(negation) complete' if, for every sentence φ in the language of the theory, either φ or ¬φ is deducible in T's proof system. If this were the case, then truth could be equated with provability. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 01.1) | |
| A reaction: The word 'negation' seems to be a recent addition to the concept. Presumable it might be the case that φ can always be proved, but not ¬φ. |
| 10609 | Two routes to Incompleteness: semantics of sound/expressible, or syntax of consistency/proof [Smith,P] |
| Full Idea: There are two routes to Incompleteness results. One goes via the semantic assumption that we are dealing with sound theories, using a result about what they can express. The other uses the syntactic notion of consistency, with stronger notions of proof. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 18.1) |
| 10080 | 'Effective' means simple, unintuitive, independent, controlled, dumb, and terminating [Smith,P] |
| Full Idea: An 'effectively decidable' (or 'computable') algorithm will be step-by-small-step, with no need for intuition, or for independent sources, with no random methods, possible for a dumb computer, and terminates in finite steps. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 02.2) | |
| A reaction: [a compressed paragraph] |
| 10087 | A theory is 'decidable' if all of its sentences could be mechanically proved [Smith,P] |
| Full Idea: A theory is 'decidable' iff there is a mechanical procedure for determining whether any sentence of its language can be proved. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 03.4) | |
| A reaction: Note that it doesn't actually have to be proved. The theorems of the theory are all effectively decidable. |
| 10088 | Any consistent, axiomatized, negation-complete formal theory is decidable [Smith,P] |
| Full Idea: Any consistent, axiomatized, negation-complete formal theory is decidable. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 03.6) |
| 10081 | A set is 'enumerable' is all of its elements can result from a natural number function [Smith,P] |
| Full Idea: A set is 'enumerable' iff either the set is empty, or there is a surjective function to the set from the set of natural numbers, so that the set is in the range of that function. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 02.3) |
| 10083 | A set is 'effectively enumerable' if a computer could eventually list every member [Smith,P] |
| Full Idea: A set is 'effectively enumerable' if an (idealised) computer could be programmed to generate a list of its members such that any member will eventually be mentioned (even if the list is empty, or without end, or contains repetitions). | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 02.4) |
| 10084 | A finite set of finitely specifiable objects is always effectively enumerable (e.g. primes) [Smith,P] |
| Full Idea: A finite set of finitely specifiable objects is always effectively enumerable (for example, the prime numbers). | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 02.4) |
| 10085 | The set of ordered pairs of natural numbers <i,j> is effectively enumerable [Smith,P] |
| Full Idea: The set of ordered pairs of natural numbers (i,j) is effectively enumerable, as proven by listing them in an array (across: <0,0>, <0,1>, <0,2> ..., and down: <0,0>, <1,0>, <2,0>...), and then zig-zagging. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 02.5) |
| 10601 | The thorems of a nice arithmetic can be enumerated, but not the truths (so they're diffferent) [Smith,P] |
| Full Idea: The theorems of any properly axiomatized theory can be effectively enumerated. However, the truths of any sufficiently expressive arithmetic can't be effectively enumerated. Hence the theorems and truths of arithmetic cannot be the same. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 05 Intro) |
| 10600 | Being 'expressible' depends on language; being 'capture/represented' depends on axioms and proof system [Smith,P] |
| Full Idea: Whether a property is 'expressible' in a given theory depends on the richness of the theory's language. Whether the property can be 'captured' (or 'represented') by the theory depends on the richness of the axioms and proof system. | |
| From: Peter Smith (Intro to Gödel's Theorems [2007], 04.7) |
| 21565 | Richard's puzzle uses the notion of 'definition' - but that cannot be defined [Russell] |
| Full Idea: In Richard's puzzle, we use the notion of 'definition', and this, oddly enough, is not definable, and is indeed not a definite notion at all. | |
| From: Bertrand Russell (On 'Insolubilia' and their solution [1906], p.209) | |
| A reaction: The background for this claim is his type theory, which renders certain forms of circular reference meaningless. |
| 21564 | Vicious Circle: what involves ALL must not be one of those ALL [Russell] |
| Full Idea: The 'vicious-circle principle' says 'whatever involves an apparent variable must not be among the possible values of that variable', or (less exactly) 'whatever involves ALL must not be one of ALL which it involves. | |
| From: Bertrand Russell (On 'Insolubilia' and their solution [1906], p.204) | |
| A reaction: He offers this as a parallel to his 'no classes' principle. That referred to classes, but this refers to propositions, and specifically the Liar Paradox (which he calls the 'Epimenedes'). |