MHB Converting statements and logic

[strifex]

Hello! I'm just starting out on this logic train and I'm not sure I'm grasping it correctly. I took a statement and attempted to convert it into the symbols below.

∀x∈ℤ,∃y∈ℤ,(E(x)∧E(y)) → x = 2y

The original phrase is:

Any even integer is equal to twice some other event integer.

Which I translated to:

For all x in integers, and some y in integers, if x is even and y is even, then x is 2 times y.

Am I on the even on the right track? Any help would great.

 

[Evgeny.Makarov]

Hi, and welcome to the forum!

Any even integer is equal to twice some other event integer.

This statement is false (consider, e.g., 2), but that's OK because a statement does not need to be true to be convertible to a formula.

Note also that the precise syntax of formulas differs between different textbooks, so one may consider $$\forall x\in\mathbb{Z}\,A$$ fine, while another may require rewriting this as $$\forall x\,(x\in\mathbb{Z}\to A)$$ or something like $$\forall x\,(Z(x)\to A)$$. Also, there may be different rules of scope: some books say that the scope of quantifiers is as small as possible, so $\forall x\,A\to B$ is interpreted as $(\forall x\,A)\to B$ (in this case one has to write $\forall x\,(A\to B)$ to have the whole implication under $\forall$), while others make the scope as large as possible.

∀x∈ℤ,∃y∈ℤ,(E(x)∧E(y)) → x = 2y

This does not reflect the meaning of the original statement. This formula is true. Indeed, for every $x$ I can find a $y$ that is not even, for example, $y=1$. This would make $E(y)$ and $E(x)\land E(y)$ false and the implication $E(x)\land E(y)\to x=2y$ true regardless of the value of $x=2y$.

There is the following rule of thumb. If one has a restriction like "$x$ is even" after a quantifier (i.e., "for all even $x$" or "there exists an even $x$"), then one separates this restriction from the rest of the formula with $\to$ after the universal quantifier and with $\land$ after the existential quantifier. That is, $\forall x\,(E(x)\to\dots)$ and $\exists x\,(E(x)\land\dots)$.

 

[strifex]

Hi, and welcome to the forum!

This statement is false (consider, e.g., 2), but that's OK because a statement does not need to be true to be convertible to a formula.

Note also that the precise syntax of formulas differs between different textbooks, so one may consider $$\forall x\in\mathbb{Z}\,A$$ fine, while another may require rewriting this as $$\forall x\,(x\in\mathbb{Z}\to A)$$ or something like $$\forall x\,(Z(x)\to A)$$. Also, there may be different rules of scope: some books say that the scope of quantifiers is as small as possible, so $\forall x\,A\to B$ is interpreted as $(\forall x\,A)\to B$ (in this case one has to write $\forall x\,(A\to B)$ to have the whole implication under $\forall$), while others make the scope as large as possible.

This does not reflect the meaning of the original statement. This formula is true. Indeed, for every $x$ I can find a $y$ that is not even, for example, $y=1$. This would make $E(y)$ and $E(x)\land E(y)$ false and the implication $E(x)\land E(y)\to x=2y$ true regardless of the value of $x=2y$.

There is the following rule of thumb. If one has a restriction like "$x$ is even" after a quantifier (i.e., "for all even $x$" or "there exists an even $x$"), then one separates this restriction from the rest of the formula with $\to$ after the universal quantifier and with $\land$ after the existential quantifier. That is, $\forall x\,(E(x)\to\dots)$ and $\exists x\,(E(x)\land\dots)$.

Thank you for taking the time to help me! I'm still a bit confused though. The original statement states that x is an EVEN integer and y is another EVEN integer, but your examples use y =1. If you put set y to 1, then it the first part of my formula is false. I set E(x) = x is even. So for the first half to be true, both x and y must be even.

 

[Evgeny.Makarov]

The original statement states that x is an EVEN integer and y is another EVEN integer, but your examples use y =1.

I am talking about your formula rather than the original statement, and yes, I am taking $y=1$.

If you put set y to 1, then it the first part of my formula is false.

Yes.

If you have a vessel filled with water, the water does not need your permission to escape through some approved hole. If there is a hole, the water will escape. Similarly, a formula $\exists x\,A$ does not accept recommendations about $x$. If there is a single $x$ that makes $A$ true, then $\exists x\,A$ is true. Now, $y=1$ makes $E(x)\land E(y)$ false; therefore, it makes $E(x)\land E(y)\to x=2y$ true. Recall the truth table for $\to$, where 1 denotes truth and 0 falsehood.
\[
\begin{array}{c|c|c}
A&B&A\to B\\
\hline
0&0&1\\
\hline
0&1&1\\
\hline
1&0&0\\
\hline
1&1&1
\end{array}
\]
That's it: a single value of $y$ (regardless of $x$) makes $E(x)\land E(y)\to x=2y$ true; therefore, $\exists x\,(E(x)\land E(y)\to x=2y)$ is true for all $x$; therefore, $\forall x\exists y\,(E(x)\land E(y)\to x=2y)$ is true. (I don't put parentheses around $E(x)\land E(y)$ because usually one posits that conjunction binds stronger than implication.)

 

[strifex]

I am talking about your formula rather than the original statement, and yes, I am taking $y=1$.

Yes.

If you have a vessel filled with water, the water does not need your permission to escape through some approved hole. If there is a hole, the water will escape. Similarly, a formula $\exists x\,A$ does not accept recommendations about $x$. If there is a single $x$ that makes $A$ true, then $\exists x\,A$ is true. Now, $y=1$ makes $E(x)\land E(y)$ false; therefore, it makes $E(x)\land E(y)\to x=2y$ true. Recall the truth table for $\to$, where 1 denotes truth and 0 falsehood.
\[
\begin{array}{c|c|c}
A&B&A\to B\\
\hline
0&0&1\\
\hline
0&1&1\\
\hline
1&0&0\\
\hline
1&1&1
\end{array}
\]
That's it: a single value of $y$ (regardless of $x$) makes $E(x)\land E(y)\to x=2y$ true; therefore, $\exists x\,(E(x)\land E(y)\to x=2y)$ is true for all $x$; therefore, $\forall x\exists y\,(E(x)\land E(y)\to x=2y)$ is true. (I don't put parentheses around $E(x)\land E(y)$ because usually one posits that conjunction binds stronger than implication.)

I see. So I need to make it to where, for example, if x =2 and y = 1, the result would be false? Also, the notation you mention at the end your first comment was a bit confusing, can you please clarify?

 

[Evgeny.Makarov]

So I need to make it to where, for example, if x =2 and y = 1, the result would be false?

It's hard to answer your question because the result should be a formula that does not depend on $x$ and $y$; it should be either true or false. And it should convey the meaning of the original English phrase.

Also, the notation you mention at the end your first comment was a bit confusing, can you please clarify?

Could you describe what exactly is confusing? I used the same notations as you did: quantifiers, $E(x)$, $\land$ and $\to$. By ellipsis I denoted the remaining part of the formula. I meant that if you want to say "All even numbers satisfy a property $P$", then you write $\forall x\,(E(x)\to P(x))$, and if you want to say "There exists an even number that satisfies $P$", then you write $\exists x\,(E(x)\land P(x))$.

 

[strifex]

It's hard to answer your question because the result should be a formula that does not depend on $x$ and $y$; it should be either true or false. And it should convey the meaning of the original English phrase.

Could you describe what exactly is confusing? I used the same notations as you did: quantifiers, $E(x)$, $\land$ and $\to$. By ellipsis I denoted the remaining part of the formula. I meant that if you want to say "All even numbers satisfy a property $P$", then you write $\forall x\,(E(x)\to P(x))$, and if you want to say "There exists an even number that satisfies $P$", then you write $\exists x\,(E(x)\land P(x))$.

I was referring to the "is even" notation. So, I've seen some write it as such:

∀x∈ℤ, x is even,∀y∈ℤ, y is even, x = 2y.

But I'm still not clear how to write "is even" symbolically.

 

[Evgeny.Makarov]

But I'm still not clear how to write "is even" symbolically.

You can write "$x$ is even" as $\exists y\,x=2y$ if $x$ and $y$ range over integers. But I have not suggested any way to write "$x$ is even" in the previous posts. I followed your example in writing $E(x)$. Writing "$x$ is even" is a slightly different problem from writing the original statement.

It's best not to overquote and to leave only the relevant portion of the previous post.