Godel Flashcards
x is even
x < y
Axiom
Fundamental assumption or self-evident truth that serves as a starting point for logical reasoning.
Formula
- Syntactically valid way or arranging characters
- Formula that represents a relationship between variables
Theorem
- A statement that can be proven to be true based on axioms
If the system is inconsistent…
then every formula is provable
If you can find a formula that is not provable…
then the system is consistent
Universally valid
- Always true regardless of the truth values of their components
- Tautology
- Ex: p or not p
Complete
- Every true statement in the system’s language can be proven from the axioms
- Must prove S or notS
- Incomplete: there exist true statements about natural numbers that cannot be proven using Peano Arithmetic
Consistent
- A consistent system of axioms does not lead to contradictions
- Cannot prove S and notS
- Inconsistent: sysetem has x=1 and x=2
Decidable
Decidable if there exists an algorithm that always terminates with a correct yes/no answer
What did Godel prove?
Any set of axioms you could posit as a possible foundation for math will inevitably be incomplete
If the system is inconsistent
Anything is provable
If something is not provable
consistent
If something is not universally valid
consistent
p or q
not universally valid
How to get from axiom/theorem to a true statement about logic?
arithmetic opertation OR logical deduction
First-order logic vs propositional logic
- First-order has “there exists” and “for all”
Independent
Axioms that cannot be proven or disproven using the other axioms within that system
