6

If I were to come up with a function $f: \mathbb{N} \to \mathbb{N}$ that makes relation $R_a$ transitive yet non-reflexive and non-symmetric such that

$$q \, R_a \, z \text{ if } f(q) = z,$$ what kind of function should I come up with? I spent the past three hours trying to come up with one but I still don't understand how inputting one number can produce two different results... Do I need to use a piecewise?

Because isn't it transitive when you input $1$ and by some relation, you then get $2$. Then when you input $2$ into that relation you get $3$. Because of transitivity $1$ now should also produce $3$. This makes no sense to me...

Sahiba Arora
  • 10,847
execorders123
  • 71
  • my first though, would be something based on $x<y$ which is transitive but non reflexive, nor symmetric. – zwim May 09 '20 at 12:19
  • 1
    Hint: if $f(a)=b, f(b)=c$ then by transitivity $f(a)=c$ and so $b=c=f(b)$. So every number in range of $f$ Is fixed by $f$. – Ned May 09 '20 at 12:53
  • 1
    In your argument, you assume that $2$ and $3$ are not equal, so to speak . – Ned May 09 '20 at 13:44

2 Answers2

4

How about $f(n)=17$ for all $n$?

Ned
  • 3,852
  • For something slightly more interesting, $f(x) = |x|$ – Ned May 09 '20 at 15:13
  • the problem asks for transitive, non-symmetric, and non-reflexive function. This function is symmetric and reflexive – execorders123 May 09 '20 at 20:59
  • 2
    @execorders123 No it's not: $f(1)=17\neq 1$ so the relation defined is not reflexive, and $f(17)\neq q$ so the relation is not symmetric. Remember that to be reflexive you must have $n R n$ for all $n\in \mathbb N$ and similarly for symmetry, so a single counterexample suffices to show that the relation is not reflexive or symmetric. – dbmag9 May 09 '20 at 21:05
  • 3
    Perhaps your confusion is between 'not being reflexive', which means that there is some $n\in\mathbb N$ such that $n \not R n$, and being anti-reflexive, which means that there is no $n\in\mathbb N$ such that $n R n$. The function defined here is not reflexive, but it does not have the anti-reflexivity property (since $17 R 17$). – dbmag9 May 09 '20 at 21:11
  • @dbmag9 oh so is your logic that because there is at least one example of f(n) = 17, f(17) = n not being the case which would be f(1) = 17, but f(17) !=1, it would not be considered symmetric. And the same for reflexivitiy, f(1) != 1 so it's not reflexive. – execorders123 May 09 '20 at 22:41
  • @execorders123 That's correct. – dbmag9 May 10 '20 at 10:35
3

Suppose $f$ makes $R_a$ transitive. Let $y,z\in \mathbb{N}$ such that $$f(x)=y, f(y)=z$$ for some $x \in \mathbb{N}.$ Transitivity now implies $f(x)=z.$ So $y=z.$ So $f(y)=y$ for every $y \in f[\mathbb{N}].$

Of course, constants are an example. But they are not the only example. The above argument suggests that you only need to find a function which fixes the elements in the range. For instance

$$f(n)=\begin{cases}1, \text{if }n \text{ is odd}\\2, \text{ if }n \text{ is even}\end{cases}.$$

$f$ is not reflexive because $f(3)\neq3$ and not symmetric because $f(3)=1$ but $f(1)\neq 3.$

Obviously you could have chosen any odd and even number in place of $1$ and $2$ respectively.

You can come up with plenty of other examples in a similar way.

Community
  • 1
Sahiba Arora
  • 10,847