Question

Prove that if there is an injection f : A ! A which is not surjective, then A is not a nite
set.
. . . . . . . . . .

Answer 1

Prove that if there is an injection f : A -> A which is not surjective, then A is not a finite set.
. . . . . . . . . .

Answer 2

in other words, prove A is infinite

Answer 3

i think we can do this by contradiction , assume there is an injection f A->A which is not surjective and A is finite

Answer 4

Not easy lol....working on it

Answer 5

yeah, it seems to be a stumper

Answer 6

I got the question from this book, page 66
http://www.math.vt.edu/people/day/ProofsBook/IPaMV.pdf

Answer 7

Consider the polynomials..... F(x^i)=x^(1+i) with i an element of the natural numbers....... clearly the domain which is the x^i is contained in the x^(i+1)... but of course the function is not subjective. not we know dim( Im(F(x^i)) ) + 1 = dim(x^(i+1)) now regardless of the i you choose you will always have an i+1 in the range... so thats how id argue it is not finite.

Answer 8

kind of sketchy

Answer 9

hmm

Answer 10

what is dim x^i, and what is F(x^i)
F(x^i) = x^0 + x^1 + x^2 + ...

Answer 11

ok so the range is the set of polynomials x^1.... the F function acting on the domain elements F(x^i) outputs the range of polynomials of one higher order than the domain... so range is the set of polynomials x^(i+1)...... for example if i =3 then Domain = 1,x,x^2,x^3 and the range =1,x,x^2,x^3,x^4

Answer 12

should be x^i not 1 in the first sentence

Answer 13

i havent seen this function before F(x^i), is it from linear algebra

Answer 14

the dimenstion of the domain of (x^i) is i +1 and the dimension of the range (x^(i+1)) would be i +2

Answer 15

all the function F does is it adds 1 to the exponent

Answer 16

if F is applied to x it becomes x^2....if the function F is applied to x^66 it becomes x^67

Answer 17

ok

Answer 18

so F(x^i) = x^i+1

Answer 19

yes exactly

Answer 20

we know dim( Im(F(x^i)) ) + 1 = dim(x^(i+1))

Answer 21

prove the contrapositive

Answer 22

the contrapositive is
if A is finite then there exists a surjection

Answer 23

so if \(A=\{x_1,x_2,\cdots,x_n\}\)

show \(A=\{f(x_1),f(x_2),\cdots,f(x_n)\}\)

Answer 24

errr
if A is finite then for all f : A->A , f is not 1-1 or is surjective

Answer 25

original statement:
if there exists f :A->A such that f is 1-1 and not onto, then A is infinite.

contrapositive:
if A is finite then for all f : A->A , f is not 1-1 or is surjective

Answer 26

do you agree with the contrapositive, did i do that right?

Answer 27

not those

Answer 28

what did i do wrong

Answer 29

can yu finish the proof

Answer 30

I guess that will work

Answer 31

you can still prove it by doing what I suggested

Answer 32

oh

Answer 33

assume A is finite

if f is not 1-1 then we are done so assume f is 1-1 ...prove it is surjective

Answer 34

is that your proof that you suggested earlier ?

Answer 35

no..that is just the very beginning...now do what I mentioned above

Answer 36

since \(A\) is finite we can write it as \[A=\{x_1,x_2,\cdots,x_n\}\]

Answer 37

ok

Answer 38

then consider the set \[\{f(x_1),f(x_2),\cdots,f(x_n)\}\]

Answer 39

can you show that each of the mappings is unique?

Answer 40

given that f is one-to-one

Answer 41

if we can show that { f(x1) ,f(x2) , ...f(xn) } = A , for any f, then we have shown it is surjective

Answer 42

for any \(x_i,x_j\) with \(x_i\ne x_j\)

we get \(f(x_i)\ne f(x_j)\)

Answer 43

yes since each xi is mapped to a unique element in A and the mapping is exhaustive...then for any b in A there is an xi such that f(xi)=b

Answer 44

since our original set {x1,x2,...xn} is distinct, then { f(x1),f(x2)..f(xn)} is also all distinct

Answer 45

, because f is 1-1

Answer 46

only because f is one-to-one

Answer 47

yes

Answer 48

wait, so how does that show your conclusion

Answer 49

you said since the mapping is exhaustive

Answer 50

that is the definition of onto (surjective)

\[f:A\to B\]

is surjective if for any \(b\in B\) there exists an \(a\in A\) such that \[f(a)=b\]

Answer 51

yes

\[\{f(x_1),f(x_2),\cdots,f(x_n)\}=\{x_1,x_2,\cdots,x_n\}\]

Answer 52

though the order is probably different

Answer 53

ok so we have to find , given b element B, an a element of A such that f(a) = b

Answer 54

yes..that is 'onto'

Answer 55

right, the rule might be hard to find since we could mix up the order

Answer 56

yes..the function is a permutation of the elements of \(A\)

Answer 57

but we don't have to specify the rule though

Answer 58

though we could