1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prove all subsets of a finite set are finite

  1. Apr 1, 2012 #1
    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{1-1}{\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. jcsd
  3. Apr 2, 2012 #2


    User Avatar
    Science Advisor

    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.
  4. Apr 2, 2012 #3


    User Avatar
    Gold Member

    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 one-to-one 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 one-to-one. Use the fact that [itex]g:X \rightarrow X[/itex] is one-to-one 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].
  5. Apr 3, 2012 #4
    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.

    From the definition of finite set,
    [itex]\exists f: S \stackrel{1-1}{\rightarrow} S[/itex] and [itex]f(S) = S[/itex].

    And from the infinite set definition,
    [itex]\exists g: T \stackrel{1-1}{\rightarrow} T[/itex] and [itex]g(T) \subset T[/itex].

    As K^2 mentioned, [itex]g(T) \subset T \subset S = f(S)[/itex].​

    I have a question for jgens:
    Can you elaborate a bit on what you said here? I'm having a bit of trouble following.
    (I rewrote what you said for the sets and functions to correspond to what I'm showing.)
    Last edited: Apr 3, 2012
  6. Apr 3, 2012 #5


    User Avatar
    Gold Member

    Let me know what you are having difficulty following and then I can tailor my feedback around that.
  7. Apr 3, 2012 #6
    "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 one-to-one."

    What about the first sentence makes f one-to-one?

    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.

    Attached Files:

  8. Apr 3, 2012 #7


    User Avatar
    Gold Member

    Just apply the definition of one-to-one directly. The argument is almost trivial.

    Just use the definition of [itex]f(S)[/itex]. I would elaborate more, but I am not convinced you have even tried showing that the function I defined is one-to-one or that the equality above holds. If you have, then you need to show your work and where you have gotten caught up, and at that point I can help you.

    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.
  9. Apr 3, 2012 #8
    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 one-to-one 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 one-to-one 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]."
  10. Apr 3, 2012 #9


    User Avatar
    Gold Member

    Yep. The proof I suggested is specifically tailored around that definition.
  11. Apr 3, 2012 #10
    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
    Edit: The only proofs I've presented that I fully understood have been from naive set theory, so this is pretty difficult for me to grasp.
  12. Apr 3, 2012 #11


    User Avatar
    Gold Member

    We are using [itex]g[/itex] to define [itex]f[/itex] so that is the connection between them. If you are asking why did I choose that [itex]f[/itex], then the answer to that is I wanted to extend the one-to-one function on [itex]T[/itex] to a one-to-one function on [itex]S[/itex]. Otherwise I am not really sure what you are confused about here. Surely you have defined a function before, no?

    We are still working within the confines of naive set theory. You will notice that none of the definitions for [itex]f[/itex] of [itex]g[/itex] involved any set theoretic axioms.
  13. Apr 3, 2012 #12
    I don't think I have defined a function, no. I have definitely heard the phrase being thrown around but I never heard explicitly what it meant. I understand what a function is in an algebraic context, but not in the sense that it is a type of relation between two sets. If I ever have defined one, then I wouldn't be able to tell you because I probably did it unknowingly.
  14. Apr 3, 2012 #13


    User Avatar
    Gold Member

    Well you will have to define a function for either the proof by contradiction or the direct proof, so I guess that it's good to learn now. Do you know what the definition of a function is?

    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.
  15. Apr 3, 2012 #14
    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).
  16. Apr 3, 2012 #15


    User Avatar
    Gold Member

    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 one-to-one 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].
    Last edited: Apr 3, 2012
  17. Apr 3, 2012 #16


    User Avatar
    Science Advisor

    Your example is correct, but your definition seems confusing.
  18. Apr 3, 2012 #17
    Okay, I think I'm starting to get it now.
    Writing out exactly what the function from S\T to S\T was really helped. I'll refer to it as h.

    Assume [itex]g: T \stackrel{1-1}{\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 one-to-one 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 1-1.
    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
    (ii) For all [itex]x \in X, F(x)[/itex] is a singleton subset of [itex]Y[/itex], i.e. a set containing a single element.​

    - - - - - - - - -
    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?
    Last edited: Apr 3, 2012
  19. Apr 8, 2012 #18
    After presenting this step, I was told that my conclusion isn't solid enough. What could I be missing?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook