# Writing propositions using connectives and quantifiers

Printable View

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Oct 20th 2013, 11:20 AM
MichaelH
Writing propositions using connectives and quantifiers
Hi guys,

I'm struggling to take on these questions where I am asked to write propositions using connectives and quantifiers:

Let P(x) be the statement that says that a real number x has some property P.

For every two real numbers
x and y with x<y, there is a real number with the property P between x and y.

I must also construct a negation for this problem. There is also a very similar question to this that I have to do but instead of using P(x) as the statement that says a real number x has some property P,
I must let P(n) be the statement that says that a natural number n has some property P then write the following statement using connectives and quantifiers:

Any sum m + n of natural numbers m and n which have the property P, has the property P.
• Oct 20th 2013, 12:08 PM
emakarov
Re: Writing propositions using connectives and quantifiers
Well, take a shot at these questions, and we'll give you feedback. Surely you suspect that the statement that starts with "For every two real numbers x and y..." is written as ∀x ∀y...
• Oct 20th 2013, 12:13 PM
MichaelH
Re: Writing propositions using connectives and quantifiers
Quote:

Originally Posted by emakarov
Well, take a shot at these questions, and we'll give you feedback. Surely you suspect that the statement that starts with "For every two real numbers x and y..." is written as ∀x ∀y...

Well I have started with:

(∀x ∈ R)(∀y ∈ R)(x < y)(∃(x<P(z)<y))

Although I just know this must be wrong.
• Oct 20th 2013, 12:25 PM
SlipEternal
Re: Writing propositions using connectives and quantifiers
Quote:

Originally Posted by MichaelH
Well I have started with:

(∀x ∈ R)(∀y ∈ R)(x < y)(∃(x<P(z)<y))

Although I just know this must be wrong.

Good start. You are missing something after the existence symbol. Right now, that reads: "For all real numbers x, for all real numbers y, x<y, there exists an inequality such that x<P(z)<y for some undefined z."

Try using a colon when you are restricting a quantifier. For example:

$\displaystyle (\forall x \in \mathbb{R})(\forall y \in \mathbb{R}: x<y)(\exists \ldots)$
• Oct 20th 2013, 12:30 PM
MichaelH
Re: Writing propositions using connectives and quantifiers
Quote:

Originally Posted by SlipEternal
Good start. You are missing something after the existence symbol.

Would I have to define z by stating that it is in R?
• Oct 20th 2013, 12:33 PM
SlipEternal
Re: Writing propositions using connectives and quantifiers
I updated my post above with some additional advice.

Quote:

Originally Posted by MichaelH
Would I have to define z by stating that it is in R?

Yes. Also, once you define z, it is not P(z) that lies between x and y. It is z that does. So, you need [x < z < y AND P(z)].
• Oct 20th 2013, 12:37 PM
MichaelH
Re: Writing propositions using connectives and quantifiers
Quote:

Originally Posted by SlipEternal
I updated my post above with some additional advice.

Yes. Also, once you define z, it is not P(z) that lies between x and y. It is z that does. So, you need [x < z < y AND P(z)].

Got you, thanks for that. For the second question, where would I even start?
• Oct 20th 2013, 12:44 PM
emakarov
Re: Writing propositions using connectives and quantifiers
I would encourage the OP to expand the abbreviation $\displaystyle (\forall y \in \mathbb{R}: x<y)$. This is not the basic formula syntax, and it is important to be able to write it in full.

Often people are not sure whether "For all x and y such that x < y, Q(x, y) holds" is rendered ∀x ∀y. x < y ∧ Q(x, y) or ∀x ∀y. x < y → Q(x, y). The first version is wrong because it is not claimed that x < y for all x and y (and also Q(x, y)). Another way to look at it, if someone chose x and y and it happened that x ≥ y, then nothing is claimed; Q(x, y) is only guaranteed when x < y. This resembles implication because implication is true when the hypothesis is false. Indeed, the correct formula is ∀x ∀y. x < y → Q(x, y).
• Oct 20th 2013, 12:45 PM
SlipEternal
Re: Writing propositions using connectives and quantifiers
Do you mean the negation? Or the similar question with natural numbers? For the similar question with natural numbers, here is a start...

$\displaystyle (\forall m \in \mathbb{N})(\forall n \in \mathbb{N})(P(m)\wedge P(n) \Rightarrow ...)$

(I updated this to take emakarov's advice into account. I have seen and used a colon to restrict qualifiers, so I was not aware it was not "basic". Then again, I have never actually checked to see what is considered basic syntax...)
• Oct 20th 2013, 12:54 PM
MichaelH
Re: Writing propositions using connectives and quantifiers
@emakarov where are you defining that x and y are real numbers?

And for the negation, do I just change all "for all" signs to "their exists" signs?
• Oct 20th 2013, 01:08 PM
SlipEternal
Re: Writing propositions using connectives and quantifiers
You change all "for all" signs to "there exists" signs, all "there exists" signs to "for all" signs, and negate any expressions based on those. So, let's negate emakarov's example: $\displaystyle (\forall x \in \mathbb{R})(\forall y \in \mathbb{R})(x < y \Rightarrow Q(x,y))$

It's negation would be: $\displaystyle (\exists x \in \mathbb{R})(\exists y \in \mathbb{R}) \neg (x<y \Rightarrow Q(x,y))$. So, how do you negate a conditional statement? The only time a conditional $\displaystyle A \Rightarrow B$ is false is when you have $\displaystyle A \wedge \neg B$. So, it would be $\displaystyle (\exists x \in \mathbb{R})(\exists y \in \mathbb{R})(x<y \wedge \neg Q(x,y))$
• Oct 20th 2013, 01:11 PM
emakarov
Re: Writing propositions using connectives and quantifiers
Quote:

Originally Posted by MichaelH
@emakarov where are you defining that x and y are real numbers?

You can add "∈ R" to "∀x" and other quantifiers.
• Oct 20th 2013, 01:39 PM
MichaelH
Re: Writing propositions using connectives and quantifiers
Quote:

Originally Posted by SlipEternal
You change all "for all" signs to "there exists" signs, all "there exists" signs to "for all" signs, and negate any expressions based on those. So, let's negate emakarov's example: $\displaystyle (\forall x \in \mathbb{R})(\forall y \in \mathbb{R})(x < y \Rightarrow Q(x,y))$

It's negation would be: $\displaystyle (\exists x \in \mathbb{R})(\exists y \in \mathbb{R}) \neg (x<y \Rightarrow Q(x,y))$. So, how do you negate a conditional statement? The only time a conditional $\displaystyle A \Rightarrow B$ is false is when you have $\displaystyle A \wedge \neg B$. So, it would be $\displaystyle (\exists x \in \mathbb{R})(\exists y \in \mathbb{R})(x<y \wedge \neg Q(x,y))$

I understand it now. Thank you guys. The only thing I don't understand is the use of "Q" - sorry if it is a silly question!

Then for the next question, could I write:

$\displaystyle (\forall m \in \mathbb{N})(\forall n \in \mathbb{N})(P(m)\wedge P(n) \Rightarrow P(m+n))$
• Oct 20th 2013, 01:44 PM
SlipEternal
Re: Writing propositions using connectives and quantifiers
Quote:

Originally Posted by MichaelH
I understand it now. Thank you guys. The only thing I don't understand is the use of "Q" - sorry if it is a silly question!

Q is some property. Given x and y, Q(x,y) is true if the property holds for the given x and y and it is false if the property does not hold. In other words, replace Q(x,y) with another expression that completes the problem. If x<y, then what should be true? Q(x,y) = "there is a real number between x and y with the property P"

Quote:

Originally Posted by MichaelH
Then for the next question, could I write:

$\displaystyle (\forall m \in \mathbb{N})(\forall n \in \mathbb{N})(P(m)\wedge P(n) \Rightarrow P(m+n))$

Looks good to me
• Oct 20th 2013, 01:52 PM
MichaelH
Re: Writing propositions using connectives and quantifiers
Would I need to define Q at all?
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last