# G8. Relations (in Logic, not in Love)

The proof of Godel’s theorems deals with “relations”, which was not a term that I was familiar with before learning about Godel. I could have benefited from a short introduction, so here goes.

Let’s see what wikipedia has to say…

In mathematics, a

finitary relationover setsX_1, …, _X__nis a subset of the Cartesian productX_1 × … × _X__n; that is, it is a set ofn-tuples (x_1, …, _x__n) consisting of elementsx__iinX__i.

Oh, wikipedia… how you can turn simple ideas into unintelligible gibberish. Let’s try another source: Encyclopedia Brittanica…

Relation, in logic, a set of ordered pairs, triples, quadruples, and so on. A set of ordered pairs is called a two-place (or dyadic) relation; a set of ordered triples is a three-place (or triadic) relation; and so on. In general, a relation is any set of ordered n-tuples of objects.

Much more clear. Now let’s see a bunch of examples:

**Equality**: \(Eq(m, n)\) is a two-place relation that consists of all pairs \((m, n)\) such that \(m = n\).

**Less than**: \(Lt(m, n)\) is a two-place relation that consists of all pairs \((m, n)\) where \(m < n\).

Hopefully you’re starting to get the picture.

**Prime**: \(Prim(n)\) is a one-place relation that consists of all elements \(n\) that are prime. One-place relations are often called “properties”.

**Divisibility**: \(Div(m, n)\) consists of all pairs \((m, n)\) such that \(m\) is divisible by \(n\).

**Factorial**: \(Fact(m, n)\) consists of all pairs \((m, n)\) s.t. \(m = n!\).

**Prime Factors**: \(NPrimeFactors(m, n)\) consists of all pairs \((m, n)\) s.t. the number \(m\) has \(n\) unique prime factors.

**Prime Factor Multiplicity**: \(exf(m, n, i)\) consists of all triples \((m, n, i)\) s.t. \(i\) is the exponent of the \(n\)th prime number in \(m\)’s prime factorization.

In this way, you can see how relations are extremely general and can represent properties of numbers (e.g. primeness) as well as things that are normally described as functions (e.g. factorial or the exponent of the \(n\)th prime number in \(m\)’s factorization), but if you boil it down… it’s just a set.