First order language

From Maths
Revision as of 05:06, 8 September 2016 by Alec (Talk | contribs) (Created initial version of page.)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Provisional page grade: A
This page is provisional
This page is provisional and the information it contains may change before this notice is removed (in a backwards incompatible way). This usually means the content is from one source and that source isn't the most formal, or there are many other forms floating around. It is on a to-do list for being expanded.The message provided is:
Needed for set theory
Stub grade: A
This page is a stub
This page is a stub, so it contains little or minimal information and is on a to-do list for being expanded.The message provided is:
Tasks:
  1. Expand on the logical connective symbol caution.
There are notes on this topic

Definition

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

See next

  • Term - the set of all terms is denoted [ilmath]\mathscr{L}_T[/ilmath]
  • Formula - the set of all formulas is denoted [ilmath]\mathscr{L}_F[/ilmath]

TODO: Add more


References

  1. 1.0 1.1 1.2 Mathematical Logic - Foundations for Information Science - Wei Li

Template:Formal logic navbox