3

I know that to some extent this question may be insignificant, but I'm a little bit uncomfortable with the vacuous implication in this situation.

We know that two lists are equal iff they have the same length and the same elements in the same order. And we know that two empty lists are equal.

So how could we formally prove that two empty lists have the same elements in the same order?

(I think somehow vacuous implication could prove it, but I'm a little bit confused about how to construct the implication since we need to account for the order and the multiplicity of the elements in a list)

J-A-S
  • 621
  • I ran out of time for an edit , hence I rewrite the comment : "Order" does not make sense here since there are no elements, and both lists have the same number of elements , namely $0$. The conditions for A in the implication $A\implies B$ are not met (we cannot speak of the "same order", if we would omit "in the same order", there would be no problem) , hence $A$ is false and therefore the implication true. Such vacous truth's lead to the Curry-paradox. – Peter Jul 10 '20 at 11:15
  • I just realize that even without the "order" we would run into a vacous truth because "the elements are the same" also does not make sense if there are none. – Peter Jul 10 '20 at 11:15
  • 1
    A list is a sequence (maybe finite) $(a_n)$ and $(a_n)=(b_n) \text { iff } a_n=b_n$, for every $n$. To say that a list $L$ is empty means to say that $a \notin L$ for every $a$, i.e. $L=\emptyset$. Thus, if $L$ and $L'$ are both empty, both are equal to the empty set. – Mauro ALLEGRANZA Jul 10 '20 at 11:31
  • @Peter: Seeing how $\varnothing$ is an ordinal, which is a list of length $0$, it seems to me that it makes perfect sense talking about "the order" and "elements of" an empty list. – Asaf Karagila Jul 10 '20 at 11:45
  • 1
    Similar to @Mauro ALLEGRANZA’s comment: You can define a list to be a set of sets of cardinality 2, each containing a set of cardinality 1 and a positive integer (assuming you don’t treat the integers as sets), e.g. $a = { {{a_1}, 1}, {{a_2}, 2 }, \ldots }$, where you would require that if some element contains a positive integer $n$, and there’s another positive integer $m<n$, then some element contains $m$. Now list equality is just set equality (no need to check order), and the empty list is the empty set. – Joe Jul 10 '20 at 12:50

2 Answers2

2

If two lists both have length $17$, how can we establish that they "have the same elements in the same order"? What does that phrase mean?

One possible way to say two lists $A$ and $B$ have the same elements is, for all $x$, $x$ is in $A$ if and only if $x$ is in $B.$

A possible way to say that the elements of $A$ and $B$ are in the same order, given that they have the same elements, is that for all $x$ and $y$, $x$ and $y$ are in $A$ and $x$ occurs before $y$ in $A$ if and only if $x$ and $y$ are in $B$ and $x$ occurs before $y$ in $B$.

If $A$ and $B$ are empty then for all $x$ and $y$, $x$ does not occur in $A$ and $x$ does not occur in $B$, hence both directions of the implication for "same elements" are vacuously true. Also, it is not true that $x$ and $y$ are in $A$ and also not true that $x$ and $y$ are in $B$, hence both directions of the implication for "same order" are vacuously true.

The ideas above seem to work if a list is an ordered set (with no repetition of elements) but not if repetition of elements is allowed. So you probably need something different. But it really depends on how you define a list in the first place.

A list of length $N$ might be defined a function from the first $N$ integers to the elements of the list. For example, suppose we say $A$ is a list if there exists a unique non-negative integer $N$ called the length of $A$, such that if $k$ is an integer, $1 \leq k \leq N,$ then the $k$th element of $A$ exists and may be called $A(k).$ Then $A$ and $B$ have the same elements in the same order if their lengths are the same number $N$ and if $A(k) = B(k)$ for every integer $k$ where $1\leq k\leq N.$ Can you see how this is satisfied vacuously if $N= 0$?

But a list $A$ might be defined inductively as follows: either $A$ is the empty list (containing no elements), or $A$ is the ordered pair $(a,A')$ where $a$ is the first element of $A$ and $A'$ is a list. That is, we make lists by inserting elements at the beginnings of existing lists, starting with the empty list.

Now the question is what it means for two such lists to have the same elements in the same order. We might define this inductively too, that is, $A$ and $B$ are equal if they are both empty or have equal first elements inserted in front of equal lists. But in that case there's no "proof" that empty lists are equal; we had to accept it by definition in order to support the definition of equality for non-empty lists.

The same problem occurs if we define lists recursively by appending elements to existing lists, that is, a list $A$ is either the empty list or $(A',a)$ where $A'$ is a list and $a$ is an element.

So the question that first has to be answered is, what's a list? Until that is answered with a mathematical definition, no proof is possible.

David K
  • 98,388
  • Thank you David, I think the quantifiers helps a lot :) May I further ask for just one more clarification: how would you modify your implications if my definition for two lists and to be the same requires repetitions of elements in the list to have meaning? [e.g. I require the list (1,2,3) and the list (1,2,2,3) to be two different object, that's what I meant by "multiplicity" matters] From your current statements, I can't see how repetitions in lists are being accounted... – J-A-S Jul 10 '20 at 12:23
  • What exactly does “occurs before” mean? What if $a = (1,1,2,2,2,1,1)$ and $b=(1,1,1,2,2,1,1)$. Do we have “1 occurs before 2” and “2 occurs before 1” in both lists? – Joe Jul 10 '20 at 12:27
  • yep, I think me and @Joe are asking more or less the same question here – J-A-S Jul 10 '20 at 12:36
  • @Joe Good point. In my answer as initially written, I did not provide any support for repetition of elements. Partly that's due to not actually having defined a list in the first place. – David K Jul 11 '20 at 00:09
1

Formally we need to take element from first list and show, that it is in second list in same order. But "take element from first list" is false sentence, so you can finish implication with any sentence, especially with "element is in second list in same order" and implication is true.

Same for reverse:

That all elements from first list are in second in same order is not enough to show lists equality. We need reverse, that all elements from second list are in first in same order. And analogical consideration gives this for second list in same way as for first one.

zkutch
  • 13,410
  • Good answer, but what do you mean with "same for reverse" ? – Peter Jul 10 '20 at 11:18
  • 1
    @Peter. Thanks. Added to answer. – zkutch Jul 10 '20 at 11:24
  • Exactly, since the other list is also emtpy , the implication is correct in both directions, a good point I did not point out in my above comments. (+1 , and suggestion for an accept) – Peter Jul 10 '20 at 11:29