/sci/ - Science & Math

[Anonymous No.7493785]

I have created a very weird function and I want people who know mathematical logic to check my thinking.

Gödel numbering allows us to number proofs. Define F_n to be the set of all functions from N->N which have a proof of Gödel number less than n which has the conclusion that the function exists. Note that F_n is a finite set, and that for each f in F_n, f(n) is defined. Thus there is a maximum f(n) in F_n. Define the function w in the following manner: w(n) = max (F_n(n)) + 1. Suppose w could be proved to exist. Then there would be some Gödel number, a, that expressed that proof. But then w would be in F_a and w(a) = max (F_a(a)) + 1 > w(a) + 1 and so 0 > 1, a contradiction. So w cannot be proven to exist. But w(n) can be shown to exist for all n, because F_n exists for all n, and max F_n(n) exists for all n.

Have I made a mistake somewhere, or is all this kosher? Is the existence of w independent of arithmetic?

[Anonymous No.7493792]

>>7493785
I smell checkmate, atheists.

[Anonymous No.7493793]

Subtle homework thread is subtle

[Anonymous No.7493801]

>>7493793
man I'm just trying to create a function that grows faster than busy beaver and then I got stuck down this rabbit hole

[Anonymous No.7493818]

>Note that F_n is a finite set, and that for each f in F_n, f(n) is defined.
What does defined mean? With choice, you may not even be able to write down the function.

Does exist/defined mean that there is an effective procedure here?

>Thus there is a maximum f(n) in F_n.
>in F_n.

[Anonymous No.7493838]

>>7493818
ad.:
Yeah my problem is, I think, that I don't know how you capture your functions which are eventually allowed to be in F_n. Or, in turn, why w (that uses the set F_n in its definition) should be in that class.

[Anonymous No.7493842]

>>7493818
The godel number (n) is finite, thus the expressions in the proof are finite (namely the expression of the function). f(n) is defined because f is a function from N->N, f exists, thus f(n) exists.

There is an f in F_n such that f(n) is maximized.

[Anonymous No.7493850]

>>7493838
They are the functions which can be proved to exists by proofs with Godel number less than n. Or that's the idea at least. We are assuming for the sake of contradiction that w has such a proof, (a), and then noting that w is thus in F_a.

[Anonymous No.7493935]

bampu

[Anonymous No.7494012]

>>7493850
Maybe you misunderstood me.
What is the language that you're encoding, that you can speak of existence proofs of functions. If you're in arithmetic, why should the function w which is specifies with a sentence involving the sets of functions be expressible in the object language?

[Anonymous No.7494030]

>>7494012
Oh that makes more sense. I don't really know. This is where my knowledge falls short. I've been assuming first-order logic and arithmetic.

How can w be expressed in first-order logic and arithmetic? I'm gonna go give that a think.

[Anonymous No.7494118]

>>7494012
I think it's likely that w cannot be expressed in first-order logic and arithmetic, which neatly resolves my questions about it's paradoxical nature. It also grows faster than any function that can be described by first-order logic and arithmetic, which is pretty neat. I think that's better than busy beaver.

[Anonymous No.7496112]

Let's see if I can't be more precise. Let's see what we can do in the realm of arithmetic and whatever order logic is necessary to make existential statements about functions. Call it x. First let's define a predicate, FUN.
FUN takes a godel number and a function symbol f. It returns true if and only if there is some theta such that theta(f) evaluates to true and the godel number describes a proof from axioms that ends with a statement that theta uniquely defines a function in N*N. In first order logic I believe such a statement looks like:
\forall f,g \in N \cross N \theta(f) \wedge \theta(g) \Rightarrow (f=g) \wedge (\forall x, y \exists a,b \in N f(x) = y \Leftrightarrow x = a \wedge b = y) \wedge (\forall a \in N \exists b \in N f(a) = b) \wedge (\forall a, b, c \in N f(a) = b \wedge f(a) = c \Rightarrow b = c)
I believe FUN can be expressed as a x'th order statement with a free variable a and f, for the godel number and the function, respectively.
Then I believe we can define a x'th-order statement that uniquely defines w:
\forall n, m, a \in N \forall g \in N \cross N \exists m' \in N (w(n) = m' \Leftrightarrow a < n \Rightarrow THETA(a, g) \Rightarrow (g(n) < m' \wedge g(n) < m \Rightarrow m' \le m)

[Anonymous No.7496126]

>>7496112
Dude please, JSMath tags, and parenthesize your shit, I mean priority between \wedge and \Rightarrow is meh.

[Anonymous No.7496171]

>>7496112
you shouldn't handwave these matters, it doesn't work well with such things. For example, you take <span class="math"> f,g \in \mathbb{N}^2 [/spoiler], thus tuples of natural numbers, and then evaluate them, which is absurd.

If you meant to quantify over functions then you left the realm of 1. order logic. To apply anything like Gödel you need to be really careful w.r.t. the exact logics you are using and the distinction between object and metalanguage.