Picking Subsets

It is time for us to start approaching the infinity! I'll start by addressing the issue of picking a subset of a set. If a set is finite, say the set {x,y,z,w,t}, I might look at its elements one by one and decide if I like them or not. So, I like x and y, I don't like z, I do like w, but I don't like t. Is there in our universe the set of elements that I liked? Of course, it's just the set {x,y,w} (which we went through the trouble of describing last time). So we know how to pick subsets of finite set. However, if our universe is to be sufficiently reach, it must have the set {0,1,2,3,…} of all natural numbers, so how do you pick subsets of this set?

Naively, you might try to just go through natural numbers one by one, saying again for each one if you like it or not. But are you ever going to finish your "like-dislike" thread this way? After all, we've been all told as children that you can't count (go through) all the numbers!! 😄 Slyer among you would then probably say: "Well, I just like odd numbers and hate even ones, and that's my picking!" And exactly, you would be on the right path!

When moving to the realm of infinite, we have to abandon our desire to pick subsets of a set element by element. We salvage as much as we can by keeping the ability to pick elements of a set by their shared property. If I denote by P some property that I have in mind, any set x might have or might not have the property P. I can also say that P(x) holds or P(x) fails. (Of course, exactly one of these alternatives. 😉) So, if I have some set X and some property P, I assert it as an axiom that there exists a set Y whose elements are exactly those elements of X that have the property P. (There is a subtlety here of what a "property" actually is, but let's skip over this for now.) This new axiom is called the Axiom of Comprehension.

So, if I have a set X and a property P, then I have the set of all elements of X which have the property P. Of course, it is unambiguous what the elements of such a set must be, so the Axiom of Extensionality guarantees that there cannot be two different such sets. I will denote this set by

{x∈X:P(x)}.

Going back to the example above, once we get the set {0,1,2,3…} of all natural numbers and once we know what it means to be odd, we can then pick the subset consisting of those natural numbers which are odd. In other words, we'll immediately get the set {1,3,5,…}.

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