Results 1 to 8 of 8

Math Help - Basic Set Theory Question

  1. #1
    Newbie
    Joined
    Dec 2009
    Posts
    8

    Basic Set Theory Question

    1. How many subsets are there of the set {1,2,3,...,n}? How many maps of this set into itself? How many maps of this set onto itself?

    2. How many functions are there from a nonempty set, S, into the null set? How many functions are there from the null set into an arbitrary set, S?

    To anyone helping me with the above two questions, thank you! I am studying analysis on my own, so any help is certainly appreciated! Those two questions came out of "Introduction to Analysis" by Rosenlicht.

    Also, if you have any suggestions that might be more suitable for self study, I'd be very thankful. I don't have any solutions in the back of this text! Haha.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,649
    Thanks
    1597
    Awards
    1
    Quote Originally Posted by AdvoTV View Post
    1. How many subsets are there of the set {1,2,3,...,n}? How many maps of this set into itself? How many maps of this set onto itself?
    2. How many functions are there from a nonempty set, S, into the null set? How many functions are there from the null set into an arbitrary set, S?

    To anyone helping me with the above two questions, thank you! I am studying analysis on my own, so any help is certainly appreciated! Those two questions came out of "Introduction to Analysis" by Rosenlicht.
    Also, if you have any suggestions that might be more suitable for self study, I'd be very thankful. I don't have any solutions in the back of this text!
    If you have to ask about these two questions, then I do not think you have the grounding necesssary to selfstudy analysis.
    I would suggest that you start with a lower level testbook, say a discrete mathematics which includes chapters on set theory.
    Last edited by Plato; December 21st 2009 at 12:59 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    I agree with Plato. Although I can still give you some help:

    1. Let p denote the amount subsets of {,1,..., n}. Then observe that p= \sum_{k=0}^n{n \choose k}.

    Now observe that the binomium of Newton gives  2^{n} = (1+1)^n = p

    I expect you to work out the details yourself.

    Observe that an injective map f has the whole set {1,...,n} as image. How many ways can we permutate this set?

    Observe that an onto map from f:{1,..,n}-->{1,..,n} is automatically injective....
    Last edited by Dinkydoe; December 22nd 2009 at 03:48 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Mar 2009
    Posts
    256
    Thanks
    1
    Quote Originally Posted by AdvoTV View Post
    1. How many subsets are there of the set {1,2,3,...,n}? How many maps of this set into itself? How many maps of this set onto itself?

    2. How many functions are there from a nonempty set, S, into the null set? How many functions are there from the null set into an arbitrary set, S?

    To anyone helping me with the above two questions, thank you! I am studying analysis on my own, so any help is certainly appreciated! Those two questions came out of "Introduction to Analysis" by Rosenlicht.

    Also, if you have any suggestions that might be more suitable for self study, I'd be very thankful. I don't have any solutions in the back of this text! Haha.
    Very interesting questions,particularly the 2nd one.
    The 1st one is trivial and can be found in many books.But the 2nd one is a bit tricky and is based on the following theorems:

    1) for all sets,  S\neq\emptyset ,then there does not exist a function from S to the empty set.

    2) for all sets ,S, the empty set is a function from the empty set to S

    Or in a more mathematical notation:

    1) \forall S: S\neq\emptyset\Longrightarrow\neg \exists f(f:S\rightarrow\emptyset).

    2) \forall S: \emptyset :\emptyset\rightarrow S.

    Now since those questions came out from your Analysis book and since most Analysis books offer basic set theory ,you should be able by looking carefully on your book set theory to tackle those problems.

    But the 2nd question i must admit is quite difficult.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    What do you mean by this?

    2) for all sets ,S, the empty set is a function from the empty set to S

    : .
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by AdvoTV View Post
    1. How many subsets are there of the set {1,2,3,...,n}? How many maps of this set into itself? How many maps of this set onto itself?

    2. How many functions are there from a nonempty set, S, into the null set? How many functions are there from the null set into an arbitrary set, S?

    To anyone helping me with the above two questions, thank you! I am studying analysis on my own, so any help is certainly appreciated! Those two questions came out of "Introduction to Analysis" by Rosenlicht.

    Also, if you have any suggestions that might be more suitable for self study, I'd be very thankful. I don't have any solutions in the back of this text! Haha.
    See my previous post (click here). This will answer Q2.

    In case you are interested in other perspective of an empty function, below is some additional stuff.
    ------
    Empty set can also be thought as an initial object in the category of Sets. That means, there exists a precisely one morphism \emptyset \rightarrow X for every object X in the category of Sets.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Dec 2009
    Posts
    8

    Thank You - to all.

    Thank you to all of you who have posted. Yes, I agree it would be beneficial to go to a discrete/combinatorial mathematics text and read through it prior to looking at analysis. Usually, I believe that is the case! I am going to make an attempt to tackle this intro analysis/advanced calculus text because the preface does clearly state that undergraduate calculus is the only prerequisite.

    I actually did figure out question one the way that it has been explained here (through the use of the binomial theorem), but I was curious if there was another way to actually prove that the power set of the set {1,2,3,...,n} is the solution. Perhaps there isn't. Perhaps I don't know enough to figure out a different way!

    The second problem that several of you made a post on - now I'm gonna have to go study my logic again... sigh. This is a labor of love. Thank you, and Merry Christmas!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Mar 2009
    Posts
    256
    Thanks
    1
    The "vaciously true" proof that the Wikipedia is showing is a Semantical proof.

    In mathematics all proofs are syntactical.

    For example in proving : The empty set is a subset of all sets ,A.

    We have to prove that for all,x : x\in\emptyset\Longrightarrow x\in A.

    Now to avoid a proper proof we can say :

    Since x\in\emptyset is false ,the conditional x\in\emptyset\Longrightarrow x\in A is always true.

    This is a semantical proof.

    So the two theorems above that i mentioned DO have a proper mathematical proof .

    A difficult one i must admit
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question on basic Ring theory
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 6th 2012, 01:00 AM
  2. Basic Field Theory Question
    Posted in the Advanced Algebra Forum
    Replies: 8
    Last Post: February 10th 2010, 10:16 PM
  3. Basic Set Theory Question
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 15th 2009, 09:57 PM
  4. Group Theory - Basic question on existence of sub-groups
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: August 15th 2009, 11:36 PM
  5. Basic Set theory question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 16th 2008, 06:02 PM

Search Tags


/mathhelpforum @mathhelpforum