PHIL30043 Power and Limits of Logic

Get Started. It's Free
or sign up with your email address
PHIL30043 Power and Limits of Logic by Mind Map: PHIL30043 Power and Limits of Logic

1. Godel's Incompleteness

1.1. Godel numbering

1.1.1. Definition A relationship between natural numbers and statements such that 1) Every statement has a unique number 2) The Godel number of any statement is calculable 3) It is decidable as to whether a number the Godel number of some statement (and if so what statement) Denote ^A^ the Godel number of the expression A

1.2. Diagonalisation

1.2.1. Diagonalisation of a formula Definition Is sort of a function from the set of formulas to the set of formulas Given a formula A (in particular with free variable x), its diagonalisation is (exists x) (x = ^A^ and A(x)) Equivalently, "A(^A^) is true" Equivalently, "A holds true of its own Godel numer" Note: The diagonalisation of a formula simply yields another formula, it is not asserting the truth of that formula! Examples Diagonalisation of "x is even" Diagonalisation of "x + 0 = x" Diagonalisation of "x = x+1"

1.2.2. The diagonalisation function diag(n) Definition diag(n) a function from N => N If n is NOT the Godel number of some formula, just return 0 Otherwise, return the Godel number of the diagonalisation of that formula So diag(^A(x)^) = ^"(exists x) (x=^A(x)^ and A(x)"^ Equivalently, diag(^A(x)^) = ^"A(^A^) is true"^ Equivalently, diag(^A(x)^) = ^"A holds true of its own Godel number"^ Examples if n=1234 (not the Godel number of any formula) if n=^"x is even"^ if n=^"x+0=x"^ diag(n) is recursive So it is represented in Q

1.2.3. Diagonalisation Lemma Definition If diag(n) is represented in some theory T... ...then for any formula B(y)... ...there exists some sentence G... ...such that T |- G == B(^G^) Proof Representation of diag(n) in the theory Consider F, G So if T represents diag(n), then for any formulat B(n), there is some statement G such that T |- G == B(^G^) In other words.... If a theory represents diag(n), then for every predicate, there exists some sentence which is logically equivalent to the predicate of the Godel number of that sentence! This is a bit like a "fixed point" for the predicate (although we are not asserting that this is the only fixed point) Each predicate magically has some (at least one) related sentence which is logically equivalent to that predicate, fed the Godel number of that sentence, which is WEIRD

1.3. Definability

1.3.1. Definition A set of numbers N is definable by a formula B(n) in theory T iff... ... T |- B(n) iff n in N ... T |- ~B(n) iff n not in N

1.3.2. Implications If T is a consistent theory at least as strong as Q, then the set of theorems in T is not definable in T Proof Let T be a consistent theory at least as strong as Q Denote C(y) Question: does T |- G or not? Either way, contradiction. Hence, C does not exist, so the set of theorems of T is not definable in T.

1.4. Examples of applications of Incompleteness

1.4.1. Any consistent, deductively defined extension of Q is incomplete Since T extends Q, it does not represent its own theorems Since T extends Q, it represents all recursive sets So the set of theorems of T is not a recursive set So T is not decidable If it were complete, then it would be decidable (since consistent and DDT) So it isn't complete!

1.4.2. Set of theorems of predicate logic is undecidable Suppose the theorems of predicate logic were undecidable Then, any statement of Q could be proven from axioms, simply (Q1 & Q2 & ...) => S But Q isn't decidable! So, predicate logic is undecidable (eg. "Problem reduction")

1.4.3. True Arithmetic is undecidable Since TA has a model (by definition, the standard model of arithmetic), it is consistent Since TA is the set of all things true of the model, it is complete Because consistent and complete, it is not DDT Because extension of Q, it is not decidable

1.4.4. Summary Consistent, Q-extension ==> ~DefinesOwnSetOfTheorems (1) DefinesAllRecursiveSets (2) So ~HasRecursiveSetOfTheorems (3) Consistent, Complete, DDT ==> HasRecursiveSetOfTheorems (4) So, Consistent, DDT, Q-extension ==> Incomplete (5) PL If PL decidable then Q decidable (6) But Q not decidable So PL undecidable (7) TA Consistent, Complete, Q-extension So DefinesAllRecursiveSets (from 2) So ~DefinesOwnSetOfTheorems (from 1) So ~HasRecursiveSetOfTheorems (from 3) So ~DDT (from 5) (8) So Truth in standard model of arithmetic is not recursive, and not recursively enumerable

1.5. Lobs theorem

1.5.1. Provability predicate Definition A predicate B in theory T such that If T is DDT, then it the following statement is recursive: "x is the Godel number of a T-proof of the statement with Godel number y" So B(y) = (exists x)P(x,y) says that there exists a proof of y

1.5.2. Implications If T proves that a proof of A implies A... then T proves A If diagonalisation lemma holds for T, and there is a provability predicate B for T... ...then... ... T |- B(^y^) => y implies that T |- y Godels Second Incompleteness Theorem if B is a provability predicate for T And diagonalisation lemma holds for T And T is consistent Then T does not prove that ~B(^1=0^) Ie. T cannot prove its own consistency

1.5.3. Proof Too complicated lol

2. Computability

2.1. Definition

2.1.1. (This wasn't really presented as a theorem in lecture notes)

2.1.2. The set of recursive functions is exactly the set of functions computable by register machines

2.1.3. Equivalently, for Turing-machines, and other formulations

2.2. Proof

2.2.1. ==> Any recursive function can be implemented as a register machine Zero: has a simple register machine with a single instruction Succ: has a simple register machine with a single instruction Identity: has a simple register machine with a few instructions Cn[]: just chain the relevant register machines together Pr[]: simple put in a bigger register machine which decrements counter and repeats etc Mn[]: simply put in a bigger register machine which increments counter, checks condition and halts

2.2.2. <== Any register machine can be represented as a recursive function Represent the state of the register machine as a number Prime number theorem: STATE(S,A,B,C....) === 2^S * 3^A * 5^B * 7^C etc The machine has halted when S=0, so when STATE is odd Produce primitive recursive function which calculates the state of the register machine at step number N Function accepting x1,x2,....xm,n Pr(takestep, n) takestep defined by conditions where coefficients are 0 if case does not match instruction, 1 if case does match instruction Each instruction in the register machine is simply multiplication, exponentiation, etc! Produce minimisation function to calculate the step number at which it halts (if any) Given the STATE value, return s (extracted from p0^s) When s=0, RM has halted, and minimisation has terminated If s never is 0, the RM never halts, and the minimisation is undefined Produce primitive function to extract the output number from the state at the final step Given the minimisation function finding the value of y such that the RM halts Call the Pr(takestep,y) function, divide repeated by 3, the number of times we divide by 3 is the final output.

2.2.3. What it means Register machines and recursive functions pick out exactly the same set of calculations/computations Fun fact: any recursive function can be rewritten to use only a single minimisation function!

2.3. Incomputability Incalculability

2.3.1. Definition There are functions which are incomputable/incalculable

2.3.2. Proof: direct appeal to cardinalities There are countably many recursive functions/register-machines/turing-machines/pick your favourite However there are uncountably many functions Eg. consider that each function has a "characteristic bitstream", and every bitstream characterizes some function There are uncountably many bitstreams So there are uncountably many functions Therefore the are functions which are non-recursive/not-register-machine-computable/not-turing-machine-computable/etc

2.3.3. Examples Diagonalisation of total recursive functions Idea: within the set of total functions, any enumeration of total recursive functions will miss some total functions Define f* Suppose f* was recursive Therefore f* is non-recursive Halting problem The Idea: If we assume that the halting problem is Turing-computable, then we can derive a contradiction. Hence, the halting problem is not Turing-computable. Proof Busy Beaver function The Idea Proof

3. Compactness

3.1. Definition

3.1.1. Positive formulation X has a model <=> Every finite subset X' has a model Equivalently: X is satisfiable if and only iff every finite subset X' is satisfiable

3.1.2. Negative formulation X doesn't have a model <=> Some finite subset X' doesn't have a model Equivalently: X is unsatisfiable if and only if some finite subset X' is unsatisfiable

3.1.3. Due to equivalent between |= and |- (soundness and completeness) we can say the same for trees

3.2. Proof

3.2.1. X is consistent => [All] X' is consistent Clearly, if X has a model M, then every finite subset X' has a model - obviously M, if nothing else. Equivalently, if [Exists] X' inconsistent => X is inconsistent

3.2.2. [All] X' are consistent ==> X is consistent Instead show the contrapositive: that X is inconsistent ==> Some finite X' is inconsistent Instead, show this contrapositive using trees, given the equivalence between |= and |-, If "X |-" (ie. the tree starting with X closes), then the closed tree is finite, and every branch is closed in finite number of steps. Only a finite number of statements , X', were used to produce the tree closure That finite set of statements, X', is inconsistent Hence there exists a finite subset X' of X, which is inconsistent So if X is inconsistent, then some finite subset X' is inconsistent So if all finite subsets X' are consistent, then X is consistent True with respect to models as well as proofs, since |- <==> |=

3.3. Applications/consequences

3.3.1. Generally, able to show satisfiability of X without producing a complete model (just produce model for every subset)

3.3.2. Inexpressibility of finitude in FOPL "There is no way to say that there are only finitely many things" Sentences: X "There are only finitely many things" "It is not the case that there exist exactly 1 things" "It is not the case that there exist exactly 2 things" "It is not the case that there exist exactly 3 things" etc However any finite X' of X is satisfiable/consistent, since the first n are true of any model with n+ objects.. By compactness theorem, X is consistent, ie. satisfiable, ie. has a model But that means it is true in some infinite models! This is a contradiction Hence, "There are only finitely many things" cannot be expressed in FOPL

3.3.3. The consistency of infinitesimals with the reals Statement S: There exists c such that c < 1/n for all n Sets defined Let X1 be the set of statements already true Let X2 be the set of statements 0 < c < 1/1, 1/2, 1/3, ...... Let X be X1 + X2 Let X' be any finite subset of X The statement above is true for any finite X' subset X, since we find the X2 statement with largest denominator 1/n and set x = 1/(n+1) Since S is consistent why any finite X' subset of X, by the compactness theory, X is consistent Hence, infinitesimals defined in this way are consistent with the reals (aka. hyperreals) So given the standard model of the reals M, we can create a non-standard model including hyperreals, which makes the same things true!

3.3.4. Countable model theorem Definition If (finite or countably infinite) set X can be satisfied, then it can be satisfied by some finite or countably infinite domain Proof Suppose X is finite/countably-infinite set of statements which is satisfiable So a branch of the tree starting with X remains open This branch uses finite/countably-infinite number of names So a model with finite/countably-infinite number of objects in its domain can be constructed So X can be satisfied by a finite/countably-infinite model

4. Completeness

4.1. Definition

4.1.1. Positive formulation The completeness theorem states that if an argument is valid according to models, then is valid according to the proof method. Equivalently, if there exists no model for {X, ~A} (ie. unsatisfiable), then the argument "X |- A" is valid (according to the proof method). Equivalently, validity in terms of models (ie. no countermodel) implies validity in terms of proof methods (ie. tree closes) Equivalently, "|=" ==> "|-"

4.1.2. Contrapositive formulation Equivalently, if there the proof method states that an argment is invalid, then, there exists a countermodel Equivalently, invalidity in terms of methods (ie. existence of countermodel) implies invalidity in terms of proof methods (ie. tree remains open) The tableaux method for PL is complete: if there is no model in which {X,~A}, then the tree starting with {X, ~A} will close. Equivalently, "|/-" ==> "|/="

4.2. Examples

4.2.1. The tableaux method for FOPL is complete

5. Soundness

5.1. Definition

5.1.1. Positive formulation The soundness property states that if an argument is valid according to a proof method, then there exists no countermodel to the argument Equivalently, validity in terms of proof methods (ie. tree closes) implies validity in terms of models (ie. no countermodel exists) Equivalently, "|-" ==> "|="

5.1.2. Contrapositive formulation Equivalently, if a countermodel for the argument exists, then the proof method will show that the argument is invalid. Equivalently, invalidity in terms of models (ie. existence of countermodel) implies invalidity in terms of proof methods (ie. tree remains open) Equivalently, "|/=" ==> "|/-"

5.2. Examples

5.2.1. The tableaux proof method for PL or FOPL is sound: if a tree starting with {X, ~A} closes (Ie. X |- A), then there exists no model for {X, ~A}. Ie. validity in terms of the proof method implies validity in terms of models

6. Basic concepts

6.1. Language

6.1.1. A definition of allowable sentences?

6.2. Sentence

6.2.1. Properties True or false (given a model) Tautological Contradictory

6.2.2. Relationships Equivalence Embeds Transitive Symmetric Reflexive Entailment / Implication / Consequence A -> B A entails B A implies B B is a consequence of A Transitive Not symmetric Reflexive

6.2.3. Set of sentences Properties Satisfiable / unsatisfiable

6.3. Argument

6.3.1. Definition A set of premises and a conclusion

6.3.2. Properties Valid / Invalid Validity according to models Validity according to proof methods

6.4. Model

6.4.1. An interpretation (true/false) of all atomic sentences / literals

6.4.2. Defines truth for a language

6.4.3. Cannot contain contradiction Since interpretation function is a *function*, it returns exactly one output for each input

6.5. Proof method

6.5.1. Properties Sound / unsound Complete / incomplete Decidability

7. Advanced concepts

7.1. Set

7.1.1. Definition Unordered (possibility infinite) collection of distinct elements

7.1.2. Properties Empty / Non-empty Cardinality Finite Infinite Can't contain themselves (for this course at least) Must only contain "earlier defined" sets

7.1.3. Special examples The Empty Set Omega Same cardinality as the set of natural numbers Same cardinality as any countably infinite set Set of all bitstreams Uncountably infinite!

7.1.4. Recursivity of sets Recursive set Characteristic function (of a set) Definition Recursively enumerable set A set such that some recursive total function e, e(0), e(1), e(2), .... enumerates the members of the set (NOTE: Says nothing about non-membership of the set, in finite time... could wait forever!) Relationships A recursive set is recursively enumerable. But a recursively enumerable set is not necessarily a recursive set

7.1.5. Theory Definition A set of statements closed under logical consequence If T |- A, then A in T Qualities of theories Properties Relationships Ways of defining theories Deductively defined theory Examples Robinson's Arithmetic (Q) Peano Arithmetic (PA) Truth Arithmetic

7.2. Function

7.2.1. Definition A function has a domain, a range, and a mapping Each object in the domain is mapped to exactly one object in the range Total function Definition Partial function Definition

7.2.2. Notation Mathematical notation Lambda notation

7.2.3. Recursive functions Definition Functions made up of specific building blocks Recursive functions are either the basic functions, or functions built up via composite functions from recursive functions, and nothing else

7.3. Register Machine

7.3.1. Definition Finite number of buckets Unending supply of marbles Instruction sets [#, +/- Bucket, Next, -Next] Input in buckets, output in first bucket (by convention)

7.3.2. Relationship to functions A RM "computes the partial function" f if and only if; a) for every input x for which f(x) is defined, the RM outputs f(x) on that input; and b) for every input x for which f(x) is undefined, the RM never halts Ie. it computs the partial function if it produces the correct outputs, and always halts for undefined values

7.4. Diagonalisation

7.4.1. Any set which is uncoutnably infinite can be diagonalised: any enumeration will miss out some members (actually, the vast majority of members)

7.4.2. Examples Any enumeration of bitstreams which miss out the bistream with bits flipped along the diagonal Any enumeration of real numbers will miss out the real number with digits incremented along the diagonal Any enumeration of the characteristic bistreams of functions will miss out the characteristic bitstream of the functions which are flipped Any enumeration of Turing machines will miss out [ TODO ] Any enumeration of recursive functions will miss out on f*(n)=f_n(n)+1 If f* was in the enumeration then it is at index m So f*(m)=f_m(m)+1=f*(m)+1 - contradiction!

8. Logics taxonomy

8.1. Propositional logic

8.1.1. Language Literals Connectives And, Or, Imply, Negate Sentences built up from these (using brackets)

8.1.2. Models Made up of true/false values for each proposition

8.1.3. Normal forms Disjunctive normal form Not unique Every statement is equivalent to something in DNF Process Conjunctive normal form / Clausal form XOR conjunctive normal form

8.1.4. Proof methods Tableaux Process Soundness of Tableaux method for FOPL Completeness of Tableaux method for FOPL Decidability of Tableaux method for FOPL

8.2. First order predicate logic

8.2.1. Language Predicate literals Px Connectives And, Or, Imply, Negate Quantifiers Universal, existential Sentences built up from these (using brackets)

8.2.2. Models Non-empty domain Interpretation (true/false) of all P(x1,x2..xn) Interpretation of all names (from domain objects) NOTE: "standard name" - natural, canonical name for domain objects

8.2.3. Normal forms Prenex normal form Quantifiers followed by DNF Every statement in FOPL equivalent to something in Prenex Process

8.2.4. Proof methods Tableaux with quantifiers ?? Hilbert proofs Language Process Conditional proofs Soundness of Hilbert proof method for FOPL Completeness of Hilbert proof method for FOPL Hilbert Inconsistency Definition Decidability of Hilbert proof method for FOPL