8
$\begingroup$

I was thumbing through my bro's logic book and got caught far longer than I expected. I got to the point where what they call first-order logic is introduced, but I don't understand why they define constant symbols. It looks to me as if everything that can be done with them could also be done with free variables. Looks a bit pointless to me. Usually I'd ask my bro but he is on the road for a week, so I hope some of you might help me. Thx!


To ask more specific: What can I do or express with a set of sentences with $n$ constant symbols that I can't express with a set of formulas with $n$ free variables but no constants?

  • 1
    Constants are not absolutely needed. They do make things more pleasant in many situations, including the construction of models, and in applications of the Compactness Theorem. In various formal theories, such as field theory, or Peano Arithmetic, it is useful to have constant symbols. They make the axioms more natural, more understandable.2012-01-22
  • 0
    So it is nothing more than a convenience like "p->q" is for "not p or q"?2012-01-22
  • 0
    @André: I disagree. Without constant symbols it is impossible to write down e.g. the first-order theory of groups with an element of infinite order.2012-01-22
  • 0
    @Zhen Lin: Certainly true, unless one cheats by introducing additional function symbols.2012-01-22
  • 0
    Why? Shouldn't something like: 1. for all x,y: f(x,f(y,z))=f(f(x,y),z) 2. for all x: f(x, e) = x 3. for all x: f(e, x) = x 4. for all x exists y: f(x, y) = e 5. (one for each n>=1) not f^n(c,c) = e 6. not c = e do the trick (c and e are free variables)?2012-01-22
  • 0
    @alexis: The usual definition of truth for formulas with free occurrences of variables is to interpret these variables to be *universally quantified*. (Some presentations don't bother to assign truth value to formulas with free variables.)2012-01-22
  • 0
    @André: In the book an interpretation J=(S,f) is defined as a structure S and a (variable-)assignment f. When "satisfies" is defined, an unquantified variable x gets the value f(x) which still seems to me to be the same as c^S for a constant c. I haven't read anything yet towards free variables being universally quantified. Please explain further.2012-01-22
  • 0
    @alexis: how would you axiomatize, in usual first-order logic, but without constant symbols, a group which has an element that is not of finite order?2012-01-22
  • 0
    @CarlMummert As I described in my comment above. Sorry that layout got screwed.2012-01-22
  • 0
    @alexis: the set of formulas that you have above would be true in a group that has no elements of infinite order, but does have for each $n$ an element of order $n$. Well, if you tweak them to make them syntactically correct (what is $f^n(c,c)$ when $f\colon G^2\to G$?) and to make them consistent.2012-01-22
  • 0
    @Carl Mummert: about that group, what if you let $\Phi_n$ be the axiom: " $\lnot (\forall g)(g=e \vee g^2 = e \vee \cdots \vee g^n = e)$", where $x=e$ is an abbreviation for the formula "$(\forall h)(hx=h)$" and add the axiomscheme $(\Phi_n)_{n\in\mathbb N}$ ?2012-01-22
  • 0
    @Myself: that scheme says there is no bound on the orders but not that there is an element of infinite order. The product of all finite cyclic groups has no bound on orders of elements but no element of infinite order.2012-01-23
  • 0
    @CarlMummert: I hope that the axioms 1-4 and 6 are correct/clear. But yes, I made a mistake with axiom 5. Let me try again, I hope I get the TeX markup right: $\{ \neg f(c, f(c, f(c, ... f(c,c))...)) = e | \forall n >= 1\ \mbox{ applications of }\ f \}$. Together with the other axioms shouldn't this cause the variable c to be mapped to an element of infinite order?2012-01-24

2 Answers 2

9

Variables and constants serve distinct purposes in first order logic, and for that reason behave differently on a syntactic level.

The "scope" of a variable (in a sentence) is only in the formula in which it is defined, or the subformula where it is being quantified over. It serves not to distinguish a specific element, but to represent a set of possible elements. When a variable (in a formula) is interpreted in a structure, it can (and often should) be interpreted in different ways. In a sense, a variable only acquires identity in a particular interpretation inside a structure: in a theory, it is a placeholder. It is this understanding that allows us to quantify over variables.

Constants, however, are much more global. One can reuse a constant in many different formulas, so as to connect them. For example, if I wanted to talk about constant $c$ larger than all natural numbers, I could write $c > 0, c > S(0), \cdots$, an infinite family of formulas. To interpret these formulas in a structure, I would need a number greater than all natural numbers. If $c$ were merely a variable, I would have to write $\exists x ( x > 0), \exists x (x > S(0)), \cdots$: each formula would be disjoint from the other, and I interpret this collection of formulas in $\mathbb{N}$, even though it contains no element larger than all natural numbers. Moreover, certain theories (such as the theory of groups), make use of a distinguished element (such as the identity element). We would like to talk about that distinguished element, rather than treating it as a placeholder, which it is not. We would not want to consider all possible ways of interpreting elements in a group as the identity element: for a fixed group, there is a fixed identity element. As a result, one might say that constants have identity even in a theory, and indeed we introduce new constants to our language if we want to talk about larger models.

  • 0
    So it is just an oddity of this book that interpretations are defined to have a variable assignment that is global to all formulas?2012-01-22
  • 0
    No. It's just that variables in sentences of a theory are quantified over, so the global assignment of meaning to variables is only important in the model.2012-01-22
  • 0
    To clarify: when you interpret formulas in a model, you need to have a variables be interpreted the same way in all formulas. The difference emerges in a theory, when you are only allowed sentences . In that context, variables are always quantified over, as they solve as placeholders. It's precisely because we think of them as placeholders that we can interpret them differently in the same structure. However, constants are never quantified over, because their meaning shouldn't be ambiguous. A constant in a theory is like "3" in arithmetic.2012-01-22
  • 0
    But doesn't a set of formulas with $n$ free variables and no constant symbols provide the same expressive power as a set of formulas with $n$ constant symbols and no free variables?2012-01-27
0

A "pointed set" is a set together with a distinguished element $*$. The first-order language used to describe such a structure has one constant symbol "$*$" and the usual logical symbols. There are no additional axioms.

The first-order language for "real-closed field" has constant symbols $0, 1$, operation symbols (binary function symbols) $+, \times$ and binary relation symbol $\lt$. There are then some axioms describing properties that these must satisfy.

I don't know if these are what you are driving at, or completely off the mark...