A list of interesting topics I will read when I have spare time.
Ich muss wissen. Ich will weiss.
Logic
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?
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)
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 xn+yn=zn
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)
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])
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)
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
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.
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)
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
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.
Schmitt-Conway-Danzig's biprism which can fill space only in
aperiodic way
Analysis
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.
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
References 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 (3rd edition, by Chang and Keisler) 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)