Notes:First order language

Sources:

1. Books:A Course on Mathematical Logic - Shashi Mohan Srivastava(ref)
2. Books:Mathematical Logic - Foundations for Information Science - Wei Li(ref)

The reference will be used when the books agree.

Summary

From my reading I can basically conclude:

• We define first order languages according to a grammar, anything that results from this is a thing in the language, regardless of whether or not it is "utter crap" and the problem of saying whether something is true or false isn't easy, perhaps even possible, but we can say "given this (these) thing(s) then this other thing follows"

Definitions

First Order Language

The references have not been closely compared and were studied separately (months apart) A first order language consists of two types of symbol:

1. Logical symbols (which are the same for all FOLs)
   1. Variable symbols - at most countably many and may be empty, [ilmath]x_1,x_2,\ldots[/ilmath] used for both. The [ilmath]x_1,x_2,\ldots[/ilmath] order is called the alphabetical order
   2. Logical connective symbols - Which are: [ilmath]\neg,\ \wedge,\ \vee,\ \rightarrow[/ilmath] and [ilmath]\leftrightarrow[/ilmath]
      • Disputed, uses few (2) connectives and shows the rest can be constructed from these. It should be easy to "unify them"
   3. Quantifier symbols - [ilmath]\forall[/ilmath] and [ilmath]\exists[/ilmath]
   4. Equality symbol - the set containing [ilmath]\doteq[/ilmath]
   5. Parenthesis symbols - [ilmath]([/ilmath] and [ilmath])[/ilmath]
2. Non-logical symbols (which vary from theory to theory), there are 3 kinds
   1. [ilmath]\mathscr{L}_c[/ilmath] - the set of constant symbols, at most countably many of them, [ilmath]c_1,c_2,\ldots[/ilmath]
   2. [ilmath]\mathscr{L}_f[/ilmath] - the set of function symbols, at most countably many of them, [ilmath]f_1,f_2,\ldots[/ilmath], [ilmath]fx_1\ldots x_m[/ilmath] denotes an [ilmath]m[/ilmath]-ary function symbol, for [ilmath]m\ge 1[/ilmath] being the number of variable symbols as well as the number of arguments to the function
   3. [ilmath]\mathscr{L}_p[/ilmath] - the set of predicate symbols, at most countably many of them, [ilmath]P_1,P_2,\ldots[/ilmath], [ilmath]Px_1,\ldots x_m[/ilmath] denotes an [ilmath]m[/ilmath]-ary predicate symbol for [ilmath]m\ge 1[/ilmath] being the number of variable symbols as well as the number of arguments to the predicate

We shall use [ilmath]\mathscr{L} [/ilmath] to represent a FOL

Terms

The terms of a FOL, [ilmath]\mathscr{L} [/ilmath] are defined inductively as follows:

1. [ilmath]\mathrm{T}_1[/ilmath] - Each constant symbol is a term
2. [ilmath]\mathrm{T}_2[/ilmath] - Each variable symbol is a term
3. [ilmath]\mathrm{T}_3[/ilmath] - If [ilmath]t_1,\ldots,t_n[/ilmath] are terms and [ilmath]f[/ilmath] is an [ilmath]n[/ilmath]-ary function symbol, then [ilmath]ft_1,\ldots t_n[/ilmath] is a term.

[ilmath]\mathscr{L}_\mathrm{T} [/ilmath] denotes the set of all terms of a FOL [ilmath]\mathscr{L} [/ilmath]. There is a BNF form of these, but it is trivial to show from the above so I wont rewrite it.

It seems that it is impossible to write crap at this point as a term is just a variable, or a constant, of a function of some (functions of) variables and constants.

Logical formulas

The logical formulas of a FOL [ilmath]\mathscr{L} [/ilmath] (or just "formulas" for short) will be represented by uppercase symbols, [ilmath]A,\ B,\ldots[/ilmath], They are defined inductively as follows:

1. [ilmath]\mathrm{F}_1[/ilmath] - For [ilmath]t_1,t_2\in\mathscr{L}_\mathrm{T} [/ilmath] then [ilmath]t_1\doteq t_2[/ilmath] is a formula.
2. [ilmath]\mathrm{F}_2[/ilmath] - For [ilmath]t_1,\ldots,t_n\in\mathscr{L}_\mathrm{T} [/ilmath] and [ilmath]P[/ilmath] is an [ilmath]n[/ilmath]-ary predicate, [ilmath]Pt_1\ldots t_n[/ilmath] is a formula.
3. [ilmath]\mathrm{F}_3[/ilmath] - If [ilmath]A[/ilmath] is a formula, then so is [ilmath](\neg A)[/ilmath]
4. [ilmath]\mathrm{F}_4[/ilmath] - If [ilmath]A[/ilmath] and [ilmath]B[/ilmath] are formulas, then so are [ilmath](A\wedge B)[/ilmath], [ilmath](A\vee B)[/ilmath], [ilmath](A\rightarrow B)[/ilmath] and [ilmath](A\leftrightarrow B)[/ilmath]
5. [ilmath]\mathrm{F}_5[/ilmath] - If [ilmath]A[/ilmath] is a formula and [ilmath]x[/ilmath] a variable, then both [ilmath]\forall xA[/ilmath] and [ilmath]\exists xA[/ilmath] are formulas. We call [ilmath]x[/ilmath] a bound variable

Additionally:

• Formulas defined by just [ilmath]\mathrm{F}_1[/ilmath] and [ilmath]\mathrm{F}_2[/ilmath] are called atomic formulas; the rest are composite formulas.

[ilmath]\mathscr{L}_\mathrm{F} [/ilmath] denotes the set of formulas of a FOL [ilmath]\mathscr{L} [/ilmath].

Crap is now possible; like [ilmath](x\doteq y)\wedge(x\not\doteq y)[/ilmath], however there are 2 kinds of crap, the first is that which is always crap, like the example I just gave, and some things which are crap given a certain set of assumptions

---

OLD PAGE

All from Books:A Course on Mathematical Logic - Shashi Mohan Srivastava

Definition

A first order language, [ilmath]L[/ilmath], consists of two types of symbols:

1. Logical symbols
   • A sequence of variables, [ilmath]x_1,x_2,\ldots[/ilmath] (this is the alphabetical order of the variables)
   • logical connectives, [ilmath]\neg[/ilmath] (negation), [ilmath]\vee[/ilmath] (disjunction - posh way of saying "or"),
   • a logical quantifier [ilmath]\exists[/ilmath] (existential qualifier) and
   • the equality symbol, [ilmath]=[/ilmath]
2. Non-logical symbols (which vary from theory to theory)
   • A set of constant symbols, [ilmath]\{c_i\vert i\in I\} [/ilmath],
   • for each positive integer, [ilmath]n\in\mathbb{N}_{\ge 1} [/ilmath] a set of [ilmath]n[/ilmath]-ary function symbols, [ilmath]\{f_j\vert j\in J_n\} [/ilmath]
   • for each positive integer, [ilmath]n\in\mathbb{N}_{\ge 1} [/ilmath] a set of [ilmath]n[/ilmath]-ary relation symbols, [ilmath]\{p_k\vert k\in K_n\} [/ilmath]

Terminology

• Expression - any finite sequence of symbols of a language.