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.

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...

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.

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

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?

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)].

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?

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

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

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?

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

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.

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

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

Re: Writing propositions using connectives and quantifiers

Would I need to define Q at all?