So. We want to be able to look at logic from a formal, rigorous perspective-- which means we need to define logic formally. The guiding question when defining it should be: What does a logic look like? We want variables and all the fun logical connectives, and we want them to mean something, and we want all the meanings (eventually) to boil down to the question "Is this statement true?".

So, let's make each of those happen, one at a time;

First, we need some symbols. We will call S our

**alphabet**-- the set of symbols. This may be tediously formal, but it must be done. Since we want to create a logic, we need the logical symbols: So S contains the connectives and quantifiers, (I'm not going to list them) and just as importantly: variables. These are our

**logical symbols**. Since this is

*mathematical*logic, we need some mathy

**non-logical symbols**; these will be

**constant symbols**,

**relation symbols**and

**function symbols**(these will also "look like" variables, but we want to distinguish between them for reasons we will see shortly). We will also consider '=' to be a logical symbol-- I know it's a relation, but it's a special one, and we want to keep it special.

So, we have a bunch of symbols; that doesn't do us much good, so let's let S* be the set of finite sequences from S. Namely, the empty sequence (I'll use _|_) is in S*, S is a subset of S*, and if a and be are in S, ab (the concatenation of a and b) is in S*.

We want to define a

**language**, L, as a subset of S*, but while any subset is a language, we don't want just any subset: it has to be something that we can "read" in a meaningful way. We have to define our language inductively, and piece by piece. I'll let you know when we get there.

Let the set of

**L-terms**(or just terms) be the smallest T such that:

- V (the set of variables) is in T.
- C (the set of constant symbols) is in T.
- Whenever t_1,...t_k are in T, and f is a k-ary function symbol, f(t_1,...,t_k) is in T.

A term is an object which we can equip with some non-logical value, which may need some sort of context (a value for a variable). But a term does us no good on its own, if we are interested in logical values. So, an atomic formula is:

- if t, u are terms, then "t=u" is an atomic formula.
- if t_1,...,t_k are terms, and R is a k-ary relation symbol, then R(t_1,...,t_k) is an atomic formula

The set of L-formulas (or just formulas) is defined inductively:

Base case: Atomic formulas are formulas.

Closure: The set of formulas is closed under logical connectives, and quantifiers.

(What this means is that if you have two formulas, p and q, you can connect them using a logical connective, and you can quantify them, and the sequence of symbols you create will also be a formula.)

So, we now have something that

*looks like*the logic we know. But there is a problem: if x and y are variables, "x=y" is a valid formula. But what are x and y?

In that formula, both x and y are

**free variables**. For a given formula the free variables are :

- (for s, t terms) FV(s=t)= var(s)Union var(t) [var(t) means the variabls in t]
- (for R a k-ary relation) FV(R(t_1,...,t_k))= Union(t_i)(over 1≤i≤k)
- (for ~ a logical connective, a,b formulas) FV(a~b)= FV(a)UnionFV(b)
- (for x a var, b a formula) FV(forall x, b)= FV(there exists x, b)= FV(b)\{x}

So finally, we have: A sentence is a formula with no free variables, and

*our*logical language, L, is the set of all sentences from S*.

Cool! We have a logical language. Looking back at our list of things we want, we've got connectives, and we've got quantifiers and just a little bit more. Unfortunately, this means we're not quite done: this language is meaningless. We haven't once said what these symbols

*actually mean*. And we will learn how to do that next time.

## No comments:

Post a Comment