Formal Theories Flashcards
Theories formulas in the language of first-order logic:
- Specific non-logical sombols (language)
- For axiomatic theories: specific axioms
In FOL, soundness and completeness happen at a certain time
Define a theory:
A theory (T) is a set of sentences, such that
s ∃ T iff T ⊢ s
Sentence: formulas with no free variables
Therefore, sentences are closed under deduction (deductively closed). Whatever deduce from the formulas in a theory is itself already a theory
What arethe types of theories?
- Axiomatic
- Consistent
- Complete
- Incomplete
Axiomatic Theory:
Theory is axiomatic if there is a decidable set of sentences A (axioms)
Such that: T = {s | A ⊢ s}
Every element in the theory can be deduced from the axioms. Need a set of axioms that are decidable
Consistent Theory:
Theory T is consistent if it does not contain an inconsistent pair of formulas (i.e. both A and ~A)
Complete Theory:
Theory T is conplete if, for any sentence A in the langauge, either T ⊢ A or T ⊢ ~A.
Theory incomplete, if there is a wff A such that T⊬ A and T⊬ ~A
How to show that a theory is consistent?
- Derive theorems and see whether you can get an inconsistent pair. When to know when to stop?
- Give a model (interpretation in a structure that makes all formulas true)
Define a model:
interpretation in a structure that makes all formulas true
How can a model be used to try and show the consistency of Euclidean geometry (and corresponding subsets of numbers)?
a) Euclidean geometry ! Model using pairs of R (real numbers, cartesian coordinates).
Thus, the consistency of geometry depends on/is relative to R .
* Next problem: How do we know that our notion of R is consistent?
b) R can be characterized in terms of sets and rational numbers (Dedekind).
c) Rational numbers can be characterized as tuples of integers, e. g., (1, 2) for 1/2
d) Integers can be characterized as tuples of IN, e. g., (0, 1) or (2, 3) for -1 .
- Good, but you still need to show the consistency of the theory of natural Numbers
What are possible solutions to determining the consistency of Euclidean Geometry?
1. Reduce the natural numbers to logic (Frege).
Frege’s system was inconsistent’: Russell’s paradox.
2. Reduce the natural numbers to set theory (Cantor):
What about the set that contains all those sets that don’t contain themselves? {x | x ∄ x}
3. Accept only the natural numbers!
(Kronecker: ‘God created the integers, all the rest was made by humans.’)
* Ok, but rather limiting and not really convincing. . .
What where Hilbert’s Problems in 1900?
Problem 01:
Cantor’s problem of the cardinal number of the continuum: Is there a cardinality between aleph-0 and 2^(aleph-0)?
Problem 02:
The compatibility (consistency) of the arithmetical axioms
What was Hilber’s Programme?
Aim Hilbert’s program: “Establish once and for all the certitude of mathematical methods”
Strategy:
(A) “Finitary number theory” is certain and consistent
(B) Transfer to the rest of mathematics
Thus, we have …
(A) Meaningful, contentful theory: finetary arithmetic
(B) Formal systems can interpreted mathematically
How to foramlize a particular theory?
Introduce additional axioms about the non-logical symbols in langauge
Cannot derive any propositions about geometry from logic along, but can from (1) logic and (2) Euclid’s axioms
What are the theories of arithmetic?
- Dedekind-Peano Arithmetic (DPA), or
- First-Order Arithmetic (FOA), or
- Typological Number Theory (TNT) [Hofstadter]
What are the axioms for the “theories of arithmetic?”
How to show that something does not derive?
Rather than showing that something cannot derive, show that it does not follow semantically.
What is ω-imcomplete?
System is ω-incomplete if all the strings in a pyramidal family are theorems, but the universally quantified summarizing string is not a theorem.
Summarizing string: ∀x: (0 + x) = x
Neither is ~∀x: (0 + x) = x a theorem of the system.
Independence and its relation to geometry and arithmetic?
Still consistent; cannot derive inconsistent pair (wff A and ~A)
What is the induction axiom?
Consider:
Ω = {x is a sentence in the language of FOA | x is true in N}
(1) Is this set a theory?
(2) Is this set consistent?
(3) Is this set complete?
(4) What is the relation between DPA and Ω?
