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.
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 .
Now observe that the binomium of Newton gives
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....
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, ,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) : .
2) : .
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.
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 for every object X in the category of Sets.
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!
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 : .
Now to avoid a proper proof we can say :
Since is false ,the conditional 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