Foundations and logic

What proof, independence and undecidability actually mean, and why three of those words get used for two different things.

7 questions. Reveal each answer when you have committed to one.

1. What distinguishes a conjecture from a theorem?

   • AA conjecture has not been proved
   • BA conjecture is known to be false
   • CA conjecture has no counterexample
   • DA conjecture is shorter
   Show the answer

   A. A conjecture has not been proved

   A conjecture is a precisely stated claim awaiting proof or disproof. It is not a weaker kind of theorem, and it carries no guarantee: conjectures are regularly disproved after large amounts of supporting evidence. More on conjecture.

2. How many counterexamples are needed to disprove a universal claim?

   • ANone, because disproof needs a general argument
   • BOne
   • CInfinitely many
   • DA majority of the cases
   Show the answer

   B. One

   This asymmetry is why numerical evidence never settles a universal claim: proving it requires an argument covering every case, refuting it requires exactly one case. More on counterexample.

3. Gödel’s first incompleteness theorem applies to a formal system that is strong enough to express arithmetic and is also

   • Adecidable
   • Bfinite
   • Cconsistent and effectively axiomatised
   • Dcomplete
   Show the answer

   C. consistent and effectively axiomatised

   Consistency is required because an inconsistent system proves everything, including every true statement. Effective axiomatisation is required because true arithmetic is complete and escapes the theorem only by having no listable axioms. More on gödel’s incompleteness theorems.

4. What does it mean that the continuum hypothesis is independent of ZFC?

   • AIt is unproved but expected to be true
   • BNo algorithm can decide it
   • CIt is false
   • DNeither it nor its negation can be proved from ZFC
   Show the answer

   D. Neither it nor its negation can be proved from ZFC

   Gödel showed in 1940 it cannot be disproved from ZFC and Cohen showed in 1963 it cannot be proved. That is a definitive answer about what those axioms decide, which is why it is not an open problem in the usual sense. More on continuum hypothesis.

5. Two sets have the same cardinality when

   • Atheir elements can be matched one to one with none left over
   • Bthey are both infinite
   • Cone is contained in the other
   • Dthey contain the same elements
   Show the answer

   A. their elements can be matched one to one with none left over

   This criterion reproduces counting for finite sets and produces genuinely different sizes of infinity for infinite ones. It also makes some sets the same size as their own proper subsets, which is the defining oddity of the infinite. More on cardinality.

6. Why does the axiom of choice have no content for finite collections?

   • AFinite sets are countable
   • BThe choices can be made one at a time by induction
   • CThe axiom applies only to sets of real numbers
   • DFinite sets have no proper subsets
   Show the answer

   B. The choices can be made one at a time by induction

   For finitely many nonempty sets, induction produces the selection with no extra assumption. The entire content of the axiom is the infinite case, and specifically the case where no rule for choosing is available. More on axiom of choice.

7. A statement true of the natural numbers but unprovable in a given consistent system shows that the system is

   • Aunfounded
   • Binconsistent
   • Cincomplete
   • Dmeaningless
   Show the answer

   C. incomplete

   Incompleteness is exactly this: a true statement the system cannot reach. It says nothing about the system being wrong, and adding the statement as a new axiom simply produces a new system with the same property. More on gödel’s incompleteness theorems.