Relations, part 2

[I continue writing in the form of a dialogue between Master (M) and Apprentice (A).]

A: O Noble Teacher, last time we talked, you said that a unary relation is just an arbitrary set. But you didn't explain why would you introduce another word just to mean "set"!

M: O My Dear Apprentice, that is because when we say R is a unary relation, we usually have context in mind and we usually say more. For example, we might be thinking about some set X and then we might say that R is a unary relation on set X. In this way, we want to say more then just "R is a set". Formally, we mean that R is a subset of X, but intuitively, we separate elements x of X into those for which the relation R(x) holds and those for which the relation R(x) does not hold. Here, "R(x) holds" just means "x∈R" and "R(x) does not hold" means x∈R−X.

A: Okay, that makes more sense. But what about binary relations, are they "on a set" as well?

M: They can be! Saying that R is a binary relation on set X is just saying "R⊆X×X". You'll note also that asserting this inclusion immediately implies that R is a binary relation: R is a set because it's contained in a set and all elements of R are ordered pairs - ordered pairs of elements of X! 

A: Okay, can you give me an interesting example of a binary relation on some set?

M: Of course! Let us take X=ω for our set, that is the set of all natural numbers, and let us take
R:={(m,n)∈ω×ω:m∈n}.
Another way to say what R is, is to say R=∈∩(ω×ω), which is the intersection of a class and a set. By Axiom of Comprehension, this is a set. This is a very special binary relation and it is usually denoted by <. Now, we have that, for example,
3∈{0,1,2,3,4,5}=6,
so 3<6. But, on the other hand, 6<3 does not hold. In order to see this, note that 6<3 would mean 6∈3, while we saw that 3∈6, so if this situation were real, we would have 6∈3∈6. But this is false! Remember, that's one of those pathological situations made impossible Axiom of Induction. The most important point that I'd like you to take from this example is that < is in fact the standard ordering of the natural numbers! The relation m<n holds if and only if natural number m is strictly smaller than natural number n.

A: This is great, Master! I've just learned how to code the ordering of the natural numbers as a set! However, I don't know what an ordering actually is...

M: Okay, I'll explain that to you next time we meet.

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

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 pr...
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