Some Basics

Variables

p. 24

See how the Fates their gifts allot,
For %$A$% is happy—%$B$% is not,
Yet %$B$% is worthy, I dare say, Of more prosperity than %$A$%.
                     (The Mikado, Gilbert and Sullivan)

---

Philosophers often use the symbolism of formal first-order predicate logic as a kind of substitute for English.

Logic Symbols
%$\forall ,\Pi$%,()	for all
%$\exists ,\Sigma$%	there is at least one there are
%$\land ,\&$%	and
%$\lor$%	or
%$\lnot ,\APLnot{}$%	not
%$\rightarrow ,\supset $%	if then
%$\iff ,\equiv$%	if and only if
%$\square , L$%	necessarily
%$\lozenge , M$%	possibly

Use vs Mention

Socrates is a philosopher.

'Socrates' has three syllables.

I am Shaughan.

My name is 'Shaughan.'

My name's name is ''Shaughan.''

My name's name, ''Shaughan,'' is spelled with one pair of single quotes.

My name, 'Shaughan,' has no quotes in it.

Every collection has something not in it, an argument

Let %$S$% be a collection. Let %$R$% be the collection of all things in %$S$% that are not collections that are members of themselves: %\[R=\{x\in S:x\notin x\}\]% Suppose %$R$% is in %$S$%. Is %$R$% in %$R$%? If %$R$% is in %$S$%, then %$R$% is in %$R$% if and only if %$R$% is not in %$R$%, which is impossible. Thus, %$R$% is not in %$S$%.

Now, apply what we just showed to %${\bf U}$%, the collection of absolutely everything. If we let %$U$% be the %$S$% in the argument above, we see that the %$R$%, the collection of absolutely everything that is not a collection that is a member of itself, is not in %$S$%, contradicting that %${\bf U}$% is absolutely everything. Thus, there can be no such thing as everything!

---

More Notation

Variables: %$u,v,w,x,y,z$%

Constant symbols: %$a,b,c,d,e,i,l,m,n$%

Special constant symbols: %$0,1,\varnothing ,\text{'Socrates'}$%

Function symbols: %$f,g,h$%

Special function symbols: %$+,\cdot ,\text{'the mother of,'} \cup ,\cap ,\setminus$%

Relation symbols: %$A,\dots ,T$%

Special relation symbols: %$\in ,<, \text{ \rule{1em}{0.5pt} is between \rule{1em}{0.5pt} and \rule{1em}{0.5pt}}$%

Relation variables: %$U,\dots ,Z$%

Structures (Models)

A language is just a set of constant, function, and relation symbols. We (nearly) always take = to be in every language even if it is not explicitly listed. The language of arithmetic, for example, might be %$\{0,S,+,\cdot ,<\}$%.

A structure for a language is the following list of data: a nonempty domain, an object in the domain for each constant symbol in the language, a function on the domain for each function symbol in the language (example—'+' stands for %$\{\langle 0,0,0\rangle ,\langle 2,2,4\rangle ,\dots\}$%, and a relation on the domain for each relation symbol in the language (example—< stands for %$\{\langle 0,1\rangle ,\langle 5,234342 \rangle ,\dots\}$%.

A theory in a language is just a set of sentences in the language. A model of a theory is just a structure for the language of the theory in which all of the sentences in the theory are true.

An interpretation of a language is the following list of data: a description of a domain (the domain is the natural numbers), the name of an object for each constant symbol in the language (example—'0' stands for zero), a description of a function for each function symbol in the language ('+' stands for addition), and a description of a relation for each relation symbol in the language ('<' stands for less than).

In ordinary language, we generally use the word language not for an empty set of symbols, but for a system of symbols that have a use. Thus, in ordinary and philosophical language, we use the word 'language' to stand either for a structure or an interpretation (essentially never for a language in the mathematical sense). Be careful!

---

Tarski said, and it is widely accepted, that a sentence %$\phi$% is a logical consequence of a set %$\Gamma$% of sentences if %$\phi$% is true in every model of %$\Gamma$%.

We can devise a purely syntactic set of rules for going from some sentences to others. (Example: we can go from %$p\land q$% to %$p$%.) A proof of %$\phi$% from %$\Gamma$% is a list of sentence such that the last sentence is %$\phi$% and such that every sentence on the list is either a member of %$\Gamma$% or follows from previous sentences by the rules.

A sentence %$\phi$% is provable or derivable from %$\Gamma$% if there is a proof of %$\phi$% from %$\Gamma$%.

Important but obvious fact:

If %$\phi$% is derivable from %$\Gamma$%, then %$\phi$% is a logical consequence of %$\Gamma$%.

Definition:

First-order logic is logic with no capitalized variables.

Surprising and important fact:

Standard proof systems for first-order logic are complete: If %$\phi$% is a logical consequence of %$\Gamma$%, then %$\phi$% is derivable from %$\Gamma$%.

-- ShaughanLavine - 15 Jan 2009