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

  • Thread starter MathematicalPhysicist
  • Start date
  • Tags
    Infinite Set
In summary, to prove that X is an infinite set, it must be shown that for every function f:X->X there exists a proper nonempty subset A of X such that f(A) is a subset of A. This can be proven by constructing A recursively and using the fact that if a is in A, then f(a) is also in A. For the converse, it must be shown that if X is finite, then there exists a function f:X->X such that for every proper subset A of X, f(A) is not a subset of A. This can be proven by assuming X is finite and deriving a contradiction by constructing a function f:X->X such that f(A) is not a subset of A for
  • #1
MathematicalPhysicist
Gold Member
4,699
371
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?
 
Physics news on Phys.org
  • #2
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
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.
 
  • #4
AKG, any reply?!
 
  • #5
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
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?
 
  • #7
loop quantum gravity said:
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."
 

1. How do you prove that X is an infinite set?

To prove that X is an infinite set, one must show that there is no upper bound or limit to the elements in X. This can be done by demonstrating that for any given number N, there exists an element in X that is greater than N. This shows that X has an infinite number of elements and is therefore an infinite set.

2. What is the relationship between functions and subsets in proving X is an infinite set?

In order to prove that X is an infinite set, one must show that there exists a function that maps the elements of X to a subset of X. This means that for every element in X, there is at least one other element in X that is mapped to it. This relationship between functions and subsets helps to demonstrate the infinite nature of X.

3. Can a finite set also have a relationship between functions and subsets?

Yes, a finite set can also have a relationship between functions and subsets. However, in this case, the function would map the elements of the finite set to a proper subset of the set itself. This is because a finite set has a limited number of elements, so it is not possible for every element to have another element in the set mapped to it.

4. How does the Cantor's diagonal argument relate to proving X is an infinite set?

Cantor's diagonal argument is a proof technique that is commonly used to show that a set is infinite. This argument involves constructing a new element that is not in the set by using the diagonal elements of a given set. If the set is infinite, this new element will always exist, thus proving the infinite nature of the set. This argument is often used in combination with the relationship between functions and subsets to prove that X is an infinite set.

5. What is the significance of proving X is an infinite set?

Proving that X is an infinite set has significant implications in mathematics and other fields. It allows for the understanding and exploration of infinite structures and concepts, such as infinite series, limits, and cardinality. In addition, the concept of an infinite set is crucial in many areas of mathematics, including calculus, topology, and number theory.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
3K
  • Calculus and Beyond Homework Help
Replies
1
Views
487
  • Set Theory, Logic, Probability, Statistics
Replies
15
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
23
Views
1K
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Set Theory, Logic, Probability, Statistics
2
Replies
54
Views
3K
Back
Top