Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say:

  • $x_i$ are members of a set (e.g. nodes of a graph) and
  • there is a quantity $V(x_i)$ associated with each (e.g degree of the node)

Let's say $Q(x_i,x_j)$ denotes the equality $V(x_i) = V(x_j)$ so the statement "There is a pair of nodes that have the same degree" would be: $$\exists x\exists y\left(Q(x,y)\land\lnot(x=y)\right)$$

How can I construct $Q(x,y)$?

I tried along the lines of $$Q(x,y): \forall z( (P(x,z)\rightarrow \exists w(P(y,w))) \land (P(y,z)\rightarrow \exists w(P(x,w))) )$$ (where $P(x,y)$: "x has an edge to y") but that doesn't get me anywhere.

PS: It's not homework

share|improve this question

1 Answer 1

up vote 2 down vote accepted

In general, you can't.

First-order logic cannot by itself express any notions that depend on counting and arbitrary natural numbers. So if your only primitive relation is that two vertices are connected by an edge, then the property of having the same degree is not first-order definable.

In order to speak about vertex degrees, you need to add appropriate primitive notions (relations or functions) and axioms to the language, to define how the degree works.

The most general approach would be to add individuals to stand for particular numbers in the universe, together with new predicates "is a vertex" and "is a number", axioms saying that everything is either a vertex or a number, but not both, a function symbol taking a vertex to its degree and so forth. The trouble is that it wouldn't be easy to specify axioms guaranteeing that the degree given by the new function symbol actually agrees with how many edges the vertex has. So perhaps it would be better to extend the language to speak directly of finite set of vertices, and relations between such sets -- in which case you can express things like "there is a one-to-one relation between the neighbors of vertex $x_1$ and the neighbors of vertex $x_2$.

These approaches will both lead you to build moderately large parts of set theory or number theory into your theory, and you might need to worry about whether the theory achieves Gödel strength (in which case you're going to lose completeness, if that matters to you), and so forth.

So in practice the best conclusion to draw is that if you need to speak about node degrees, then first-order logic is not the right tool to do it with.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.