Second-order and Fixed-point Logic: Describing Graphs

In summary, The conversation is about representing certain properties of a graph using second-order logic versus fixed-point logic, specifically the idea of a graph having an even number of edges. The participants discuss different approaches and functions to express this property mathematically. One suggestion is to use the function Degree(edge(X,Y)) and another is to define the degree of a vertex and its relation to the sum of degrees in the graph. In the end, the mathematical representation of a graph is summarized as a pair of sets of vertices and edges.
  • #1
nounou
27
0
Does anyone have an idea how can we represent certain properties of a graph using
second-order logic, versus fixed-point logic :

like saying that a graph has an even number of edges

I've been trying to find a way to solve this for the past two days !

Any help?

Anyone ?
 
Physics news on Phys.org
  • #2
Counterexample : Take the graph A-B...this one has only 1 edge...

I suppose you want to say : the sum of the degrees in a graph is even (the degree of a vertex is the sum of edges arriving at that vertex).

This is simply because the sum of the degree of each vertex is 2*n_edges...
 
  • #3
Thanx Kleinwolf,
So you think i would use another function Degree(edge(X,Y)) ? But how how will I say mathematically that the sum is even Sigma Degree(edge(X,Y)) = 2*n...?
 
  • #4
If I remember well, with symbols loved by mathematicians, a graph is a pair of set G=(V,E). The elements of V are the vertices v_i. The elements of E are the edges e_i=(v_1,v_2), linking vertices v_1 with v_2.

The degree of a vertex v_i is defined by : [tex] deg(v_i)=\sum_{e\in E|v_i\in e} 1[/tex]

Then : [tex] \sum_i deg(v_i)=\sum_{v_i\in V}\sum_{e\in E|v_i\in e}1=\sum_{e\in E}\sum_{v_i\in V|v_i\in e}1=\sum_{e\in E}2 [/tex]

The last equality sign just comes from the fact that an edges links two vertices.
 

FAQ: Second-order and Fixed-point Logic: Describing Graphs

1. What is second-order logic and how does it relate to describing graphs?

Second-order logic is a type of mathematical logic that allows quantification over both individual objects and sets of objects. It is particularly useful for describing properties of graphs, as it allows for the quantification over subgraphs and sets of vertices or edges.

2. How is fixed-point logic used in describing graphs?

Fixed-point logic is a type of second-order logic that allows for the definition of recursive functions. In terms of describing graphs, fixed-point logic can be used to define graph properties that are defined in terms of themselves, such as connectivity or cycles.

3. What are some common applications of second-order and fixed-point logic in graph theory?

Second-order and fixed-point logic are commonly used in graph theory to define and prove properties of graphs, such as connectivity, planarity, and colorability. They are also used in algorithm design and optimization problems on graphs.

4. Can graphs be fully described using second-order and fixed-point logic?

No, second-order and fixed-point logic are powerful tools for describing properties of graphs but they cannot fully capture all aspects of a graph. For example, they cannot describe properties that are dependent on the specific structure of a graph, such as the shortest path between two vertices.

5. Are there any limitations to using second-order and fixed-point logic in describing graphs?

One limitation of second-order and fixed-point logic is that they are not decidable, meaning there is no algorithm that can determine whether a given logical statement is true or false. This can make it difficult to use in automated reasoning and decision-making processes.

Similar threads

MHB Multi-Graph Logic Exercise: Describe as First-Order Structure
Replies
4
Views
2K
A Concrete examples of randomness in math vs. probability theory
Replies
11
Views
1K
MHB Graph Grammer Function For Two Exotic Graphs Question please.
Replies
4
Views
2K
Python Help solving a geometrical matching issue with Graph Neural Networks
Replies
1
Views
632
I Computer languages as examples in formal logic
2
Replies
40
Views
7K
MHB Attempting to add logic mathematics to a college paper - need your input
Replies
2
Views
2K
MHB A Subset of a Graph with No Perfect Matching
Replies
1
Views
1K
Are Logic Games Necessary for Success on the LSAT?
Replies
3
Views
2K
Role of classical logic in studying logic
Replies
6
Views
5K
B How can I linearize my (negative slope) quadratic graph?
Replies
16
Views
4K

Hot Threads

Recent Insights

Back
Top