# Can reasoning be modeled as a preference relation over sets of propositions?

So the idea is to model reasoning as a preference relation over sets of propositions. Given sets of propositions S1 and S2, we might have the relation S1 < S2, which we can read as "S2 is preferred over S1." And what this means operationally is that if our entire belief set was initially S1, we would be willing to replace our (entire) belief set S1 with S2.

It is convenient to set aside < for now and define things with ≤ since that is the language of partial orders. We can read S1 ≤ S2 as "S2 is acceptable from S1." S1 ≤ S2 means S1 < S2 or S1 = S2.

The relation ≤ should be a partial order. It should be reflexive: S ≤ S for all sets of propositions S. It should be transitive: S1 ≤ S2 and S2 ≤ S3 should imply S1 ≤ S3. It should be antisymmetric: if S1 ≤ S2 and S2 ≤ S1 then S1 = S2.

There can be sets of propositions S1 and S2 where S1 ≰ S2 and S2 ≰ S1, and in this case neither S1 can be concluded from S2, nor S2 concluded from S1.

The preference relation S1 < S2 can then be defined as S1 ≤ S2 and S1 ≠ S2.

For example: we may prefer {A, A->B, B} over {A, A->B} alone, so {A, A->B} < {A, A->B, B}, and therefore from {A, A->B} we would prefer to add the proposition B and reach {A, A->B, B}. This is (a particular example of) modus ponens.

In general, for a formal deductive logic, a reasonable preference relation could have S1 < S2 iff (1) every formula in S2 is derivable from the conjunction of formulas in S1, and (2) S2 is a superset of S1. Condition (2) means we are never "giving up" any theorems as we reason, only adding to the set. This is not the only possible preference relation for the logic, but it's one reasonable choice.

Since this is preference rather than deduction, it can account for non-logical or empirical reasoning, such as preferring one hypothesis to explain the data over another. This would be represented as {D, H1} < {D, H2} where D is the data, H1 is one hypothesis, and H2 is a preferred hypothesis.

It would be necessary to mark propositions with their provenance, so that we are allowed to throw out and change hypotheses as above, but not allowed to throw out and change the data.

Reasoning would consist of moving through the preference graph from less-preferred to more-preferred sets of propositions.

A "truth" from a starting proposition set S1, would be defined as any proposition P, such that there is a proposition set S2 with S1 ≤ S2, and if S2 ≤ S3, then P ∈ S3.

In other words, in our ascent up the preference graph from S1, if we are able to reach a point where we conclude P, and where from that point all the nodes above us also have P, then P was a truth of our starting point S1.

A truth is a proposition that holds "in the limit" as we ascend the preference graph.

We might want to require that the set of truths as we ascend should be unchanged. In other words, if P is a truth of S1, and S1 < S2, then we demand P also be a truth of S2. This restricts the possible structure of the preference graph.

We may also wish to talk about what beliefs a person would immediately recognize as preferable from their current belief set, as opposed to what would be preferable after a million inference steps. This can be represented with a relation <ᵢ where the i stands for "immediate," and A <ᵢ B means "B is immediately preferred to A." The set of all edges (A, B) where A <ᵢ B would form a directed acyclic graph, which could be extended to A < B by taking the transitive closure. In a deductive logic, A <ᵢ B would hold provided that B = A ∪ {b} where b is a proposition, not previously in A, that can be obtained in one step by applying an inference rule to some of the propositions in A.

Are there any aspects of reasoning that can't be captured by a system like this?

• Is S1 ≤ S2 defined as S1 = S2 ∨ S1 < S2, where = is set extensionality and < is preference relation? If that's the case, I don't see how S1 ≤ S2 would have the intended reading of "S2 is acceptable from S1" if it is the case that S1 < S2. There seems to be two separation notions or ordering here Mar 27 at 18:45
• @ayylien Yes that is how it is defined. What's wrong with that intended reading? "S1 ≤ S2" means we are allowed to end up at S2 if we started at S1. It seems "S2 is acceptable from S1" is a way to describe that situation. Mar 27 at 19:06
• Are you allowing connectives? If so, your poset will be a complemented lattice, and those are already standard models for interpreting logics: Boolean lattice (classical), measurable subset lattice (for probabilistic logics), Heyting lattice (for intuitionism), Hilbert lattice (for quantum logic), etc. I suspect that deduction/preference distinction is just surface grammar, they mutually convert. As described, you are only capturing analog of implication with ≤, and that is not functionally complete. And it looks purely propositional, so relational reasoning will not be covered either. Mar 27 at 20:18
• @Conifold The elements of the poset are sets of propositions, not propositions, so I don't think any of that applies. Connectives appear in the individual propositions in each set, not in the graph. Mar 27 at 20:21
• @causative this looks a lot like a kripke frame, with 'P is a truth' corresponding to '□P', right?
– ac15
Mar 27 at 21:42

Can reasoning be modeled as a preference relation over sets of propositions?

Are there any aspects of reasoning that can't be captured by a system like this?

I'll focus on "Is there any system like this?": since we're talking about orderings on sets of objects, one can always look it at the induced ordering by restriction on singletons, so it makes sense to view this as an extension problem, and hence in the following we'll assume a partial order R as given on a set S.

Now, Barberá & Pattanaik' (1984) paper Extending an order on a Set to the power set: Some remarks on Kannai and Peleg's approach has the interesting impossibility theorem:

If S contains at least three linearly related elements, there exists no binary relation < on its powerset satisfying statements (K) and (M')

which are

(K) Let A, B be subsets of S: if (for all x in A and all y in B, xRy) and (for some x in A and some y in B, xRy and not yRx), then A < B

(M') If A, B and C are subsets of S such that A is disjoint from both B and from C, and B < C, then union{A, B} < union{B, C}

These seem pretty ok requirements for a model of reasoning: under the reading "B is acceptable from A", (K) is about always 'updating' from A to B in case B is 'definitely acceptable' from A, and (M') is a certain 'weak monotonicity' condition - though one may object to (M') on these same grounds - and so, in a sense, there would be no such 'nice' system

In fact the theorem is not proved assuming (K), but rather with the weaker condition (B)

(B) For all distinct x, y in S, if xRy, then {x, y} < {x} and {y} < {x,y}

implied by (K), which looks a bit weird in context. Speaking of which, the authors emphasize that context is key when choosing which conditions to impose on the orderings, and there also a possibility result on the paper for the case one weakens (M'), so maybe not all is lost

• More to the point, it's not clear to me how any of this applies to the preference relation I want to use to model reasoning. What would S (in the paper they call it Ω) be? A totally ordered set of propositions? Who says there's any relevant total order on the set of propositions? Mar 28 at 0:03
• The paper has a background hypothesis that the order on objects is linear, but since the proof only uses it for the three selected objects, and in our context of propositions it would make little sense to impose linearity, I made minor modifications. Also: K implies B
– ac15
Mar 28 at 0:04
• Oh right, my mistake about K implying B. Anyway, why do you assume there is some order on the set of propositions that our preference order on the set of sets of propositions would have to conform to? Mar 28 at 0:06
• If there's an order defined on sets of propositions, and 'p' and 'q' are individual propositions, then looking at them as singleton sets {p} and {q}, one has an induced order on propositions
– ac15
Mar 28 at 0:12
• Supposing the propositions are theorems in some deductive logic, I wouldn't accept (K). Here's why: suppose that A is a set of a million individually rather minor theorems, and suppose B is a single surprising and important result. I don't think a mathematician would necessarily prefer to believe B over A. The value of the many minor theorems could add up to collectively be greater than the one important result. Also, I don't think there's necessarily a preference either way - we could have neither A ≤ B nor B ≤ A, the mathematician isn't willing to abandon either belief-set for the other. Mar 28 at 0:28

I personally think all of the formal logic will fall into place easily if you can spend some time thinking about what you mean by "preference" and produce a more precise criteria.

I prefer the word "coherence", maybe. It sounds like these "sets of propositions" don't impose any structure between each of the propositions in a given set. It's not like a set marks which of its propositions depend on, or follow from, which others. They apparently just "go together better".

If that is what we settle on as "what is going on here", the mathematics are simple. We have a set of all possible propositions P. We consider every possible combination of such propositions, which is the set of all subsets of P, a.k.a., the power set.

In this abstract model, we don't know a specific value for the coherence of any of these sets. But we can assume each one has an intrinsic coherence anyway. So Coherence(Set) = k, for each set, for some value k.

This would naturally induce some type of ordering.

You then wish to distinguish any propositions p which are present in a "chain" - that is, a proposition which is present for an unbroken sequence of greater sets, up to some (locally) maximal set.

Sets have a natural ordering, that of inclusion. So, in a way, you are asking for "overlap" between the "coherence" ordering and the "inclusion" ordering.

This model is not complicated. Perhaps it would be more interesting if you tried it out on some concrete values.

I'm trying to write this up in Coq, but I haven't found the time yet. Hopefully, once written, you could use it to construct actual models of such a universe of propositions, and to see how this model behaves when you actually apply it, and if you want to modify it in some way.

I think some really awesome stuff could be possible if you analyze this structure as a multi-lattice.