minimum limit for axioms in a system?



If we have an axiom system with a finite number of axioms, we can always reduce them to only one, replacing the set of original axioms with their conjunction.


Thus, every non-trivial axiom system that is finitely axiomatized can be formulated in an equivalent form with a single axiom.


Gödel's Incompleteness Theorems apply to systems that (in addition to other conditions) have a set of axioms that is finite or at least decidable; Robinson arithmetic, for example, is finitely axiomatized and it is enough for G's Theorem.



from logic - What is the minimum number of axioms required for a system of axioms? - Philosophy Stack Exchange


Robinson arithmetic


1. Sx ≠ 0


0 is not the successor of any number.


2. (Sx = Sy) → x = y


If the successor of x is identical to the successor of y, then x and y are identical. (1) and (2) yield the minimum of facts about N (it is an infinite set bounded by 0) and S (it is an injective function whose domain is N) needed for non-triviality. The converse of (2) follows from the properties of identity.


3. y=0 ∨ ∃x (Sx = y)


Every number is either 0 or the successor of some number. The axiom schema of mathematical induction present in arithmetics stronger than Q turns this axiom into a theorem.


4. x + 0 = x


5. x + Sy = S(x + y)


(4) and (5) are the recursive definition of addition.


6. x·0 = 0


7. x·Sy = (x·y) + x


(6) and (7) are the recursive definition of multiplication.


Travelling salesman problem - Wikipedia



General number field sieve - Wikipedia



links, notes and resources



Share the love!

Thank y'all kindly for the read!