Hey there! Sign in to join this conversationNew here? Join for free
x Turn on thread page Beta
    • Thread Starter
    Offline

    15
    ReputationRep:
    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 N_m \rightarrow N_n then m \leq n.

    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 N_m \rightarrow N_n 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 x_1,x_2 \in X, such that f:N_m \rightarrow X and g:N_n \rightarrow Y, then its cleary obvious that f(x_1)=y=f(x_2), hence f(x_1)=f(x_2) but x_1 \not = x_2 which proves this is not an injection.

    Assume n=k

    N_m \rightarrow N_k is an injection therefore m \leq k.

    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, m \leq k \leq k+1. 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) \Rightarrow(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.
    Offline

    12
    ReputationRep:
    What are the sets N_m and N_n?
    • Thread Starter
    Offline

    15
    ReputationRep:
    (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
    i:N_{3} \rightarrow X 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
    N_3 \rightarrow X.
    Offline

    12
    ReputationRep:
    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.
    • Thread Starter
    Offline

    15
    ReputationRep:
    (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.
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    Yeah, that proof looks fine. I'm not sure why your book does everything by induction.
    • Thread Starter
    Offline

    15
    ReputationRep:
    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 f(g(x)) 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.
    Offline

    16
    ReputationRep:
    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: 0 = \emptyset, n = \{0,1,2,\ldots,n-1\} (Using this definition, N_m = m)

    Definition: (Order on the natural numbers) We say m \ge n if n \subseteq m

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

    Claim: If there exists an injection N_m \rightarrow N_n then m \leq n.

    We will prove the contrapositive:

    If m>n, then there cannot exist an injection \phi: m \rightarrow n

    Proof:

    We will proceed by contradiction. Suppose such a \phi existed. Since m > n \Rightarrow m \supset n. Consider \phi(n) 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 x \in m-n, \phi(x) \in  n by construction, but \forall y \in n \exists t \in n such that \phi(t) = y, so there exists \phi(t) = \phi(x), but x \not= t, since x \in m-n, t \not \in m-n. But \phi 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.
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: July 26, 2009
Poll
Do you like carrot cake?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.