Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Infinite set question.

  1. Feb 10, 2007 #1
    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. jcsd
  3. Feb 10, 2007 #2

    AKG

    User Avatar
    Science Advisor
    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, ....
     
  4. Feb 11, 2007 #3
    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. Feb 13, 2007 #4
    AKG, any reply?!
     
  6. Feb 13, 2007 #5

    AKG

    User Avatar
    Science Advisor
    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.
     
  7. Feb 15, 2007 #6
    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?
     
  8. Feb 15, 2007 #7

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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."
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Infinite set question.
  1. Infinite sets? (Replies: 2)

Loading...