Search Results

I think you're right. In Gödel's speed-up theorem, one may consider the statement $\sigma$, asserting that "there is no proof of $\sigma$ in PA of length less than a googolplex symbols." Now, if the …

John Steel spoke at the EFI series at Harvard concerning his ideas on The triple helix, which has to do in part with the interplay of large cardinal strength and the arithmetic interpretability hierar …

The question becomes interesting when it is interpreted as a technical question about the extent to which we can have a semi-formal language somehow in-between the truly formal proofs, which are large …

Gödel had conjectured that large cardinals might settle the continuum problem. He thought, for example, that perhaps the existence of a measurable cardinal would imply $\neg\text{CH}$. Such a perspect …

I believe that the answer to your question lies with the Lindenbaum algebra, which is a Boolean algebra (and topological space) that is naturally associated with any formal language, and which provide …

In the second case, you are saying that a certain tautology is provable. In the first case, you are saying that if phi is provable, then a certain other implication is provable. And one way you could …

Here is perhaps a more relatable example, which doesn't use self-reference. (I once heard a similar such example from W. Hugh Woodin.)$\newcommand\Con{\text{Con}}\newcommand\ZFC{\text{ZFC}}$ Let $\ps …

The claim you have asked us to prove is not true. If PA is consistent, then by the Incompleteness Theorem there are $\Pi_1$ statements that are independent of PA, such as Con(PA), which can be seen to …

Surprisingly, the answer is yes! Well, let me say that the answer is yes for what I find to be a reasonable way to understand what you've asked. Specifically, what I claim is that if PA is consistent …

Although the other answers correctly explain the basic logical equivalence of the two proof methods, I believe an important point has been missed: With good reason, we mathematicians prefer a direct …

Yes, this concept depends on how you represent the function. For example, the constant zero function is provably total, under that description, that is, using the formula $\varphi(x,y)$ equal to "$y …

I think that there are numerous trivial examples of this. Take any implication $p\to q$ that is provable, but has no short proof. It follows that the equivalence $$q\leftrightarrow (p\vee q)$$ is …

Let me point out that there are really a family of Church-Turing theses assertions. On the one hand, for what is sometimes described as the weak Church-Turing thesis, one imagines an idealized human …

Noah has given an excellent answer. Here is another way to look at such an answer. Theorem. For EVERY computably enumerable set $R$ and for every computably axiomatizable consistent theory $T$, the …

$\newcommand\Con{\text{Con}}\newcommand\ZFC{\text{ZFC}}$ So on the one hand, we have the usual assertion $\Con(\ZFC)$, which asserts that $\ZFC$ is consistent using a straightforward representation o …