Revisions - MathOverflow

Return to Answer

corrected typo

view source

edited Mar 24 2010 at 15:03

Niel de Beaudrap
1,018●4●10

Set $\nu$ to be the product a multiple of the first n primes, for a graph on n vertices.

Set $V(n,\nu) \equiv \big( n \in \nu \in n \mathbb N \;\;\&\;\; n ~\text{prime}\big)$.

The sole explicit instance of "Gödel numbering" in this scheme is in the construction of μ. However, it suffices to admit very simple choices of V and E to represent an arbitrary graph. The number μ isn't even terribly esoteric: the only retriction on μ is that the exponents of its prime factorization are always square-free, and have exactly two prime factors when they are non-zero. This construction generalizes to multigraphs hypergraphs and graphs with loops trivially.

view source

answered Mar 24 2010 at 13:27

Niel de Beaudrap
1,018●4●10

This question sounds more like a research project than a definite problem. Part of the reason for me to say this is because this question is only interesting if you impose some (ill-defined) qualifications on what an interesting answer can be; and even then, it is not clear how one can answer the question without having the insights into the structure of the integers which you are hoping to find. Having said that, I'll hazard some elementary observations.

Throughout the following, I will refer to the integer which corresponds to a vertex in a graph as its index.

The problem of Gödel numbering

Your question is still about computable predicates. As long as you do so, without imposing further restrictions, there will still be too much room open for Gödel numbering to give solutions to sub-problems.

The predicate V₀ that I described before, while 'elaborate' (in that it would not be so simple in closed form), relied quite heavily on using prime factorization as a means of describing compound data structures --- specifically, in order to construct the indices of vertices to represent a sort of label for the vertex, its adjacency relations to other vertices, and even complete information about the entire graph.

In order to obtain "interesting" representations of graphs just by families of indices and relations on them, we obviously want to reduce reliance on Gödel numbering. We can do this by disallowing Gödel numbering in the indices,* i.e. in the first argument n to the predicate V and the first two arguments to the predicate E. But even if we do this, a very modest amount of Gödel numbering in the third argument μ to E gives away the whole game, as I show below.

^{* Of course, this pre-supposes that determining what constitutes Gödel numbering is a computable problem; I would argue that it isn't even well-defined. We can concievably describe a restriction to how much one can exploit the prime factorization of indices, but this would not address information being carried by the integer in e.g. representation of the index in base 1000, or any arbitrarily esoteric-but-computable representation of the index. Furthermore, even while prohibiting Gödel numbering, we still presumably want/need the index to bear some information; just not potentially arbitrarily complex information. But let's ignore that technical problem and suppose it can be done for the sake of argument.}

A "significantly less complex" universal set of predicates

It suffices to do the following:

Set $\nu$ to be the product of the first n primes, for a graph on n vertices.
Set $V(n,\nu) \equiv \big( n \in \nu \mathbb N \;\;\&\;\; n ~\text{prime}\big)$.
Set $\mu = 2^{e_1} 3^{e_2} \cdots p_m^{e_m}$, for a graph on m edges, where each integer e_j is a product of two primes which are the indices of adjacent vertices.
Set $E(n,m,\mu) \equiv (\exists p~\text{prime}):\big(\mu \in p^{nm}\mathbb N \;\;\&\;\; \mu \notin p^{nm + 1} \mathbb N\big)$.

The key to this construction, of course, is that the prime numbers serve as "easily distinguishable" indices for the vertices, to the extent that any number which is a multiple of two or more primes may be easily interpreted as a set; and then we store multiple sets by storing them in the exponents of a prime factorization of some integer.

I may have fallen afoul of some restriction you have in mind; for instance, it is likely that the set of μ of the form above (either in the explicit construction or the generalization for prime power indices) have small "measure", for many reasonable definitions of measures. From you examples e.g. of cycle graphs, however, I assume the fact that not all μ fall under this construction is not a problem.

Approaches to trees which avoid Gödel numbering

'Universal' predicates which rely on Gödel numbering are obviously boring, in that they indicate only what is possible. After one understands Gödel numbering as a means of representing data structures, they are not in themselves interesting. The challenge is then to see what one can do without using Gödel numbering (which I take in a practical sense to refer to using integers only to denote sequences or collections of other integers).

This is tricky for a graph class such as "arbitrary trees" (or even "arbitrary binary trees"), because there is little structure to deal with; it seems to me that natural representations of them will amount to something like lattices of subsets with added restrictions.

The trick is that for each index, you would like to identify a unique vertex (depending possibly on μ) which can be its "parent" (in the picture of rooted trees); or more generally, however one defines the set of allowed indices, at most one element of the set can be its parent, with exactly one vertex failing to have a parent.

This is where your question becomes ill-defined. Your motivation seems to be to somehow plumb the structure of the integers using graphs; but to do this, we must somehow already have a structure to hand to represent trees. This is not a research problem, so much as it is a very open-ended research programme.

Two potential approaches --- simple ones, and so likely not to be realizable --- occur to me.

Once more, we can consider prime factorizations. To avoid the temptation of Gödel numbering, we should not be too picky with the indices; the index-set should admit integers with non-trivial common divisors. A natural choice of edge-predicate is then $$ E(n,m,\mu) \equiv \big(\exists A,B\big):\Big(\{A,B\} = \{n,m\} \;\;\&\;\; A/B ~\text{is the largest prime factor of $A$}\Big) ,$$ that is, where transition from each vertex v to its parent corresponds to division by the largest prime factor of the index of v. A natural choice of predicate V is then to choose indices which are factors of some particular integer.
It is not clear to me how general a class of trees we can get from this; we can easily obtain paths and stars, and some variety of other trees. It is also not clear to me how to get a reasonably varied class of binary trees.
We can consider ways of partitioning integers into a sum of smaller integers. Because addition in itself has so "little" structure, any structure would have to come from the allowed set of summands, which has to be given by the integer μ; this comes dangerously close to Gödel numbering. A simple solution is to use this integer to parameterize a family of summands, e.g. powers of μ. This too can lead to Gödel numbering of a different sort; a possible approach is to use ternary expansions of integers to represent the location of a node in a tree by left-right branching from the root, with log₃(n) representing the distance from the root, and the j^th digit representing whether one takes the left or right branch at the j^th level to reach the vertex in question. So there is a real question of what there is that one can do, under the constraint of doing something interesting.
A compromise is to succumb to prime factorization, but to more or less ignore the exponents to avoid the temptation to do Gödel numbering. So, the possible transitions may be taken to be the (maximal) prime-power factors of μ. This still uses μ to denote a set of integers, but not a set with arbitrary elements. To identify a parent of an index, one may take the number which may be reached by subtracting the largest allowable transition. One may easily obtain paths (e.g. restrict to odd indices and take μ = 2) and arbitrary star graphs (e.g. restrict indices to 1 and p+1 for p prime, and take μ to be a suitable square-free integer). It's not obvious how to get arbitrary trees.
One can think of generalizing this to allow transitions which are e.g. arbitrary prime-power factors, not just maximal prime-power factors. This can be used to get a wide variety of trees. For instance, we may consider restricting the indices to integers n which are a sum of at most k powers of two, and let the parent of each index be the one which is obtained by subtracting the largest power 2^r < n. This is pretty simple; but also dangerously close to the ternary scheme described above. It is not clear exactly how to delineate the boundary between 'interesting' and 'using Gödel numbering'. (Then again, perhaps this last decomposition isn't interesting anyway --- or perhaps it is merely the concept of 'the structure of an arbitrary tree' which is not especially interesting.)

In closing

Unless your objective is actually to embark on an open-ended research project, you might want to restrict your question a bit more. In particular, you should give some thought to imposing conditions which would prevent "trivial" solutions, especially using numerical tricks to embed the structures you are interested in into the indices and/or parameters.

Unless you somehow refine your question, it is just extremely open-ended. Not to say that it isn't a nice sort of project.