First-order logic : repesenting graphs

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