Mathematical aphorisms. Part 4.

Bicategories are useful because they allow to constructively compare comparisons.

Advertisements
Posted in Category Theory, expository, mathematical aphorisms, Mathematics | Leave a comment

Vignettes. Part 11.

There is a body of results in higher category theory which this expository blog post will present you a toy version of.

Not to bias this post too much, and not to slight said body of results (they actually are much more substantial than the following story might make you believe), I will not say what technical term said results usually go by. Here I will call them robustness theorems. Disclaimer: this is non-standard terminology.

What I really mean is a term similar to the term Tauberian theorems in number theory: an umbrella term binding together a bundle of similar results.
So again, I won’t tell you what these theorems are usually called—only so much: (0) the analogy with Tauberian theorems is rather apposite (the two bundles of results are spiritually quite similar) in that this is about giving a reasonable meaning to expressions  (1) I here will call them by the unusual term robustness theorems.

So what is the simplest robustness theorem, the toy robustness theorem?
To my mind, arguably, it is the following.

Suppose you know a person P.

Suppose it is understood what the two symbols F and G mean in the communication between you and P. That is, you know how to interpret both F and G.

However, the symbols Screenshot from 2017-08-07 07-44-56 and Screenshot from 2017-08-07 07-44-34 are considered nonsense; you will never be satisfied to have made sense of something P sends to you unless you have assembled a well-formed expression involving only F and G.

Now suppose a person P sends to to you a string of symbols.

Suppose what you are being flashed on your display is

(Symbol0)Screenshot from 2017-08-07 07-45-26

Now what to make of that? This symbols itself is evidently sort-of-a-finite-string
of symbols, quite-string-like indeed. But what is it supposed to mean?
In principle, of course, you are free to interpret in any way you want.
You might interpret it as true, for example.
Yet this is not the intended interpretation.
There is something that this symbol was made for.

It might not surprise you that (Symbol0) is intended to represent one morphism H  in a category \textsf{C}, with H intended to be assembled from the morphisms G and F .
It will also not surprise you that here, ’assembled from’ does not mean
’assembled in any way you like’, not even ‘in any meaningful way’ .

While logically there is no reason why the above geometric picture must  mean the morphism  G\circ F\circ G, there are customs regarding how the assembling should work, and those demand the interpretation G\circ F\circ G.

In principle, you could define any crazy interpretation of the above symbol, for example G\circ F\circ G\circ F\circ G would also define a morphism b\rightarrow a there is nothing logically wrong with such a deviant rule, but it does not give the intended interpretation. (It would be similar to having a private rule to interpret the string ‘seventeen’ to mean the number 19.)
In short, we have to give a rule (for brevity, we will take ‘rule’ to be a convenient monosyllabic synonym for the tetrasyllabic ‘algorithm’) for how to assemble expressions like (Symbol0) into one morphism of a category (to be precise: this, too, is an arbitrary choice-of-semantics that we make here: for the sake of this expository post, we just decide to only interpret expressions in humble 1-categories, while the robustness theorems apply to higher categories), and this rule should be generally applicable and, logically-consistent.

Let us try to make such an interpretation-rule:

(R0) Start at the left of the expression-to-be-interpreted, move rightwards, select the first letter you hit, hold it, interpret it as the name of a morphism in a 1-category \mathsf{C}, go on moving rightwards until the next,
hold it, interpret it accordingly, compose the two you morphisms you hold via the composition-function \circ of \textsf{C} to get a single morphism, hold it, go on moving to the right, repeat all of this, until you have reached the right-hand end of the symbol. The morphism-that-is-the-iterated-composite is the interpreation of the expression.

Applied to (Symbol0), (R0) gives us the interpretation (G \circ F ) \circ G \in \mathrm{mor}(\mathsf{C}).
Now comes the catch, an alternative scenario: suppose you were being flashed—perhaps due to some technical malfunction, or because you are standing on the other side of a window pane that P is scribbling (Symbol0) on—the symbol

Screenshot from 2017-08-07 09-20-42

Now what sense to make of that?

Being human, you might recognize this to be just the mirror-image of (Symbol0), and derive your interpretation from this observation, and the above procedure.

Yet, for the sake of argument, suppose you are being not very perceptive today, and perhaps currently so much in awe of the idea of non-text syntax that you cannot do better than to timidly and rigidly stick to your interpretationi rule (R0) when interpreting Screenshot from 2017-08-07 09-24-58.

You are then led to interpret Screenshot from 2017-08-07 09-24-58 to the composite

(TemporaryInterpretation0) Screenshot from 2017-08-07 09-28-15

 

 

which, however, does not yet make sense under the hypotheses stipulated in the beginning (namely that the symbols Screenshot from 2017-08-07 07-44-56 and Screenshot from 2017-08-07 07-44-34 in an interpretation of P’s messages are not acceptable to you).

Then there are the two following reasonable interpretation-options open to you, to give acceptable meaning to (TemporaryInterpretation0): either you reflect each variable in Screenshot from 2017-08-07 09-43-26separately to arrive at (G\circ F)\circ G, which happens to be the same as what you interpreted (Symbol0) to.
However, it is also reasonable, and arguably more reasonable, that you simply reflect the expression Screenshot from 2017-08-07 09-43-26 from (TemporaryInterpretation0) in its entirety about the vertical axis to arrive at G\circ (F\circ G).
So, in summary, in two scenarios you ended up with the interpretation (G\circ F)\circ G, while in another scenario (in a sense, in one-out-of-three possible scenarios for the communication process), you ended up with G\circ (F\circ G).
Fortunately, the usual axioms of 1-category theory contain an equality statement
expressing associativity of composition, telling you that, in particular, G\circ (F\circ G) = (G\circ F)\circ G.
So if you interpret (Symbol0) in any one of the above ways,

  • the axioms of 1-categories are robust to some of the vagaries of communication, provided that customary interpretation rules are used,

in that

  • the resulting morphisms came out the same, despite your rigid rule (R0),
    and despite the transmission error that handed you a mirror image, and despite the arbitrary choice of what to make of reflected letters.

We hasten to add that, needless to say

  • no non-trivial axiomatic system can be robust against all possible non-customary and possibly crazy interpretation rules (like, say, a rule which would interpret the mirror-image Screenshot from 2017-08-07 07-44-34 to mean F\circ F).

One can illustrate this above story in an informal ‘diagram’ (disclaimer: this
diagram is not known to be a mathematical object; the arrows have different sorts; not all arrows in the following are claimed to be morphisms of a category):

Screenshot from 2017-08-07 09-54-32

Here, ‘identity cell’ is a technical term, more or less synonymous with ‘equality’. (In case you are interested, ‘equality’ rather means something like a logical judgement, with which one just declares two things to be equal, while ‘identity cell’ means something like evidence, emphasizing that there is some specified amount of data in a standardized form, witnessing that the two things in question are equal).

To sum up, we have our toy robustness theorem:

  • the axioms of 1-category theory make the transmission of the one-member class of symbols \{ (Symbol0) \} robust against (0) rather arbitrary distortions of the symbol by Euclidean plane isometries, and quite some more distortions, and (1) a rigid interpretation rule like (R0). The resulting morphism of the category is exactly the same.

 

Posted in Category Theory, expository, logic, Mathematics, Olds | Leave a comment

Mathematical Aphorisms. Part 3.

With the discovery of higher dimensional algebra, the standard technical term linear equation accidentally has acquired a non-standard second meaning. In particular:

old-sense linear equation\overset{\not\Longleftarrow}{\Rightarrow}new-sense linear equation\overset{\not\Longrightarrow}{\Leftarrow}any old-sense equation.

Posted in Category Theory, expository, mathematical aphorisms, Mathematics | Leave a comment

Vignettes. Part 10.

In one of his very useful writings, Robert Harper writes the following thoughtful sentence:

But the upshot of Gödel’s Theorem is that as soon as we fix the concept of formal proof, it is immediate that it is not an adequate conception of proof simpliciter, because there are propositions that are true, which is to say have a proof, but have no formal proof according to the given rules.

With simpliciter Harper presumably (?) alludes to, and warns readers against, the logical fallacy a dicto secundum quid ad dictum simpliciter which was already known to, and warned against by, Kant.

A dicto secundum quid ad dictum simpliciter is Latin, whose literal translation is roughly from what-is-the-secondary-saying to the absolute saying, and can be rendered into more usual English as something like from a qualified claim to conclude an absolute claim. It means, it seems to me, the error of, from a statement-given-under-certain-qualifying-conditions, to conclude a statement-purported-to-be-true-absolutely.

A physical example of a dicto secundum quid ad dictum simpliciter often given is the seemingly unqualified statement Water boils at 100 degrees Celsius. This is a seeming dictum simpliciter which really is a dictum secundum that has forgotten (or hidden) a qualification: atmospheric pressure.

The connection to a dicto secundum quid ad dictum simpliciter not being explicitly made in loc. cit., to make a precise connection of a dicto secundum quid ad dictum simpliciter with Gödel’s first incompleteness theorem one of course now has to speculate: one attempt, in words, would be the following. One views Gödel’s first incompleteness theorem to show that a naive absolute conception of provability is itself a fallacy. For example, one could write, if only words are allowed, and abbreviating w.t.s.f.\equiv ‘within the same formalization’:

  • Gödel’s first incompleteness theorem shows that to conclude from the fact that in special instances formal statements can be proved w.t.s.f., the absolute statement that every true formal statement can be proved w.t.s.f., is to commit a dicto secundum quid ad dictum simpliciter.

Readers who would like some in-depth-reading on simpliciter may like to read D.G.Walton, Logique & Analyse 129-130 (1990), 113-154.

 

Posted in expository, logic, Vignettes. | Leave a comment

Vignettes. Part 9. Two different meanings of “star hypergraph”.

This little post is meant to be technically useful, pointing out one of the myriad clashes of terminology that exist in just about any science.

I happenend to know the term “star hypergraph” for a long time, but only in what I thought the only and usual sense (applying to  “hypergraph” in the most standard sense nowadays: set of subsets sets of a specified set).

Yesterday I saw that within the digraph-theoretic literature, there is a another meaning of “star hypergraph”. So here there are the two definitions, for the benefit of others who are puzzled by someone else using “star hypergraph” in another way than what one is used to, and turning to search engines for help.

Definition (star hypergraph; usual meaning for abstract hypergraphs; cf. e.g. the article J. Beck, Surplus of Graphs and the Lovász Local Lemma. Section 1).

Suppose H=(V,E) is an abstract hypergraph. (I.e. V is a set and E\in 2^{2^V}.) Then H is called a star hypergraph if and only if (writing \lvert\cdot\rvert for the cardinality of a set)

  1. for all e,e'\in E, \lvert e\cap e'\rvert\leq 1,
  2. for all v\in V, \lvert \{e\in E\colon v\in e \}\rvert=2.

Remark. Obviously, axioms 1. and 2. are independent. To see 1. \not\Rightarrow 2., consider any…err…star?…consisting of more than two hyperedges, any two of which intersect in precisely one ground-set element; this “star”, which in hypergraph-theory is more usually referred to by the whimsical-yet-evocative name sunflower, or the technical term \Delta-system,  is not a “star hypergraph”, since 2. is false. To see 2. \not\Rightarrow1., an easy counterexample is the hypergraph consisting of countably-infinitely-many four-element contiguous subsets (aka intervals) of \mathbb{Z}, any two consecutive of which interesecting in exactly two ground-set-elements: there, every ground-set element is in precisely two hyperedges, so 2. is true, but 1. is false.

Definition (star hypergraph; a meaning in digraph-theory ; cf. e.g. the article Jørgen Bang-Jensen, Stéphan Thomassé: Highly connected hypergraphs containing no two edge-disjoint spanning connected subhypergraphs. Below Theorem 3).

A star hypergraph consists of data

  • an abstract hypergraph H=(V,E)  (I.e. V  a set and E\in 2^{2^V}.)
  • a function h\colon E\rightarrow V

subject to the one axiom

  • for all e\in E, h(e)\in e.

Remark. Of course, the latter definition of “star hypergraph” is (equivalently) nothing else than a family of pointed sets.

Remark. Needless to say, the two above definition of star hypergraph do not have anything naturally to do with one another. They are already type-wise different, the latter “star hypergraph” having one more piece of specified data (the function h), and  lacking the two axioms of the former “star hypergraph”.

 

Posted in expository, infelicities, Mathematics, Olds | Leave a comment

Compressing and summarizing. Part 4.

[Disclaimer: this a blog-post consciously written in the style adumbrated in Compressing and summarizing. Part 0. For the original, see https://arxiv.org/abs/1708.00148. Compression ratio here is high. ]

This reports on this recent preprint by Siddharth Baskar and Alex Kruckman.

  • Loc. cit. proves that for any purely relational signature \Sigma, and for any class \mathbb{K} consisting of finite \Sigma-structures,

\mathbb{K} has the strict order property

if and only if

\mathbb{K} uniformly interprets the natural numbers.

  • I recall that a logical formula \psi having the strict order property relative to a theory \mathbb{T} means that for every model \mathfrak{A} of \psi, the poset P := \{ (a_i,a_j)|  \models\exists a\in \lvert \mathfrak{A}\rvert,\, (  \neg\psi(a,a_i)\wedge\psi(a,a_j)     )                                    \} contains arbitrarily long finite chains.

(to be continued)

Posted in Uncategorized | Leave a comment

Compressing and summarizing. Part 3.

[Disclaimer: this a blog-post consciously written in the style adumbrated in Compressing and summarizing. Part 0. For the original, see https://arxiv.org/abs/1707.09400. Compression ratio here is high. ]

 

This recent preprint of Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo on digraphs is very interesting to me, because

  • I am recently quite involved in digraph-theory for more than one reason,
  • since student-days I am very interested  in max-cut-like problems like the folklore classic recalled in Prop. 1. of loc. cit.

so I’ll here report on loc.cit.

For further reference, we introduce notation:

  • Let \mathsf{BipDgr} denote the full subcategory of the category \mathsf{Dgr} of digraphs which is spanned by the bipartite digraphs. For each digraph D let \mathsf{BipDgr}(D) denote the full subcategory of \mathsf{BigDgr} spanned by the spanning bipartite subdigraphs of D. Let 2^V denote the power-set of the set V, considered as a posetal category in the usual way.    Central concept of loc. cit. is, for each digraph D=(V,A), a functor

F(D)\colon 2^V\rightarrow\mathsf{BipDg}(D)

which in particular takes any U\subseteq V to digraph (V,\{  (x,y)| x\in U, y\in V\setminus U, (x,y)\in A \}).

Graph here means undirected simple graph.

For brevity,

  • ‘isol.-free.’ is an abbreviation for ‘is free of isolated vertices'(=has minimum degree at least one),
  • (d_0,d_1)-bipartition’ is an abbreviation for ‘bipartition V = V_0\sqcup V_1 of the vertex set of the graph such that each vertex in V_i has at least d_i neighbours in V_{1-i}. Loc. cit. Problem 2 denotes this by the longer ‘(\delta\geq k_1 , \delta\geq k_2)-bipartite partition’.

On a pedantic note, it seems an improvement to replace the formulation ‘bipartite-partition’ of loc. cit. with ‘bipartition’, since strictly speaking a ‘bipartite partition’ is not defined in graph theory, and since my alternative suggestion is even shorter than the original.

Prop. 1 loc. cit. recalls the fact that every finite graph admits an unfriendly partition. Loc. cit. then points out that this implies that every finite isol.-free graph admits a partition such that the bipartite graph defined by it is itself isol.-free. This of course implies that there is a time O(n) algorithm to decide if an $n$-vertex graph admits a (1,1)-bipartition.

Loc. cit. then states the more general class of decision problems

  • (d_0,d_1)\mathsf{BIPAR} \equiv given a finite graph, to decide whether it admits at least one (d_0,d_1)-bipartition.

Loc. cit. inter alia gives a proof that

  • if d_0+d_1\leq 3, then (d_0,d_1)\mathsf{BIPAR} admits an algorithm polynomial in the order of the input graph,
  • if d_0+d_1\geq 4, then (d_0,d_1)\mathsf{BIPAR} is NP-complete.

To be continued.

 

Posted in compressing and summarizing, digraph theory, Mathematics, News, Research | Leave a comment