2

What is the minimum number of axioms you need, apart from definitions and usage of the notation, such that you have a system that does not contradict itself?

I would just think that the answer is simply 1, but then, what does Godel's incompleteness theorem say about it? Would there exist a statement that cannot be proved?

Improve this question
0

3 Answers 3

Reset to default
8

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 otehr 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.

Improve this answer
1
  • 3
    Well, I'd say the minimum number of axioms for a contradiction free system must be zero. Usually this would be ruled out as a trivial case, but for the sake of the OP I think it's worth emphasizing here that vacuous systems are in fact consistent.
    – David H
    Mar 9, 2015 at 20:00
3

GIT only applies to axiom systems that can express the natural numbers. Given any such one-axiom system, it would be incomplete.

An example of a one-axiom system that's incomplete would be the conjunction of the Godel-Bernays axioms. http://en.wikipedia.org/wiki/Von_Neumann%E2%80%93Bernays%E2%80%93G%C3%B6del_set_theory

In other words, NGB can be finitely axiomatized so that you could then take the logical conjunction of each of the axioms to make a single statement that encapsulates all of the axioms. It would then be incomplete.

Improve this answer
4
  • You cannot take the conjunction of the Godel-Bernays axioms because there are infinitely many of them. But if you're looking for a one-axiom system that's incomplete, you don't need anything remotely this complicated. Just take a single variable $x$, a single predicate symbol $P$, and a single axiom $P(x) -> P(x)$.
    – WillO
    Mar 9, 2015 at 23:00
  • @WillO I picked NGB because it's finitely axiomatizable. But perhaps I'm misunderstanding some distinction between finitely axiomatizable and having finitely many axioms. Is that the case? "NBG, unlike ZFC and MK, can be finitely axiomatized." en.wikipedia.org/wiki/… But I've never studied NBG so perhaps I'm missing a subtlety.
    – user4894
    Mar 9, 2015 at 23:30
  • It surprises me to learn that (at least according to Wikipedia) NGB can be finitely axiomatized, but one does hope to learn something new every day. The one thing I'd be cautious about is that even if NGB is finitely axiomatizable, it remains the case (unless I'm mistaken again) that the usual NGB axioms are infinite in number, so that when you say "take the conjunction of all the axioms", you need to make it clear that you are talking about some alternate (finite) set of axioms, not the usual (infinite) set.
    – WillO
    Mar 9, 2015 at 23:33
  • @WillO - you can see in Elliott Mendelson, Introduction to mathematical logic (4th ed - 1997), page 225-on, a version of NGB without axiom schema. See page 240 : "This completes the list of axioms of NBG, and we see that NBG has only a finite number of axioms".
    – Mauro ALLEGRANZA
    Mar 10, 2015 at 7:47
0

A really simple axiomatic system to consider:

Alphabet: |

Axiom: ||

Rule of inference: We can append | to the end of every statement.

From the only axiom, we infer |||.

From |||, we infer ||||.

From ||||, we infer |||||.

And so on.

Obviously no contradictions are possible, but we cannot derive |.

A little more complicated system with something like true and false statements:

Alphabet: ~ |

Axiom 1: |

Axiom 2: ~||

Rule of inference: You can append || to the end of each statement.

Note that we cannot derive both statement x (not beginning with '~') and statement ~x. So, no "contradictions." You cannot derive ~|. You also cannot derive ||.

So, I'm guessing, you will need at least one axiom and one rule of inference in any axiomatic system. If you want to model "true" and "false" statements, you will probably need at least two axioms.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.