2

So I work with theoretical chemistry and time and again we end up walking into what is, for us, uncharted mathematical territories in our search for the patterns and symmetries of nature and its atomic arrays (crystals, molecules and whatnot).

Recently I've been struggling to find what I've learned to call a "binary injective function", which is, as I understand, a function of two arguments which returns a unique value for each unique pair of arguments.

I've seen this problem treated in a number of forms, for example here and here. This last one even has an entry in the Math.Stackexchange itself right here.

None of these links however, show that this or that function is injective, and the more I look it up on the internet, the more convinced I get that this is actually an open problem in mathematics. Is that so? Well maybe the ones around here with knowledge of mathematical scientific frontiers can give us a clue as to what is known about these little beasts.

And just so I don't end up asking too vague a question, here is the overall description of what I understand as an injective function, the kind I need specifically.

So my problem is about a function with two arguments $f(x,y)$ such that $ f:\mathbb{V} \times \mathbb{V} \rightarrow \mathbb{R}$, for $\mathbb{V} = \{ x | x \in [-\frac{\tau}{2},\frac{\tau}{2}]\}$. As stated above, the function needs to be injective which means that there must be a single value associated with a particular set of arguments. I think that means that the equation $f(x,y)=c$ has, at most, only one solution for any $c \in \mathbb{R}$.

Which reminds me that the function doesn't have to be bijective in the reals, there can be real numbers that will never be assigned to any particular set of arguments, it just have to be injective. It also doesn't have to have any analytical or algebraic form, it can be thought of as procedure, a computational sequence of steps that will generate unique outputs for every unique pair of inputs.

Anyways, I wandered a lot about the internet trying to find a function that would fit these criteria. I even tried other types of domains which also represented the same space of angles, like $\mathbb{W} = \{x | x \in [0,\tau]\}$. So I looked for:

  • $f:\mathbb{V} \times \mathbb{V} \rightarrow \mathbb{R}$

  • $f:\mathbb{W} \times \mathbb{V} \rightarrow \mathbb{R}$

  • $f:\mathbb{V} \times \mathbb{W} \rightarrow \mathbb{R}$

  • $f:\mathbb{W} \times \mathbb{W} \rightarrow \mathbb{R}$

Hoping that domain definition would give me some insight, but to no avail. The injective binary functions still elude me.

So my question is: Does any of you know of a 2-variable function that is injective for any of the domain options shown?

Community
  • 1
urquiza
  • 887
  • 1
    What do you mean by $\mathbb{Q} = [-\frac{τ}{2}, \frac{τ}{2}]$? Usually $\mathbb{Q}$ is fixed to mean the rational numbers, so are you redefining it to mean the closed interval here? Or do you mean just rational numbers from that interval? Similarily with $\mathbb{P}$, it usually means the irrational numbers in this context. – user87690 Oct 29 '14 at 12:47
  • Given real numbers $a,b$ with $a<b$, there is no continuous injection $[a,b] \times [a,b] \rightarrow \mathbb{R}.$ (Perhaps someone can supply a proof?) There can certainly exist discontinuous ones, though. – goblin GONE Oct 29 '14 at 12:50
  • @user87690 yes I was redefining the symbol, but in order to keep it true to the standard notation, I edited it out and called my domain sets $\mathbb{V}$ and {\mathbb{W}$. – urquiza Oct 29 '14 at 13:04
  • Given @goblin's comment, and the fact that physical processes tend to be continuous, I'm wondering if you really need an injective function or simply one that is injective in each variable separately (that is, for fixed $v$, the function $f(v,.)$ is injective and similarly $f(.,v)$ is injective). Can you clarify what you are trying to model? – rogerl Oct 29 '14 at 13:14
  • 1
    goblin: Since $[a, b] × [a, b]$ is compact, we would have a subspace of $\mathbb{R}$ homeomorphic to $[a, b] × [a, b]$, which is not possible, e. g. because of dimension. – user87690 Oct 29 '14 at 13:14
  • @goblin what if the interval isn't closed? For example, $g:\mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R}$. If that $g$ function exists, it surely can act as my $f$. – urquiza Oct 29 '14 at 13:19
  • 1
    @urquiza: It is the same problem if you want that function to be continuous. If there is a continous injection $\mathbb{R} × \mathbb{R} \to \mathbb{R}$, then its restriction to $[0, 1] × [0, 1]$ is an embedding of two-dimensional space into a one-dimensional space, which is not possible. – user87690 Oct 29 '14 at 13:28

1 Answers1

3

First note that $\mathbb{W}$ is just shifted $\mathbb{V}$ so regarding the question, there is no difference in those four cases.

1) There exist an injective mapping from $\mathbb{V} × \mathbb{V}$ into $\mathbb{R}$. Since $\mathbb{V} ⊆ \mathbb{R}$, we have a nice injective mapping, even an embedding $\mathbb{V} × \mathbb{V} \to \mathbb{R} × \mathbb{R}$. And there is a theorem stating that for every infinite set $A$, there is a bijection between $A$ and $A × A$. One can imagine the base case of the theorem – enumerating pairs of natural numbers (starting with the origin and concatenating the finite diagonal lines in the first quadrant). So by composing our embedding with a bijection between $\mathbb{R} × \mathbb{R}$ and $\mathbb{R}$, we get desired injective mapping.

2) As said in comments, there is no continuous injective function $\mathbb{V} × \mathbb{V} \to \mathbb{R}$, because the continuous injectivity could then be promoted to embedding on any compact subspace, so we would get a two-dimensional compact subspace of one-dimensional real-line, which is not possible.

3) One can construct an explicit injective function $\mathbb{V} × \mathbb{V} \to \mathbb{R}$. Real numbers are almost the same thing as infinite sequences of ones and zeroes. Informally, you can imagine taking a decimal expansion of the real, but using binary digits instead, the only problem is that there are two different expansions of each rational number – the one ending with $1000…$ and the one ending with $0111…$. Formally, there is a quotient function $2^ω \to [0, 1]$. $2^ω$ is a set of all functions from $ω$ to $2 = \{0, 1\}$, i.e. the set of all infinite sequences of zeroes and ones. It has also a structure of a topological space – taking the product topology of infinite product of $2$-point discrete spaces. This topological space is called Cantor space and is homeomorphic to Cantor set in reals (http://en.wikipedia.org/wiki/Cantor_set). The quotiet just glues the endpoints of the gaps in the Cantor set (i.e. the two equivalent binary expansions of rational numbers) together. So any irrational number has one preimage and any rational number has two preimages. By choosing one preimage for each irrational number, you get an injective function $[0, 1] \to 2^ω$ which is not continuous, but is kind of nice, as created from that quotient mapping. So now we have $[0, 1] × [0, 1] \to 2^ω × 2^ω \to 2^ω \to [0, 1] ⊆ \mathbb{R}$, since $2^ω × 2^ω$ is homeomorphic to $2^ω$ – from a pair of sequences you form one sequence by intertwining the sequences – you realize first sequence on odd indices and the second on even indices.

user87690
  • 9,133
  • So if I convert $2^\omega$ to its binary form, there is a one-on-one correspondence between the $\omega$ argument and the strings generated, as long as I know which kind of pre-images I want to choose from, is that it? Then I can "unwind" the resulting sequence to check what arguments I get by building the first argument with odd indices and the second one with even ones... Am I following? – urquiza Oct 29 '14 at 18:01
  • You don't convert $2^ω$, it already is the set of all infinite sequences of ones and zeroes by definition. Basicaly you just move between $[0, 1]$ and $2^ω$, because bijection between $2^ω × 2^ω$ and $2^ω$ is easy to find and it's even a homeomorphism. The way $2^ω \to [0, 1]$ is natural, you just interpret the element of $2^ω$, which is an infinite sequence of ones and zeroes, as a binary expansion of a number and assign that number. The other way around you get injective function $[0, 1] \to 2^ω$, by choosing a preimage wrto original function. – user87690 Oct 30 '14 at 08:16
  • So I have two decimals represented as binary digits. I take both of them (inputs) and entwine the string of binary digits which represent them, the first argument's digits goes in even indices and the second in the odds. The resulting sequence thus constructed can then be represented in decimal notation for the output and it will land between $0$ and $1$? – urquiza Oct 31 '14 at 23:57
  • @urquiza: Yes, that's right. Just a minor thing, you don't have to represent the output in decimal notation, it just corresponds to a real number. A real number is technically different from its decimal representation. But that's just a detail. – user87690 Nov 01 '14 at 10:13