# Tagged Questions

39 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 ...
117 views

### How can the Gödel sentence be Pi_1

The Gödel sentence must be provable or unprovable by itself - you have to resolve all definitions until it only uses the elementary symbols of Peano arithmetic. What is the correct way to resolve ...
88 views

### $\textbf{Q}$ fails to prove some correct $\forall$-rudimentary sentence

Show that the existence of a semirecursive set that is not recursive implies that any consistent, axiomatizable extension of Q fails to prove some correct $\forall$-rudimentary sentence. I ...
44 views

### A Question About Tennebaum's Theorem?

Tennenbaum's theorem proves there are no countable recursive nonstandard models of Peano arithmetic. It is a proof by contradiction. If our countable, nonstandard model is recursive, then, given a ...
59 views

### Ackermann function is not primitive recursive

The function of the Ackermann function is defined as $$A_{0}(y)= y+1$$ $$A_{x+1}(0)= A_{x}(1)$$ $$A_{x+1}(y +1)= A_{x}(A_{x+1}(y))$$ I want to show that the function of ackermann is primitive ...
62 views

### A is recursive iff A is the range of an increasing function which is recursive

Working a problem stated in Enderton, but stated better and apparently stronger in Soare. All citations hereon are for Soare (1987). Would appreciate help on the proof. I know there has to be a more ...
33 views

### Kolmogorov (Kolmogoroff- ) Complexity of infinite sequences, Request for Proof

Let $\xi \in X^{\omega}$ be an infinite sequence and denote by $\xi[1\ldots n]$ its length $n$ initial segment. Then (due to Martin-Löf) the following holds: For every $\xi \in X^{\omega}$ there ...
29 views

### Direct proof that $K \leq_\mathrm{T} Rec$

Soare's Recursively Enumerable Sets and Degrees (1987) shows that $Rec = \left\{ e : W_e \text{ is recursive} \right\}$ is $\Sigma^0_3$-complete via its relationship to other index sets, namely $Cof$ ...
32 views

### Kolmogorov (Kolmogoroff-) Complexity, Contradiction with Invariance Theorem.

Fix some programming languages $S$ which is rich enough such that one can write interpreters for $S$ in $S$. Define $$K(w) := \mbox{length of a shortest program producing w}.$$ Now fix some ...
82 views

### Proof-theoretic characterization of the primitive recursive functions?

The total recursive functions are exactly those number-theoretic functions that can be represented by a $\Sigma_1$ formula of first-order arithmetic. Is there a similar characterization of the ...
63 views

### How does one generally use partial function in logical statements?

How does one generally use partial function in logical statements? How it's done in practice? Specifically, let $M$ by a Turing machine, $f_M:\{0,1\}^*\to\{0,1\}$ the characteristic function which ...
62 views

### Problem from Cutland's Computability: 3.2. problem 3

The problem goes as follows. Let f: N --> N, such that f is partial, N is the natural numbers, and let m $\in$ N. Construct a non-computable function g such that g(x) = f(x) for x$\le$m. Proof: By ...
57 views

### Complexity of Recursively Inseparable Sets

I am interested in examples of recursively inseparable sets. A standard example is the set of positive integers encoding a Turing machine that halts in an odd number of steps on blank input versus ...
47 views

### Non-computable c.e. sets are Kurtz random

I'm trying to directly show that non-computable c.e. sets are Kurtz random, without using the concept of genericity, but to little success. I assume by way of contradiction that $\emptyset'$ (for ...
244 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 ...
103 views

### Elementary references on Robinson Arithmetic, Prim. Recursive fns etc.

I'm in the middle of revising my freely available and much-downloaded introductory notes Gödel Without (Too Many) Tears. (They are a sort of cut down version of part of my Gödel book, and I'm ...
34 views

### Are these sets recursive, r.e. or none

Are the sets a) $\{x | \exists y \phi_x(y) = 0\}$ b) $\{x | \phi_x(5) \uparrow \land x \leq 5\}$ recursive, recursively enumerable (r.e.) or none of them? Please explain your solution. $\phi_x$ ...
64 views

### Can we find a formula defining a recursively enumerable set?

By Post's Theorem we know that a set $A\subseteq\mathbf{N}$ is recursively enumerable iff it is definable by a $\Sigma_1$-formula, i.e. there exists a $\Sigma_1$-formula $\varphi(x)$ with $x$ free ...
58 views

### Computably enumerable sets are not algorithmically random

I am informed that no computably enumerable sets are algorithmically random. I tried to show it by constructing an ML test, and looked up the proof in Downey & Hirschfeldt, but in vain. I would ...
43 views

### Steps for applying Rice's theorem to any sets

I know that this set: $$\{i\ |\ \ \phi_i(n) \text{ converges } \}$$ is not recursive and that this can be shown by Rice's theorem. But everywhere I look i just found that it's not recursive ...
81 views

### Proving sets to be (not) recursive or r.e.

I am stuck proving the following sets to be recursive or recursive enumerable (or none of the both). first set: $$\{i\ |\ \exists n, \phi_i(n) \text{ converges and } \phi_i(n+1) \text{ converges}\}$$ ...
106 views

### Is it possible to create a string with known Kolmogorov Complexity?

I wish to compare compressors using strings with known Kolmogorov Complexity, but I haven't got the theoretical background and tools to understand how to do that. I'm just starting in this area and ...
50 views

### The universal turing relation

I'm just starting to learn computability. Some treatments of the subject use a relation they call $T$, which I think is called the universal recursive relation. It's defined something like this ...
187 views

### Are there more true statements than false ones?

Let us enumerate all statements of PA or ZFC by length, upto n characters, then in the limit as $n\rightarrow\infty$, what proportion of statements are provably true, provably false, or independent? ...
135 views

### About theorem's proof length in propositional calculus

In PC(propositional calculus) system, how long will a formula's proof be? That is to say if there exists a computable function $f$ such that for any formula $A$, if $\vdash_{\mathrm{PC}}A$ then $A$ ...