Questions & explanations
1. Why do non-standard models exist despite the induction axiom?
The induction axiom in Peano arithmetic says that if a property holds for 0 and whenever it holds for a number it holds for its successor, then it holds for all numbers. In a non-standard model, this axiom is still true, but it only applies to properties that can be defined in the language of arithmetic. The property 'being a standard natural number' is not definable in that language, so induction does not force all numbers to be standard. The existence of non-standard models follows from the compactness theorem: we can add an infinite set of axioms stating that a new constant c is greater than each standard number, and every finite subset has a model (the standard numbers with c interpreted as a large enough number). Therefore, the whole theory has a model, which must contain a non-standard element.
2. What is logical syntax in Carnap's view?
Logical syntax is the study of the formal structure of a language, focusing only on the rules for forming and transforming sentences, not on their meaning. Carnap believed that philosophical problems about mathematics could be solved by clarifying the syntax of mathematical language. For him, a sentence is analytic if it is true solely because of its syntactic form and the meanings of its logical terms, like 'all bachelors are unmarried'. Analytic truths do not need empirical evidence; they are true by definition and the rules of language. Carnap's tolerance principle says we can freely choose any syntactic rules for a language, as long as they are consistent and useful. This means there is no single 'correct' logic or mathematics; we can adopt different frameworks for different purposes.
3. Why is the Baire category theorem important in constructive analysis, and what are its limitations?
The Baire category theorem is important because it is used to prove many fundamental results, such as the open mapping theorem and the uniform boundedness principle in functional analysis. In constructive analysis, we need a version that is provable without choice to keep the theory computable. However, the constructive version is more limited: it may only apply to spaces that are 'complete' in a stronger sense (like 'metric spaces with a modulus of completeness') or to spaces that are 'separable'. This means some classical applications are not constructively valid. For example, the classical proof that a Banach space cannot be a countable union of closed subspaces with empty interior uses the Baire category theorem, but the constructive version may not apply to all Banach spaces.
4. Compare the consistency of propositional logic with that of Peano arithmetic.
Propositional logic is a very simple formal system that deals with logical connectives like 'and', 'or', 'not'. Its consistency is easy to prove: we can use truth tables to show that every provable formula is a tautology (true in all assignments), and a contradiction like P and not P is not a tautology. So propositional logic is consistent. Peano arithmetic is much stronger; it includes axioms for natural numbers and induction. Its consistency is not provable within Peano arithmetic itself (by Gödel's theorem), but it can be proven in ZFC set theory by constructing a model (the natural numbers). However, ZFC's consistency is again unprovable within ZFC. So propositional logic's consistency is absolute and simple, while Peano arithmetic's consistency is relative and deeper.
5. How does a non-standard model differ from the standard natural numbers?
The standard natural numbers are the usual counting numbers 0,1,2,... In a non-standard model, there are additional numbers that come after all the standard ones. These non-standard numbers form a structure that looks like the natural numbers followed by a copy of the integers (..., -2, -1, 0, 1, 2, ...) repeated many times, each block being densely ordered. The arithmetic operations (addition and multiplication) extend to these new numbers in a way that still satisfies the Peano axioms. However, the induction principle in the non-standard model is not the same as the usual induction on natural numbers because it applies to all elements, including non-standard ones. This shows that the Peano axioms do not uniquely determine the structure of natural numbers.
6. What does it mean to prove consistency of a formal system?
Proving consistency of a formal system means showing that the system does not prove a contradiction, i.e., there is no statement P such that both P and its negation are provable. For a consistent system, there is at least one statement that is not provable (unless the system is trivial). Consistency is a fundamental property because an inconsistent system proves every statement, making it useless. Proofs of consistency often use a model: if we can construct a mathematical structure that satisfies all axioms, then the system is consistent because a contradiction would not hold in that model. However, Gödel's second incompleteness theorem says that a sufficiently strong system cannot prove its own consistency (unless it is inconsistent).
7. How does the constructive Baire category theorem differ from the classical one?
The constructive version typically requires the dense open sets to be 'located' or to have a certain property that allows us to construct a point in the intersection without choice. One common approach is to use a 'Baire space' that is a complete metric space with a countable base, and then use a 'choice-free' method like the 'Baire category theorem for complete metric spaces with a countable base' which can be proved using induction. Another approach is to use the 'Baire category theorem for separable complete metric spaces', where separability provides a countable dense set that can be used to avoid choice. The constructive theorem is weaker because it may require extra conditions like separability or a 'witness' for denseness.
8. Give an example of a set whose size is between ℵ₀ and 𝔠 if CH is false.
If the Continuum Hypothesis is false, then there exists a set of real numbers with cardinality strictly between ℵ₀ (the size of natural numbers) and 𝔠 (the size of the continuum). For instance, one can consider the set of all countable ordinals, which has size ℵ₁, the first uncountable cardinal. Under the negation of CH, ℵ₁ is less than 𝔠. However, it is not obvious that ℵ₁ is a subset of the reals; but it is consistent that the reals have size ℵ₂, so ℵ₁ is an intermediate cardinal. Another example: the set of all functions from natural numbers to {0,1} that are eventually zero has size ℵ₀, but the set of all functions has size 𝔠. If CH fails, there are many intermediate sizes, but no concrete example is known in ZFC alone.
9. Compare the computational content extracted from proofs in Peano arithmetic versus in weaker systems.
Proofs in Peano arithmetic (PA) can be transformed into constructive proofs using techniques like Gödel's Dialectica interpretation, which yields a program in a system of higher-type functionals. The extracted program may use recursion up to ε₀. For weaker systems like primitive recursive arithmetic (PRA), the extracted programs are primitive recursive functions, which are simpler and have bounded recursion. The computational content from PA is more complex and may involve bar recursion or transfinite recursion. In proof mining, the goal is to extract feasible bounds; often, even from PA proofs, one can obtain primitive recursive bounds by using techniques like monotone functional interpretation.
10. Compare the Continuum Hypothesis with the Axiom of Choice in terms of acceptance.
The Axiom of Choice (AC) is widely accepted by most mathematicians and is part of standard ZFC set theory. It has many useful consequences, like that every vector space has a basis. The Continuum Hypothesis (CH) is much more controversial and is not generally accepted as a true or false statement about the mathematical universe. Many set theorists work in ZFC without CH, but some explore alternatives like the Proper Forcing Axiom that implies ¬CH. Unlike AC, which is used in many branches of mathematics, CH has fewer practical implications outside set theory. The independence of CH shows that the concept of 'set' is not fully determined by ZFC, leaving room for different philosophical views.
11. What is the Elementary Theory of the Category of Sets (ETCS)?
ETCS is a set theory expressed in the language of category theory. Instead of treating sets as collections of elements with a membership relation, ETCS describes sets as objects in a category that satisfies certain axioms. The axioms include that there is a terminal object (like a singleton set), that pullbacks exist (allowing products and intersections), and that the category is well-pointed (elements determine maps). ETCS is equivalent in strength to the usual Zermelo-Fraenkel set theory with Choice (ZFC) but without the axiom of replacement. It provides a foundation for mathematics that is structuralist: it focuses on the relationships between sets rather than their internal composition.
12. Give an example of a consistency proof using a model.
Consider the formal system of group theory: axioms for a binary operation that is associative, has an identity element, and every element has an inverse. To prove consistency, we can give a model: the set of integers with addition. This structure satisfies all the group axioms. Since the integers exist (in standard mathematics), the axioms are consistent—they do not lead to a contradiction. Similarly, Euclidean geometry can be shown consistent by interpreting points as pairs of real numbers. However, for stronger systems like Peano arithmetic, a model exists (the natural numbers), but proving that model exists requires assuming a stronger system, so it is a relative consistency proof.