Thread: Quantifiers and the general solution of the recurrence relation

Please help me with these 2 problems

1)
a) Express the statement "Every negative number has another negative number greater than it" using quantifiers.
b) Express the negation with no negation symbols in front of quantifiers, and then state the negation in words.
c) Is the statement true for the integers? For the rationals?

so I for part a) i did ∀x∃y[( x< 0 Y <0) --> x < y ) , the statement is false because if x = -1 , there is no negative number greater than -1

i'm not sure how to do the negation , but i'm sure that the negation statement is true for the integers, not sure for the rationals.

2) Find the general solution of the recurrence relation a₁ = 1 , a₂ = 2, a_n = 7a_n-1 - 10 a_n-2 + 3ⁿ + 8
I got a_n = (-2) (2)ⁿ + (17/10) (5)ⁿ -(9/2) 3ⁿ +2, but i think i got the coefficient (-2) and (17/10) are wrong.

Originally Posted by Tiome

so I for part a) i did ∀x∃y[( x< 0 ∧ Y <0) --> x < y ), the statement is false because if x = -1 , there is no negative number greater than -1

I agree that the original statement is false for the integers. However, the formula you wrote is true for the integers! Indeed, given any x, take y = 1. Then the premise of (x < 0 ∧ y < 0) -> x < y is false, so the whole statement is true.

It helps to think in terms of proof of formulas. What should a proof of the statement "Every negative number has another negative number greater than it" do? Given any x together with an evidence that x is negative, it must produce some y and two pieces of evidence: that y is negative and that x < y. Note that producing the evidence that y < 0 is the proof's responsibility; it is not given to it for free in the same way as the evidence that x < 0 is given. In general, a proof of ∀x P(x) is given x while a proof of ∃x P(x) has to produce x. Similarly, a proof of P -> Q is given an evidence for P and it has to produce an evidence for Q. For this problem, this means that y < 0 should be on the right-hand side of the implication: ∀x∃y[x < 0 -> (y < 0 ∧ x < y)]. In fact, I prefer ∀x[x < 0 -> ∃y(y < 0 ∧ x < y)] because here the proof can use the evidence that x < 0 to help it come up with y.

Constructing negation is very simple. First, you put ¬ in front of the whole formula. The problem says to move ¬ inside the quantifiers, which you can do using the following equivalences:

¬∀x P(x) <=> ∃x ¬P(x)
¬∃x P(x) <=> ∀x ¬P(x)

If you'd like, you can move ¬ further inside using

¬(P -> Q) <=> P ∧ ¬Q
¬(P ∧ Q) <=> ¬P ∨ ¬Q
¬(P ∨ Q) <=> ¬P ∧ ¬Q
¬¬P <=> P

Originally Posted by Tiome

c) Is the statement true for the integers? For the rationals?

The original statement is true on rationals because for each positive rational x there exists a smaller positive rational, e.g., x/2.

Thank you , it helped a lot

Originally Posted by Tiome

Please help me with these 2 problems

1)
a) Express the statement "Every negative number has another negative number greater than it" using quantifiers.
b) Express the negation with no negation symbols in front of quantifiers, and then state the negation in words.
c) Is the statement true for the integers? For the rationals?

so I for part a) i did ∀x∃y[( x< 0 Y <0) --> x < y ) , the statement is false because if x = -1 , there is no negative number greater than -1

Your original statement was "Every negative number has another negative number greater than it". There is nothing in that about integers. If x=-1 then y= -1/2 is a negative number larger than x. For any negative number x, x/2 is a negative number larger than x.

[quote i'm not sure how to do the negation , but i'm sure that the negation statement is true for the integers, not sure for the rationals.[/quote]
The negation of the statement is "There exist a negative number having no negative number larger than it". Yes, the negation is true for integers because the original statement was false for integers. Because the original statement was true for rational numbers, the negation is false for rational numbers.

2) Find the general solution of the recurrence relation a₁ = 1 , a₂ = 2, a_n = 7a_n-1 - 10 a_n-2 + 3ⁿ + 8
I got a_n = (-2) (2)ⁿ + (17/10) (5)ⁿ -(9/2) 3ⁿ +2, but i think i got the coefficient (-2) and (17/10) are wrong.
[/QUOTE]