Number of functions from one set to another

  • Thread starter Thread starter parelem
  • Start date Start date
  • Tags Tags
    Functions Set
Click For Summary
The number of functions from the set {1,...,n} to the set {0,1} is calculated by recognizing that each element in the first set can be mapped to either 0 or 1. This results in two choices for each of the n elements, leading to a total of 2^n possible functions. A formal proof can be constructed using the principle of multiplication, where each mapping decision is independent. The discussion also highlights uncertainty about the level of formality required for the proof. Ultimately, the conclusion is that there are 2^n functions from {1,...,n} to {0,1}.
parelem
Messages
1
Reaction score
0

Homework Statement


How many functions are there from {1,...,n} to {0,1}? and prove.


The Attempt at a Solution


For any k in {1,...,n} we can map k to either 0 or 1. So for any k there are two possible images. Since there are n kinds of k (from 1 to n) then there are 2^n possible functions


I'm not sure how to formally prove this, or what kind of proof to use at least.
 
Physics news on Phys.org
I would call that a proof. How formal do you want to be?
 

Thread 'Distance between a Clock's hands when the distance is increasing most rapidly'

Question: A clock's minute hand has length 4 and its hour hand has length 3. What is the distance between the tips at the moment when it is increasing most rapidly?(Putnam Exam Question) Answer: Making assumption that both the hands moves at constant angular velocities, the answer is ## \sqrt{7} .## But don't you think this assumption is somewhat doubtful and wrong?
View full post »

Similar threads

How should I show the following by using the signum function?
  • · Replies 14 ·
Replies
14
Views
2K
Prove every subset of countable set is either finite or else countable
  • · Replies 1 ·
Replies
1
Views
2K
Find the number of possible functions from one set to another
  • · Replies 2 ·
Replies
2
Views
1K
Finding the nth roots of a complex number
  • · Replies 22 ·
Replies
22
Views
867
Proving piecewise function is k-differentiable
  • · Replies 5 ·
Replies
5
Views
2K
Monotonic sequence definition of Continuity of a function
  • · Replies 13 ·
Replies
13
Views
2K
Prove that ##\lim\limits_{x \to \infty} f(x) = 0##
  • · Replies 3 ·
Replies
3
Views
877
Prove if ##a\cdot c = b \cdot c## then ##a = b## using Peano postulates
  • · Replies 2 ·
Replies
2
Views
1K
Can the summation formula be proven by counting a set in two ways?
  • · Replies 17 ·
Replies
17
Views
2K
Proving convergence of rational sequence
  • · Replies 2 ·
Replies
2
Views
2K