Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Category Theory Illustrated – Orders

abuseofnotation.github.io

Post reply on HN
Print view View original

41–50 of 72 posts

Re: Category Theory Illustrated – Orders

#41

Post by gopiandcode »

gobdovan wrote: post #40
zaphar wrote: post #37

Earlier quoted context omitted.

Why assume it is javascript? The article doesn't indicate the language anywhere that I can see.

Ok, let's say that it is not JS, but an untyped, closure-based programming language with a strikingly similar array and sort API to JS. Sadly, this comparator is still wrong for any sorting API that expects a general three-way comparison, because it does not handle equality as a separate case. And to tie it down to the mathematics: if a sorting algorithm asks for a full comparison between a and b, and your function r…

> an untyped closure-based programming language with a similar array and sort api to JS

Ah! You're talking about Racket or Scheme!

```

> (sort '(3 1 2) (lambda (a b) ('(1,2,3)

```

I suppose you ought to go and tell the r6rs standardisation team that a HN user vehemently disagrees with their api: https://www.r6rs.org/document/lib-html-5.96/r6rs-lib-Z-H-5.h...

To address your actual pedantry, clearly you have some implicit normative belief about how a book about category theory should be written. That's cool, but this book has clearly chosen another approach, and appears to be clear and well explained enough to give a light introduction to category theory.

Re: Category Theory Illustrated – Orders

#42

Post by layer8 »

gobdovan wrote: post #40
zaphar wrote: post #37

Earlier quoted context omitted.

Why assume it is javascript? The article doesn't indicate the language anywhere that I can see.

Ok, let's say that it is not JS, but an untyped, closure-based programming language with a strikingly similar array and sort API to JS. Sadly, this comparator is still wrong for any sorting API that expects a general three-way comparison, because it does not handle equality as a separate case. And to tie it down to the mathematics: if a sorting algorithm asks for a full comparison between a and b, and your function r…

It could be a typed programming language where the sort function accepts a strict ordering predicate, like for example in C++ (https://en.cppreference.com/cpp/named_req/Compare).

Re: Category Theory Illustrated – Orders

#43

Post by mrkeen »

gobdovan wrote: post #40
zaphar wrote: post #37

Earlier quoted context omitted.

Why assume it is javascript? The article doesn't indicate the language anywhere that I can see.

Ok, let's say that it is not JS, but an untyped, closure-based programming language with a strikingly similar array and sort API to JS. Sadly, this comparator is still wrong for any sorting API that expects a general three-way comparison, because it does not handle equality as a separate case. And to tie it down to the mathematics: if a sorting algorithm asks for a full comparison between a and b, and your function r…

> Sadly, this comparator is still wrong for any sorting API that expects a general three-way comparison, because it does not handle equality as a separate case.

Let's scroll up a little bit and read from the section you're finding fault with:

  the most straightforward type of order that you think of is linear order i.e. one in which every object has its place depending on every other object
Rather than the usual "harrumph! This writer knows NOTHING of mathematics and has no business writing about it," maybe a simple counter-example would do, i.e. present an ordering "in which every object has its place depending on every other object" and "leaves no room for ambiguity in terms of which element comes before which" but also satisfies your requirement of allowing 'equal' ordering.

Re: Category Theory Illustrated – Orders

#44

Post by gobdovan »

gopiandcode wrote: post #41
gobdovan wrote: post #40

Earlier quoted context omitted.

Ok, let's say that it is not JS, but an untyped, closure-based programming language with a strikingly similar array and sort API to JS. Sadly, this comparator is still wrong for any sorting API that expects a general three-way comparison, because it does not handle equality as a separate case. And to tie it down to the mathematics: if a sorting algorithm asks for a full comparison between a and b, and your function r…

> an untyped closure-based programming language with a similar array and sort api to JS Ah! You're talking about Racket or Scheme! ``` > (sort '(3 1 2) (lambda (a b) ( '(1,2,3) ``` I suppose you ought to go and tell the r6rs standardisation team that a HN user vehemently disagrees with their api: https://www.r6rs.org/document/lib-html-5.96/r6rs-lib-Z-H-5.h... To address your actual pedantry, clearly you have some imp…

The syntax in the article is not scheme, you can clearly see it in my comment you're responding to.

As for your 'light introduction' comment: even ignoring the code, these are not pedantic complaints but basic mathematical and factual errors.

For example, the statement of Birkhoff’s Representation Theorem is wrong. The article says:

> Each distributive lattice is isomorphic to an inclusion order of its join-irreducible elements.

That is simply not the theorem. The theorem says "Theorem. Any finite distributive lattice L is isomorphic to the lattice of lower sets of the partial order of the join-irreducible elements of L.". You can read the definition on Wikipedia [0]

The article is plain wrong. The join-irreducibles themselves form a poset. The theorem is about the lattice of down-sets of that poset, ordered by inclusion. So the article is NOT simplifying, but misstating one of the central results it tries to explain. Call it a 'light introduction' as long as you want. This does not excuse the article from reversing the meaning of the theorem.

It's basically like saying 'E=m*c' is a simplification of 'E=m*c^2'.

[0] https://en.wikipedia.org/wiki/Birkhoff%27s_representation_th...

Re: Category Theory Illustrated – Orders

#45

Post by gobdovan »

mrkeen wrote: post #43
gobdovan wrote: post #40

Earlier quoted context omitted.

Ok, let's say that it is not JS, but an untyped, closure-based programming language with a strikingly similar array and sort API to JS. Sadly, this comparator is still wrong for any sorting API that expects a general three-way comparison, because it does not handle equality as a separate case. And to tie it down to the mathematics: if a sorting algorithm asks for a full comparison between a and b, and your function r…

> Sadly, this comparator is still wrong for any sorting API that expects a general three-way comparison, because it does not handle equality as a separate case. Let's scroll up a little bit and read from the section you're finding fault with: the most straightforward type of order that you think of is linear order i.e. one in which every object has its place depending on every other object Rather than the usual "harr…

Your reply only works if the article were consistently talking about a strict order. However, it is not. It explicitly introduces linear order using reflexivity and antisymmetry, in other words, a non-strict `If the author wanted to describe a 'no ties' scenario where every object has its own unique place, they should have defined a strict total order.

They may know everything about mathematics for all I care. I am critiquing what I am reading, not the author's knowledge.

Edit: for anyone wanting a basic example, ["aa", "aa", "ab"] under the usual lexicographic <=. All elements are comparable, so "every object has its place depending on every other object." It also "leaves no room for ambiguity in terms of which element comes before which": aa = aa < ab. Linear order means everything is comparable, not that there are no ties. By claiming "no ties are permitted" while defining the order as a reflexive, antisymmetric relation, the author is mixing a strict-order intuition into a non-strict-order definition.

Re: Category Theory Illustrated – Orders

#46

Post by renticulous »

raincole wrote: post #4
dgan wrote: post #3

I think it is pretty obvious that at the challenge with all abstract mathematics in general and the category theory in particular isnt the fact that people dont understand what a "linear order" is, but the fact it is so distant from daily routine that it seems completely pointless. It's like pouring water over pefectly smooth glass

Is there a "mind-blowing fact" about category theory? Like the first time I've heard that one can prove there is no analytical solution for a polynomial equation with a degree > 5 with group theory , it was mind-blowing. What's the counterpart of category theory?

https://en.wikipedia.org/wiki/Abstract_nonsense

https://math.stackexchange.com/questions/823289/abstract-non...

Sometimes the proof in category theory is trivial but we have no lower dimension or concrete intuition as to why that is true. This whole state of affairs is called abstract nonsense.

Re: Category Theory Illustrated – Orders

#47

Post by Chinjut »

raincole wrote: post #4
dgan wrote: post #3

I think it is pretty obvious that at the challenge with all abstract mathematics in general and the category theory in particular isnt the fact that people dont understand what a "linear order" is, but the fact it is so distant from daily routine that it seems completely pointless. It's like pouring water over pefectly smooth glass

Is there a "mind-blowing fact" about category theory? Like the first time I've heard that one can prove there is no analytical solution for a polynomial equation with a degree > 5 with group theory , it was mind-blowing. What's the counterpart of category theory?

Well, group theory is a special case of category theory. A group is a one object category where all morphisms are invertible. You do group theory long enough and it leads you to start thinking about groupoids and monoids and categories more generally as well.

Re: Category Theory Illustrated – Orders

#48

Post by pfortuny »

raincole wrote: post #4
dgan wrote: post #3

I think it is pretty obvious that at the challenge with all abstract mathematics in general and the category theory in particular isnt the fact that people dont understand what a "linear order" is, but the fact it is so distant from daily routine that it seems completely pointless. It's like pouring water over pefectly smooth glass

Is there a "mind-blowing fact" about category theory? Like the first time I've heard that one can prove there is no analytical solution for a polynomial equation with a degree > 5 with group theory , it was mind-blowing. What's the counterpart of category theory?

One of the most striking things is that cartesian products of objects do not correspond to set-cartesian products. This to me was mind-blowing when studying schemes.

Re: Category Theory Illustrated – Orders

#49

Post by mrkeen »

gobdovan wrote: post #45
mrkeen wrote: post #43

Earlier quoted context omitted.

> Sadly, this comparator is still wrong for any sorting API that expects a general three-way comparison, because it does not handle equality as a separate case. Let's scroll up a little bit and read from the section you're finding fault with: the most straightforward type of order that you think of is linear order i.e. one in which every object has its place depending on every other object Rather than the usual "harr…

Your reply only works if the article were consistently talking about a strict order. However, it is not. It explicitly introduces linear order using reflexivity and antisymmetry, in other words, a non-strict ` If the author wanted to describe a 'no ties' scenario where every object has its own unique place, they should have defined a strict total order. They may know everything about mathematics for all I care. I am…

  Definition: An order is a set of elements, together with a binary relation between the elements of the set, which obeys certain laws.

  the relationship between elements in an order is commonly denoted as ≤ in formulas, but it can also be represented with an arrow from first object to the second.
All of the binary relations between the elements of your example are:

"aa" ≤ "aa"

"ab" ≤ "ab"

"aa" ≤ "ab"

> By claiming "no ties are permitted" while defining the order as a reflexive, antisymmetric relation, the author is mixing a strict-order intuition into a non-strict-order definition.

There aren't any ties to permit or reject.

  we can formulate it the opposite way too and say that each object should not have the relationship to itself, in which case we would have a relation than resembles bigger than, as opposed to bigger or equal to and a slightly different type of order, sometimes called a strict order.

Re: Category Theory Illustrated – Orders

#50

Post by wasabi991011 »

gobdovan wrote: post #24
mrkeen wrote: post #20

Earlier quoted context omitted.

It really isn't a long enough section to get lost in. The 'not accurate' diagram says that orange-less-than-yellow implies yellow-not-less-than-orange. Hard to find fault with. > NO. Antisymmetry doesn't exclude `x = y`. Ties are permitted in the equality case. Antisymmetry for a non-strict order says that if both directions hold, the two elements must in fact be the same element. The author is describing strict comp…

My comment is not long enough either to get lost in. The prose "It also means that no ties are permitted - either I am better than my grandmother at soccer or she is better at it than me" is inaccurate for describing antisymmetry. In the same short section, you first state the correct condition: You have x ≤ y and y ≤ x only if x = y from which it doesn't follow that "It also means that no ties are permitted". The "n…

The prose is correct.

You (presumably) aren't your grandmother, so we have x=/=y. Therefore by the biimplication, (x ≤ y and y ≤ x) is false i.e. either x ≤ y (I am better than my grandmother) or y ≤ x (my grandmother is better than me). The "neither" case is excluded by the law of totality.

Post reply on HN