Infinite set question.

  • #1
MathematicalPhysicist
Gold Member
4,362
241
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?
 

Answers and Replies

  • #2
AKG
Science Advisor
Homework Helper
2,565
4
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
MathematicalPhysicist
Gold Member
4,362
241
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.
 
  • #5
AKG
Science Advisor
Homework Helper
2,565
4
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
MathematicalPhysicist
Gold Member
4,362
241
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
AKG
Science Advisor
Homework Helper
2,565
4
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?
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."
 

Related Threads on Infinite set question.

Replies
3
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
22
Views
863
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
4
Views
2K
Replies
25
Views
12K
  • Last Post
Replies
2
Views
2K
  • Last Post
2
Replies
31
Views
27K
Top