First-order logic : repesenting graphs

  • Context: Undergrad 
  • Thread starter Thread starter nounou
  • Start date Start date
  • Tags Tags
    Graphs Logic
Click For Summary

Discussion Overview

The discussion revolves around representing graphs in first-order logic, specifically focusing on how to express the number of edges in a graph. Participants explore various approaches to formulate sentences that accurately convey the existence of a specific number of edges, including zero, one, and more generally, n edges.

Discussion Character

  • Exploratory
  • Technical explanation
  • Mathematical reasoning

Main Points Raised

  • One participant asks how to express that a graph has exactly 6 edges in first-order logic.
  • Another suggests starting with simpler cases, such as expressing the number of edges as 0, 1, or 2.
  • Concerns are raised about how to represent the number of edges, with one participant stating they can express the existence of an edge but struggle with counting them.
  • Discussion includes the need to express uniqueness in edges, with references to how to state that a graph has exactly one edge.
  • Participants discuss the use of existential and universal quantifiers to express the existence and uniqueness of edges.
  • One participant proposes using multiple variables to represent edges but questions the number of variables needed for n edges.
  • There is an exploration of how to combine existential and universal quantifiers to express the existence of edges in various quantities.

Areas of Agreement / Disagreement

Participants do not reach a consensus on how to express the number of edges in first-order logic, with multiple competing views and approaches remaining throughout the discussion.

Contextual Notes

Participants express uncertainty about the correct formulations and the implications of their statements, indicating a reliance on definitions and the need for further clarification on the use of quantifiers.

Who May Find This Useful

This discussion may be of interest to those studying formal logic, graph theory, or mathematical logic, particularly in the context of expressing properties of graphs using first-order logic.

  • #31
Thanx honestrosewater. Hurkyl, any hints?
 
Physics news on Phys.org
  • #32
Hurkyl,
to extend
Ex(Dx) & AxAy((Dx & Dy) -> x = y) : Ex(Dx & Ay(Dy -> x = y).

to make it represent two edges

There exists at least one edges and there exists at most two edges: There exists exactly two edges: There exists two unique edges:

Ex(Dx) & AxAyAz((Dx & Dy & Dz) -> x = y & y=z) : (??I have no clue??).

Am I on the right track?

nounou
 
  • #33
nounou said:
Hurkyl,
to extend
Ex(Dx) & AxAy((Dx & Dy) -> x = y) : Ex(Dx & Ay(Dy -> x = y).
Just to be clear those are two equivalent formulas above- I could have put an equivalence sign but I had a thing going with the colons.
to make it represent two edges

There exists at least one edges and there exists at most two edges: There exists exactly two edges: There exists two unique edges:

Ex(Dx) & AxAyAz((Dx & Dy & Dz) -> x = y & y=z) : (??I have no clue??).

Am I on the right track?

nounou
I'll run through it just to give you an idea of how the process might go, but I'm not sure my answer will be correct- we'll need someone else like Hurkyl to check. Check it yourself too. Okay, there are two parts to unique existence:
1) Existence
2) Uniqueness
You need both, and you know how to state both:
1) Existence- Ex(Dx)
2) Uniqueness- AxAy((Dx & Dy) -> x = y).
Now in the above formulas, "x" and "y" are variables, right? They range over your constants. So Ex(Dx) says that at least one of your constants has the property D (of being an edge). So you're correct that Ex(Dx) alone could mean two constants have the property D, or one or three or all, etc. So just start the formula off- you can always change it later if you need to:
Ex(Dx)
Now you need to specify exactly how many constants have the property D. You'll add this on as a conjunct:
Ex(Dx) &
Notice that this ends the scope of the first quantifier. IOW, if you then put:
Ex(Dx) & x
The last "x" is free. Okay, so how do you say that there are exactly two constants with the property D? If you say there is at least one and at most two, that means there is either one or two. So you need to say there are at least two. IOW, there is a constant with the property D and there is another constant with the property D and those two constants aren't the same:
Ex(Dx) & ExEy(Dx & Dy & ~(x = y))
Now you need to say there are at most two constants with the property D. IOW, if there is a third constant with the property D, then it's the same as one of the first two (just add another conjunct):
Ex(Dx) & ExEy(Dx & Dy & ~(x = y)) & ExEyAz[(Dx & Dy & ~(x = y) & Dz) -> ((z = x) v (z = y))]
I don't know if I should have used the exclusive "or", but since it's not familiar and we already have that ~(x = y), I don't think it's needed. Now we can get rid the extra conjuncts:
ExEyAz[(Dx & Dy & Dz & ~(x = y)) -> ((z = x) v (z = y))]
Something doesn't seem right. I want to say that
ExEy(Dx & Dy & ~(x = y))
I don't want to say if ... then ... so I don't think I want it in the implication. Instead:
ExEyAz[(Dx & Dy & ~(x = y)) & (Dz -> ((z = x) v (z = y)))]
Now I'm saying if there is another constant- any constant- then it will be equal to one of the first two. Final answer ;) Correct?
Notice the formula for exactly one can be written as:
ExAy(Dx & (Dy -> x = y))
Which has the same general form as my best guess (seeing a pattern?), making me more confident. But...
 
  • #34
Thanx honestrosewater, I will try writing the formulas down.
 
  • #35
I hope you're not giving up- you're almost there. You can say it in English: There exist n edges[/color] and none of them are the same[/color] and if y is an edge, then y is the same as one of the edges already named[/color]. So just take it a step at a time.
There exist n edges:[/color]
Ex1Ex2...Exn[Dx1 & Dx2 & ... & Dxn][/color]
and none of them are the same:[/color]
Ex1Ex2...Exn[Dx1 & Dx2 & ... & Dxn[/color] & ~(x1 = x2) & ... & ~(xn-1 = xn)][/color]
You can shorten that to:
Ex1Ex2...Exn[Dx1 & Dx2 & ... & Dxn[/color] & ~((x1 = x2) v ... v (xn-1 = xn))][/color]
and if y is any edge, then y is the same as one of the edges already named:[/color]
Ex1Ex2...ExnAy[/color][Dx1 & Dx2 & ... & Dxn[/color] & ~((x1 = x2) v ... v (xn-1 = xn))[/color] & (Dy -> ((y = x1) v (y = x2) v ... v (y = xn)))][/color].
Now that I've slept on it, I'm almost certain this is correct. If you have a teacher, you can ask them. I don't have a teacher to ask, but just thinking it through, it makes perfect sense to me. Does it make sense to you?
BTW, I hope I'm not annoying you- just tell me and I'll drop it.
 
  • #36
Also, you need one ~(xa = xb) for every combination of a and b. So to say there are 6 edges you need C(6, 2) = 15 different ~(xa = xb).
 

Similar threads

Undergrad On the meaning of logical implication within specific context/models
  • · Replies 22 ·
Replies
22
Views
3K
Graduate Second-order arithmetic
  • · Replies 34 ·
2
Replies
34
Views
3K
Undergrad About the undecidability of first-order-logic
  • · Replies 26 ·
Replies
26
Views
4K
High School Are Implication and Equivalence Interchangeable in Logic?
  • · Replies 9 ·
Replies
9
Views
2K
Undergrad Questions about SMT logic solvers
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Correlation vs causality implied by a graph
  • · Replies 45 ·
2
Replies
45
Views
4K
Undergrad Number of edges in a tree digraph
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Proof involving functional graphs and the injective property
  • · Replies 3 ·
Replies
3
Views
1K
Undergrad Why the emphasis on first-order logic?
  • · Replies 9 ·
Replies
9
Views
2K
MHB Are Events in Random Graphs from G(n, 1/2) Independent?
  • · Replies 1 ·
Replies
1
Views
2K