3
$\begingroup$

The problem is: prove the existence of function $f: \mathbb{R}\times\mathbb{R} \rightarrow \mathbb{N}$ such that $f(x,y)=f(y,z)\implies x=y=z$. I was thinking about $f(x,y) = \left\{ \begin{array}{ll} 1 & \textrm{iff $x=y$}\\ something & \textrm{ iff $x\neq y$} \end{array} \right.$ but I guess we need to have bijection from $\mathbb{N}$ to $\mathbb{R}$ to do that, which don't exist because $|\mathbb{N}| < |\mathbb{R}|$. EDIT: let's make it clear. If we take some $c \neq g$, $f(c,c)$ can't be equal to $f(g,g)$.

$\endgroup$
  • $\begingroup$ @pingwindyktator I don't understand how your edit follows from the question. If it does, the question is easy (just count the possible values of $f(a, a)$), but I think showing this is hard. $\endgroup$ – Noah Schweber Jan 18 '16 at 19:16
  • $\begingroup$ Haven't you proven it is impossible? if $x,y \in R; x \ne y$ then $f(x,x) \ne f(y,y)$. So g(x) = f(x,x) f: R -> N is an injective function. Which is impossible. So such a function can't exist? At least I think so. I could have made a careless error. $\endgroup$ – fleablood Jan 18 '16 at 19:19
  • $\begingroup$ @fleablood The OP's edit is at odds with their actual question . . . $\endgroup$ – Noah Schweber Jan 18 '16 at 19:22
  • 2
    $\begingroup$ Oops. my error. x \ne y so f(x,x) = (y,y) is not a case of (x = $\alpha$ and $\alpha$ = y$). VERY careless error on my part. f(x,x) = f(y,y) => f(x,z) = f(z,y) iff x = z and z = y which, duh, need not be the case. $\endgroup$ – fleablood Jan 18 '16 at 19:43
  • 1
    $\begingroup$ Nope, I'm definitely wrong. f(x,x) = f(y,y) \=> x = y as .... x and y aren't the same. $\endgroup$ – fleablood Jan 18 '16 at 19:44
5
$\begingroup$

There seems to be a misunderstanding: the original condition

$$f(x, y)=f(y, z)\implies x=y=z$$

does not imply the new (added in an edit) condition

$$f(x, x)=f(y, y)\implies x=y.$$

To see this, consider the following counterexample: let $f: \{1, 2\}\rightarrow \{1, 2, 3\}$ be given by

  • $f(1, 1)=f(2, 2)=1$,

  • $f(1,2)=2$, and

  • $f(2, 1)=3$.

This $f$ satisfies the original condition, but not the new condition.

It's easy to show that there are no functions $\mathbb{R}^2\rightarrow \mathbb{N}$ satisfying the new condition. Perhaps surprisingly, if we restrict attention to the original condition, there are such functions! Moreover, we don't even need something silly like the axiom of choice to build them!


Construction. Let $\mathcal{A}=\{A_r: r\in\mathbb{R}\}$ be a family of sets of natural numbers other than $0$ with the property that $$r\not=s\implies A_r\setminus A_s\not=\emptyset.$$

Now define $f(r, s)$ as follows:

  • If $r\not=s$, then $f(r, s)$ is the least element of $A_r\setminus A_s$.

  • If $r=s$, then $f(r, s)$ is $0$.


Verification. Now suppose $f(x, y)=f(y, z)$ and it is not the case that $x=y=z$.

First, let's see that the numbers $x, y, z$ must be distinct. Suppose $x=y$. Then $f(x, y)=0$. But since $y\not=z$ (by assumption that "$x=y=z$" fails) then $f(y, z)\in A_y\not\ni0$, so $f(y, z)\not=f(x, y)$. Similarly, we can't have $y=z$.

So $x, y, z$ are distinct. But then $f(x, y)\in A_x\setminus A_y$, and $f(y, z)\in A_y\setminus A_z$. In particular, we have

  • $f(x, y)\not\in A_y$, but

  • $f(y, z)\in A_y$.

Oops.


Caveat. Of course I'm skipping a crucial step here: showing that such a family $\mathcal{A}$ actually exists. Since there was some disagreement over whether such families actually exist, let me give a concrete one here:

Fix your favorite bijection $F$ between $\mathbb{N}$ and the set of finite binary strings $2^{<\omega}$; separately, fix your favorite bjection $G$ between $\mathbb{R}$ and the set of infinite binary strings $2^\omega$. Now, given a real $r$, we view each real $r$ as an infinite sequence, and let $A_r$ be the set of natural numbers standing for initial segments of that sequence: more formally, we let $$A_r=\{F^{-1}(\sigma): \sigma\prec G(r)\}.$$

The resulting family is in fact an almost disjoint family: the intersection $A_r\cap A_s$ for $r\not=s$ is always finite, but every $A_r$ is infinite!

$\endgroup$
  • $\begingroup$ genius. Thanks! $\endgroup$ – pingwindyktator Jan 18 '16 at 19:50
  • $\begingroup$ @pingwindyktator This is a great example of just how weird sets can be - even at a fairly concrete level! This seemed "obviously false" to me as well, and I spent a while trying to disprove it; after the fifth or so time I failed, I started to see a pattern :P. $\endgroup$ – Noah Schweber Jan 18 '16 at 19:51
  • $\begingroup$ but you didnt get my edit right. "If we take some $c\neq g$, $f(c,c)$ can't be equal to $f(g,g)$" is $c \neq g \implies f(c,c) \neq f(g,g)$ :) $\endgroup$ – pingwindyktator Jan 18 '16 at 19:53
  • $\begingroup$ @pingwindyktator That's the contrapositive of what I wrote - they're equivalent. (Keep in mind $f$ is a function, so if $c=g$ we'll by definition have $f(c, c)=f(g, g)$.) $\endgroup$ – Noah Schweber Jan 18 '16 at 19:54
  • $\begingroup$ Reread your edit: (x,y)(y, z) is a case of the second term of the first being the first term of the second. i.e. (x, W)(Y, z) where W = Y. That is simply not the case with (x,x)(z,z) this is a case of (x, W)(Y, z) where W = x $\ne$ z = Y$. The second term of the first (x) is NOT equal to the first term of the second (y). It simply doesn't follow. I feel very abashed as I fell for it to... but it was simply an oversight. $\endgroup$ – fleablood Jan 18 '16 at 20:02

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.