# Infinite set question.

1. Feb 10, 2007

### MathematicalPhysicist

i need to prove that X is an infinite set iff for every function f:X->X there exists a proper nonempty subset A of X such that f(A) is a subset of A.

well i thought about it, and perhaps bacuase X is infinite it has a subset which is infinite countable, let denote it by A={x1,x2,x3,...}, let f:X->X be any function, and let's look on f:A->X, f(A) is alos infinite countable, by definition: f(A)={f(x)|x in A}, we can't have A to be a proper subset of f(A), cause if it does then: |f(A)|>|A| but then we have aleph-null is bigger then itself which is a contradiction.

now then, we have for every f:X->X there exists a nonempty proper subset A of X, such that f(A) is a subset of A.
if X is finite then i need to show that there's a bijection between X and a proper subset of it (which is a contradiction), we have f(X) a subset of X, and f(A) a subset of A, but i dont know how to procceed from here, any advice?

2. Feb 10, 2007

### AKG

f(A) is not infinite countable by definition. A can be a proper subset of f(A). A being a proper subset of f(A) does not imply |f(A)| > A. Every line of your proof is false.

Construct A recursively. Let x1 be any element of X. What's a good choice for x2?

For the converse, observe that if a is in A, then f(a) is in f(A). For f(A) to be a subset of A, A must also contain f(a). Applying this argument again and again, we find that A must contain fn(a) for all n. Find a function such that fn[/sup](a) = a iff n = k|X| for some k = 0, 1, 2, ....

3. Feb 11, 2007

### MathematicalPhysicist

for your first question i would say it's f(x1), and the next term would be f(f(x1)) etc.
now for the converse, if were to find such a function how would that help me?
i need to prove that X is infinite, but then how can f^n(a)=a where n=k*|X| when |X| isnt finite?
perhaps im missing something here?

btw, about my proof, i see your point if f:A->X, then f is onto f(A) and
|f(A)|<=|A|, but that doesnt mean f(A) is a subset of A.

4. Feb 13, 2007

### MathematicalPhysicist

AKG, any reply?!

5. Feb 13, 2007

### AKG

My hint was to be applied to proving the contrapositive of the converse, not the converse itself. You should know the two are equivalent, however, so this is okay to do. So assume X is finite, and try to derive that there exists a function f:X -> X such that for every proper subset A of X, f(A) is NOT a subset of A.

6. Feb 15, 2007

### MathematicalPhysicist

AKG, the converse of A->B is B->A and the contrapositive of B->A is ~A->~B.
anyway i know that they are equivalent.
so you want to prove that if X is finite then you cant prodcue a subset like this, am i right?

7. Feb 15, 2007

### AKG

You want to, "assume X is finite, and try to derive that there exists a function f:X -> X such that for every proper subset A of X, f(A) is NOT a subset of A."

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook