f: A --> B is injective if for every 'x' in Set A, there is one and only one image 'y' in Set B and for every 'y' in Set B there is unique pre-image in Set A.

Hence Set B may be any arbitrary one. Only condition is that n(B) > or = n(A)

Thank you for remembering the definition of one-to-one map. Nevertheless, it is very simple to see that a map f:X --> X is injective provided that for every pair (x,y) lying in X, the relation f(x )= f(y) implies x = y. Do you agree?

Well, now the question is whether such a kind of mapping is always possible to be defined. Consider that to know whether or not f(x) = f(y) you must know the definition of f(x) and f(y), and in other topic commented in this webpage, I have proved that not every real number can be defined by means of a finite statement.

Excuse me for the explanation, but I think that the topic needs to be redirected.

O.k.

suppose A is countably infinite set & B is a finite set. in this case we cannot define an injection from A to B becose there are infinitely many elements in A which have no image in B if the correspondence is injective and this violates the defination of function that every element in domain set has an(uniqe) image in codomain set. so answer of your question is no for this case.

Dear Swadhin,

Of course, this case is obvious. However, the impossibility I am referring to is a consequence of the impossibility of defining the members of every set by finite statements. This impossibility has been proved in other topic. It is clear that for two members of a set, say x and y, which cannot be defined by means of finite statements, in general, there is no finite procedure in order to distinguish whether or not both are the same. Now, if f is a function such that f(r)=x and f(s) =y and r is different from s, to be f injective, f(r)=x must be also different from f(r)=y, and we are assuming that there is no finite procedure to discern whether or not x =y. Accordingly, by no means we can know whether or not f is injective. This kind of impossibility is what I have in mind, because it is stated in a way which does not depends on the size of the involved sets. By contrast, it is a consequence of the existence of members which must defined by endless procedures. Thus, the infinity lies in member definitions instead of set size.

If "arbitrary" is interpreted as "any", then the answer is clearly no. Try f:X->Y with X={0,1,2,...} and Y={0}: X is countable and Y has only one member. Any (total) map fails to be injective. Am I missing something?

Perhaps, the expression is ambiguous. I apologize. What I mean it is better expressed in the following terms:

"Can you always define an injective map from a countable set into an infinite one?"

Since it is a well known fact that it is not possible to define an injection from X into a set smaller than X, I have supposed that it would be understood the codomain to be greater than or equal to the corresponding domain, without stating this requirement explicitly.

However, there is a lack of accuracy. Sorry.

Thanks for correcting me.

"Can you always define an injective map from a countable set [X] into an infinite one [Y]?"

Yes. Comparison of cardinalities yields |X|

Esteban, I think you need to specify exactly what you are referring to when you say "finite statement" or "finite definition." For example, are you allowing or disallowing recursion? It isn't clear to me after reading this and related threads whether you are referring to a finite syntax or a finite semantics.

This question was answered in other thread. Nevertheless, it is easy to explain. A Gödel's numbering function assigns a positive integer to each statement, which can be split in a finite set of primitive ones. What I call finite statement are those expressions having assigned a Gödel's number. You can see this topic in http://mathworld.wolfram.com/GoedelNumber.html.

Now, consider that if every member of an uncountable set E can be defined by a finite statement, then any Gödel's numbering function sends E into the set of positive integers. This fact implies E to be countable, which contradicts the assumed uncountability nature of E. The conclusion is that every uncountable set must contain some members which can not be defined by means of finite statements.

Finally, if two members x and y of E cannot be finitely defined, there is no finite procedure to compare them; hence it is not always possible to discern whether or not both are de same. Without knowing whether or not x=y it is not possible to know whether a function with domain E is injective.

Of course, you can think that invisible men do not exist, because you have never seen one of them. Analogously, you can think that undefinable objects do not exist, because you have never read a definition of one of them. Nevertheless, if Gödel's method is adequate, there exist such a kind of objects. I have no personal preferences; accordingly if Gödel' s method fails, then the logics developed in the last century must be rejected.

Esteban, I see now what you mean.

Usually one starts from a structure L = < R , f , c > and then defines a Goedel numbering of statements in that particular syntax. A change of L implies a change in numbering. You, if I got it correctly, start the other way around. Your "primitive" notion is Goedel numbering and you call a statement finite iff it can be expressed by *some* Goedel number. Correct?

O.k.

Ok, you can´t always compare two numbers x, y to know if they are the same. But what I don't understand is in wich way this is related to the original question. I mean: it doesn't matter if you can or can't compare the numbers, the function always exists.

Even if you are unable to find the images of the elements in the domain, you can always be absolutly sure that you are going to have finite different elements in an uncountable set.

The question is not the existence, but the possibility of defining it. Notice, that the topic is:

"Can you define.....". and it is not "Does there exist...."

Now, consider the following question: Let x = 0.a_1a_2a_3a_4.....and y = 0.b_1b_2b_3b_4.... two irrational numbers. Suppose that you know that for every integer smaller than a large one M the relation a_n = b_n holds. Can you accept that

x = y? Of course, the answer is not, and it does not matter how large M is. However, rational numbers possess always a repeating pattern. Since patterns must consist of a finite sequences of figures, one can always decide whether or not two rational numbers are the same by comparing a finite sequence of figures,

That does not hold in every case. The rational number 0.1 is the same as the rational number 0.0999... but this would not be established by comparing a finite sequence of figures.

Do you think that 0.1 is irrational? If the answer is not, this is not the case I have exposed. Accuracy is a good practice.

I think you have misunderstood, I am saying that 0.1 is rational and is equivalent to the rational with the infinite decimal expansion 0.0999...

You said "one can always decide whether or not two rational numbers are the same by comparing a finite sequence of figures" and I was pointing out that this is not necessarily the case with every rational number, depending on how one chooses to write it. Accuracy is indeed important...

Dear Carrol

Of course, a rational number must be always defined by means of a finite sequence of figures. For instance in your example 0.0999.... the dots in the tail means that the following figures are constantly equal to "9". If by means of the dots ...... you do not denote that the following figures are equal to "9" it is not possible to guess whether the 1000-th figure can be "5" or "9".

If I impose the rationality either the number must be defined as a quotient of two integers n/m or in decimal expressions the mantissas must contain a repeating pattern. If you do not define the pattern, the number is undefined.

The requirement of being rational imposes to be defined as a quotient or by means of a repeating pattern. In both cases is possible to be identified by a finite sequence of figures,

I am tired explaining such an elementary questions. I have under consideration to ignore others similar questions.

Tarancon - I was not asking a question, I think you still don't understand. I was not commenting on how a rational number is defined. I'm sorry that you seem to have found this confusing. I was referring to your assumption regarding the comparison of two rational numbers.

Dear Rob,

Can you compare two numbers without defining them?

Excellent !!! tell me whether or not the numbers x and y that I have in mind are the same.

You are right, I cannot understand how to compare irrational numbers without previously defining them.

Tarancon, I'm sorry that you still didn't understand my point, but I can try to explain to you one more time.

Note that what I am saying has nothing to do with irrational numbers, sorry this wasn't clear.

My question to you would be:

Can you decide whether the two rational numbers 0.1 and 0.0999... are the same by comparing a finite sequence of figures?

The answer is clearly no. This illustrates my point that your statement "one can always decide whether or not two rational numbers are the same by comparing a finite sequence of figures" is not completely accurate.

I hope this is more clear.

O.k.

"Can you decide whether the two rational numbers 0.1 and 0.0999... are the same by comparing a finite sequence of figures?"

Isn't that a bit superficial? From the moment you say "rational numbers", you don't have to compare anything since you are talking about the same *number* in two different notations.

Yes, you're right. I was just saying that they are the same number but it does not contain the same series of digits when notated in the two different forms. It is a bit superficial, but was in response to an earlier comment.

It seems rather pedantic, but it is the case that you cannot decide whether or not XV and 15 are the same just by comparing ASCII characters. Ditto for 1 and 0.99..., since they have different digits. However if you have a translation map, mapping each rational to a quotient q/p, you can. So the *rationals* 1 and 0.99.. can indeed be compared in a finite number of steps (involving the previously mentioned map) and it will turn out that they are the same.

Dear Rob Carroll,

Yesterday I had no time to write a post and I have answered with a laconic O.K.

Now, I have to explain you why your example is not admissible.

Why do you know that both numbers 0.1 and 0.09999… are the same?

Indeed, because you know a simplification method for mantissas. You know that every mantissa with a tail consisting of an infinite sequence of "9" can be simplified.

Every body know that to compare expressions previously they must be simplified. If you are asked to compare 6/4 and 12/8 previously you must simplify them obtaining 6/4 = 3/2 and 12/8 = 3/2. To compare the expressions 3.3.3-2.2 and 9-4 previously they must be simplified. To compare two sentences, previously they must be translated to the same language. Likewise, if you know that mantissas can be written in two different ways, when you have to compare two decimal expressions, previously you have to simplify them. Every comparison method requires a previous simplification or translation.

I hope that now you can understand why your example is not admissible,