Logic formula translation

Question

I'm translating logic formulas into English and I've come across the following logic L-formula:

$ \forall i \forall j \forall k: (\mathrm{in}(i,xs) \land \mathrm{in}(j,xs) \land \mathrm{in}(k,xs) \Rightarrow i = j \lor j = k \lor i = k)$

With the $\mathrm{in}(x,xs)$ predicate meaning $x$ is in $xs$.

To which I have translated as "At least two elements are the same" but I can't be sure whether this is correct or not. My thinking is that if one of them satisfies then right hand side then the whole statement is true but as this is an implication the left hand side can be false for the whole formula to be true.

I think an example of a list with four elements that satisfies this would be something like

$[1,1,2,3]$

And a list of elements that violates this would be

$[1,2,3,4]$

The discourse is the set of natural numbers.

I am pretty sure I have translated this incorrectly. Does the right hand side of the implication mean that at least two elements are the same? I am quite unsure about this.

Answer 1

The actual translation of the formula is

For all triplets of elements $(i,j,k)$, if all three elements lie in $xs$, then at least one pair of them is equal.

In other words, there cannot be three different elements all present in $xs$.

So, if $xs = [1,2,3]$, then the statement is false, since I can set $i=1,j=2,k=3$ and the implication falls:

• $\mathrm{in}(i, xs)$ is obviously true, and so is $\mathrm{in}(j,xs)$ and $\mathrm{in}(k,xs)$.
• $i=j$ is not true, $i=k$ is not true, and $j=k$ is not true.

Answer 2

Your example with $[1,1,2,3]$ looks like you're misunderstanding something about how quantifiers and variables work.

You don't need to have more than a single $1$ present in the list in order for two of the variables both to be $1$. The three variables get values independently of each other, and the same value can be bound to more than one variable at the same time, without any special permission.

So when your formula is of the form $\forall i \forall j \forall k : \varphi$ it claims (perhaps correctly, perhaps not) that $\varphi$ is true when $i=j=k=1$ and when $i=1, j=2, k=3$ and when $i=18, j=42, k=18$ and so forth -- every way to assign some number to each of the variables must lead to $\varphi$ being true, and this is independent of which values are in your list.

Perhaps you're thinking of a variable as a little box named "k" that you can put a value into. That picture is slightly misleading because it can give the impression that putting the value into the box named "k" will prevent you from putting that value into the box named "j" too. It might be better to think of a variable as a post-it label that you stick onto the value saying "this value is now what I mean when I say k" -- and there's nothing wrong with sticking several of these labels to the same number.