Results 1 to 7 of 7

Math Help - Discrete Math - Last Problem. Need Help!

  1. #1
    Member
    Joined
    Jan 2009
    Posts
    93

    Discrete Math - Last Problem. Need Help!

    Q: Prove the proposition P(1) , where P(a) is the proposition If n is a positive integer, then n ≥ n. What kind of proof did you use?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    P(a) is the proposition If n is a positive integer, then n ≥ n.
    If it's a and not n, for all a , P(a) is a tautology and then P(1) is true. (Let n be a positive integer, ( n=n \wedge n\geq 1 )\Rightarrow n^2=n\times n\geq 1\times n=n

    If it's n and not a , 1 is a positive integer and 1^2=1\geq 1 , therefore P(1) is true.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jan 2009
    Posts
    93
    Quote Originally Posted by clic-clac View Post
    If it's a and not n, for all a , P(a) is a tautology and then P(1) is true. (Let n be a positive integer, ( n=n \wedge n\geq 1 )\Rightarrow n^2=n\times n\geq 1\times n=n

    If it's n and not a , 1 is a positive integer and 1^2=1\geq 1 , therefore P(1) is true.
    thanks click-clac for helping me with this. As I go over what you wrote, I am still having difficulty understanding this.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Mhh ok no problem
    First I wanted to know :
    where P(a) is the proposition If n is a positive integer, then n ≥ n.
    Is it P(a) or P(n)?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jan 2009
    Posts
    93
    Quote Originally Posted by clic-clac View Post
    Mhh ok no problem
    First I wanted to know :
    Is it P(a) or P(n)?
    it is P(n). My bad. I accidentily looked at the question below it also. That is where P(a) came from.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Ok! I'll write \mathbb{N}^* instead of \mathbb{N}-\{0\}.

    We have P(n):\ n\in\mathbb{N}^*\Rightarrow n^2\geq n
    Thus P(1):\ 1\in \mathbb{N}^*\Rightarrow 1^2\geq 1

    Consider the formula F:\ A\Rightarrow B, if A is false or if B is true, then F is true.
    1^2\geq 1 is true, therefore the implication 1\in \mathbb{N}^*\Rightarrow 1^2\geq 1 is true: we've proved P(1).

    ***********

    Another way to prove P(1) (and even more) is to say that the proposition P(x) is a tautology (i.e. is always true). Indeed:
    \circ If x isn't a positive integer, then x\in\mathbb{N}^* is false and the implication x\in\mathbb{N}^*\Rightarrow x^2\geq x is true: P(x) is true.
    \circ If x is a positive integer, (x\geq x\ \text{and}\ x\geq 1)\Rightarrow x\times x\geq x\times 1\Rightarrow x^2\geq x because the multiplication on \mathbb{N} is compatible with the order. So the second part of the implication is true, and again P(x) is true.

    In conclusion, whatever is x (a number, a matrix, a topological space...), P(x) is true. In particular, P(1) is true.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jan 2009
    Posts
    93
    Quote Originally Posted by clic-clac View Post
    Ok! I'll write \mathbb{N}^* instead of \mathbb{N}-\{0\}.

    We have P(n):\ n\in\mathbb{N}^*\Rightarrow n^2\geq n
    Thus P(1):\ 1\in \mathbb{N}^*\Rightarrow 1^2\geq 1

    Consider the formula F:\ A\Rightarrow B, if A is false or if B is true, then F is true.
    1^2\geq 1 is true, therefore the implication 1\in \mathbb{N}^*\Rightarrow 1^2\geq 1 is true: we've proved P(1).

    ***********

    Another way to prove P(1) (and even more) is to say that the proposition P(x) is a tautology (i.e. is always true). Indeed:
    \circ If x isn't a positive integer, then x\in\mathbb{N}^* is false and the implication x\in\mathbb{N}^*\Rightarrow x^2\geq x is true: P(x) is true.
    \circ If x is a positive integer, (x\geq x\ \text{and}\ x\geq 1)\Rightarrow x\times x\geq x\times 1\Rightarrow x^2\geq x because the multiplication on \mathbb{N} is compatible with the order. So the second part of the implication is true, and again P(x) is true.

    In conclusion, whatever is x (a number, a matrix, a topological space...), P(x) is true. In particular, P(1) is true.
    I see now. Thanks clic-clac
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Need Help on a hard problem on discrete math.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 19th 2011, 03:17 PM
  2. Discrete Math Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 17th 2010, 11:29 PM
  3. Discrete Math Problem! HELP!!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 30th 2008, 10:48 AM
  4. Discrete Math Problem - Relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 27th 2007, 08:08 PM
  5. Discrete Math problem
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: February 15th 2007, 01:57 PM

Search Tags


/mathhelpforum @mathhelpforum