Difference between revisions of "First order language"

Latest revision as of 10:45, 8 September 2016

There are notes on this topic

Definition

A first order language, $\mathcal{L}$ consists^[1] of two types of symbols, non-logical and logical, these are described in the tree below:

• Non-logical symbols - these are the same for all first order languages
  • $V$ - The set of (at most countably many, possibly empty) variable symbols: $x_1,x_2,\ldots,x_n,\ldots$
  • $C$ - The set of logical connective symbols. Caution:Not all of these are needed, you can write some in terms of others
    1. $\neg$ - logical not
    2. $\wedge$ - logical and
    3. $\vee$ - logical or
    4. $\rightarrow$ - logical implication, "if ... then ..."
    5. $\leftrightarrow$ - logical equivalence (AKA: if and only if)
  • $Q$ - The set of quantifier symbols. Caution:Given $\neg$ you can define $\forall x(A)$ as $\neg(\exists x(\neg(A)))$ or define $\exists x(A)$ as $\neg(\forall x(\neg(A)))$
  • $E$ - The set containing the equality symbol. We will use $\doteq$ for this (to separate it from equality in the meta-language)
  • $B$ - The set of brackets, that is "(" and ")".
    • AKA: $P$ - for "parentheses", but you know it's BODMAS not "PODMAS".
• Non-logical symbols - these vary from language to language
  • $\mathscr{L}_c$ - the set of (possibly zero, at most countably many) constant symbols, $c_1,c_2,\ldots,c_n,\ldots$.
  • $\mathscr{L}_f$ - the set of (possibly zero, at most countably many) function symbols.
    • Each function has an arity, and we write $ft_1t_2\cdots t_m$ for an $m$-ary function (here the $t_i$ are terms)
      • Here $m\ge 1$^[1] Caution:This is disputed, Kunen's Set Theory gives an example of $0$-ary predicates and functions!
  • $\mathscr{L}_P$ - the set of (possibly zero, at most countably many) predicate symbols, $P_1,P_2,\ldots,P_n,\ldots$.
    • Each predicate has an arity and we write $Pt_1t_2\cdots t_m$ for an $m$-ary predicate symbol. Here the $t_i$ are terms
      • Here $m\ge 1$^[1] Caution:This is disputed, see caution above

See next

• Term - the set of all terms is denoted $\mathscr{L}_T$
• Formula - the set of all formulas is denoted $\mathscr{L}_F$
  • Sentence - a special kind of formula
• Structure
  • Domain
  • Interpretation
• Model
  • Assignment

TODO: Add more

References

1. ↑ ^{Jump up to: 1.0 1.1 1.2} Mathematical Logic - Foundations for Information Science - Wei Li

Template:Formal logic navbox