Infinite set question.

Gold Member
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?

AKG
Homework Helper
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, ....

Gold Member
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.

Gold Member

AKG
Homework Helper
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.

Gold Member
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?

AKG