Showing posts with label graph theory. Show all posts
Showing posts with label graph theory. Show all posts

Friday, June 7, 2019

Truly going beyond the binary in marriage?

There is an interesting sense in which standard polygamy (i.e., polygyny or polyandry) presupposes the binarity of marriage. In standard polygamy, there is one individual, A, who stands in a marriage relationship to each of a plurality of other individuals, the Bs. But the marriage relationships themselves are binary: A is married to each of the Bs, and the Bs are not married to each other (they have a different kind of relationship).

The same would be true with more complex graph theoretic structures than the simple star-shaped structure of polygyny and polyandry (with A at the center and the Bs at the periphery). If Alice is married to Bob and Carl, and Bob and Carl are each married to Davita, the quadrilateral graph-theoretic structure of this relationship is still constituted by a four binary marriage relationships.

Thus, in these kinds of cases, what we would have are not a plural marriage, but a plurality of binary marriages with overlap. This, I think, makes for more precise terminology. The moral and political questions normally considered under the head of “plural marriages” are about the possibility or morality of overlap between binary marriages.

To truly go beyond the binary would require a relationship that irreducibly contains more than two people, a relationship not constituted by pairwise relationships. I think a pretty good case can be made that even if one accepts overlapping binary marriages, as in standard polygamy, as genuine marriages (I am not sure one should), irreducibly non-binary relationships would still not be marriages (just as unary relationships wouldn't be). The structure of the relationship is just radically different.

Thursday, August 3, 2017

Connected and scattered objects

Intuitively, some physical objects, like a typical organism, are connected, while other physical objects, like a typical chess set spilled on a table, are disconnected or scattered.

What does it mean for an object O that occupies some region R of space to be connected? There is a standard topological definition of a region R being connected (there are no open sets U and V whose intersections with R are non-empty such that R ⊆ U ∪ V), and so we could say that O is connected if and only if the region R occupied by it is connected.

But this definition doesn’t work well if space is discrete. The most natural topology on a discrete space would make every region containing two or more points be disconnected. But it seems that even if space were discrete, it would make sense to talk of a typical organism as connected.

If the space is a regular rectangular grid, then we can try to give a non-topological definition of connectedness: a region is connected provided that any two points in it can be joined by a sequence of points such that any two successive points are neighbors. But then we need to make a decision as to what points count as neighbors. For instance, while it seems obvious that (0,0,0) and (0,0,1) are neighbors (assuming the points have integer Cartesian coordinates), it is less clear whether diagonal pairs like (0,0,0) and (1,1,1) are neighbors. But we’re doing metaphysics, not mathematics. We shouldn’t just stipulate the neighbor relation. So there has to be some objective fact about the space that decides which pairs are neighbors. And things just get more complicated if the space is not a regular rectangular grid.

Perhaps we should suppose that a physical discrete space would have to come along with a physical “neighbor” structure, which would specify which (unordered, let’s suppose for now) pairs of points are neighbors. Mathematically speaking, this would turn the space into a graph: a mathematical object with vertices (points) and edges (the neighbor-pairs). So perhaps there could be at least two kinds of regular rectangular grid spaces, one in which an object that occupies precisely (0,0,0) and (1,1,1) is connected and another in which such an object is scattered.

But we can’t use this graph-theoretic solution in continuous spaces. For here is something very intuitive about Euclidean space: if there is a third point c on the line segment between the two points a and b, then a and b are not neighbors, because c is a better candidate for being a’s neighbor than b. But in Euclidean space, there is always such a third point, so no two points are neighbors. Fortunately, in Euclidean space we can use the topological notion.

But now we have a bit of a puzzle. We have a topological notion of a physical object being connected for objects in a continuous space and a graph theoretic notion for objects in a discrete space. Neither notion reduces to the other. In fact, we can apply the topological one to objects in a discrete space, and conclude that all objects that occupy more than one point are scattered, and the graph theoretic one to objects in Euclidean space, and also conclude that all objects that occupy more than one points are scattered.

Maybe we should have a disjunctive notion: an object is connected if and only if it is graph-theoretically connected in a space with a neighbor-relation or topologically connected in a space with a topological structure.

That’s not too bad, but it makes the notion of the connectedness of a physical object be a rather unnatural and gerrymandered notion. Maybe that’s how it has to be.

Or maybe only one of the two kinds of spaces is actually a possible physical space. Perhaps physical space must have a topological structure. Or maybe it must have a graph-theoretic structure.

Here’s a different suggestion. Given a region of space R, we can define a binary relation cR where cR(a, b) if and only if the laws of nature allow for a causal influence to propagate from a to b without leaving R. Then say that a region of space R is connected provided that any two distinct points can be joined by a sequence of points such that successive points are cR-related in one order or the other (i.e., if di and di+1 are successive points then cR(di, di+1) or cR(di+1, di)).

On this story, if we have a universe with pervasive immediate action at a distance, like in the case of Newtonian gravity, all physical objects end up connected. If we have a discrete universe with a neighbor structure and causal influences can propagate between neighbors and only between them, we recover the graph-theoretic notion.

Tuesday, April 9, 2013

Grounding and category theory

I've been searching for the right kind of mathematical structure to think about the phenomenon of grounding or partial grounding with. The orthodoxy is that the right structure is a partial ordering. That the axioms of partial ordering are satisfied by partial grounding has been challenged and defended. But even the critics have tended to take partial grounding to be something like[note 1] a single relation, or perhaps a small collection of related relations, between pairs of propositions or between a proposition and a set of propositions. I've offered two suggestions (first and second) on how to model grounding using graphs. But I now think all of these approaches abstract away too much of the structure of grounding and/or are unable to capture all the prima facie possibilities that a theory of grounding should recognize.

For instance, the relational approach loses sight of the structural fact that one can sometimes have two different grounding relations between a pair of propositions. Let W be the proposition that Smith is drinking water and let H be the proposition that Smith is drinking H2O. Let D be the disjunction of W and H: the proposition that Smith is drinking water or drinking H2O. If we think of grounding as a relation, we can certainly say that H grounds D. But we want to be able to say that there are two groundings between H and D: H grounds D directly by being one of its disjuncts and indirectly by grounding W which is another disjunct. And this structure is not captured by the orthodoxy. The graph approach nicely captures this sort of thing, but it does not adequately capture the compositional structure which is that the indirect grounding that H provides for D is a composition between a grounding by H of W and a grounding by W of D. There are ways to make it capture this, say by identifying composition of grounding with sequences of arrows in the directed graph, but this won't work for infinite sequences of arrows, something that we should not rule out in the formalism. I realized this when trying to finish a paper on grounding and fundamentality.

I am now wondering if the right structure isn't that of a category. Maybe the objects are true propositions. The arrows are groundings, i.e., token grounding-like relations. Every arrow is at least a partial weak grounding (weak, because there are identity arrows). Some arrows may be full groundings. There is a nice associative compositional structure.

There will be further structure in the category. For instance, perhaps, every family of true propositions will have a coproduct, which is the conjunction of the propositions in that family. The canonical injections are the partial groundings that conjuncts give to the conjunction, and the universal property of the coproduct basically says that when a proposition is weakly partially grounded by each member of a family of propositions, then there is a coproduct weak partial grounding arrow from the conjunction of that family to the proposition. This is very nice.

We might also consider a move to a category where the objects are all propositions, but that creates the challenge that we need to keep track of which propositions are true and which groundings are actual. For that p partially grounds q is, in general, a contingent matter.[note 2] Truth and actuality of grounding respects the category structure. Actual groundings only obtain between truths, and compositions of actual groundings are actual.

The category structure is going to yield transitivity of weak partial grounding. There are apparent counterexamples to transitivity. But it is my hope that when we keep track of the additional structure, and think of the token groundings as central rather than the relation of there being a token grounding, the result is not going to be problematic.

It is now interesting to investigate what different category theoretic phenomena occur in the grounding category, and how they connect up with metaphysical phenomena. One thing I'd like to see is if there is a neat category theoretic characterization of full, as opposed to partial, grounding.

I have an intuitive worry about the above approaches. Intuition would suggest that if conjunctions are coproducts, then disjunctions would be products. But they're not. For in general there is no grounding from a disjunction to disjuncts. This could be related to another worry, that because categories include identity arrows, I had to take the arrows to be weak groundings—i.e., I had to allow each proposition to count as having a grounding between itself and itself.

I do not know if category theory will in the end provide a good mathematical home to grounding structures, but I am hopeful.

Wednesday, November 16, 2011

The fecundity of Spinoza's claims

Say that the fecundity of a claim in a logically interconnected text, like Spinoza's Ethics, is the number of claims that logically depend on it. Using the Tredwell adjacency data, I sorted the claims in Spinoza's Ethics in order of decreasing fecundity. We can measure the fecundity in percentages: the percentage of the claims that depend on the given claim.

The result is here. (The explanations of what the items are are here, from Tredwell.) Fecundity is a measure of how fundamental a given claim is to the system.

The twelve most fecund claims, with their number of dependants, are:

  1. 1A04: 300 (77.3%)
  2. 1D03: 296 (76.3%)
  3. 1D04: 295 (76.0%)
  4. 1D05: 292 (75.3%)
  5. 1A06: 291 (75.0%)
  6. 1A01: 291 (75.0%)
  7. 1P01: 290 (74.7%)
  8. 1A05: 290 (74.7%)
  9. 1P04: 290 (74.7%)
  10. 1P02: 289 (74.5%)
  11. 1P03: 289 (74.5%)
  12. 1P05: 289 (74.5%)
Unsurprisingly, they're all from Part I of the Ethics, and unsurprisingly the first six are all axioms or definitions.

The most fecund is Axiom 4, that the cognitio (understanding?) of the effect depends on the cognitio of the cause, which, through Spinoza's overreading of it (it sounds like a weak claim, and that's why we are tempted to agree, but in fact it is a strong claim), becomes the root of the epistemologically central 2 Proposition 7, which says that the order and connection of things is the order and connection of ideas. In fact, it is largely through this 2P07 that Axiom 4 gets its fecundity: 2P07 has a fecundity of 60%, and assumes nothing other than 1A04.

The most fecund derived claim is 1 Proposition 4, that distinct things must differ in attribute or mode.

Unsurprisingly, the ontological argument is central: the fecundity of 1 Proposition 11, that God exists, is 73%.

The most fecund claim from outside of Part 1 is the aforementioned 2 Proposition 7, whose centrality cannot be denied.

There are 103 propositions that have zero fecundity.

Axiom 2 of Part I has zero fecundity in the database I am using, as do 5A02 and 2A08. Due to the limitations of my method, axioms and definitions with zero fecundity don't appear in the results I linked to, though I may fix that eventually. The case of Axiom 2 of Part I interesting and surprising, since it basically states Spinoza's version of the Principle of Sufficient Reason. My feeling is that it is implicitly used all over the place.

The least fecund axiom that actually gets used is 5A01, about contrary actions, which has only one dependent. The next, somewhat more fecund axiom is 4A01, at 4% fecundity, which says that for any thing, there is a stronger thing which can destroy it.

Surprisingly to me, the least fecund axiom from Part 1 is 1A03, at 8%, which basically affirms that causation is deterministic. This may initially suggest that Spinoza's causal determinism is not as central to his thought as it is normally thought to be. But that might be too quick, because I suspect that much if not all of the deterministic import of 1A03 is found in 1A04, especially as interpreted by 2P07 and with the understanding the the logical connections between ideas are always entailment relations.

Tuesday, November 15, 2011

Spinoza graphs

R. F. Tredwell has the data for generating a logical dependency graph of Spinoza's Ethics. I converted the data into DOT format so it can be used with GraphViz, and used GraphViz's dot to generate visual representations.

Here is a giant zoomable graph of the whole Ethics.  (There a "View original" link there, to download the original jpeg.)

Potentially more interesting are the individual graphs of the five parts of the Ethics.  Each graph includes the items from the part in question, as well as the dependencies from earlier parts.  (Again, there is a "View original" link for each which downloads the jpeg file.)
Here is some additional material: