Have you ever tried to test if one set in Python was less than another set?
A = {1,2}
B = {1,3}
C = {1,2,3}
print(A < B) #output: False
print(A < C) #output: True
print(B < C) #output: TrueBut what does that even mean? And in what world is "5 < 3 = True"? Well, let's start at the beginning!
Sets and Classes and Baking
A set is an unordered list of elements, in both Python and Mathematics. In Python, a class is a way to define a general object that allows you to create specific instances of that object. We must start every class by initiating its attributes, and we can also define functions (methods) that work within the class, or methods that work on the class itself, and many other fun things.
Let's say we enjoy baking and want to bake a cake. Let's define the Cake class and define a few initial variables like a list of ingredients, a list of portion sizes for each ingredient, and a bake time.
class Cake():
def __init__(self, ingredients, portions, bake_time):
self.ingredients = ingredients
self.portions = portions
self.bake_time = bake_timeThe function "__init__(...)" runs as soon as we define an instance of our class and "self" means the function is running on that instance in particular, and not the whole class (although the variable "self" itself could be anything but we choose this for convention and clarity). So we could define two different cake recipes as we try to learn to bake a cake.
Cake1 = Cake(['egg','flour'],[1,2],10)
Cake2 = Cake(['egg','flour','butter'],[2,2,1/2],15)And we can access those attributes we defined explicitly, because the "__init__(...)" function created those variables as soon as we defined the two cakes.
And altering the attributes of one class object doesn't change others of the same class. For example, increasing bake time or adding ingredients for Cake1 doesn't change Cake2.
print(Cake1.ingredients) #output: ['egg','flour']
print(Cake2.ingredients) #output: ['egg','flour','butter']
Cake1.ingredients.append('vanilla')
print(Cake1.ingredients) #output: ['egg','flour','vanilla']
print(Cake2.ingredients) #output: ['egg','flour','butter']In addition to attributes, classes have functions that can be called for each instance of the object. So let's say we want to be able to bake our cakes. At the moment, let's just make the output depend on whether the "bake_time" is long enough.
class Cake():
def __init__(self, ingredients, portions, bake_time):
self.ingredients = ingredients
self.portions = portions
self.bake_time = bake_time
def bake(self):
if self.bake_time < 20:
print('Cake is gooey.')
elif self.bake_time < 30:
print('Cake is perfect!')
else:
print('Cake is overcooked.')Now if we just call "bake()", we get "NameError: name 'bake' is not defined". And that's because we have to call bake() for a specific instance of the class.
Since we set "Cake.bake_time = 20" and "Cake2.bake_time = 15", we see the outputs are correct.
But notice the difference between the "bake()" and "__init__(...)" functions. Both are methods inside the class but the "__init__(...)" function gets automatically called, while we have to explicitly call "bake()". That's because "__init__(...)" is an example of a dunder method or magic method. The "Dunder" comes from "Double Underscore". And "__init__(...)" isn't the only dunder method! Which leads us back to our sets.
Understanding Less Than in Python Classes
When we write something like "A = {1,2}", Python actually calls the set class and tells it to construct the set with elements 1 and 2. This class has its own attributes and methods. To see these for a particular class, we write "dir(class)", for directory. For set, we get
['__and__', '__class__', '__class_getitem__', '__contains__', '__delattr__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__iand__', '__init__', '__init_subclass__', '__ior__', '__isub__', '__iter__', '__ixor__', '__le__', '__len__', '__lt__', '__ne__', '__new__', '__or__', '__rand__', '__reduce__', '__reduce_ex__', '__repr__', '__ror__', '__rsub__', '__rxor__', '__setattr__', '__sizeof__', '__str__', '__sub__', '__subclasshook__', '__xor__', 'add', 'clear', 'copy', 'difference', 'difference_update', 'discard', 'intersection', 'intersection_update', 'isdisjoint', 'issubset', 'issuperset', 'pop', 'remove', 'symmetric_difference', 'symmetric_difference_update', 'union', 'update']This by itself gives a quick and clear idea of things we can do with sets: check equality or containment, take differences, symmetric differences, unions, intersections, and much more. But within the dunder methods, we see "__gt__, __ge__, __lt__, __le__", which stands for "greater than", "greater than or equal to", "less than", "less than or equal to". These functions are the ones that are actually being called when we write something like "{1,2} < {1,3}" or "{1,2,3} ≥ {1,3}".
And this is another benefit of dunder methods: they translate simple written instructions to hidden python functions so you don't have to deal explicitly with the methods inside that class.
In fact, if you look at the Cake class we defined, then "dir(Cake)" shows
['__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__le__', '__lt__', '__module__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__', 'bake']But that's way more than we defined! And that's because Python automatically adds these dunder methods whenever we define a class. For example, when we access a class object's attributes by writing "Cake1.bake_time", the "__getattribute__" dunder method is automatically called to do this action. When we changed the bake_time with "Cake1.bake_time = 20", Python used the "__setattr__" method to do so.
So then what does the "__lt__" method do? It's right there! Let's try:
print(Cake1 < Cake2)
#output: TypeError: '<' not supported between instances of 'Cake' and 'Cake'So some of these dunder methods are defined without us having to do anything, while others like "__init__" require us to tell it what to do when the function does get called. If we try to investigate "set.__lt__" any further, we see
print(set.__lt__) #output: <slot wrapper '__lt__' of 'set' objects>and wrappers are a path I don't want to go down right now! What it essentially means is that the "less than" function for sets in Python is wrapped in another function in C that does the check. And what check is that? Containment! Which explains the very first example we did. "A < B" is translated by "set.__lt__" into a check for whether A is contained in B. You can read even deeper into the details here, where the construction of the set object is inspired from a certain algorithm in Donald Knuth's fundamental book series "The Art of Programming".
Partially Ordered Sets (Posets)
Now we want to use this knowledge of Python dunder methods to work with fun mathematical objects. So let's start by defining the star of this post: Posets.
Definition) A Partially Ordered Set (Poset) is a set of elements along with an ordering < that can be represented as a set of ordered pairs of elements, with (x,y) meaning x < y.
I remember learning about posets and then trying to view everything through that lens...and I'm sure that's a common experience! Because posets really do pop up everywhere in mathematics and have such interesting properties. Many theorems can be rephrased as being about posets and perhaps more importantly, many theorems in the wider world of mathematics are derived from important theorems about posets.
Inspired by the last section...let's combine Python and Posets!
ASIDE: There are a ton of programming languages that allow you to work with posets, my favorite being SageMath/CoCalc. The following is just a fun exercise in connecting math and programming!
Let's begin by writing the basics of our class. Let's assume we have a set "set_" of elements of our poset and a set "relations_" of ordered pairs of elements.
class Poset():
def __init__(self,set_,relations_):
self.set = set_
self.relations = relations_Note we use "set_" as a variable because "set" is a built-in class. Then "relations_" is just for continuity, we could have just said relations.
We immediately run into an issue. Our dunder method "__lt__()" gives us the ability to compare two instances of a class, but just defining a single class Poset won't let us compare elements in that way. So we need to actually convert each element of "set_" into its own class, which we'll call PosetElement. Remember this isn't a weird thing to do - whenever you type a number, Python converts it to a int class instance; whenever you type 'blah', Python converts it to a str class instance; and as we've seen, sets {1,2} are interpreted as set class instances.
The fact that PosetElement will work on the "set_" entered means that we might as well have a nested class. And since we'll be defining "__lt__(...)" inside this class, we need to also pass it the full set of relations. To overwrite the usual "<", we go ahead and explicitly define it inside PosetElement as follows:
class PosetElement():
def __init__(self1,name,relations_):
self1.name = name
self1.relations = relations_
def __lt__(self1,B):
return ((self1.name,B.name) in self1.relations)Then with A and B as instances of the class PosetElement, we get that "A < B" becomes a check of whether the ordered pair "(A.name,B.name)" is in the set of relations we defined.
But we still need to do one more thing, which is to convert all elements given to us in "set_" into PosetElement objects. This is as easy as adding the line
for i,s in enumerate(set_):
self.set[i] = self.PosetElement(s,relations_)to the "__init__" function within the Poset class. Put all together, we get this.
class Poset():
class PosetElement():
def __init__(self1,name,relations_):
self1.name = name
self1.relations = relations_
def __lt__(self1,B):
return ((self1.name,B.name) in self1.relations)
def __init__(self,set_,relations_):
self.set = set_
for i,s in enumerate(set_):
self.set[i] = self.PosetElement(s,relations_)
self.relations = relations_Example
Ok, now that we've set it all up, let's do an example! We'll just look at the set [1,2,3] and impose the relations that
1 < 2
1 < 3
3 < 2
Then we can establish this poset by writing
EP = Poset([1,2,3],[(1,2),(1,3),(3,2)])Let's define our poset version of 1,2, and 3.
_1 = EP.set[0]
_2 = EP.set[1]
_3 = EP.set[2]We can be sure that our conversion worked by checking types:
print(type(_1)) #output:<class '__main__.Poset.PosetElement'>Checking our relation, we see that while 2 < 3 in the usual sense, the "__lt__(...)" overwrite returns False for "_2 < _3" because (2,3) isn't an ordered pair in our set of relations. Here are some examples:
print(_2 < _3) #output: False
print(_1 < _2) #output: True
print(_1 < _3) #output: True
print(_3 < _2) #output: TrueWe can visualize this poset as a graph with vertices "set_" and an arrow from x to y if (x,y) is in "relations_":
Arithmetic Posets
What if we're in a situation where the relations between our elements is determined in some arithmetic way, i.e. with a formula or rule? Then defining "relations_" as ordered pairs of elements and then passing that into Poset can be cumbersome, especially if you have a lot (or perhaps, an infinite number) of elements. It would be simpler to hard-code it in.
For example, we can define a poset called the Divisibility Poset, whose elements are all positive integers less than some given integer n that divide n. The relation a < b tells us that a divides b. Here is a plot of this poset when n = 6.
Let's recreate our Poset class for this specific arithmetic poset. There are a few simplifications we can make:
Remove all appearances of "relations_" and "set_".
Add an input variable n, which will tell us "self.set" is the set of divisors of n.
Replace "__lt__(self1,B)" code with "return (B.name%self1.name == 0)", which will tell us whether self1 divides B, which tells us if self1 < B in our divisibility poset.
Putting this all together, our class becomes
class DivisibilityPoset():
class PosetElement():
def __init__(self1,name):
self1.name = name
def __lt__(self1,B):
return ((B.name)%(self1.name) == 0)
def __init__(self,n):
self.set = []
for i in range(1,n+1):
if n%i == 0:
self.set.append(self.PosetElement(i))Doing a few tests on n = 6 shows us success!
DP = DivisibilityPoset(6)
for el in DP.set:
print(el.name) #output: 1,2,3,6
_1 = DP.set[0]
_2 = DP.set[1]
_3 = DP.set[2]
_6 = DP.set[3]
print(_1 < _2) #output: True
print (_2 < _3) #output: False
print (_3 < _6) #output: True
print(_6 < _3) #output: FalseP-Adic Poset
For the final part of this post, we'll make what I'll call a "p-adic poset". The p-adics are a number system in which the size of a number depends solely on how many times p divides it. Technically, we'd have to talk about valuations, completions, and extensions, but the above definition by itself is enough for this example.
We can visualize this by plotting along the number line the number of times p divides it. If we take p = 2 as an example, then we get the following plot for the first 20 integers.
And doing p = 3 with the first 50 integers gives
You can see the spike in the middle is 27 = 3^3. And of course there is no real line between integer points, but this is nicer visually!
Having a tool to encompass this relationship would be a great help in understanding the p-adics, so let's write out the changes to the previous DivisibilityPoset we will have to make.
Make "set" essentially infinite and add the input variable p.
Find how many times p divides a given integer (which is called its p-adic valuation).
Rewrite "__lt__(self1,B)" to be a basic inequality between self1 and B valuations.
For the first goal, we simply choose as big a number as we want, call it M, and make "set" from "range(1,M+1)". For the second, we need to write a function to get an integer's p-adic valuation, which isn't too tough using the % operator in Python, which represents to the modulus function in math. Specifically, A%B = A mod B = "A modulo B". So we take a number, check its value mod p, and if it's 0, we divide by p. Then we repeat until we don't get 0, which tells us our number is no longer divisible by p. This can be accomplished with a while loop. Keeping track of how many loops we do gives us our valuation!
def padic_val(a,p):
val = 0
A = a
while A%p == 0:
val += 1
A = int(A/p)
return valWe actually need a little more. Though this issue doesn't arise when p is a prime number, if we let p be an arbitrary integer, then we can have fractional valuations. For example, since 2 = sqrt(4), we'd have the 4-adic valuation of 2 being 1/2. And we could extend this further to all positive rationals to get negative valuations - BUT I'm catching myself talking about extensions, which I said I wouldn't.
So sticking with p prime, we can check a few examples just to be sure.
print(padic_val(24,2)) #output: 3
print(padic_val(3,2)) #output: 0
print(padic_val(5,3)) #output: 0
print(padic_val(9,3)) #output: 2
print(padic_val(27,3)) #output: 3So finally we come to our P-Adic Poset!
class PAdicPoset():
class PosetElement():
def __init__(self1,name,p):
self1.name = name
self1.p = p
def __lt__(self1,B):
sval = padic_val(self1.name,self1.p)
Bval = padic_val(B.name,self1.p)
return (sval < Bval)
def __init__(self,p):
self.set = list(range(1,10**6 + 1))
for ind,i in enumerate(self.set):
self.set[ind] = self.PosetElement(i,p)As usual, we've got to do a few examples. We'll look at the 3-adics.
PAP = PAdicPoset(3)
_2 = PAP.set[1]
_3 = PAP.set[2]
_5 = PAP.set[4]
_6 = PAP.set[5]
_9 = PAP.set[8]
_27 = PAP.set[26]
print(_2 < _3) #True
print(_9 < _6) #False
print(_2 < _27) #True
print(_5 < _3) #TrueAnd you see that it's exactly within the 3-adic Poset that our initial question is answered:
5 < 3 = True
Thank you for reading!
Jonathan M Gerhard
Comments