How do I prove that the following argument is valid for any finite universe of discourse?

Question

I'd like to prove that the following argument is valid for any finite universe of discourse.

$$ \begin{aligned} 1.\ & ( \exists x )(\exists y) Gxy \\ 2.\ &(x) \lnot Gxx \\ 3.\ &(x)(y)(z)[(Gxy \land Gyz) \to Gxz] \\ \therefore 4.\ &(\exists x)(\exists y)[Gxy \land \lnot (\exists z)Gzx] \\ \end{aligned} $$

The argument is not quantificationaly valid, because there are interpretations on which 1-3 are true, but 4 is false.

For instance:

UD: Set of positive integers
Gxy: x is greater than y

Which gives us,

1. Some positive integer is greater than another positive integer
2. No positive integer is greater than itself.
3. For all positive integers x, y, and z, if x is greater than y and y is greater than z, then x is greater than z.

Therefore,

4. For some positive integer x and some positive integer y, x is greater than y and there is no positive integer z such that z is greater than x—some integer is the greatest positive integer.

1-3 are clearly true while 4 is false, so the argument is invalid on this interpretation.

If we change the interpretation so that Gxy = x is less than y, believe the argument is valid on this new interpretation.

Of course, it is also valid for some interpretations where the UD is finite.

For example:

UD: {Jack, Jill, Susan}
Gxy: x is taller than y

Or:

UD: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Gxy: x is greater than y

Intuitively, it seems to me that this argument will be valid for all interpretations where the UD is finite, but how do I demonstrate this mathematically?

Answer 1

Note that premises 2 and 3 would be true if and only if $G$ is irreflexive and transitive. That means that $G$ has to be a strict partial order.

Examples of partial orders would be just the kinds of things you indicate: greater than or smaller than on the integers, taller than on people, etc. However, note that those are all all total orders: for any two different objects, either one will be 'greater than' the other, or vice versa. This need not be true for a partial order. For example, the (strict) subset relationship on sets is a (strict) partial order: it is transitive and irreflexive ... but it is not always the case that for any two different sets, one is the subset of the other.

However, if you have a partial order, you can still 'line up' all the objects in such a way that any 'greater than' relation that does hold goes from 'left' to right'. Or, if you want to think about this graphically: if the objects are nodes, and any relationship $G$ between $a$ and $b$ is an arrow from node $a$ to $b$, then there are no directional cycles ... for if there would be, then the transitive closure would force there to be an arrow from an object to itself, and it would no longer be irreflexive. In fact, having lined up all objects this way, you could even add an arrow between any two objects from left to right (this would be the equivalent of extending the partial order into a linear order).

OK, so whether our order is total or merely partial, by transitivity and irreflexivity, it must be true that we can line up all objects from 'left' to 'right' so that any relationship (arrow) goes from left to right. However, given that there are only a finite number of objects, and given that by premise $1$ there is at least one relationship (arrow), it must be true that there is a left-most element that still has an outgoing arrow, but no incoming arrow. But given that element, the conclusion is true. This argument works for any finite domain and interpretation of $G$, and hence the conclusion does follow from the premises for any finite domain.