Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Motivating example

All vertices $v$ in a 3-connected graph have degree $d(v) \geq$ 3 (because every two vertices are connected by three independent paths).

What is the "logical difference" between (i) 3-connectedness and (ii) minimal degree $\delta(G) = 3$? That is: which properties $\phi(G)$ make the statement

The graph $G$ is 3-connected if and only if $\delta(G) = 3$ and $\phi(G)$



Consider a setting with a fixed language and theory. Let two properties $F(x)$ and $G(x)$ with $(\forall x) F(x) \rightarrow G(x)$ be given. Ask the question: Are there properties $H(x)$ such that $(\forall x) F(x) \leftrightarrow G(x) \wedge H(x)$? And which?

For which languages and theories and/or in which cases might such a question have a definite and sensible answer? By which means could the answer be derived?

It's - very loosely speaking - about resolving some kind of "logical equation":

$F > G \Rightarrow (\exists H)\ F = G + H \Rightarrow \bf{H = F-G}$.

share|improve this question
Since you can always take $H(x)$ to be $F(x)$, or to be $G(x)\to F(x)$, you probably want to pin down what you meant by a "sensible answer". –  Andreas Blass Jan 22 '13 at 2:07
The two not-very-sensible answers in my previous comment are the extreme cases. The properties $H(x)$ that you asked about can be characterized as those properties that satisfy, in your fixed theory, the two implications $(forall x)\,(F(x)\to H(x))$ and $(\forall x)\,(H(x)\to(G(x)\to F(x))$. –  Andreas Blass Jan 22 '13 at 2:13
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.