4
$\begingroup$

Recently, I attempted to generalize the fixed-point lemma and proved the following:

Let $ F_n $ be the set of all formulas with $ n $ free variables in $L_{PA}$.

Let us define the unary function $ f $ by $ f(\sigma) = \ulcorner \sigma \urcorner $, where $\sigma$ will be any element of $F_n$​, i.e., where $\sigma$ will be any formula in $L_{PA}$ with $n$ free variables and $\ulcorner \sigma \urcorner$ will be the Gödel number of the formula. Therefore, $ f $ is not a function within $ L_{PA} $.

Let $ \mu $ be the smallest set of unary functions，each of which domain is $F_n$ , that satisfies:
$(1). f \in \mu $
$(2).$For any $f_1, f_2, \ldots ,f_n \in \mu$, let unary function $g$ defined by $ g(\sigma) = \ulcorner \sigma(f_1(\sigma), f_2(\sigma), \ldots, f_n(\sigma)) \urcorner $, where $\sigma$ will be any element of $F_n$​, then we have $g \in \mu $.

Then: for any $ \psi \in F_m $ and any $ n + m $ functions $ f_1, f_2, \ldots, f_{n+m} \in \mu $, there exists $ \varphi \in F_n $ such that:

$$ PA\vdash \varphi(f_1(\varphi), \ldots, f_n(\varphi)) \leftrightarrow \psi(f_{n+1}(\varphi), \ldots, f_{n+m}(\varphi)) $$

The proof itself is straightforward, but I am unsure under which existing research this result is covered, that is, what is the limit to which the fixed point lemma can be generalized? Recently, I have been reading C. Smorynski's article "Fixed Point Algebras." Am I heading in the right direction with my research?

Improve this question
$\endgroup$
10
  • $\begingroup$ Why do you write $\mu(x)$ for a family of functions? What is $\mu$ without $x$? I have trouble parsing the question beacause of all those $x$'s. $\endgroup$
    – Andrej Bauer
    Commented Aug 8 at 22:50
  • 2
    $\begingroup$ You say that $\mu$ is a set of functions, but then make an assertion about a certain Gödel code being an element of $\mu$. I'm not sure what you are trying to say without further explanation. $\endgroup$
    – Joel David Hamkins
    Commented Aug 9 at 0:28
  • 5
    $\begingroup$ Sorry, I still don't get it. What do the brackets mean for you? Are these Gödel numbers? If $\mu$ is a set of functions, then those numbers are constant functions? Or what? And what do you mean by $f(x)=\ulcorner x\urcorner$, where neither $f$ nor $x$ has been quantified? Is $f(x)$ a function, or the value of the function at $x$ or a term? But $\ulcorner x\urcorner$ is the Gödel number of the variable symbol $x$? Or what? I am unsure of almost every single formal statement in your question. $\endgroup$
    – Joel David Hamkins
    Commented Aug 9 at 11:19
  • 1
    $\begingroup$ It still doesn't make any sense. It might make sense if you deleted those $\forall \sigma \in F_n$ quantifiers, and you wrote your functions in functional notation. So the first clause would read $(\sigma \mapsto \lceil \sigma \rceil) \in \mu$. $\endgroup$
    – Andrej Bauer
    Commented Aug 9 at 13:34
  • 3
    $\begingroup$ @Stanleysun I recommend that you use far more words in your question. Write complete English sentences to explain your ideas, with embedded formalism within those sentences, when necessary, for precise reference. For example: "Let us define the function $f$ by $f(x)=\ulcorner x\urcorner$, where $x$ will be any syntactic item in the language." (If that is indeed what you mean.) And that definition shouldn't be part of the defining property of $\mu$ but rather prior to it. $\endgroup$
    – Joel David Hamkins
    Commented Aug 9 at 15:24

1 Answer 1

Reset to default
7
$\begingroup$

Raymond Smullyan has several works, including several books, that explore diverse generalizations of the kind of fixed-points that your question is about.

Run the following search on MathSciNet: ti:(self-reference) au:(smullyan)

You will find the works I am talking about (8 in all). Perhaps the main one is:

  • Smullyan, Raymond M., Diagonalization and self-reference, Oxford Logic Guides. 27. Oxford: Clarendon Press. xv, 396 p. (1994). ZBL0810.03001.

I am not sure if your exact fixed-point result is in there, but he has many very general fixed points of a similar nature.

Let me also mention a short elementary note that I wrote for use in some graduate seminars, A review of the Gödel fixed-point lemma with generalizations and applications, where I discuss the double fixed point and larger fixed-point systems, along with several applications, including the universal algorithm and other such results. Some of the fixed-point results are simpler than yours and you may know of them already, but the applications are interesting and other readers may find the presentation useful.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thank you very much, I will read this book. $\endgroup$
    – Stanley sun
    Commented Aug 9 at 21:19
  • 2
    $\begingroup$ Not too long ago, Smorynski published an interesting article on the history of (the various kinds of) diagonalization, and it is the kind of article that both a novice and an expert can benefit from; alas it is not free access: The early history of formal diagonalization by C Smoryński, Logic Journal of the IGPL, Volume 31, Issue 6, December 2023, Pages 1203–1224, doi.org/10.1093/jigpal/jzac054 $\endgroup$
    – Ali Enayat
    Commented Aug 11 at 20:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .