Logic: Find a sentence that satisfies certain properties

109 Views Asked by At

1) Let $L=\{R\}$ be a language with $R$ a binary function symbol. Find a sentence $\phi$ which is true in $N_2 = (\mathbb{N}^*, |)$, where $|$ is the divisibility relation, but false in $(P_{fin}(\mathbb{N}), \subseteq)$, where $P_{fin}(\mathbb{N})$ is the set of (possibly empty) finite subsets of $\mathbb{N}$, and $\mathbb{N}^*$ is the set of non-zero natural numbers.

Attempt at the solution: I tried many combinations of $\forall x\exists y$ but I just couldn't get a solution... Could someone please give me a hint?

2) Let $L = \{<\}$. Find a sentence $\phi$ which is true in $(\mathbb{Q}, <)$ but false in $(\mathbb{Z},<)$.

Attempt at the solution: I think what makes $\mathbb{Q}$ different from $\mathbb{Z}$ is that the former is a set of fractions. So we should focus on this property. However, I can't assume something like x/y, because we are not given any binary function symbol to consider division...

1

There are 1 best solutions below

5
On

The second one is answered in a comment. Let me do the first one.

I am assuming that your first order logic has equality; if it does not, define $x = y$ as a shorthand for $xRy \land yRx$. (Note that in both your structures, this is the same as equality.)

Define $$ \phi = \forall x \exists y \exists z((yRx \land zRx \land y \neq z \land x \neq y \land x \neq z ) \to \exists w(wRx \land w \neq y \land w \neq z \land w \neq x)). $$ That is, for each $x$, if there are $y,z$ in the $R$-relation to $x$, and these three are all distinct, then there is a fourth (distinct) $w$ which is also in the $R$-relation $x$. This sentence is false in the divisibility structure: $4$ only has $2$ and $1$ strictly dividing it. However, it is true in the subset structure: if $w$ has two distinct strict subsets, it has at least two elements $a,b$; hence it has at least three distinct strict subsets, namely $\{a\},\{b\},\emptyset$.