Register to reply 
Prove all subsets of a finite set are finite 
Share this thread: 
#1
Apr112, 11:35 PM

P: 187

1. The problem statement, all variables and given/known data
Check the title 2. Relevant equations Using the following definition of finite/infinite: A set X is infinite iff [itex]\exists f:X \rightarrow X[/itex] that is injective but [itex]f(X) \not= X[/itex], i.e. [itex]f(X) \subset X[/itex]. A set X is finite iff [itex]\forall f:X \stackrel{11}{\rightarrow} X[/itex] it must follow that [itex]f(X) = X[/itex]. 3. The attempt at a solution My instructor's very picky about the definitions I'm supposed to use, but I'm having a lot of trouble wrapping my head around this. Could someone explain them to me? And what information I'm supposed to get from the definition? Thanks in advance. 


#2
Apr212, 12:18 AM

Sci Advisor
P: 2,470

Well, suppose, you have a set [itex]Y \subset X[/itex] and that Y is infinite. Then there exists an injective mapping [itex]f:Y \rightarrow Y : f(Y) \subset Y \subset X[/itex]
Now all you have to do is come up with a function g that does the same thing to X. You already know how to map elements of Y subset. Just got to figure out what to do with X\Y. 


#3
Apr212, 12:20 AM

P: 1,622

Getting the right intuition for these definitions of finite and infinite is definitely tricky. Unfortunately I am tired and have a problem set due early tomorrow morning that I still need to finish up, so I cannot help explain these definitions at the moment. I can, however, help you solve the problem.
Let [itex]X[/itex] be a finite set and suppose that [itex]S \subseteq X[/itex]. Let [itex]f:S \rightarrow S[/itex] be onetoone and define [itex]g:X \rightarrow X[/itex] such that [itex]g(x)=f(x)[/itex] for all [itex]x \in S[/itex] and [itex]g(x) = x[/itex] for all [itex]x \in X \setminus S[/itex]. Then [itex]g[/itex] is onetoone. Use the fact that [itex]g:X \rightarrow X[/itex] is onetoone and that [itex]X[/itex] is finite to show that [itex]f(S) = S[/itex]. Hint: [itex]g(X) = f(S) \cup (X \setminus S)[/itex]. 


#4
Apr312, 07:05 PM

P: 187

Prove all subsets of a finite set are finite
Thank you both for responding, I just got my first opportunity to look over your help.
Here's how I'm starting off: Let [itex]S[/itex] be a finite set, and let [itex]T \subset S[/itex], where [itex]T[/itex] is an infinite set.I have a question for jgens: Can you elaborate a bit on what you said here? I'm having a bit of trouble following. 


#5
Apr312, 07:13 PM

P: 1,622




#6
Apr312, 07:29 PM

P: 187

"Define [itex]f:S → S[/itex] such that [itex]f(x) = g(x)[/itex] for all [itex]x \in T[/itex] and [itex]f(x) = x[/itex] for all [itex]x \in S \setminus T[/itex]. Then f is onetoone."
What about the first sentence makes f onetoone? And from the hint, if f(S) = S, how is [itex]f(S) = g(T) \cup S \setminus T[/itex]? Is this after I show that g(T) = T? I drew a diagram to visualize the situation. 


#7
Apr312, 07:44 PM

P: 1,622

Edit: You also need to realize that me and K^2 are suggesting very different proofs. His solution is a proof by contradiction while my solution is a direct proof. So you should choose one solution or the other and go with that, if that is what was confusing you. 


#8
Apr312, 07:53 PM

P: 187

Actually, I was hoping to prove by contradiction, but I'd still like to see this method through.
Before I start working on your suggested route, I want to make sure that you're referring to the same definition of onetoone that my prof provided: "Let [itex]f[/itex] be a function from [itex]X[/itex] to [itex]Y[/itex]. Then [itex]f[/itex] is said to be onetoone iff [itex]x, z \in X[/itex], where [itex]x \not= z[/itex], always implies that [itex]f(x) \not= f(z)[/itex], i.e. [itex]f(x) = f(z)[/itex] implies that [itex]x = z[/itex]." 


#9
Apr312, 08:03 PM

P: 1,622




#10
Apr312, 08:28 PM

P: 187

I'm afraid I don't see the connection between f and g. I guess my question is, what does it mean to define the function [itex]f[/itex]? And what information should I immediately be getting from



#11
Apr312, 08:41 PM

P: 1,622




#12
Apr312, 08:51 PM

P: 187




#13
Apr312, 08:55 PM

P: 1,622

Edit: A purely set theoretic notion of function is not necessary here, but I am not quite sure how else to help you understand this. 


#14
Apr312, 09:08 PM

P: 187

Pretty sure: (in my own words) a function is a relation from one set X to another set Y that maps only one f(x) in Y to each x in X, and the domain is all of set X.
And as an example: If X = {1, 2} and Y = {a, b}, then f = {(1, a), (2, a)} is a function, f = {(1, a), (2, b)} is a function, but f = {(1, a), (1, b)} is not a function (since x=1 is mapped to more than one element in Y). 


#15
Apr312, 09:16 PM

P: 1,622

There are some problems with your definition, but I am not going to nitpick now. To define [itex]f[/itex] notice that we assume some onetoone function [itex]g:T \rightarrow T[/itex] exists. Define the function [itex]\mathrm{id}_{S \setminus T} = \{(x,x) \in (S \setminus T) \times (S \setminus T)\}[/itex]. Now take [itex]f = g \cup \mathrm{id}_{S \setminus T}[/itex]. The function [itex]f[/itex] I just defined is the same function as I defined earlier. Earlier I just specified the values of the function in a more understandable way; that is, if [itex]x \in T[/itex] then I said [itex]f(x) = g(x)[/itex] and if [itex]x \in S \setminus T[/itex] then I said [itex]f(x) = x[/itex].



#16
Apr312, 09:19 PM

Sci Advisor
P: 1,169

Your example is correct, but your definition seems confusing.



#17
Apr312, 09:51 PM

P: 187

Okay, I think I'm starting to get it now.
Assume [itex]g: T \stackrel{11}{\rightarrow} T[/itex] exists. Define [itex]h: (S \setminus T) \rightarrow (S \setminus T), h = \{ (x, x) : x \in S \setminus T \}[/itex]. This function is onetoone by definition. (right? Since the image of each x is x. I'm not sure how to phrase it exactly.) Define [itex]f: S \rightarrow S, f = g \cup h[/itex], or [itex]f(S) = g(T) \cup h(S \setminus T)[/itex]. So if [itex]x \in T[/itex], then [itex]f(x) = g(x)[/itex] because g was assumed to be 11. And if [itex]x \in S \setminus T[/itex], then [itex]f(x) = x[/itex] because h(x) = x. Since f is the union of two injective functions, it must also be injective, right? So now I just have to show that [itex]g(T) = T[/itex]?          Edit: Oh, and as for the definition of a function, here's what my booklet says: A relation [itex]F[/itex] from [itex]X[/itex] to [itex]Y[/itex] is a function if and only if (i) [itex]D_G = X[/itex], and         Edit 2: Ok, I feel that I've made some progress. [itex]f(S) = g(T) \cup h(S \setminus T)[/itex]. [itex]f(S) = S[/itex] (because S is a finite set), and [itex]h(S \setminus T) = S \setminus T[/itex] (because it's an identity function). Since [itex]T \subseteq S[/itex], [itex]S = T \cup (S \setminus T)[/itex]. Then it follows that [itex]g(T) = T[/itex]. Therefore, since g is injective and g(T) = T, T is a finite set. Am I right in thinking this way? 


#18
Apr812, 11:51 PM

P: 187




Register to reply 
Related Discussions  
Set of finite subsets of Z+ is denumerable  Calculus & Beyond Homework  16  
Cardinality of the set of all finite subsets of [0,1]  Set Theory, Logic, Probability, Statistics  2  
Finite subsets of N  Linear & Abstract Algebra  3  
Set of all finite subsets of N (real analysis)  Calculus & Beyond Homework  4  
The cardinality of the set of all finite subsets of an infinite set  Set Theory, Logic, Probability, Statistics  10 