Talk:Minimal WRT Restriction

From ProofWiki
Jump to navigation Jump to search

Prime.mover, since you are an expert at logic, do you think you could formulate a clean generalization of this? If $B \subseteq A$, $R$ is a relation on $A$, and $P(B, R)$ is any statement that in some sense only uses $R$ to compare elements of $B$, then $P(B,R)$ is equivalent to $P(B,R \restriction B)$. --Dfeuer (talk) 19:55, 19 April 2013 (UTC)

Does this help? : Properties of Restriction of Relation --prime mover (talk) 20:01, 19 April 2013 (UTC)
Not really, although all of those proofs could be written to use the general principle I'm so vaguely describing. The intuitively trivial principle proves that (for suitable _____):
$R$ is _____ on $B$ iff its restriction to $B$ is _____.
The essential limitation is that it must be possible to write the propositional formula so that $R$ appears only within something of the form $xRy$, where $x$ and $y$ are required or known to be in $B$. It cannot have, for example, anything about the transitive closure of $R$, or the unrestricted image of $R$, or any such funny business. --Dfeuer (talk) 20:19, 19 April 2013 (UTC)
This is beginning to sound like a conversation from ... --prime mover (talk) 20:42, 19 April 2013 (UTC)
Haha. It's not that bad. Some examples:
Let $R$ be a relation on $A$ and let $B$ be a subclass of $A$. Let $R'$ be the restriction of $R$ to $B$.
$R$ is transitive on $B$: the property is $\forall a,b,c \in B: aRb \land bRc \implies aRc$.
$\forall S \subseteq B: |R^{-1}(S) \cap B| < 3$. While this doesn't have the required form, it can be put in such a form by rewriting the inner expression as $|\{x \in B: \exists s \in S: xRs \}|$.
Non-example: Just about any statement involving transitive closure. If $A = B \cup \{ \infty \}$ and $R$ extends $R'$ by letting $xR\infty$ and $\infty R x$ for all $x \in B$, there won't be any meaningful relationship between $R^+ \restriction B$ and $(R \restriction B)^+$. --Dfeuer (talk) 21:13, 19 April 2013 (UTC)

I'm going to have to reiterate the aims of this website: it's not intended as a place for doing research, it's primarily a reference resource.

I expect there are plenty of sites (mathhelpforum might be a good place to go, if it's still going) which can help you out with this. As for me I expect I could figger out what you're about but I don't have the headspace at the moment to do much more than the ongoing maintenance task that I'm involved in. --prime mover (talk) 21:19, 19 April 2013 (UTC)

Research, eh? This is just formalizing intuition that we already use here without bothering (in most cases) even to mention it. The theorem this talk page is attached to is one I doubt most texts would even bother to proveā€”it's just too trivial. This sort of thing is really all over the place. --Dfeuer (talk) 21:41, 19 April 2013 (UTC)
My rate is $\$200$ an hour (payable via PayPal). --prime mover (talk) 21:54, 19 April 2013 (UTC)