Re: Finitely Valid Formula



William Elliot wrote:
herbzet wrote:

Can an FOL formula be valid in every finite domain, yet be
invalid in some infinite domain?

Yes. Let the FOL language include a binary relation <= and axioms
for a linear order. What statement is valid in every finite
domain that's not valid in some infinite domains?

No. A for <=, is
(Ax).x <= x
(Ax,y)((x <= y)&(y <= x) -> x = y)
(Ax,y,z)((x <= y)&(y <= z) -> x <= z)
(Ax,y)((x <= y) v (y <= x))

Thus
A -> (Ax,y,z)((x <= y)&(y <= z) -> x <= z)
is an instant of a tautology. What holds for all finite linear orders
that doesn't hold for the integers, the rationals or the reals?

1) ExAy (x <= y)
2) ExAy (y <= x)

Existence is unique.

True, but I couldn't think of how to say that simply.

(E!x)(Ay)(x <= y)
(E!x)F(x), there exists exactly one x such that F(x), is defined as
(Ex)F(x) & (Ax,y)(F(x) & F(y) -> x = y)

OK, good. (Uses "=")

So either A -> ExAy(x <= y) or A -> ExAy(y <= x) would fill the bill.

Can't help mentioning the second axiom contains a sign for equality! :-)

Ok, you want FOL without equality? Then let's see, axioms for < are
(Ax)~(x < x)
(Ax,y,z)(x < y & y < z) -> x < z)
and for total order, hm..
(Ax,y)(x < y or x = y or y < x).

Oops, there's that sign for equality again!

Ok, lets use total quasi order

Total order? Total quasi order? You overestimate me.

A total order is the same as a linear order.
A quasi order is an order without asymmetry.
Below are the axioms for a total quasi order.
They're the same as the axioms for a total or linear order
except for omitting asymmetry, (a <= b <= a) -> (a = b).

(Ax)(x <= x)
(Ax,y,z)(x <= y & y <= z -> x <= z)
(Ax,y)(x <= y or y <= x)

What changes regards your solution?

Not sure at this point what axioms we are/aren't using.

FOL (without equality) and the three immediately above for <=.
What changes regards your solution?

My solutions are still good. They lose the property of necessarily
being unique endpoints.

Somehow it seems there's a better answer, but I can't think of it.

a) I thought you might just define "=" to use in conjunction with
the first set of four axioms. Would the following axioms
be sufficient?

A first order language with equality FOL_=, has a binary relation constant
= and the axioms for equality: identity axiom and substitution schemata:
(Ax)(x = x)
(Axy)(x = y -> (P(x) -> P(y)))

Let P_s(x) be x = s. Use P_x(x) to show equality is symmetrical and then
use P_z(y) to show equality is transitive, (x = y)&(y = z) -> (x = z).

Ax(x = x)
Axy[(x = y) -> (y = x)]
(Maybe we need a biconditional?)
No, prove the other implication from the first.

OK. I guess that _was_ obvious.

That axiom is symmetry.

Axyz[((x = y) & (y = z)) -> (x = z)]

Those are the axioms for an equivalence relation. You've yet to prove
substitution. However, if you no relation symbols, = is the only relation
constant and you have no function symbols or constants, then you have
substitution. Alternative axioms:
(Ax)(x = x)
(Ax,y,z)((x = y & y = z) -> (z = y))
^^^^^
No doubt you meant "z = x"?

b) I thought you might define "=" in terms of "<=" (instead of
"<=" in terms of "=".) I don't know if that's possible or,
if possible, complicated.

a = b would be (a <= b)&(b <= a).

I thought of that, but if you substitute it for "=" in the second
axiom for linear/total order, you get a tautology.

Immediately is the identity axiom and
for the substitution axiom, you would need prove that by induction over
the length of the statement. Your statements would be limited to FOL with
no relation symbols nor constants except <= and no function symbols nor
constants. If you wanted to included function symbols, you'd likely want
added axioms x <= y -> (f(x) <= f(y) & g(x,z) <= g(x,y)) and the like and
for relation symbols x <= y -> (P(x,z) -> P(y,z)). That should suffice
to establish substitution at the cost of severely limiting relations and
functions.

c) It occurred to me that even if we add to the original four
axioms the formula

ExAy(x <= y) & ExAy(y <= x)

We still don't get only finite sets: the (now five) axioms
would also hold for closed intervals of rationals or reals
(and other infinite sets).

That is so. However you need only one infinite domain for the problem.

Right.

What do call a linear order that is not dense, like the
integers? A sequential order, maybe?

Discrete. (Ax)((Ey)(y < x) -> (Ez).(z < x) & ~(Ea)(z < a < x))
and the order dual statement reversing all a < b with a > b. Hm...
(Ax,y)(x < y
-> (Eu,v).(x < u) & (v < y) & ~(Ea)(x < a < u) & ~(Ea)(v < a < y)

There's another answer: Every finite total order is discrete.

We even could have a (partial) order using < and only
~(Ex)(x < x)
(Ax,y,z)((x < y & y < z) -> x < z)
Then every (partial) finite order is discrete, even anti-chains with
~(Ex,y)(x < y)

???????????? Anti-chains? This seems to wreck the whole idea!
Also it seemms this anti-chain formula implies the two axioms. :-\
I guess that makes sense: if X is an anti-chain, then X is
a partial order. I don't see that an anti-chain must be finite.

In addition every totally ordered finite set is bounded below and above
and is discrete. Find an infinite linear order with the same property.

1/2, 3/4, 7/8, ... (Does "bounded" mean here the bound must be in the
set? If yes, put an x >= 1 at the end).

Every total finite order is well ordered and the reverse order is also
well ordered. There by golly, is a property unique to finite linear
orders. Whoops, well ordered is 2nd order predicate.

Damn!

What do you call an order consisting of the negative reals and the
positive integers?

Mongreloid? Clopen? Total?

Order theory, studying exclusively the transitive, reflexive and
usually asymmetrical <=, is a branch of mathematics.

Interesting stuff.

--
hz
.

Relevant Pages

  • Re: Finitely Valid Formula
    ... and for total order, hm.. ... A total order is the same as a linear order. ... Below are the axioms for a total quasi order. ... However you need only one infinite domain for the problem. ...
    (sci.logic)
  • Re: Finitely Valid Formula
    ... infinite domains, so it's negation is valid only in finite domains? ... and for total order, hm.. ... Not sure at this point what axioms we are/aren't using. ... What do call a linear order that is not dense, ...
    (sci.logic)
  • Re: Finitely Valid Formula
    ... A total order is the same as a linear order. ... Below are the axioms for a total quasi order. ... = and the axioms for equality: identity axiom and substitution schemata: ... The opposite of chain or linear order is anti-chain, ...
    (sci.logic)
  • Re: abundance of irrationals!)
    ... >> A linear order is any structure satisfying the axioms I gave. ... Induction is irrelevant. ... I guess that's what a teacher from Oklahoma State University ...
    (sci.math)