Proving X is an Infinite Set: The Relationship between Functions and Subsets

[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 don't know how to procceed from here, any advice?

 

[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 x₁ be any element of X. What's a good choice for x₂?

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 fⁿ(a) for all n. Find a function such that f_{n[/sup](a) = a iff n = k|X| for some k = 0, 1, 2, ...}

 

[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| isn't finite?
perhaps I am 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 doesn't mean f(A) is a subset of A.

 

[MathematicalPhysicist]

AKG, any reply?!

 

[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.

 

[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 can't prodcue a subset like this, am i right?

 

[AKG]

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 can't prodcue a subset like this, am i right?

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."