Results 1 to 3 of 3

Math Help - theorem about finite sets

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    theorem about finite sets

    Hi

    I have to prove the following theorem

    Prove that if n\in\mathbb{N} and A\subseteq I_n then A is finite
    and |A|\le n.

    here I_n=\{i\in\mathbb{Z^+}\lvert\; i\le n\}

    Let me write this in logical form

    \forall n\in\mathbb{N}\;\underbrace{\forall A[(A\subseteq I_n)\Rightarrow(A\mbox{ is finite } \wedge |A|\le n)]}_\text{P(n)}

    I am going to prove this by induction.

    Let

    P(n) : \forall A[(A\subseteq I_n)\Rightarrow(A\mbox{ is finite } \wedge |A|\le n)]

    So we need to prove,

    \forall n\in\mathbb{N}\;P(n)

    Base case : n=0

    let A be arbitrary. Suppose A\subseteq I_0.
    \because I_0=\varnothing\;\therefore A=\varnothing

    So A is finite since A\sim I_0\;\Rightarrow |\varnothing|=0

    \therefore |A|\le 0\;\Rightarrow P(0)

    Induction case: Let n\ge 0 be arbitrary. Suppose P(n). Now let A be arbitrary
    and suppose A\subseteq I_{n+1}. Now there would be two special cases.

    Special Case 1: (n+1)\in A


    Now define

    C=\{n+1\}\mbox{ and } D=A\setminus C

    since C has a single element , or since C\sim I_1, C is finite and
    \lvert C\rvert=1

    \because A\subseteq I_{n+1}\;\therefore D\subseteq I_n

    Using inductive hypothesis, D is finite and \lvert D\rvert \le n

    Now I am going to use the following theorem, which is proved in the Velleman's book

    Theorem: Suppose A and B are disjoint finite sets. Then A\cup B is finite
    and \lvert A\cup B \rvert=\lvert A\rvert+\lvert B\rvert


    \because C\cap D=\varnothing , they are disjoint finite sets , so
    A=C\cup D is finite and |A|=|C|+|D| \le \; n+1

    |A|\le \; n+1

    since A is arbitraty it proves P(n+1)

    Special Case 2: (n+1)\notin A

    Let x\in A be arbitrary. x\in I_{n+1}

    \because (n+1)\notin A\;\therefore x\neq (n+1)

    \therefore x\in I_n

    since x is arbitrary, A\subseteq I_n. By inductive hypothesis,
    A is finite and |A|\le n < (n+1)

    \therefore |A|\le (n+1)

    Since A is arbitrary it proves P(n+1). So by principle of induction,

    \forall n\in\mathbb{N}\;P(n)

    Is the proof correct ?

    Thanks

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: theorem about finite sets

    The proof is correct but may not be appropriate for all audiences. To begin with, the statement that a subset of {1, ..., n} has size <= n is completely obvious to most people and needs a proof only in certain circumstances, e.g., when you are working with specific axioms or when you want to explain the proof to a computer using a proof assistant. The amount of details in the proof is also overwhelming for human audience, in particular, for the fact that A\subseteq I_{n+1} and n+1\notin A imply A\subseteq I_n. Next time, if your statement is too obvious or if your proof has too many or too little details, why don't you explain your reasons in the beginning?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: theorem about finite sets

    makarov,

    ok. I forgot to mention that I am doing this problem from Velleman's "How to prove it"
    .So I am expected to be as rigorous as possible. Thanks for the input.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finite SETS
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: February 8th 2010, 07:04 AM
  2. cardinality of finite sets
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: January 6th 2010, 07:47 PM
  3. finite sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: November 9th 2009, 06:07 PM
  4. [SOLVED] finite sets
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 8th 2009, 01:06 PM
  5. Proof: finite sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 26th 2009, 10:01 PM

/mathhelpforum @mathhelpforum