FO (complexity) - Logic Without Arithmetical Relations

Logic Without Arithmetical Relations

Let the successor relation, succ, be a binary relation such that is true if and only if .

Over first order logic, succ is strictly less expressive than <, which is less expressive than +, which is less expressive than bit. + and are as expressive as bit.

Read more about this topic:  FO (complexity)

Famous quotes containing the words logic and/or relations:

    The logic of the world is prior to all truth and falsehood.
    Ludwig Wittgenstein (1889–1951)

    Actually, the laboring man has not leisure for a true integrity day by day; he cannot afford to sustain the manliest relations to men; his labor would be depreciated in the market.
    He has no time to be anything but a machine.
    Henry David Thoreau (1817–1862)