Translating set syntax in FOL

65 Views Asked by At

Even though the formal syntax rules for first order logic talk about $\forall x$ or $\exists x$ without necessarily including any kind of $\in Y$ part for some domain/set $Y$, sometimes we'll see things like $\forall x \in \mathbb{N}$ for example and I was unsure where that syntax "comes in" to FOL.

In a comment on another question I was told that:

$\forall x\in Y, P(x)$ is just convenient shorthand for $\forall x(x\in Y\to P(x))$

$\exists x\in Y, P(x)$ is just convenient shorthand for $\exists x(x\in Y\land P(x))$

However I don't understand how we determine whether we need the $\to$ symbol or the $\land$ symbol. In particular why isn't it $\land$ for both, or $\to$ for both, etc? How do we know which to use in which situation?

1

There are 1 best solutions below

2
On BEST ANSWER

Consider as domain of the interpretation the set of integers, and let the naturals defines as the non-negative integers.

We have that "Every natural numbers is non negative" will be : $∀n(\text {Nat}(n) → (n ≥ 0))$ or equivalently : $∀n(n ∈ \mathbb N → (n ≥ 0))$.

What happens with $\land$ instead of $\to$ ?

We have that : $∀n(\text {Nat}(n) \land (n ≥ 0))$ will be false, because e.g. $\text {Nat}(-1) \land (-1 ≥ 0)$ is false.

$\text {Nat}(-1) → (-1 ≥ 0)$ instead, is true.


Consider now "There is a negative natural number", that is obviously false.

It will be : $\exists n(\text {Nat}(n) \land (n \lt 0))$ or equivalently : $\exists n(n ∈ \mathbb N \land (n \lt 0))$.

What happens with $\to$ instead of $\land$ ?

We have that $\exists n(\text {Nat}(n) \to (n \lt 0))$ will be true, because $\text {Nat}(-1) \to (-1 \lt 0)$ is true.