Relations

I'll write this post in form of a dialogue between Master (M) and Apprentice (A).

A: Say, O Noble Teacher, what are those "relations" that mathematicians always talk about?

M: Why, my dear Apprentice, you have already seen one kind of relations!

A: How so, O Exalted One?

M: Well, ∈ is a relation and V is also a relation! These are class-sized relations.

A: Oh, I see! But how does their "relation-ness" manifest?

M: In the case of ∈, it divides pairs of sets (x,y) into those for which x belongs to y and into those for which x does not belong to y. So, it tells us whether the statement ''x∈y" is true or false for any particular pair of sets (x,y). In this sense, they are no different from predicates or classes. Class-sized relations are the same thing as predicates.

A: I seem to understand now! ∈ is a binary predicate, so a class-sized relation. V is a class, which is the same thing as a unary predicate, so it is also a class-sized relation.

M: Well observed! And being "unary" or "binary" translates to class-sized relations as well. So, V is a unary class-sized relation and ∈ is a binary class-sized relation. There are also ternary, 4-ary, 1000-ary relations! Here is an example of a 4-ary relation: "x∈y∈z∈w and w is a natural number".

A: Why do you keep saying "class-sized relations"? Are there relations of any other size?

M: Indeed there are! In fact, when mathematicians say "relation", they usually mean a set-sized one.

A: Great, great, this is what I want to know! What are then set-sized relations?

M: The same way every set is a class, but not every class is a set, so is the case with relations. Every relation is a class-sized relation, but not every class-sized relation is a relation. I see this terminology is unfortunate... So, every set-sized relation is a class-sized relation, but not every class-sized relation is set-sized relation. Okay, this seems clearer. Now, when we say relation, we mean "set-sized relation". Usually.

A: O Noble Master, you have bewildered me with this terminological talk and I still don't understand what are relations!

M: Okay, I apologize. A unary relation is a set, any set. A binary relation is a set whose elements are ordered pairs. We say that these relations are "set-sized" exactly because they are actually sets. If you take a class-sized binary relation, say ∈, and you take a set, say ω, you can then produce a set-sized binary relation by restricting the class-sized relation to the set. What I mean by this, in the example of ∈ and ω, is to take the set

{(x,y)∈ω×ω:x∈y}

to be your set-sized relation. This is indeed a set, that follows from Axiom of Comprehension. And this is indeed a binary relation, because it is evident that all of its elements are ordered pairs.

A: But why do you say unary predicate is just a set? Why use two words for the same thing? And also, you only told me what are unary and binary relations. What about 1000-ary relations?

M: Sharp questions indeed! But they will have to wait until we meet next time...

Comments

Post a Comment

Popular posts from this blog

Axiom of Powerset

So far, I listed Axioms of the Empty Set, Extensionality, Pairing, Union, Comprehension, Induction, Replacement, and Infinity. This is not the complete list making up the Mathematical Theory of Everything, we have to add two more axioms to the list. These axioms are called Powerset  and Choice . Axiom of Powerset is relatively easy to state: for every set x in the universe, there exists a set whose elements are exactly all subsets of x . As usual, Extensionality implies that such object must be unique and we denote it by P(x). So, the defining characteristic of the set P(x) is that a given set y belongs to P(x) if and only if y is a subset of x. The other axioms don't imply existence of the powerset. More precise explanation of this will have to wait, but for now, we can kind of see that the set P(x) is "larger" than x. If a is an element of x, than {a} is a subset of x, so an element of P(x). But there are oth...
Read more

Wellorderings

I've already told you what is an ordering, but let me give a quick reminder. A ( strict) ordering  on some set X is a a binary relation, usually denoted by some variation on the symbol <, which is  irreflexive,  that is for all x∈X, it is not  the case that x<x, transitive, that is for all x,y,z∈X, if x<y and y<z, then x<z. One very important example is the standard ordering on natural numbers. In that case, we have that X=ω and <=∈. To understand the second thing, recall that in Set Theory, natural numbers are coded as 0=∅, 1={0}, 2={0,1}, 3={0,1,2}, and so on. Hence, for example, 1<3 because 1∈{0,1,2}=3. In addition to the irreflexivity and transitivity, this relation satisfies some other important properties. One of them is being total, that is for all x,y∈X, one of the options is true: x<y or x=y or x>y. The orderings which...
Read more