2
votes
1answer
160 views

Why should we accept the existence of subsets $A$ such that neither $A$ nor $A^c$ are recursively ennumerable? And how can we persuade others?

Encode every pair $(t,x)$ (where $t$ is a Turing machine and $x$ is an input string) as a distinct natural number. Then the halting subset $H$ fails to be recursive. $$H := \{(t,x) \in \mathbb{N} ...
3
votes
2answers
86 views

How does undecidability of 'theoremhood' imply that human ingenuity is necessary in mathematics?

In Robert Stoll's "Set Theory and Logic", there is the following passage on effectiveness of theorems (p. 375) : Mathematical logicians have shown that for many interesting axiomatic theories ...
0
votes
0answers
64 views

A Question Regarding Ordinal Turing Machines

Consider the following theorem of Koepke: 'A set x of ordinals is ordinal computable from a finite set of ordinal parameters if and only if it is an element of the constructible universe L". Taking ...
14
votes
3answers
313 views

Mathematical Notation and its importance

You can see how mathematical notation evolved during the last centuries here. I think everyone here knows that a bad notation can change an otherwise elementar problem into a difficult problem. Just ...
1
vote
1answer
249 views

Equivalence of sequences and subsets of natural numbers

For me, facts like the independence of the continuum hypotheses from ZFC cast a doubt on the "law of the excluded middle". (In this context, the doubt is that there might be no "final set theory" such ...
13
votes
6answers
2k views

What philosophical consequence of Goedel's incompleteness theorems?

I want to write a philosophical essay centered about Goedel's incompleteness theorem. However I cannot find any real philosophical consequences that I can write more than half a page about. I read the ...
8
votes
4answers
453 views

Consequences of solving the Halting problem

What impact would a device (ie super-computer or relativistic computer or other method) that solves the halting problem have on math? Would there be any mathematical problems left to solve? What ...
7
votes
4answers
360 views

Are the computable reals finitary?

In the comment thread of an answer, I said: The computable numbers are based on the intuitionistic continuum, and are not finitary. To which T.. replied: Computable numbers are not based on ...