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

Compressing and summarizing. Part 2.

[Disclaimer: this a blog-post consciously written in the style adumbrated in Compressing and summarizing. Part 0. For the original, see arXiv:1707.09005 [math.LO]. Compression ratio here is high. ]

The recent preprint arXiv:1707.09005 of Michael Lieberman, Jiří Rosický, Sebastien Vasey is very interesting and close to my current research interests. (Not least because I am working on a non-elementarity proof for some classes of not-necessarily locally-finite graphs, aware of modern methods and category theory.)

Introduction of loc. cit. gives very careful historical introduction, and ends with notational conventions. Authors use the left-upper-subscript convention.

Section 2 defines \mu-universal classes of structures, recalls an old theorem of Tarkski’s (for inexperience readers: needless to say, in Fact 2.2 “type” is “type as in omitting-types theorems” (search for that if you need to) i.e. roughly speaking, a set of formulas each of whose finite subsets is semantically-consistent , not “type as in type-theory”), then recalls abstract elementary classes (AEC) (see also [Kueker, Annals of Pure and Applied Logic, Volume 156, Issues 2–3, December 2008, Pages 274-286](http://www.sciencedirect.com/science/article/pii/S0168007208000997)  if you need background reading on this. Loc. cit. then recalls the definition of “admitting intersections” from Baldwin-Shelah: Examples of non-locality, The Journal of Symbolic Logic 73, (2008). Then come some motivating explanations. Note to readers: it may be fruitful to compare the concepts of “universal class” and algebraic theories. First main result of loc. cit. is

If $latex\mu$ is a regular cardinal, and \mathbb{K} is a \mu-AEC which is also pseudo-universal and does not contain the empty structure, then there is an expansion \hat{\mathbb{K}} of \mathbb{K} such that the expansion is functorial in the sense of 1412.3313, Definition 3.1,  and which is a \mu-AEC. The emphasis here is going from ‘pseudo-\mu-AEC’ to ‘\mu-AEC’.

This is not the only result of loc. cit.

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

Compressing and summarizing. Part 1.

Disclaimer: this a blog-post consciously written in the style adumbrated in Compressing and summarizing. Part 0. For the original, see Historia Mathematica Volume 6, Issue 3, August 1979, Pages 294-304. For brevity, the source is referenced by loc. cit., and sort-of-a-telegraphic style is adopted, and all factual statements, like “Zermelo wrote first” are written without phrases like “seems to be” or “apparently”, but are not meant to be statements of certainty.

There was correspondence between Gödel and Zermelo, in 1931, which is after  publication of both incompleteness theorems. Loc. cit. is about that. Zermelo wrote first. Topic was a disagreement about what a proof is. At the risk of oversimplifying: Zermelo claimed he had proved something which contradicted Gödel’s First Incompleteness Theorem. In Fundamenta Mathematicae (1930) Volume: 16, Issue: 1, page 29-47 Zermelo had described a model of his axioms of set theory, which Zermelo thought (0) could express arithmetic, and (1) was complete. However, author of loc. cit. writes that Zermelo argued “rather vaguely!” in proving what he though contradicted Gödel. Loc. cit. says” Zermelo seems not to have fully understood the implications of Gödel’s result.” Briefly: Zermelo’s objection was not correct, yet Gödel took the time to carefully respond to Zermelo, to the point of making remarks that one could call logic 101.

Posted in Uncategorized | Leave a comment

Compressing and summarizing. Part 0.

Some are of the opinion that blogs add noise to the internet and make good information harder to find. There certainly is something to this view, but I think by and large blogs are to the good, when done well. What I somehow miss, especially in the mathematical blogosphere, are compressing and summarizing reports or, so to speak, reading-logs.

I am surprised that this seems not to exist as a sort-of-a-subgenre of mathematical blogging. Of course, the default mode of mathematical blogging are almost-complete mathematical expositions, but I am missing a genre of the type “I am reading this or that  article or blog-post (given with full explicit references and credits to the original), and now I am compressing and summarizing it here, with a rather strong compression ratio, and am doing so openly for the benefit of the occasional reader searching for this or that article or blog post.”

If  became a common subgenre, there could be something of a golden age, with a differential of posts of increasing compression ratio, that readers can select from. Of course, to some extent, many blog posts are like that, but to me it does not seem a recognizable genre of mathematical blog-post. So I will, now and then, try to write such posts.

To remind me and others, in such posts:

 

  • Hardly ever anything evaluative is written.
  • The English is more or less in telegraphic style, often omitting articles.
  • There is one reference-to-be-summarized, given at the top, and later referenced by “loc. cit.”. Of course, other references can be used in the course of the summary.
Posted in compressing and summarizing, expository, Olds | Leave a comment