In this video, we'll see sample proofs of two relation properties. (The other three properties have proof outlines that are more straightforward.)

Our sample relation

Let's remember our sample relation with triples from the previous video. We defined \( V = \{0, 1, \ldots, 10\}\), i.e. integers between 0 and 10. The base set for our relation was the set of triples from V, i.e. \(T = V^3\).

We defined an define an order \(\preceq \) on \(T\) that tells us when set of triples is better than another:

\((a,b,c) \preceq (x,y,z)\) iff \(a\le x\), \(b \le y\), and \(c\le z\)

Transitive

Defn: A relation R on a base set A is transitive iff for every \(x,y,z\in A\), if \(xRy\) and \(y R z\), then \(x R z\).

Notice that our definition of transitive is an if/then statement. The base set in our relation is T (not A). So the three elements x, y, and z mentioned in the definition will be triples of integers. To make this clear, let's call them \(x = (a,b,c)\), \(y = (i,j,k)\), and \(z = (p,q,r)\).

To prove that \(\preceq\) is transitive, we use the standard direct proof outline. That is, declare our variables, assume everything in the hypothesis of the if/then statements, and put the conclusion down at the end of our draft proof.

Proof: let \((a,b,c)\), \((i,j,k)\), and \((p,q,r)\) be elements of T. Suppose that \((a,b,c) \preceq (i,j,k)\) and \((i,j,k) \preceq (p,q,r)\).

...

\((a,b,c) \preceq (p,q,r)\), which is what we needed to prove.

Now substitute in the definition of the relation \(\preceq\). Remember to do that at the bottom of the proof as well as the top, so we've converted our statements about \(\preceq\) into bits of algebra.

Proof: let \((a,b,c)\), \((i,j,k)\), and \((p,q,r)\) be elements of T. Suppose that \((a,b,c) \preceq (i,j,k)\) and \((i,j,k) \preceq (p,q,r)\).

By the definition of \(\preceq\), \((a,b,c) \preceq (i,j,k)\) means that \(a \le i\), \(b \le j\), and \(c \le k\). Similarly \((i,j,k) \preceq (p,q,r)\) means that \(i \le p\), \(j \le q\), and \(k \le r\).

...

So \(a \le p\), \(b \le q\), and \(c \le r\). By the definition of \(\preceq\), this means that \((a,b,c) \preceq (p,q,r)\), which is what we needed to prove.

Fortunately, the algebra is easy to connect:

Proof: let \((a,b,c)\), \((i,j,k)\), and \((p,q,r)\) be elements of T. Suppose that \((a,b,c) \preceq (i,j,k)\) and \((i,j,k) \preceq (p,q,r)\).

By the definition of \(\preceq\), \((a,b,c) \preceq (i,j,k)\) means that \(a \le i\), \(b \le j\), and \(c \le k\). Similarly \((i,j,k) \preceq (p,q,r)\) means that \(i \le p\), \(j \le q\), and \(k \le r\).

Since \(a \le i\) and \(i \le p\), \(a \le p\). Since \(b \le j\) and \(j \le q\), \(b \le q\). Since \(c \le k\) and \(k \le r\), \(c \le r\).

So \(a \le p\), \(b \le q\), and \(c \le r\). By the definition of \(\preceq\), this means that \((a,b,c) \preceq (p,q,r)\), which is what we needed to prove.

Antisymmetric

Now let's prove that this relation is antisymmetric. Remember that we have two equivalent definitions of antisymmetric. The first one is easier to understand, but the second "alternate" definition works much better for writing proofs.

Original Defn: A relation R on a base set A is antisymmetric iff for every \(x,y\in A\), if \(xRy\) and \(x \not = y\), then \(y \not Rx\).

Alternate Defn: A relation R on a base set A is antisymmetric iff for every \(x,y\in A\), if \(xRy\) and \(y Rx\), then \(x = y\).

So let's use the second definition and sketch our standard direct proof outline. Remember that we're using \(x = (a,b,c)\) and \(y = (i,j,k)\) to show the triplet structure.

Proof: Let \((a,b,c)\) and \((i,j,k)\) be elements of T. Suppose that \((a,b,c) \preceq (i,j,k)\) and \((i,j,k) \preceq (a,b,c)\).

....

Then \((a,b,c) = (i,j,k)\), which is what we needed to prove.

Now substiute in the definition of \(\preceq\):

Proof: Let \((a,b,c)\) and \((i,j,k)\) be elements of T. Suppose that \((a,b,c) \preceq (i,j,k)\) and \((i,j,k) \preceq (a,b,c)\).

By the definition of \(\preceq\), \((a,b,c) \preceq (i,j,k)\) means that \(a \le i\), \(b \le j\), and \(c \le k\). Similarly \((i,j,k) \preceq (a,b,c)\) means that \(i \le a\), \(j \le b\), and \(k \le c\).

....

Then \((a,b,c) = (i,j,k)\), which is what we needed to prove.

Now look at the algebra needed to connect the top and bottom. As with the transitive proof, there's not much missing.

Proof: Let \((a,b,c)\) and \((i,j,k)\) be elements of T. Suppose that \((a,b,c) \preceq (i,j,k)\) and \((i,j,k) \preceq (a,b,c)\).

By the definition of \(\preceq\), \((a,b,c) \preceq (i,j,k)\) means that \(a \le i\), \(b \le j\), and \(c \le k\). Similarly \((i,j,k) \preceq (a,b,c)\) means that \(i \le a\), \(j \le b\), and \(k \le c\).

Since \(a \le i\) and \(i \le a\), \(a = i\). Since \(b \le j\) and \(j \le b\), \(b = j\). Since \(c \le k\) and \(k \le c\), \(c = k\).

Since \(a = i\), \(b = j\), and \(c = k\), \((a,b,c) = (i,j,k)\), which is what we needed to prove.

Always use this alternate outline. Although the original intuitive definition can theoretically be used in proofs, it typically leads to problems filling in the middle section with correct math.