First-order logic : repesenting graphs

[nounou]

How can we write a sentence in first-order logic that says that a graph has exactly 6 edges? i.e. G= (V,E) (logically implies) iff |E|=6

 

[Hurkyl]

Start simple. Replace 6 with 0. Can you figure out how?
Replace 6 with 1. Can you figure out how?
Replace 6 with 2. Can you figure out how?

 

[nounou]

Actually no. I'm having trouble to represent the number of edges. I can express that there is an edge in a graph:

There_Exists_x There_exists_y edge(x,y).

but how can I express that there are n edges in the graph.

Any ideas ?

 

[Hurkyl]

Hrm. Your variables, then, must range over the vertices of the graph, and you assume that there is exactly one edge between a given pair of vertices?


Anyways, so you've managed to solve (the complement of) my first problem: how to express that a graph has no edges.


So let's move onto the next: how to express that a graph has a single edge... have you ever expressed before the notion that there is one (and only one) object that satisfies a given property?

 

[nounou]

Im sorry. I don't know how to. I'm not so good at this.Any hints?

 

[Hurkyl]

You've never had to express something like:

"This equation has a unique solution"?

 

[nounou]

Ok... So, what does this have to do with that?

 

[Hurkyl]

You want to say "This graph has a unique edge".

 

[nounou]

Ok. But a certain number of edges. I'm sorry if I am not getting what u mean. I'm not a mathematician by any means. Can u give me a simple sentence ?just to help me start and I will build up on it.

 

[Hurkyl]

I'm saying that you should fully tackle the question of expressing the statement "This graph has exactly one edge" before moving on to the tougher statement "This graph has exactly six edges".


You've already given a sample statement: You encoded: "This graph has at least one edge" as:

Ex Ey: edge(x, y)

Maybe you should explicitly write out the solution to my first exercise before moving onto the next: how can you encode: "This graph has zero edges"?

 

[nounou]

Ex Ey: ~edge(x,y)

Is this what u mean ?

 

[Hurkyl]

That's not correct. For example, take this graph:

A B---C

This graph has three vertices and one edge.

Your statement "Ex Ey: ~edge(x, y)" is true for this graph -- for example, I can select x=A and y=B, and then "~edge(A, B)" is a true statement. However, the graph obviously does not have zero edges!


In English, your statement says: "There exists a pair of vertices that don't have an edge between them". Do you see why?

 

[nounou]

Yes I do. Maybe i can use

ForAll_x ForAll_y : ~edge(x, y)

?

 

[Hurkyl]

Yes, that one's exactly right. It says "For any pair of vertices, there does not exist an edge between them."


Now onto exactly one edge...

You already know how to say "This graph has at least one edge".


I suggested considering the statement "This equation has a unique solution" because the expression of this statement in logic involves a useful trick that applies directly here...

Another way to think about it is this: can you say "This graph does not have two distinct edges"?

Or what about it's complement? "This graph has at least two distinct edges"

 

[nounou]

I have no clue. Do u have any hints on how to express that it has 2 distinct edges ?

 

[Hurkyl]

Okay, suppose you know that your graph has only one edge.

I take two sheets of paper. On the first sheet of paper, I write down the name of an edge in your graph. On the second sheet of paper, I write down the name of an edge in your graph.

What can you tell me about the two sheets of paper?

 

[nounou]

they contain the same edge, since my graph has only one edge

Ex Ey edge(x,y) , x=y

?

 

[Hurkyl]

they contain the same edge, since my graph has only one edge

Bingo -- and as you realize, what you need to do is to figure out how to encode that into your statement!

In other words, if we've written down the names of two edges, the names should be the same.

 

[nounou]

So is this a correct statement in first-order logic

Ex Ey edge(x,y) , x=y

 

[Hurkyl]

Nope. That statement says:

There exists two vertices such that there is an edge between them. Oh, and those two vertices happen to be equal!

(Or, in less verbose language, it's saying there's a vertex with a loop on it)

 

[nounou]

Oh . I c. But how can I actually count the edges??

 

[Hurkyl]

Let me give the outline of what I'm trying to guide you along doing:

(1) You've figured out how to say "There is exactly 0 edges"
(2) You've figured out how to say "There is at least one edge"

I want you to figure out how to day:
(3) "There is at most one edge"
And then you can put (2) and (3) together to say "There is exactly one edge".

Then, I want you to figure out:
(4) "There is at least two edges"
(5) "There is at most two edges"
And then you can put (4) and (5) together to say "There is exactly two edges"

These examples should be enough for you to see a pattern, and you can continue on to figure out how to say "There is exactly six edges".



Anyways, back to (3). You've figured out how to talk about a single edge, by using two variables denoting its endpoints. To talk about two edges, how many variables should you need?

 

[nounou]

four. I guess, but would that mean that to represent n edges I must have 2^n variables?

 

[nounou]

Is this it ?

Ex Ey Ez Ew edge(x,y), edge(z,w)

?

 

[Hurkyl]

Not 2^n, but 2*n. (Two variables per edge)

So your latest statement, "Ex Ey Ez Ew edge(x,y), edge(z,w)", says:

"There exists an edge, and there exists an edge"

(Of course, they could be the same edge)

But now you're talking about two edges, so you can start to work on the two problems involving two edges:

You still need to figure out how to say "Any two edges are equal!" (which is the same thing as "There is at most one distinct edge")

And next, you'll have to figure out how to say "There exist two distinct edges". (Which is the same thing as there exist two edges which are not equal)

 

[Hurkyl]

(BTW, I have to log off for the day -- I hope this has helped!)

 

[nounou]

It really has. Thanx alot

 

[honestrosewater]

nounou,
You've made statements with only existential quantifiers and with only universal quantifiers. Try combining existential and universal quantifiers into one statement.
Edit: Eh, I can't type today.

 

[nounou]

Thanx Hurkyl, honestrosewater

Can u help me with this:

E_x ForAll_y edge(x,y) x\= y

Is this wrong?

 

[honestrosewater]

Try unary predicates first. Let A and E denote the universal and existential quantifier and Dx mean "x is an edge".
There exists at least one edge:
Ex(Dx).
There exists at most one edge: For all x and all y, if x and y are edges, then x and y are the same edge:
AxAy((Dx & Dy) -> x = y).
There exists at least one edge and there exists at most one edge: There exists exactly one edge: There exists a unique edge:
Ex(Dx) & AxAy((Dx & Dy) -> x = y) : Ex(Dx & Ay(Dy -> x = y).

\exists ! is sometimes used as an abbreviation;
\exists !x(Px) \Leftrightarrow \exists x(Px \wedge \forall y(Py \rightarrow x = y)
It's called the unique existential quantifier or uniqueness quantifier or something similar. Now can you say there exist exactly two edges?
BTW, I happen to know about the uniqueness quantifier, but I don't really know a lot about quantifiers, so Hurkyl will have to take it from here, or I'll have to catch up quickly.

 

[nounou]

Thanx honestrosewater. Hurkyl, any hints?

 

[nounou]

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

 

[honestrosewater]

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...

 

[nounou]

Thanx honestrosewater, I will try writing the formulas down.

 

[honestrosewater]

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]
Ex₁Ex₂...Ex_n[Dx₁ & Dx₂ & ... & Dx_n][/color]
and none of them are the same:[/color]
Ex₁Ex₂...Ex_n[Dx₁ & Dx₂ & ... & Dx_n[/color] & ~(x₁ = x₂) & ... & ~(x_n-1 = x_n)][/color]
You can shorten that to:
Ex₁Ex₂...Ex_n[Dx₁ & Dx₂ & ... & Dx_n[/color] & ~((x₁ = x₂) v ... v (x_n-1 = x_n))][/color]
and if y is any edge, then y is the same as one of the edges already named:[/color]
Ex₁Ex₂...Ex_nAy[/color][Dx₁ & Dx₂ & ... & Dx_n[/color] & ~((x₁ = x₂) v ... v (x_n-1 = x_n))[/color] & (Dy -> ((y = x₁) v (y = x₂) v ... v (y = x_n)))][/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.

 

[BicycleTree]

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).