Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Combinations

Julius Hamilton (Jan 12 2025 at 17:54):

Thank you.

I meant that for 3 independent binary decisions, there are $|\{0,1\}|^3$ outcomes. Call the set of outcomes the sample space, denoted $\Omega$. Elements of $\Omega$ are of the form $(0,1,1)$, for example.

I then asked about the permutations of $\Omega$. This is where I got the number $8!$ from.

Julius Hamilton (Jan 12 2025 at 18:14):

One way to list the elements of $\Omega$ is viewing choices as a tree. Let the initial state be the root. Assume $0$ is written left of $1$. At a given node, choose the leftmost option that hasn’t been visited yet. You will make these choices, in this order:

$000, 001, 010, 011, 100, 101, 110, 111$.

Julius Hamilton (Jan 12 2025 at 18:25):

I wonder if a way to understand which permutations are rule-based rather than random is by interpreting binary strings as base $2$ integers. The above sequence becomes $0,1,2,3,4,5,6,7$.

If we started at $0$ and added $3$ mod $8$ each time, we would get $0, 3, 6, 1, 4, 7, 2, 5$. Translated into binary, this is $000, 011, 110, 001, 100, 111, 010, 101$.

So we can say that that last sequence isn’t random. When we translate it back into “$3$ independent binary choices”, it is harder to see what rule tells us how to make choice $n + 1$ if we are given choice $n$. But it turns out to be possible to do so.

Julius Hamilton (Jan 12 2025 at 18:44):

I’m basically investigating, even when we know that a set $S$ is enumerable because we found a way to enumerate it, how many other ways are there to enumerate it?

Julius Hamilton (Jan 12 2025 at 18:56):

And some aspects I am thinking about are:

Every enumeration should be able to be written as a function from $[0,7] \to S$. These are the trivial rules, which list the order of the elements directly.

Some of the enumerations can be written as inductive rules. For example, $s_0 = 0, \; s_{n + 1} = s_n + 1 \; \text{mod} \; 8$.

There are some rules which require memory, in that we have to be able to check if a sequence has been produced before.

Morgan Rogers (he/him) (Jan 15 2025 at 19:08):

The subtlety in this is that the complexity of a description is heavily dependent on which operations/rules are allowed and which are considered basic. For example, you have to exploit some structure on the set to get any rule at all (otherwise no ordering is inherently more natural than any other). Here you're using orderings on 2 and 3 plus the lexicographic ordering on one hand, and a total ordering on [8] plus the translation to base 2 on the other. Presenting the problem as a bijection as you do, you can compose with a bijection in the domain or the codomain, whose complexity must be measured. If you treat [8] as a ring of integers mod 8, you might allow addition as a basic operation on the domain. Or you might take permutations of 2 and 3 as basic on the right. Or you might measure complexity of permutations ignoring all that structure, taking transpositions as the basic ones... there is no a priori comparison between these different ways of constructing orderings from one another.