1
$\begingroup$

I am interested in the existance of closed form formulas for bijections on natural numbers.

With the term closed form is lose. Any information on formulas that represent permutations on N are welcomed. The following are some additional questions:

  1. Can any permutation be represented with a formula for elementary function on real numbers? (or finitly many different such formulas for finitly many different cases)
  2. Can any permutation be expressed just using finitly many cases and formulas from peano arithmethics?
  3. What if we include all injective functions?

EDIT: As noted by @arturo-magidin, the set of formulas over a finite sign is countable, therefore 2. is false.

EDIT Formulas could be derived from an uncountable alphabet. (For example real numbers with $+$ and $\cdot$ signs. ).

$\endgroup$
12
  • 7
    $\begingroup$ The set of bijections from $\mathbb{N}$ to itself is uncountable. The set of formulas is countable. $\endgroup$
    – Arturo Magidin
    Commented Jun 11, 2023 at 18:29
  • $\begingroup$ @ArturoMagidin ok, I this answers 2. What about 1.? We can use real numbers in formulas. $\endgroup$
    – Urh
    Commented Jun 11, 2023 at 18:47
  • $\begingroup$ There are still only countably many. Formulas are finite, from a countable alphabet. $\endgroup$
    – Arturo Magidin
    Commented Jun 11, 2023 at 19:09
  • $\begingroup$ I allow uncountable alphabet. (for exapple, all real numbers + standard operations on numbers + varialbex). {x -> rx | r is real number} is a set of uncountably many formulas encoding different functions. (ofc only a countable subset are bijections on natural numbers). $\endgroup$
    – Urh
    Commented Jun 11, 2023 at 19:41
  • $\begingroup$ Unless your formula is allowed to contain infinitely many symbols, then allowing an uncountable alphabet doesn't make any difference. Can you say a bit more about the context of your question? $\endgroup$
    – Rob Arthan
    Commented Jun 11, 2023 at 22:24

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .