Interpretation using First-order logic

377 Views Asked by At

The following formula: $$\forall x(\forall y (\forall z((x=y)\lor(y=z)\lor(z=y) )))$$ is interpreted as "there are at most two elements ". how can we write a formula for "there are exactly two elements"?

I have the idea that this is done as follows: we can find two elements that are different, but if we take more than two elements then the third is equal to one of the other two.

However, I don't have a very clear idea how to write this as a formula

2

There are 2 best solutions below

1
On

$$\exists x \exists y \big(x\neq y \land \forall z(z=x \lor z=y)\big)$$

3
On

Personally, I'd tackle this by using a variation on your sentence for "there are at most 2 elements" and then also requiring there to be at least 2. This gives exactly 2.

$$ \forall x(\exists y ((y\neq x) \land \forall z((y=z)\lor(x=z)))) $$

In English: For all $x$ there's a $y$ that is different to $x$ (at least two elements), and any third element is equal to one of the other two (at most two elements).