1
$\begingroup$

(Apologies for the long-winded description, but I found that often when writing out a thought in detail here, I have a moment of clarity. )

The question has all the info I was given. I have deduced the following:

Let $Q^{-}$ be the set of negative rational numbers , and $O^{+}$ the set of positive odd numbers.

Then, I understand that I have to find a mapping $f : Q^{-} \rightarrow O^{+}$ for all elements in $Q^{-}$ such that $f(q_{i}) = f(q_{j}) \implies i = j$.

I know that for this mapping to be valid the outputs must satisfy the following membership tests :

  1. Must be positive
  2. Must be odd
  3. Must be integer

I also know that all inputs must be of the form $\frac{m}{n} , \text{ for } m,n \in \mathbb{Z}$ and that they must be negative.

My first instinct was to use decomposition of prime odds and have each element as a power index, since this would seem to both guarantee uniqueness and satisfy:

  1. Given that $(+)\times(+) \implies (+)$;
  2. Given that $\text{ odd } \times { odd } \implies { odd }$;

Unfortunately I quickly realized that these include fractions such that for example $3^{-\tfrac{1}{2}} = \frac{1}{\sqrt{3}} \not\in \mathbb{Z}$. Hence failing to satisfy 3.

Then I came across this , which seems to perform a sort of indexing via an intermediate mapping on $\mathbb{N}$. I don't fully understand what is going on there though? If this is indeed what is happening, then wouldn't this mean that every set has an injection to any other set? Given that, all their elements can be indexed?

Is there a solution which does not involve a piece-wise function?

Also, if possible , could you explain the link above in more detail? In particular the justification for this claim $2π‘›βˆ’1, π‘›βˆˆπ, \text{ hence } 𝐴→𝐍,2π‘›βˆ’1↦𝑛$ is a bijection.

$\endgroup$
6
  • $\begingroup$ Both are countably infinite sets so a bijection exists. Why is an explicit one so important? $\endgroup$ Oct 15 '19 at 22:25
  • $\begingroup$ This is from an exam question for one of my intro classes, but there are no solutions. They ask for an explicit one and for a justification. $\endgroup$
    – Scb
    Oct 15 '19 at 22:34
  • $\begingroup$ Giving an explicit injection is really though as an exam question, because it can be hard to find one. However, with a little bit work in the lecture, this statement is trivial. As beeing said, from the lecture you should know that both sets are countable, and therefore there exists a bijection between both sets. $\endgroup$
    – Cornman
    Oct 15 '19 at 22:51
  • $\begingroup$ "Unfortunately I quickly realized that these include fractions such that for example" Then only raise them to positive powers. $q = \frac {-a}{b}$ so that $a > 0; b>0;\gcd(a,b) =1$ and $a,b\in \mathbb N$. Let $f(q) = 3^a5^b$. .... no fractions involved. $\endgroup$
    – fleablood
    Oct 16 '19 at 2:59
  • $\begingroup$ @fleablood I don’t follow. all the numbers in Q^- are by definition negative. $\endgroup$
    – Scb
    Oct 16 '19 at 11:33
2
$\begingroup$

A easy way is to build up from other injections and compose them (I'll use bijections):

  1. $f: \mathbb{N} \to Q^-$ like shown on the picture below (just that instead of $Q$ positive it's the negatives). That is a surjection actually, to make it a bijection just 'skip' all $y$ in $Q$ if it was already in the range of $f$ for the previous $x$'s. E.g. $f(5)\not = 2/2$, as that is already what $f(1)$ is; instead skip to the next rational number, $f(5)=1/3$.
  2. $g: \mathbb{N} \to O^+ = 2n-1$
  3. Then, $g(f^-1 (x))$ is what you are looking for.

In general, finding bijections between countable sets is easy (most of the time) because there is an 'easy' way to find a bijection with the natural numbers, and then by composing the bijections (one being an inverse), you can find a bijection between the two sets.

enter image description here

$\endgroup$
1
  • $\begingroup$ As defined here, $f$ isn't an injection because $f(1)=f(5)=f(12)$ etc. A little more work is necessary to explicitly define an injection. $\endgroup$ Oct 16 '19 at 0:02
0
$\begingroup$

I understand that I have to find a mapping $f : Q^{-} \rightarrow O^{+}$ for all elements in $Q^{-}$ such that $f(q_{i}) = f(q_{j}) \implies i = j$.

You mean $q_i=q_j$, but I do not understand why you put indices on your elements of $Q^-$.

At the linked thread:

You want a bijective function $f:A\to\mathbb{N}$, where $A=\{1,3,5,\dotso\}$ is the set of the odd natural numbers.

As mentiond such bijection is given by $2n-1\mapsto n$.

Proof:

$f$ is surjective. Let $m\in\mathbb{N}$ be arbitrary. We have to find a $a\in A$ with $f(a)=m$. Since $a$ is odd it is $a=2k-1$ for some $k\in\mathbb{N}$.

Then $f(a)=f(2k-1)=k$. So for $a=2m-1$, we have that $f(a)=m$, which proofs that $f$ is surjective.

Now we want to see that $f$ is injective:

We have to show that $f(a)=f(b)\Rightarrow a=b$.

As above, a, b are odd, so there are $a',b'\in\mathbb{N}$ with $a=2a'-1$ and $b=2b'-1$.

Then $f(a)=f(b)\Rightarrow f(2a'-1)=f(2b'-1)\Leftrightarrow a'=b'$. So $a=b$

I also know that all inputs must be of the form $\frac{m}{n} , \text{ for } m,n \in \mathbb{Z}$ and that they must be negative.

I think you are overthinking it a little bit. Also you have to be more concrete. For example $n$ can not be $0$.

As mentioned in the comments, if you know that both sets are countable (infinite), which they are, you know there is a bijection, and you do not have to give one explicit. That can be done with Cantor's diagnoal argument.

Study the proof where it is shown that you have a bijective mapping $\mathbb{N}\to\mathbb{Q}, similarly to what is visualiced in the answer of Shiranai.

wouldn't this mean that every set has an injection to any other set?

I do not know why you understand it like this. This can not be true. An easy counterexample would be:

$f:\{1,2\}\to {1}$, because every element (1 and 2) is mapped onto 1. If you have a function $f:X\to Y$ between finite sets, you can only have an injection if $|X|\leq |Y|$.

And a surjection if $|X|\geq |Y|$.

However, this does not help here, since your sets are infinite in cardinality, but that is the intuition behind comparing cardinality of infinite sets, or 'infinite' in general.

It is a little bit surprising that there are sets that are more infinite than others. :)

$\endgroup$
2
  • $\begingroup$ It was indeed an incredibly stupid thing to think. Thanks for your input, I'll look into that proof $\endgroup$
    – Scb
    Oct 15 '19 at 23:37
  • $\begingroup$ @Scb You do not have to be to harsh with yourself. It is good to make mistakes. $\endgroup$
    – Cornman
    Oct 16 '19 at 1:36

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.