The Trinity is Antitransitive

I grew up going to St. James United Methodist Church in Sioux City, Iowa. Every time I return home and attend church there, I rethink many of the thoughts that I have had in that building over the years.

One of those thoughts is that I have always liked one of the stained glass windows next to the pew in which my family regularly sits.

In particular, I have always liked the visual representation of the relationships in the trinity.

However, I have never known why I liked it...until now!

The Trinity is an antitransitive relation.

Now, to explain what that means.

A relation is the formal mathematical notion most closely related to the word I used before, "relationship". In the case of the Trinity relation, each pair of (distinct) words (i.e. God, Father, Jesus, Holy Spirit) is ascribed either "is" or "is not" (so the Trinity relation is a binary relation). (For each pair of identical words, the window does not state the relationship but it is implied that each word is related to itself, thus ascribed an "is" and making it a symmetric relation.)

To understand an antitransitive relation, it helps to know what a transitive relation is. A (binary) relation is transitive if

for all words x, y, and z, if x is related to y and y is related to z, then x is related to z.

The most commonly known transitive relation is the equivalence relation. As everyone knows, if x is equal to y and y is equal to z, then x is equal to z.

An antitransitive relation has the exact opposite conclusion about every triple of words. A (binary) relation is antitransitive if

for all words x, y, and z, if x is related to y and y is related to z, then x is NOT related to z.

Although somewhat counterintuitive, I believe it is the mathematical beauty of the Trinity that drew me to this window all those years ago.

(Or maybe it is because it also looks like a planar embedding of K₄...nah.)

Wizard of Oz FAIL

(Why do all my recent posts involve YouTube videos??)

You remember in the Wizard of Oz when the Scarecrow receives his brain...

He is just as stupid has when they started this their trip. After receiving his brain, the Scarecrow says

"The sum of the square roots of any two sides of an isosceles triangle is equal to the square root of the remaining side."

This is a misquote of the Pythagorean theorem. The Scarecrow is wrong in three ways:

1. It should be a right triangle, not an isosceles triangle.
2. It should be "the squares" of the sides, not "the square roots" of the sides.
3. Order matters. Only the sum of the squares of the smaller two sides add together to be the square of the longest side.

The line to correctly state the Pythagorean theorem would be

"The sum of the squares of the short sides of a right triangle is equal to the square of the longest side."

(Source: Wikipeida Article on Pythagorean theorem)

About an Unusual Theorem

Yesterday, I saw a professor write the following on the board:

Theorem:
To prove a theorem, [one] need[s] to show it's true in all circumstances.
To prove a [theorem] is false, [one] need[s] to show it's fase for just one case.

How would you go about proving such a theorem? This looks like a nasty case of infinite recursion to me.

Minimum Number of Comparisons to Find the Median

Last week in my Advanced Algorithms class, we discussed how to create a deterministic algorithm to find the kth smallest element in a list of size n. An algorithm that solves this problem is called a Selection algorithm.

The first step in the deterministic algorithm is to divide the original list into ceil(n/5) lists (each of size 5). The next step is to find the median of each 5 element list. Because 5 is a constant (with respect to n), it is acceptable to first sort each 5 element list and then extract the media (without adversely effecting the runtime).

Now, the Art of Computer Programming, Volume 3: Sorting and Searching (2nd Edition) by Kunth says that sorting 5 elements can be done in 7 comparisons. That is great, but we actually do not need to sort these 5 elements. We only need to find the median. Our class found some lecture notes from another class where the professor mentioned in passing that the median of 5 elements can be found with only 6 comparisons, but he never expained how to do this.

I was not aware of nor have I found any results of the form: Finding the median of n elements requires c comparisons. However, I was able to discover how to find the median of 5 elements by using only 6 comparisons. It was not in a paper or even some professional-looking site. It was in a forum which I am only able to view using Google's cached copy. About halfway down the page is the following figure:

This is a remarkably thorough answer. Other than two meaningless typos at the bottom (where he should have said "(C>D gives full ordering)" on the left side and should have said "(C>E gives a full ordering)" on the right side), this solution clearly shows that 6 comparisons is sufficient.

It seems unlikely that there could be a way to find the median of 5 elements with only 5 comparisons, but I have not seen any proof of such a fact. If you know a proof that 6 is indeed the minimum number of comparisons necessary to find the median of 5 elements or if you know any results for lists of larger sizes, please leave a comment.