1

There are lots of places where we encounter one-way operations where there is a defined way "forward" but no way to really go "backwards". I can think of a number of examples but the so called "arrow of time" is what really got me thinking about this. Another example I have been thinking about is in cellular automata (such as the game of Life) where for a given state there may be any number of possible "seeds" or maybe none at all so one can not really move "backwards".

I was thinking that surely the abstraction of this idea must have been studied. Structures where we can move "forward" but an inverse is not possible. I can't seem to find a formal discussion of this. Can someone please give me a push in the the "forward" direction here?

I am thinking (roughly) about a set $S$ that has an ordering $(a \leq b)$ and some operation $a * b = c$ such that $a \leq c$ and $b \leq c$ but without a corresponding inverse. As well as a universe $U$ such that $S$ is a subset of $U$ but there exists element $d$ in $U$ but not $S$ such that $d \leq x$ and $x \leq d$ is undefined for all $x$ in $S$ but $x * d = e$ is defined in $U$.

What areas of mathematics deals with such sets?

I am so lost I can't even think of a good tag for the question!

nickdmax
  • 111
  • Some cryptography depends on some functions to be "one-way": trapdoor function. – Simon Marynissen Mar 01 '17 at 21:03
  • There's also the notion of a directed space. – Malice Vidrine Mar 01 '17 at 21:09
  • Directed spaces looks promising. Thank you. – nickdmax Mar 01 '17 at 21:36
  • So the concept of spacetime helps with the arrow of time a bit. Not sure it helps with the more discreet example from cellular automata. – nickdmax Mar 01 '17 at 21:53
  • Directed sets captures the direction concept I was looking for and I will update the description when I am back at a computer. – nickdmax Mar 01 '17 at 21:57
  • @SimonMarynissen - Thank you for the one way function reference. I did think of those but since in my mind they are typically defined as "hard" to inverse which is weaker than I had in mind. But I found this statement which gives me much to think about:

    "The existence of such one-way functions is still an open conjecture. In fact, their existence would prove that the complexity classes P and NP are not equal, thus resolving the foremost unsolved question of theoretical computer science."

     – nickdmax Mar 01 '17 at 22:56

0 Answers0