3
$\begingroup$

I recently looked at Permutations on the random permutation which seems to talk about the notion of random permutuation as a notion from logic rather than probability.

The random permutation is the Fraïssé limit of the class of finite structures with two linear orders.

The intro also mentions that finite permutations are "two linear orders on a finite set".

I am not a logician, so I don't know what Fraïssé limit could be, but I got something about age in model theory.

There a sense in which a random permutation is a "universal" construction?

Is there a sense in which a "random" object can be a logical construction?

  • Ed Nelson's Radically Elementary Probability Theory is a fascinating non-standard construction of law of large numbers and stochastic proceses, but I could not find an explanation of the random permutation.
$\endgroup$
4
  • 2
    $\begingroup$ Perhaps the terminology is inspired by the example of the Rado graph (en.wikipedia.org/wiki/Rado_graph), which on the one hand is also a Fraïssé limit and on the other hand occurs with probability $1$ when you construct a random graph on countably many vertices, choosing edges independently with probability $\frac{1}{2}$. You can find some discussion of your first question here: golem.ph.utexas.edu/category/2009/11/fraisse_limits.html $\endgroup$ – Qiaochu Yuan Jun 5 '14 at 22:42
  • $\begingroup$ I am having troubling finding your question. Is it this one? "Is there a sense in which a "random" object can be a logical construction?" Or are you just looking for more information about Fraïssé limits? $\endgroup$ – Jason Rute Jun 5 '14 at 23:18
  • $\begingroup$ "What is a Fraïssé limit" would be a good candidate article for the "What is a …" series in the AMS Notices (ams.org/notices). It would have broad appeal to a number of different areas of mathematics. $\endgroup$ – Jason Rute Jun 5 '14 at 23:30
  • 1
    $\begingroup$ @JasonRute et al: chernikov.files.wordpress.com/2008/12/… $\endgroup$ – Noah Schweber Jun 6 '14 at 0:20
8
$\begingroup$

Actually, I think both "random" and "permutation" here are a bit misleading.

"Random" just means "the Fraisse limit of something." This is a very specific notion of randomness, and it may not agree with intuitions coming from probability. The Fraisse limit is a purely model-theoretic construction - given a class of finite structures with nice properties, there is a unique-up-to-isomorphism countable homogeneous structure with precisely (up to isomorphism) those finite structures as its finite substructures - and so there's nothing probabilistic here; the term "random" just comes from the intuition that in Fraisse limits "anything that can happen, will" (which can be made precise by talking about genericity; see my question "Fraïssé limits" without amalgamation). Now in practice, I suspect that there is quite a bit of overlap between the model-theoretic and probabilistic notions of randomness; but I'm also quite sure that they can diverge wildly in more complicated settings.

"Permutation" here is an even weirder term. The random permutation is defined as the Fraisse limit of the "class of finite permutations," where we think of a finite permutation as a pair of linear orderings on the same finite set (the idea being that they define a permutation: send the first$_0$ element to the first$_1$ element, the second$_0$ element to the second$_1$ element, etc.). The Fraisse limit of this class, however, is not a permutation in any obvious sense! Instead, it's a pair of linear orders on a countable set, each of which yields a copy of $(\mathbb{Q}, <)$, which interact 'randomly.'

The tension here is made clear in the second half of paragraph 1.1:

Both linear orders of the random permutation are isomorphic to the order of the rational numbers, and the random permutation is the result that appears with probability one in the natural random process that constructs both orders independently. From this it becomes clear that the random permutation cannot correspond to a single bijection on its domain $D$: indeed, it represents a double coset $Aut(D; <_2) \circ \pi \circ Aut(D; <_1)$ in the full symmetric group $Sym(D)$ on D, where π is any isomorphism from $(D;<_1)$ to $(D;<_2)$, and $Aut(D; <_i)$ denotes the automorphism group of $(D; <i)$, for $i = 1, 2$.

That is:

  • the random permutation is necessarily not a permutation in any sense,

  • the random permutation does have a probabilistic interpretation, and

  • to the extent to which the random permutation has a probabilistic interpretation, it has much more to do with linear orders than permutations.

In particular, there's an intuitive meaning of a 'random permutation' on an infinite set, and this isn't it.

Note that the crux of all this is how we choose to represent finite permutations.


Regarding your other question, on whether Fraisse limits can be thought of categorially: see this post at the $n$-category cafe: http://golem.ph.utexas.edu/category/2009/11/fraisse_limits.html. The answer seems to be "yes, with work," and the post cites Olivia Caramello, Victor Irwin, and Wieslaw Kubis in particular.

$\endgroup$
6
  • $\begingroup$ I just noticed that Qiaochu Yuan already linked to the $n$-category cafe post; oh well. $\endgroup$ – Noah Schweber Jun 6 '14 at 0:57
  • $\begingroup$ My question is on whether random permutations can be thought of categorically. I was hoping maybe there was some functor Set to some enriched version of Set with a uniform random permutation associated to each set. $\endgroup$ – john mangual Jun 6 '14 at 12:44
  • $\begingroup$ How could there be? There isn't even a canonical way to produce a random permutation with domain $\mathbb{N}$: the construction of the random permutation requires us to make (infinitely many) choices along the way. Maybe the target category could be "structures (in the signature $\Sigma$ of the random permutation) up to isomorphism," in which case the morphisms would presumably be "homomorphisms up to isomorphism." I suspect this would get a bit weird, but moving on: we would then want the following claim to be true: (cont'd) $\endgroup$ – Noah Schweber Jun 6 '14 at 16:39
  • $\begingroup$ "For every $\kappa$, there is a $\Sigma$-structure $S$ of cardinality $\kappa$ with age $\{$finite permutations$\}$ which is 'very homogeneous'." Then we could say that we had a functor from the category of infinite sets (or, more compactly, the category of infinite cardinals) to the category of $\Sigma$-structures up to isomorphism that was the "random permutation builder." However, in order for this to actually be functorial, we need that in fact the structure associated to $\kappa$ be $<\kappa$-homogeneous, and it's not at all clear to me that we can necessarily do this in ZFC. (Can we?) $\endgroup$ – Noah Schweber Jun 6 '14 at 16:41
  • $\begingroup$ In general, I think that things are only guaranteed to work at the countable level (and maybe at the level of $\omega_1$, too). $\endgroup$ – Noah Schweber Jun 6 '14 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.