1st: Alain Badiou – Course on Logic (1980 – 81)
[What follows is a translation of lecture notes from a course on Logic delivered by Alain Badiou in 1980 - 81. It is rather short and deals specifically with Gödel and his theorem of incompleteness. I am not sure who would be interested, but here is it. There are two more course notes (1981 - 82 and 1982 - 83) that I will be posting in the realitively near future. Comments would be greatly appreciated. Enjoy!]
Course on Logic (1980 – 1983)
1980 – 1981
A formal system S is composed of 4 things:
1) Alphabet = stock of signs, either
• individual constants or proper names (0, for example)
• individual variables: x, y, x’, y’ …
• predicate constants (“=”, etc.)
• function constants (“+”, “*”, “succession”…etc.)
• statement of propositional variables: p, q, p’, q’ (Not predicate variables)
• logical signs (negation, implication, and, or…and quantifiers ∃ (there is at least one), ∀ (all)); cf.:
i. operator “or”: A or B ≡ ¬A→B
ii. operator “and”: A and B ≡ ¬(A→¬B)
iii. operator “equivalence”: A/B ≡ (A → B) and (B → A)
• signs of punctuation: “(“ “,” “[“ …
2) Grammar = rules used to form the correct formulas
Cf. Three axioms of the calculus of propositions (= axiomatic schema)
• p → (q→p)
• (p → (p → r)) → ((p → q) → (p → r))
• (¬p → ¬q) → (q → p) = transposition
Cf. also axioms of calculus of predicates
• [∀a (A → B)] → [A → (∀a)B]
• (∀a)A → Subst(x/y)A: one can replace Ax for y if y does not play a particular role in A (Universal instantiation)
4) Rules of deduction
• rules of substitution: if A ↔ B, on can replace A by B in a formula.
• Modus Ponens [p →q/p//q]
• Existential Instantiation: if p then (∃x)p
• Universal Generalization: if A then (∀x)A (One can universalize a statement)
Model M constitutes an interpretive domain: all systems of formulas are interpreted as true/false.
In the system, there is not true/false.
In the model, there is not demonstration.
Where the relation of to truth to demonstration (= as in proof)
S → M ≡ Syntax → Semantics = interpretation
M → S ≡ Semantics → Syntax = formalization
Gödel’s Theorem: There is always a formal statement p that is not demonstrable or refutable in S and where it is translated in M it is true.
There are three limitations where one demonstrates that there are equivalents:
1) incompleteness (semantics): ∃ a true statement not demonstrable in S.
2) indecidable (or incomplete syntax): ∃ an indecidable statement (neither demonstrable nor refutable)
3) irreflexibility as in coherence: impossibility to demonstrate in S its coherence (non-nomology)
1+5 conditions authorizing Gödel’s Theorem:
0) Countable alphabet (discreets!→writing) and final statements (= one can number the statements!)
1) The system must receive as a possible model the integers (the system must have an arithmetic capacity): the translation of the symbols must be capable of being the integers (condition for the function crossing translation and numerization).
2) The system must receive a diagonalized numerization: ∀P ∃a as Num(P)=Tran(a): “a” is translated as the number “n” at the same time as the statement P(a) has “a” for a number; “n” is then in a diagonal position for the predicate P (double function!).
3) The system must receive a predicate D support under the demonstrability: D(i) interpreted as Tran(i)∈Dem that is true if n=Tran(i) is the number of a demonstrable statement (= reflexive condition of the system or expressive condition as far as the question of demonstrability).
These three conditions converge ≡ a single condition: that the system is capable of representing all of the recursive functions. For any elementary arithmetic model, it has these properties.
4) The system must have a symbol translating the negative.
5) Being given a predicate P, ∃ the predicate Opposed-P(i) that corresponds to not-P(i) = condition of complementation.
In fact, three conditions arise:
1. the language is finite or numberable (not the design!)
2. the system comprises a symbol for negation
3. the system admits an elementary arithmetic model (whole numbers)
Principles of demonstration
1) Let D be a predicate demonstrably defined by:
Condition 3 = ∃ Opposed-D contrary of D (cf. Gödel Theorem 5); or
Condition 2 = ∃a such that Num[Opposed-D(a)]=Tran[D(a)]=n (It states that a statement “a” is indemonstrable.
2) One can demonstrate then that Opposed-D(a) (i.e. that “a” is not demonstrable in S) is not demonstrable (→incomplete):
If it was demonstrable, on could have D[opposed-D] and therefore Tran[Opposed-D(a)]∈Dem; or the translation is precisely “ ‘a’ is not translatable” therefore, it would not know it belongs to Dem! → Contradiction. Where incomplete: a true statement (in case the statement “ ‘a’ is indemonstrable”) is indemonstrable.
3) One demonstrates that more than that it is not refutable (→ indecidability)
(a) If it was refutable, then the model would no longer be a model because one could have decided that it would be false!
(b) If not-[Opposed-D(a)] is demonstrable, its translation is not-not-Tran[D(a)]∈Dem if Tran[D(a)]∈Dem. Therefore, n=Tran[D(a)] translates demonstrable statement; however n=Num[Opposed-D(a)]. Therefore, one could in a system demonstrate a statement Opposed-D(a) and its contrary not-[Opposed-D(a)]! Inconsistence of the system.
4) One then deduces the irreflexivity of the system:
If one could have demonstrated in the system a predicate affirming the consistency of the system, then one could demonstrate in the system that one could not have at the same time D(a) and Opposed-D(a); therefore one could deduce in the system Opposed-D(a) since one knows that D(a) is true; but then, by modus ponens, the indecidable statement would be decidable in the system and the system must be incoherent!
In this way, the formal does not exhaust the true.
Double function. Canonical example: a[P(a)] if, for example, “ ‘a’ says that it has a property P”
Husserl → nomological theories say that it is its own law.
Program of work defined by Hilbert.
Gödel indicates the failure of the nomological program.