Discrete Math - Last Problem. Need Help!

**Grillakis** · January 28th 2009, 07:17 PM

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?

**clic-clac** · January 29th 2009, 02:14 AM

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.

**Grillakis** · January 30th 2009, 06:05 PM

Originally Posted by clic-clac

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.

**clic-clac** · January 31st 2009, 01:58 AM

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)?

**Grillakis** · January 31st 2009, 08:32 AM

Originally Posted by clic-clac

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.

**clic-clac** · January 31st 2009, 09:36 AM

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.

**Grillakis** · January 31st 2009, 10:03 AM

Originally Posted by clic-clac

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

Thread: Discrete Math - Last Problem. Need Help!

LinkBack

Thread Tools

Display

Discrete Math - Last Problem. Need Help!

Similar Math Help Forum Discussions

Need Help on a hard problem on discrete math.

Discrete Math Problem

Discrete Math Problem! HELP!!

Discrete Math Problem - Relation

Discrete Math problem

Search Tags