x Turn on thread page Beta
 You are Here: Home >< Maths

Simplicity can't count watch

1. I really don't want to create a new thread but I really wouldn't want to take the other thread into a big tangent. Plus, I have alot of confusion with counting. The book is crappy on these chapters. Espically, the proofs.

Anyway, I'm finding it really hard to prove this lemma

If there exists an injection then .

Firstly, this seems increadibly obvious. However, that could be that I have been thinking about this of a week. So induction on n.

Base case

If n=1, consider the contraposition i.e. that m>n implies is not a injection. If n=1, then m>1. So that must mean that X has more then one element. So if you have two elements then , such that and , then its cleary obvious that , hence but which proves this is not an injection.

Assume n=k

is an injection therefore .

To show n=k+1.

(This is where I'm struggling the base case was really long, I think I should shorten it. But, its like lol what to do.)

It clear that k+1 is only making the cardinality of the set bigger.

I guess using the n=k, there are two cases that one element hits k+1 or that it doesn't. If it doesn't then, . By the induction hypothesis.

But if say an element of N_m is does go in k+1, using the box analogy then mathematics is incosistent and I'm doomed.

P.S. I hate this proof. I can't seem to do it. I might look in the book. But, I still don't understand the proof in the book. Although, now I understand what it says and its so obvious but so gay to prove. Damn you maths.
P.P.S. I don't know what to do. I never done an induction when its like
(n this)(n something). So I think that might be the problem. But, I think the other problem is its so obvious, espically the first bit when trying to show n=K+1, but its like what do you say.
2. What are the sets N_m and N_n?
3. (Original post by Drederick Tatum)
What are the sets N_m and N_n?
Sort of natural numbers for example if you have a set X={1,2,5}. Then you will have
and this counts it.

i.e. i(1)=1, i(2)=2, i(3)=5. So N_n and N_m, is just a sort of counting set. For example N_n is just the set {1,2,..,n} and N_m is just the set
{1,2,3,...,m}.

From the above you can say |X|=3 because
.
4. Ok. So you want to prove that if f:{1,...,m} to {1,...,n} is an injection, then m is no greater than n.

You may want to check the stuff below because i'll just write down the stuff as I think of it.

Suppose m>n. We have that {f(1),...,f(m)} is a subset of {1,...,n}. So there are at most n elements in {f(1),...,f(m)}. So there are less than m elements in {f(1),...,f(m)} (since we have assumed m>n). So f(i)=f(j) for some i not equal to j. Contradiction since f is injective.
5. (Original post by Drederick Tatum)
Ok. So you want to prove that if f:{1,...,m} to {1,...,n} is an injection, then m is no greater than n.

You may want to check the stuff below because i'll just write down the stuff as I think of it.

Suppose m>n. We have that {f(1),...,f(m)} is a subset of {1,...,n}. So there are at most n elements in {f(1),...,f(m)}. So there are less than m elements in {f(1),...,f(m)} (since we have assumed m>n). So f(i)=f(j) for some i not equal to j. Contradiction since f is injective
That proof seems correct. Yeah, that makes sense. I wonder why the book doesn't give the proof like that but instead does induction.
6. Yeah, that proof looks fine. I'm not sure why your book does everything by induction.
7. I think the proof is wrong or not rigorist. Basically, its a and so on proof. But, in reality its a unformal proof that uses a look it goes like this. So yeah, I think the only way to prove it is by induction.

I can't be bothered to post the proof but I know how to do it now. I think the problem was I was under the wrong impression that if you had a composite function say then g is a bijection and f is a bijection. However, I learnt that this doesn't have to be the case. All you need is the codomain of g to be the domain of f.

Its weird as the whole box ball analogy breaks down. Or you get a ball that isn't put in the domain of f but goes to the codomain of f.

P.S. That took ages to understand the proof. But, atleast I know it now instead of learning it later.
8. I'm not sold by the proof. When we're working this low-level, it is important to specify which axioms we are working with, and what has been proven so far. Stating "less than m elements" and "at most n elements" might not be 'well defined' yet.

Here is an alternative proof which handles this:

Definition: (Construction of the natural numbers) We construct the natural numbers using the following construction: , (Using this definition, )

Definition: (Order on the natural numbers) We say if

We can prove this is a total ordering reasonably easily from our definitions.

Claim: If there exists an injection then .

We will prove the contrapositive:

If , then there cannot exist an injection

Proof:

We will proceed by contradiction. Suppose such a existed. Since . Consider which is an injection from n to n. However, injections from a finite set are bijections*. Therefore, every element in n is reached.

Now consider , by construction, but such that , so there exists , but , since . But is injective. Contradiction.

* I haven't seen a proof of this without well ordering.

(Transfinite)Induction is a powerful tool in set theory, which is probably why it is championed by the book. I wouldn't be suprised if this statement couldn't be proven without the well ordering principle.

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: July 26, 2009
Today on TSR

My friend is really wealthy

...and I'm jealous

Poll
Useful resources

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

How to use LaTex

Writing equations the easy way

Study habits of A* students

Top tips from students who have already aced their exams

Chat with other maths applicants