*Ich muss wissen. Ich will weiss.*

- Gaps between 1st order logic and 2nd order logic.
*(See [3] and here)*- Compactness theorem does not hold: there is a countable but unsatisfiable set of 2nd order logic sentences, every finite subset of which is satisfiable.
- Löwenheim-Skolem theorem does not hold: there is a 2nd order logic sentence whose models are exactly those with noncountable universes.
- There is a 2nd order logic sentence whose only model (up to isomorphism)
is
**N**. - There is a 2nd order truth definition for 1st order sentences in
**N**. - Reachability and Hamiltonian Path is definable in 2nd order logic.
*(See [25])* - Only 1st order logic satisfies 0-1 law.

- Why the name Compactness theorem? What does it relate to compactness in topology?
- Intuionistic 1st order logic
*(See [13])* - Infinitary logic
- Modal logic
- Lindström's theorem for characterizing 1st order logic as maximal logic
admitting compactness theorem and Löwenheim-Skolem theorem
*(See [6] [24] pp. 261)* - Gentzen's
proof of consistency of number theory in infinitary logic
*(See [26])* - Fixed-points
- Rosser's method to construct 1st-order undecidable sentences
*(See [3])* - Natural undecidable 1st-order sentences (e.g. Extended finite Ramsey theorem
and Goodstein
sequences. Also see here)
*(See [15])* - Hilbert's
10th problem: the impossibility of obtaining a general solution to
Diophantine equations
*(See [4] [18] [27] and here)*- Interesting/surprising consequences:
- There is a polynomial P such that nonnegative values of P form the set of prime numbers.
- More generally, so long as the set is r.e., there is a polynomial enumerating it.
- There is a
*single*polynomial such that its zero exists iff there are positive integers x,y,z,n (n > 2) satisfying*x*^{n}+y^{n}=z^{n} - There is a "universal" polynomial U(y,x1,...,x9) such that for any polynomial P, P has zeros iff U(n,x1,..,x9) has zeros (for some n).
- J.P. Jones published many papers on Diophantine equations, see here

- Restricted version of Hilbert's 10th problem
- Some known results:
- Diophantine equations with 9 variables are unsolvable (if solutions in
**N**are sought), and with 21 variables are unsolvable (if solutions in**Z**are sought) - Diophantine equations with degree 4 are unsolvable.
- Diophantine equations with degree 2 are solvable, but the algorithm does not run in polynomial time (i.e. the problem is NP-complete)

- Diophantine equations with 9 variables are unsolvable (if solutions in
- Decidable fragments of number theory
*(See [23])* - Translation of number theory in ZFC
- Other implications of Incompleteness theorem
*(See [2])* - More applications of self-application
*(See [20])* - Decidability/Undecidability of first-order logic theories:
- Theory of abelian groups (Algebraically Closed Fields and Real Closed
Fields) are decidable (because they are complete)
*(See [19])* - Theory of groups (fields, ordered fields) is undecidable.
- The universal theory of groups (i.e. word
problem for groups) is undecidable.
*(due to Novikov and Boone. See [19] and [37])*

- Theory of abelian groups (Algebraically Closed Fields and Real Closed
Fields) are decidable (because they are complete)
- Techniques to prove decidability:
- Quantifier elimination (Presburger used it to prove Theory of
**N**with Addition. Tarski used it to prove Theory of**R**with Addition and Multiplication.)*(See [1] pp. 595)*

Also see below for computational complexity of decidable logic theories. - Model-theoretic methods such as Vaught's test and categoricity (Cantor used it to prove Theory of Dense Linearly Ordered set)

*(See [1], Chapter C.3 and here)* - Quantifier elimination (Presburger used it to prove Theory of

- Degrees and jump operator.
- Creative sets, productive sets, simple sets, immune sets
*(see [7] [16])* - Arithmetic hierarchy
*(see [7] [16])* - Hyperarithmetic hierarchy
*(see [7] [16])* - Analytical hierarchy
*(see [7] [16])* - Grzegorzyk hierarchy
*(see [11])* - Post's problem
and Friedberg's solution by Finite Injury Priority Method
*(see [4] [7] [16])* - Admissible ordinals and alpha-recursion
*(See [1] pp. 653)* - Other computation models: functionals
*(See [19])*, lambda calculus, Post machine, Markov algorithms, type-0 grammar, rewriting systems

- Limitation of formal systems to prove randomness (Chaitin's algorithmic information theory)
- Complexity of logic
theories
- Time complexity of WS1S (weakly monadic 2nd order theory of successor.) Monadic means predicates can only take one argument. 1 means there is only 1 predicate. Weak means the underlying set is finite.
- S1S is equivalent to regular expressions and is thus decidable (proved by Büchi in "Weak Second-Order Arithmetic and Finite Automata")
- SnS are also decidable (see Rabin's "Decidability of Second-Order Theories and Automata on Infinite Trees" and TW's "Generalized Finite Automata Theory with an Application to a Decision Problem"), but the time complexity is non-elementary (i.e. stack of exponentials.)
- Time complexity of Presburger arithmetic
- Time complexity of Real Arithmetic

- Characterization of PH by "alternation"
- Approximability
*(See [28] [32])*- Non-approximability, APX, PTAS, FPTAS
- Approximation preserving reductions
- PCP Theorem: NP=PCP[O(log
*n*),O(1)] - Applications of list decoding in complexity theory
- Non-approximability via PCP

- Unrelativizable results, e.g. algebraic methods (arithmetization) that proves IP=PSPACE
- Boolean circuit complexity
- Berman-Hartmanis conjecture
- Ackermann function is not primitive recursive
- Kolmogorov complexity

- Inaccessible cardinals
- Mahlo cardinals
- Weakly/Strongly Compact cardinals
- Ulam's measurable cardinals
- Lebesgue's measure problem: Does there exist a countably additive,
invariant under translation and nontrivial (i.e. points have measure 0, and
not all subsets have measure 0) measure defined on
*all*subsets of**R**?

Ulam proved that any set possessing such a measure is of inaccessible cardinal. If we add the large cardinal axiom to ZFC, then the new theory is consistent with such a measure.

Banach and Kuratowski proved Continuum Hypothesis implies**R**is not real-valued measurable. - Transfinite induction (e.g. used to prove Goodstein's Theorem)

- Zermelo-Fraenkel set theory
- von Neumann-Bernays-Gödel set theory
- Axiom of
Choice , its consequences (e.g. Banach-Tarski
paradox, also see here and here,
*[33],[38]*), and its equivalences (e.g. Zorn's lemma ) - The Reflection Principle (Löwenheim-Skolem theorem ?)
- Constructible universe
*L*, cumulative hierarchy*V*, and Axiom of Constructibility "*V=L*"*(See [30])* - Fine structure of the constructible universe by Jensen
- Determinacy axioms
- Inner model
- Quine's New Foundation
- Forcing (Cohen's method and Boolean-valued Models)
- Independence results: Continuum Hypothesis (via generic sets) , Axiom of Choice (via urelements), Souslin's Hypothesis, Parallel Postulate
- Martin's axiom
- Aczel's Anti-Foundation Axiom
*(See [31])*

- Saturated models and atomic models.
- Ultraproducts and ultrafilters
- Omitting types
- Model completeness
- Ehrenfeucht-Fraisse games
- Finite structures and 0-1 law
- Morley's categoricity theorem (simply put, if countable theory T is kappa-categorical, where kappa is uncountable, then T is lambda-categorical for every uncountable lambda)
- Vaught's conjecture and Knight's counter-example
- No complete theory has exactly 2 countable models (Vaught's theorem)
*(see [21])* - A complete theory with exactly n (n > 2) countable models
*(see [21])* - A complete theory with countably many nonisomorphic countable models
*(see [21])* - A complete theory with uncountably many nonisomorphic countable models
*(proof)* - Nonstandard models for
**N**,**Q**, and**R**, and Nonstandard Analysis - Stability, simplicity, forking

- Galois theory and Abel's proof on the impossibility of solving general quintics in radicals (Also see here)
- Lattices and ordering
- Classification of finite simple groups. Also see this on-line book
- Feit-Thompson's theorem: every simple group has even order, and every solvable group has odd order (254 pages of hard math)

- Rational points on elliptic curves
- Dirichlet's Theorem
- Elliptic curves and modular forms
- Birch & Swinnerton-Dyer Conjecture
- 15 and 290 theorems
- Prime number generating formula in 26 variables, Mill's constant (also see here for the value of Mill's constant)

- Hairy ball theorem
- Jordan curve theorem (an example of an obvious fact that is very hard to prove)
- Brouwer Fixed Point Theorem
- Markov's theorem: classification
of topological manifolds of dimension 4 or higher is impossible. The proof
is based on Novikov-Boone's result on word problem of free groups.
*(see [36])* - Dimensionality Theory:
- There does not exist a continuous bijection between [0,1] and
[0,1]
^{2} - If the restriction "bijection" can be relaxed, then Peano's
space-filling curve is continuous injection from [0,1] to [0,1]
^{2}(Hahn-Mazurkiewicz theorem) - No continuous injection from [0,1] to [0,1]
^{n}exist for n>2. - Hausdorff's definition of dimension, dimension theory

- There does not exist a continuous bijection between [0,1] and
[0,1]
- Menger sponge and Sierpinski carpet are super-objects, i.e. any compact one-dimensional object is topologically equivalent to a subset of a super-object.
- Smale's eversion of a sphere
- R
^{j}and R^{k}are not homeomorphic if j != k (due to Brouwer) - Kuratowski's fourteen sets

(A complete list here)

- Differentiable manifolds
- Hironaka's resolution of singularities for fields of characteristic 0
- Uniformization theorem for Riemannian surfaces
- Gauss-Bonnet theorem ("Theorema Egregium") and Poincare-Hopf index theorem
- Milnor showed there are 28 distinct differentiable
(smooth) structures on 7-dimensional spheres
("Exotic sphere")

But an*n*-sphere (for*n*=1,2,3,5,6) has only one differentiable structure.

The case for*n*=4 is called smooth Poincare conjecture. - Donaldson's exotic 4-dimensional
differentiable structure on R
^{4} - Poincare conjecture
- Milnor's 4-dimensional non-differentiable manifold

- Milnor showed there are 28 distinct differentiable
(smooth) structures on 7-dimensional spheres
("Exotic sphere")
- Bizarre phenomena in 4 dimensions
- Riemannian geometry
- General theory of relativity and Schwarzschild's solution
- Tarski's Squaring
the Circle problem
- Two ways to do it:
- Using set-theoretical arguments, like the Banach-Tarski paradox (by Miklos Laczkovich in "Equidecomposability and discrepancy; a solution of Tarski's circle-squaring problem" [1988])
- Doing it in non-Euclidean space. See here

- Quasicrystals (5-fold symmetry) & geometry
- Schmitt-Conway-Danzig's biprism which can fill space
*only*in aperiodic way

- Continuous but nowhere differentiable functions (e.g. Weierstrass
function or path of the Brownian motion)

Baire category theorem can show that such pathological functions are actually typical in the function space. - Vitali's
construction of a Lebesgue-nonmeasurable set and other paradoxical subsets
of
**R**(*see [33]*) - 5-dimensional unit ball has the largest volume
- Enflo's proof of invariant subspace problem in a separable Banach space.
- Carleson and Hunt's proof of a.e. convergence of Fourier series of
L
^{2}and L^{p}functions. - The Kakeya problem and its connections to harmonic analysis

- Riemann Mapping Theorem
- Riemann zeta function, Gamma function, and the Prime Number Theorem
- De Brange's proof of the Bieberbach
conjecture (
*see [35]*)

- Measure-theoretic probability
- High dimensional random walks (the probability of returning to origin is 1 in 1-D and 2-D random walks, but < 1 in higher-dimensions. This was proved by Pólya)
- Brownian motions, Wiener processes, Levy processes
- Martingales
- Kalman filter
- Diffusion equations
- Ito integration
- Stochastic calculus, stochastic differential equations
- Complexification and Karhunen-Loeve expansion
- Queueing theory with heavy-traffic, diffusion approximation

- Example of nonlinear PDEs with "regular behavior": Solitons ("solitary
waves")
- The shallow water wave equations: Korteweg-de Vries (KdV) equations
- The Fermi-Pasta-Ulam (FPU) anharmonic lattices
- Nonlinear Schrodinger (NLS) equation
- sine-Gordon equations
- Inverse scattering transform (IST) method

- How to detect integrability: Painleve analysis
- Navier-Stokes equations and turbulence
- Three body problem
- Chua's circuit
- Topological entropy

- Wagner's conjecture on graph minors and Robertson &
Seymour's
*long*proof - Tait's Hamiltonian graph conjecture, Tutte's counterexample, and its relation to the four-coloring problem.
- Kuratowski's theorem on planar graphs
- No-free-lunch Theorem
- Ramsey theory ("Complete disorder is an impossibility")
- Graceful tree conjecture
- Kepler's conjecture on sphere packing
- Aperiodic tiling; Penrose tiling
- 17 plane symmetry groups ("wallpaper groups")
- Heesch number and Heesch's problem

- Hamiltonian and Lagrangian mechanics
- Hopf bifurcation and Taylor-Couette experiment
- Noether's theorem on symmetry and conservation laws
- Reversible computation and the thermodynamics of computing
- Theoretical limits of computers (enthropy, energy)
- Einstein-Podolsky-Rosen (EPR) paradox
- Kochen and Conway's Free Will Theorem
- Three roads to Quantum Gravity: superstrings/supersymmetry, loop variables (LQG), and twistors

- Mean-field theory
- Ehrenfest's classification of phase transitions
- Widom & Kadanoff scaling hypothesis
- Order parameters
- Landau-Ginzburg theory
- Renormalization group
- Ising models and Onsager's solution
- Long-range order, correlation length
- Continuous symmetries
- Self-organized criticality
- Percolation
- Catastrophe theory, Morse theory

- The lambda point (the critical temperature: 2.17 K)
- Landau's two-fluid model of liquid helium-4 II
- Superfluidity of helium-3
- Bose-Einstein condensation

1. Handbook of Mathematical Logic (edited by Barwise)

2. Aspects of Incompleteness (by Lindström)

3. Computability and Logic (by Boolos and Jeffrey)

4. Gems of Theoretical Computer Science (by Schöning and Pruim)

5. The Incompleteness Phenomenon (by Goldstern and Judah)

6. Model Theory (

7. Theory of Recursive Functions and Effective Computability (by Hartley Rogers, Jr)

8. Set Theory (by Jech)

9. Set Theory - An Introduction to Independence Proofs (by Kunen)

10. Introduction to Lattices and Order (by Davey and Priestley)

11. Recursive Function Theory and Logic (by Yasuhara)

12. The Classical Decision Problem (by Börger, Grädel, and Gurevich)

13. A Course in Mathematical Logic (by Bell and Machover)

14. Set Theory and the Continuum Hypothesis (by Cohen)

15. Introduction to Set Theory (by Hrbacek and Jech)

16. Recursively Enumerable Sets and Degrees (by Soare)

17. Infinity and the Mind (by Rucker)

18. Cornerstones of Undecidability (by Rozenberg and Salomaa)

19. Mathematical Logic (by Shoenfield)

20. Diagonalization and Self-Reference (by Smullyan)

21. The Incompleteness Phenomenon: A New Course in Mathematical Logic (by Goldstern and Judah)

22. A Shorter Model Theory (by Wilfrid Hodges)

23. A Mathematical Introduction to Logic (by Enderton)

24. Mathematical Logic (by Ebbinghaus, Flum, and Thomas)

25. Computational Complexity (by Papadimitriou)

26. Proof Theory (by Takeuti)

27. Hilbert's Tenth Problem (by Matiyasevich)

28. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties (by Ausiello and et al.)

29. The Complexity Theory Companion (by Hemaspaandra & Ogihara)

30. Constructibility (by Devlin)

31. Vicious Circles (by Barwise & Moss)

32. Approximation Algorithms (by V.V. Vazirani)

33. The Banach-Tarski Paradox (by Wagon)

34. Complex Analysis (by Ahlfors)

35. Functions of One Complex Variable II (by J. B. Conway)

36. Classical Topology and Combinatorial Group Theory, 2nd edition (by J. Stillwell)

37. The Theory of Groups, 2nd edition (by J. Rotman)

38. The Pea and the Sun: A Mathematical Paradox (by Wapner)