% Part: methods
% Chapter: proofs
% Section: introduction

\documentclass[../../../include/open-logic-section]{subfiles}

\begin{document}

\olfileid{mth}{prf}{int}

\olsection{Introduction}

Based on your experiences in introductory logic, you might be
comfortable with !!a{derivation} system---probably a natural deduction or
Fitch style !!{derivation} system, or perhaps a proof-tree system. You probably
remember doing proofs in these systems, either proving !!a{formula}
or show that a given argument is valid. In order to do this, you
applied the rules of the system until you got the desired end
result. In reasoning \emph{about} logic, we also prove things, but in
most cases we are not using !!a{derivation} system. In fact, most of the
proofs we consider are done in English (perhaps, with some symbolic
language thrown in) rather than entirely in the language of
first-order logic.  When constructing such proofs, you might at first
be at a loss---how do I prove something without !!a{derivation} system?  How
do I start? How do I know if my proof is correct?

Before attempting a proof, it's important to know what a proof is and
how to construct one.  As implied by the name, a \emph{proof} is meant
to show that something is true. You might think of this in terms of a
dialogue---someone asks you if something is true, say, if every prime
other than two is an odd number. To answer ``yes'' is not enough; they
might want to know \emph{why}. In this case, you'd give them a proof.

In everyday discourse, it might be enough to gesture at an answer, or
give an incomplete answer. In logic and mathematics, however, we want
rigorous proof---we want to show that something is true beyond \emph{any}
doubt. This means that every step in our proof must be justified, and
the justification must be cogent (i.e., the assumption you're using is
actually assumed in the statement of the theorem you're proving, the
definitions you apply must be correctly applied, the justifications
appealed to must be correct inferences, etc.).

Usually, we're proving some statement. We call the statements we're
proving by various names: propositions, theorems, lemmas, or
corollaries.  A proposition is a basic proof-worthy statement:
important enough to record, but perhaps not particularly deep nor
applied often. A theorem is a significant, important proposition. Its
proof often is broken into several steps, and sometimes it is named
after the person who first proved it (e.g., Cantor's Theorem, the
L\"owenheim--Skolem theorem) or after the fact it concerns (e.g., the
completeness theorem).  A lemma is a proposition or theorem that is
used in the proof of a more important result. Confusingly,
sometimes lemmas are important results in themselves, and also named
after the person who introduced them (e.g., Zorn's Lemma). A corollary
is a result that easily follows from another one.

A statement to be proved often contains assumptions that clarify
which kinds of things we're proving something about. It might begin
with ``Let $!A$ be !!a{formula} of the form $!B \lif !C$'' or
``Suppose $\Gamma \Proves !A$'' or something of the sort.  These are
\emph{hypotheses} of the proposition, theorem, or lemma, and you may
assume these to be true in your proof. They restrict what we're
proving, and also introduce some names for the objects we're
talking about. For instance, if your proposition begins with ``Let
$!A$ be !!a{formula} of the form $!B \lif !C$,'' you're proving
something about all formulas of a certain sort only (namely,
conditionals), and it's understood that $!B \lif !C$ is an arbitrary
conditional that your proof will talk about.

\end{document}