113
votes
The enigmatic complexity of number theory
I'm not a number theorist, but FWIW: I would talk, not so much about Gödel's Theorem itself, but about the wider phenomenon that Gödel's Theorem was pointing to, although the terminology ...
44
votes
The enigmatic complexity of number theory
What references, especially books, have been devoted to specifically addressing the source of the deep roots of the diversity and complexity of number theory?
To a first approximation, I would say ...
40
votes
Top-down mathematics, or "Where it all begins"
One approach, mentioned by Pace Nielsen in the comments, is to start with what I call strict formalism. The only substantive assumption required for strict formalism is that you are capable of ...
- 82.6k
29
votes
Accepted
What is known about the relationship between Fermat's last theorem and Peano Arithmetic?
The main reference for this topic is Angus Macintyre's appendix to Chapter 1 ("The Impact of Gödel's Incompleteness Theorems on Mathematics") of Kurt Gödel and the Foundations of Mathematics: ...
- 82.6k
23
votes
Accepted
What sorts of extra axioms might we add to ZFC to compute higher Busy Beaver numbers?
There's a certain confusion underlying your question, which Andreas Blass's answer is trying to point out. Let me see if I can explain it in different words.
You say, “the negation of Con(ZFC) proves ...
- 82.6k
20
votes
Can you have a type theory where there is type of all types?
Of course you can have $\mathsf{Type} : \mathsf{Type}$, the consequence of that is that all types are inhabited (by Girard's paradox). Some people call this an inconsistency, but that only makes sense ...
- 48.8k
20
votes
Top-down mathematics, or "Where it all begins"
Here is a possible viewpoint to contemplate:
Foundations of mathematics do not begin anywhere.
This happens to be my (current) personal belief. I agree with Monroe that the answer to the question ...
- 48.8k
19
votes
Accepted
Which kind of foundation are mathematicians using when proving metatheorems?
Your question is much more specific than your title suggests. As to the question itself, my answer is that it doesn't matter. The proof is given in mathematics, not in any formal system. A ...
- 66.8k
19
votes
What sorts of extra axioms might we add to ZFC to compute higher Busy Beaver numbers?
$\DeclareMathOperator\BB{BB}$Philosophical issues, like acceptance (or non-acceptance) of large cardinals, won't affect $\BB(n)$, because the busy beaver function is defined arithmetically and so ...
- 73.1k
19
votes
Accepted
Is every recursively axiomatizable and consistent theory interpretable in the true arithmetic (TA)?
The answer is yes. I believe the following is best attributed to Feferman 1960; more generally, look up "arithmetized completeness theorem" (which is annoyingly different from the arithmetic ...
- 21.1k
13
votes
Accepted
On structures that are not submitted to compatibility conditions
Here's the most clear-cut example I can think of:
A Galois representation consists of a field extension $K \subseteq L$, the group $G = Gal(L/K)$, and a representation $G \to GL(V)$ on a vector space ...
- 63.9k
13
votes
Accepted
Is there a semantics for intuitionistic logic that is meta-theoretically "self-hosting"?
I would argue that intuitionistic logic is perfectly self-hosting: working in an intuitionistic set theory, one can define a sound semantics of intuitionistic logic relative to models built out of ...
- 66.8k
13
votes
So after all, what is this thing about topos theory and non-binary truth?
Suppose you always want to talk about two things simultaneously for some reason. When you say "a set $A$" you actually mean a pair of sets $(A_1, A_2)$, when you say "a function $f : A \...
- 1,110
12
votes
Which kind of foundation are mathematicians using when proving metatheorems?
One direction could go like this. Let ${\rm ZFC}^+$ be the theory in the language of set theory augmented by a constant symbol ${\bf M}$ with the axioms
$\bullet$ every axiom of ${\rm ZFC}$
$\bullet$...
- 42.8k
12
votes
Accepted
Is there any set theory $T$ such that $T$ plus true arithmetic is complete with respect to statements in set theory?
There can be no such theory $T$, even if you weaken the requirement
to $T$ being merely arithmetically definable, rather than insisting it must be effective.
To see this, consider the theory T+TA, ...
- 236k
12
votes
Can you remove all the extra arithmetic from ZFC (or other theories)?
If $S$ proves no "extraneous" statements, then $S$ cannot prove $X \rightarrow Con(PA)$ for any arithmetic statement $X$ which $PA$ proves. It follows that $S + PA$ cannot prove $Con(PA)$, and ...
- 5,827
11
votes
What drawbacks are there to using NF(U) for category theory?
One serious sticking point is that the category of sets in NF is not cartesian closed.
- 66.8k
10
votes
Accepted
Is every true statement independent of $PA$ equivalent to some consistency statement?
The theory $PA + Con(PA)$ has the property you are asking for, this is the so called Friedman-Goldfarb-Harrington principle (see, e.g., Fifty years of self-reference in arithmetic, p. 366). Formally, ...
- 741
10
votes
Accepted
Is there an equivalent of the incompleteness theorems/halting problem in category theory?
There is a category theoretic version of the incompleteness theorem originally due to André Joyal that has been unavailable for a long time, but has been written up not so long ago by Joost van Dijk ...
- 42.4k
9
votes
Accepted
Can you formulate a theory stating that a truth predicate does not exist for first order set theory?
The assertion that there is (or is not) a truth predicate is expressible in the second-order language of set theory, but assuming consistency, not by any first-order assertion.
Second-order. In the ...
- 236k
9
votes
Accepted
What two ordinals are these (based on definable ordinals)?
In this answer, let me assume as you indicated in the comments that you are working in a second-order set theory with a truth-predicate for first-order truth. Such a theory goes strictly beyond ZFC in ...
- 236k
9
votes
What two ordinals are these (based on definable ordinals)?
There are several subtle issues with your post.
It is not in general possible to express the notion of "definable", because it leads to contradictions. For example, the class $D$ is not definable in ...
- 236k
9
votes
The enigmatic complexity of number theory
You might enjoy A New Kind Of Science. It is a lavishly illustrated book with copious (Edit: endnotes, not references; thanks to Scott Aaronson's review for helping me see the distinction) centered ...
9
votes
What sorts of extra axioms might we add to ZFC to compute higher Busy Beaver numbers?
Knowing the values of the Busy Beaver function is the same as knowing the truth values of $\Pi^0_1$-statements (ie statements of the form $\forall n \in \mathbb{N} \ P(n)$ for decidable properties $P$)...
- 4,667
9
votes
Is there a semantics for intuitionistic logic that is meta-theoretically "self-hosting"?
See Palmgren, Constructive Sheaf Semantics for a completeness proof for sheaf semantics within a constructive (and predicative) metatheory. The introduction also mentions several references to earlier ...
- 4,378
9
votes
Equivalences of $n$-categories
That is indeed a problem, and one could argue that this is part of the reason why these questions are difficult. But I feel that in practice that has never been a strong obstruction. I guess, one way ...
- 42.4k
8
votes
Accepted
Can adding Hilbert's epsilon to a theory, and then expanding that theories axiom schema to include the new language, cause it to become inconsistent?
Even if you're looking at extensions of ZFC, the answer is still yes. Consider the theory of ZFC plus the scheme asserting that there is no definable global choice function. That is, the formulas &...
- 236k
8
votes
Can infinity shorten proofs a lot?
A good example is a solution to Hilbert's third problem: it is not possible to cut the unit cube into finitely many polyhedral pieces and reassemble then as the regular tetrahedron of unit volume. The ...
- 28k
8
votes
On structures that are not submitted to compatibility conditions
When one studies a set with structures that do not interact with each other, then really all that matters about the set is its cardinality. And so the situation of your question can be viewed as ...
- 236k
8
votes
Is every true statement independent of $PA$ equivalent to some consistency statement?
$1$-consistency of $PA$ is a true $\Pi_3$ sentence which is not provable in $PA$+{all true $\Pi_1$ sentences} (see this article). Simple (iterated) consistency statements (as you mentioned above) are ...
- 870
Only top scored, non community-wiki answers of a minimum length are eligible