Methods

Proofs

content/methods/proofs/proofs.tex

% Part: methods% Chapter: proofs\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olchapter{mth}{prf}{Proofs}\olimport{introduction}\olimport{starting-proofs}\olimport{using-definitions}\olimport{inference-patterns}\olimport{example-1}\olimport{example-2}\olimport{proof-by-contradiction}\olimport{reading-proofs}\olimport{cant-do-it}\olimport{resources}\OLEndChapterHook\end{document}

content/methods/proofs/introduction.tex

% 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 becomfortable with !!a{derivation} system---probably a natural deduction orFitch style !!{derivation} system, or perhaps a proof-tree system. You probablyremember doing proofs in these systems, either proving !!a{formula}or show that a given argument is valid. In order to do this, youapplied the rules of the system until you got the desired endresult. In reasoning \emph{about} logic, we also prove things, but inmost cases we are not using !!a{derivation} system. In fact, most of theproofs we consider are done in English (perhaps, with some symboliclanguage thrown in) rather than entirely in the language offirst-order logic.  When constructing such proofs, you might at firstbe at a loss---how do I prove something without !!a{derivation} system?  Howdo I start? How do I know if my proof is correct?Before attempting a proof, it's important to know what a proof is andhow to construct one.  As implied by the name, a \emph{proof} is meantto show that something is true. You might think of this in terms of adialogue---someone asks you if something is true, say, if every primeother than two is an odd number. To answer ``yes'' is not enough; theymight 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, orgive an incomplete answer. In logic and mathematics, however, we wantrigorous proof---we want to show that something is true beyond \emph{any}doubt. This means that every step in our proof must be justified, andthe justification must be cogent (i.e., the assumption you're using isactually assumed in the statement of the theorem you're proving, thedefinitions you apply must be correctly applied, the justificationsappealed to must be correct inferences, etc.).Usually, we're proving some statement. We call the statements we'reproving by various names: propositions, theorems, lemmas, orcorollaries.  A proposition is a basic proof-worthy statement:important enough to record, but perhaps not particularly deep norapplied often. A theorem is a significant, important proposition. Itsproof often is broken into several steps, and sometimes it is namedafter the person who first proved it (e.g., Cantor's Theorem, theL\"owenheim--Skolem theorem) or after the fact it concerns (e.g., thecompleteness theorem).  A lemma is a proposition or theorem that isused in the proof of a more important result. Confusingly,sometimes lemmas are important results in themselves, and also namedafter the person who introduced them (e.g., Zorn's Lemma). A corollaryis a result that easily follows from another one.A statement to be proved often contains assumptions that clarifywhich kinds of things we're proving something about. It might beginwith ``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 mayassume these to be true in your proof. They restrict what we'reproving, and also introduce some names for the objects we'retalking about. For instance, if your proposition begins with ``Let$!A$ be !!a{formula} of the form $!B \lif !C$,'' you're provingsomething about all formulas of a certain sort only (namely,conditionals), and it's understood that $!B \lif !C$ is an arbitraryconditional that your proof will talk about.\end{document}

content/methods/proofs/starting-proofs.tex

% Part: methods% Chapter: proofs% Section: starting-proofs\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mth}{prf}{str}\olsection{Starting a Proof}But where do you even start?You've been given something to prove, so this should be the last thing thatis mentioned in the proof (you can, obviously, \emph{announce} that you'regoing to prove it at the beginning, but you don't want to use it as anassumption). Write what you are trying to prove at the bottom of a freshsheet of paper---this way you don't lose sight of your goal.Next, you may have some assumptions that you are able to use (thiswill be made clearer when we talk about the \emph{type} of proof youare doing in the next section). Write these at the top of the page andmake sure to flag that they are assumptions (i.e., if you are assuming$p$, write ``assume that $p$,'' or ``suppose that $p$''). Finally,there might be some definitions in the question that you need to know.You might be told to use a specific definition, or there might bevarious definitions in the assumptions or conclusion that you areworking towards. \emph{Write these down and ensure that you understandwhat they mean.}How you set up your proof will also be dependent upon the form of thequestion. The next section provides details on how to set up your proofbased on the type of sentence.\end{document}

content/methods/proofs/using-definitions.tex

% Part: methods% Chapter: proofs% Section: using-definitions\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mod}{prf}{def}\olsection{Using Definitions}We mentioned that you must be familiar with all definitions that maybe used in the proof, and that you can properly apply them. This is areally important point, and it is worth looking at in a bit moredetail. Definitions are used to abbreviate properties and relations sowe can talk about them more succinctly. The introduced abbreviation iscalled the \emph{definiendum}, and what it abbreviates is the\emph{definiens}.  In proofs, we often have to go back to how thedefiniendum was introduced, because we have to exploit the logicalstructure of the definiens (the long version of which the defined termis the abbreviation) to get through our proof.  By unpackingdefinitions, you're ensuring that you're getting to the heart of wherethe logical action is.We'll start with an example. Suppose you want to prove the following:\begin{prop}For any sets $A$ and $B$, $A \cup B = B \cup A$.\end{prop}In order to even start the proof, we need to know what it means fortwo sets to be identical; i.e., we need to know what the ``$=$'' inthat equation means for sets.  Sets are defined to be identicalwhenever they have the same !!{element}s.  So the definition we haveto unpack is:\begin{defn}Sets $A$ and $B$ are \emph{identical}, $A = B$, iff every !!{element}of~$A$ is !!a{element} of~$B$, and vice versa.\end{defn}This definition uses $A$ and~$B$ as placeholders for arbitrarysets. What it defines---the \emph{definiendum}---is the expression``$A = B$'' by giving the condition under which $A = B$ is true.  Thiscondition---``every !!{element} of~$A$ is !!a{element} of~$B$, andvice versa''---is the \emph{definiens}.\footnote{In this particular  case---and very confusingly!---when $A = B$, the sets $A$ and $B$  are just one and the same set, even though we use different letters  for it on the left and the right side.  But the ways in which that  set is picked out may be different, and that makes the definition  non-trivial.} The definition specifies that $A = B$ is true if, andonly if (we abbreviate this to ``iff'') the condition holds.When you apply the definition, you have to match the $A$ and $B$ inthe definition to the case you're dealing with.  In our case, it meansthat in order for $A \cup B = B \cup A$ to be true, each $z \in A \cupB$ must also be in $B \cup A$, and vice versa.  The expression $A \cupB$ in the proposition plays the role of~$A$ in the definition, and $B\cup A$ that of~$B$. Since $A$ and $B$ are used both in the definitionand in the statement of the proposition we're proving, but indifferent uses, you have to be careful to make sure you don't mix upthe two.  For instance, it would be a mistake to think that you couldprove the proposition by showing that every !!{element} of~$A$ is!!a{element} of~$B$, and vice versa---that would show that $A = B$,not that $A \cup B = B \cup A$. (Also, since $A$ and $B$ may be anytwo sets, you won't get very far, because if nothing is assumed about$A$ and~$B$ they may well be different sets.)Within the proof we are dealing with set-theoretic notions such asunion, and so we must also know the meanings of the symbol $\cup$ inorder to understand how the proof should proceed. And sometimes,unpacking the definition gives rise to further definitions tounpack. For instance, $A \cup B$ is defined as $\Setabs{z}{z \in A  \text{ or } z \in B}$. So if you want to prove that $x \in A \cupB$, unpacking the definition of $\cup$ tells you that you have toprove $x \in \Setabs{z}{z \in A \text{ or } z \in B}$.  Now you alsohave to remember that $x \in \Setabs{z}{\dots z\dots}$ iff $\dotsx\dots$.  So, further unpacking the definition of the$\Setabs{z}{\dots z \dots}$ notation, what you have to show is: $x \inA$ or $x \in B$. So, ``every !!{element} of $A \cup B$ is also!!a{element} of $B \cup A$'' really means: ``for every $x$, if $x \inA$ or $x \in B$, then $x \in B$ or $x \in A$.''  If we fullyunpack the definitions in the proposition, we see that what we have toshow is this:\begin{prop}For any sets $A$ and $B$: (a) for every $x$, if $x \in A$ or $x \inB$, then $x \in B$ or $x \in A$, and (b) for every $x$, if $x \in B$or $x \in A$, then $x \in A$ or $x \in B$.\end{prop}What's important is that unpacking definitions is a necessary part ofconstructing a proof. Properly doing it is sometimes difficult: youmust be careful to distinguish and match the variables in thedefinition and the terms in the claim you're proving.  In order to besuccessful, you must know what the question is asking and what all theterms used in the question mean---you will often need to unpack morethan one definition.  In simple proofs such as the ones below, thesolution follows almost immediately from the definitionsthemselves. Of course, it won't always be this simple.\begin{prob}Suppose you are asked to prove that $A \cap B \neq \emptyset$. Unpackall the definitions occurring here, i.e., restate this in a way thatdoes not mention ``$\cap$'', ``='', or ``$\emptyset$''.\end{prob}\end{document}

content/methods/proofs/inference-patterns.tex

% Part: methods% Chapter: proofs% Section: inference-patterns\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mth}{prf}{pat}\olsection{Inference Patterns}Proofs are composed of individual inferences. When we make aninference, we typically indicate that by using a word like ``so,''``thus,'' or ``therefore.''  The inference often relies on one or twofacts we already have available in our proof---it may be something wehave assumed, or something that we've concluded by an inferencealready.  To be clear, we may label these things, and in the inferencewe indicate what other statements we're using in the inference.  Aninference will often also contain an explanation of \emph{why} our newconclusion follows from the things that come before it.  There aresome common patterns of inference that are used very often in proofs;we'll go through some below. Some patterns of inference, like proofsby induction, are more involved (and will be discussed later).We've already discussed one pattern of inference: unpacking, orapplying, a definition. When we unpack a definition, we just restatesomething that involves the definiendum by using the definiens. Forinstance, suppose that we have already established in the course of aproof that $D = E$ (a). Then we may apply the definition of $=$ for setsand infer: ``Thus, by definition from (a), every !!{element}of~$D$ is !!a{element} of~$E$ and vice versa.''Somewhat confusingly, we often do not write the justification of aninference when we actually make it, but before.  Suppose we haven'talready proved that $D = E$, but we want to.  If $D = E$ is theconclusion we aim for, then we can restate this aim also by applyingthe definition: to prove $D = E$ we have to prove that every!!{element} of~$D$ is !!a{element} of~$E$ and vice versa.  So ourproof will have the form: (a) prove that every !!{element} of~$D$ is!!a{element} of~$E$; (b) every !!{element} of~$E$ is !!a{element}of~$D$; (c) therefore, from (a) and (b) by definition of $=$, $D = E$.But we would usually not write it this way. Instead we might writesomething like,\begin{quote}We want to show $D = E$. By definition of~$=$, this amounts to showingthat every !!{element} of~$D$ is !!a{element} of~$E$ and viceversa.(a) \dots (a proof that every !!{element} of~$D$ is !!a{element}of~$E$) \dots(b) \dots (a proof that every !!{element}of~$E$ is !!a{element} of~$D$) \dots\end{quote}\subsection{Using a Conjunction}Perhaps the simplest inference pattern is that of drawing asconclusion one of the conjuncts of a conjunction. In other words: ifwe have assumed or already proved that $p$ and~$q$, then we'reentitled to infer that~$p$ (and also that~$q$).  This is such a basicinference that it is often not mentioned.  For instance, once we'veunpacked the definition of $D = E$ we've established that every!!{element} of~$D$ is !!a{element} of~$E$ and vice versa. From thiswe can conclude that every !!{element} of~$E$ is !!a{element} of~$D$(that's the ``vice versa'' part).  \subsection{Proving a Conjunction}Sometimes what you'll be asked to prove will have the form of aconjunction; you will be asked to ``prove $p$ and $q$.'' In this case,you simply have to do two things: prove $p$, and then prove $q$. Youcould divide your proof into two sections, and for clarity, labelthem. When you're making your first notes, you might write ``(1) Prove$p$'' at the top of the page, and ``(2) Prove $q$'' in the middle ofthe page. (Of course, you might not be explicitly asked to prove aconjunction but find that your proof requires that you prove aconjunction. For instance, if you're asked to prove that $D = E$ youwill find that, after unpacking the definition of~$=$, you have toprove: every !!{element} of~$D$ is !!a{element} of~$E$\emph{and} every !!{element} of~$E$ is !!a{element} of~$D$).\subsection{Proving a Disjunction}When what you are proving takes the form of a disjunction (i.e., it isan statement of the form ``$p$ or $q$''), it is enough to show thatone of the disjuncts is true.  However, it basically never happensthat either disjunct just follows from the assumptions of yourtheorem. More often, the assumptions of your theorem are themselvesdisjunctive, or you're showing that all things of a certain kind haveone of two properties, but some of the things have the one and othershave the other property.  This is where proof by cases isuseful (see below).\subsection{Conditional Proof}Many theorems you will encounter are in conditional form (i.e., showthat if $p$ holds, then $q$ is also true). These cases are nice andeasy to set up---simply assume the antecedent of the conditional (inthis case, $p$) and prove the conclusion~$q$ from it.  So if yourtheorem reads, ``If $p$ then $q$,'' you start your proof with ``assume$p$'' and at the end you should have proved~$q$.Conditionals may be stated in different ways. So instead of ``If $p$then $q$,'' a theorem may state that ``$p$ only if $q$,'' ``$q$ if$p$,'' or ``$q$, provided $p$.'' These all mean the same and requireassuming $p$ and proving~$q$ from that assumption.  Recall that abiconditional (``$p$ if and only if (iff) $q$'') is really twoconditionals put together: if $p$ then $q$, and if $q$ then~$p$. Allyou have to do, then, is two instances of conditional proof: one forthe first conditional and another one for the second. Sometimes,however, it is possible to prove an ``iff'' statement by chainingtogether a bunch of other ``iff'' statements so that you start with``$p$'' an end with ``$q$''---but in that case you have to make surethat each step really is an ``iff.''\subsection{Universal Claims}Using a universal claim is simple: if something is true for anything,it's true for each particular thing.  So if, say, the hypothesis ofyour proof is $A \subseteq B$, that means (unpacking the definitionof~$\subseteq$), that, for every $x \in A$, $x \in B$. Thus, if youalready know that $z \in A$, you can conclude $z \in B$.Proving a universal claim may seem a little bit tricky. Usually thesestatements take the following form: ``If $x$ has~$P$, then ithas~$Q$'' or ``All $P$s are $Q$s.'' Of course, it might not fit thisform perfectly, and it takes a bit of practice to figure out whatyou're asked to prove exactly. But: we often have to prove that all objectswith some property have a certain other property.The way to prove a universal claim is to introduce names or variables,for the things that have the one property and then show that they alsohave the other property.  We might put this by saying that to provesomething for \emph{all}~$P$s you have to prove it for an\emph{arbitrary}~$P$. And the name introduced is a name for anarbitrary~$P$.  We typically use single letters as these names forarbitrary things, and the letters usually follow conventions: e.g., weuse $n$ for natural numbers, $!A$ for !!{formula}s, $A$ for sets, $f$for functions, etc.The trick is to maintain generality throughout the proof. You start byassuming that an arbitrary object (``$x$'') has the property~$P$, andshow (based only on definitions or what you are allowed to assume)that $x$ has the property~$Q$. Because you have not stipulated what$x$ is specifically, other that it has the property $P$, then you canassert that everything with $P$ has the property~$Q$. In short, $x$ is astand-in for \emph{all} things with property~$P$.\begin{prop}  For all sets $A$ and $B$, $A \subseteq A \cup B$.\end{prop}\begin{proof}  Let $A$ and $B$ be arbitrary sets.  We want to show that $A  \subseteq A \cup B$. By definition of $\subseteq$, this amounts to:  for every $x$, if $x \in A$ then $x \in A \cup B$. So let $x \in A$  be an arbitrary !!{element} of~$A$. We have to show that $x \in A  \cup B$. Since $x \in A$, $x \in A$ or $x \in B$. Thus, $x \in  \Setabs{x}{x \in A \lor x \in B}$. But that, by definition of $\cup  $, means $x \in A \cup B$.\end{proof}\subsection{Proof by Cases}Suppose you have a disjunction as an assumption or as an alreadyestablished conclusion---you have assumed or proved that $p$ or $q$ istrue.  You want to prove $r$.  You do this in two steps: first youassume that $p$ is true, and prove~$r$, then you assume that $q$ istrue and prove~$r$ again.  This works because we assume or know thatone of the two alternatives holds. The two steps establish that eitherone is sufficient for the truth of~$r$.  (If both are true, we havenot one but two reasons for why $r$~is true. It is not necessary toseparately prove that $r$~is true assuming both $p$ and~$q$.)  Toindicate what we're doing, we announce that we ``distinguish cases.''For instance, suppose we know that $x \in B \cup C$.  $B \cup C$ isdefined as $\Setabs{x}{x \in B \text{ or } x \in C}$. In other words,by definition, $x \in B$ or $x \in C$. We would prove that $x \in A$from this by first assuming that $x \in B$, and proving $x \in A$ fromthis assumption, and then assume $x \in C$, and again prove $x \in A$from this.  You would write ``We distinguish cases'' under theassumption, then ``Case (1): $x \in B$'' underneath, and ``Case (2):$x \in C$ halfway down the page. Then you'd proceed to fill in the tophalf and the bottom half of the page.Proof by cases is especially useful if what you're proving is itselfdisjunctive. Here's a simple example:\begin{prop}Suppose $B \subseteq D$ and $C \subseteq E$. Then $B \cup C \subseteqD \cup E$.\end{prop}\begin{proof}  Assume (a) that $B \subseteq D$ and (b) $C \subseteq E$. By  definition, any $x \in B$ is also $\in D$ (c) and any $x \in C$ is  also $\in E$ (d).  To show that $B \cup C \subseteq D \cup E$, we  have to show that if $x \in B \cup C$ then $x \in D \cup E$ (by  definition of $\subseteq$). $x \in B \cup C$ iff $x \in B$ or $x \in  C$ (by definition of~$\cup$). Similarly, $x \in D \cup E$ iff $x \in  D$ or $x \in E$. So, we have to show: for any $x$, if $x \in B$ or  $x \in C$, then $x \in D$ or $x \in E$.  \begin{quote}  So far we've only unpacked definitions!{} We've reformulated our  proposition without $\subseteq$ and $\cup$ and are left with trying  to prove a universal conditional claim. By what we've discussed  above, this is done by assuming that $x$ is something about which we  assume the ``if'' part is true, and we'll go on to show that the  ``then'' part is true as well. In other words, we'll assume that $x  \in B$ or $x \in C$ and show that $x \in D$ or $x \in  E$.\footnote{This paragraph just explains what we're doing---it's    not part of the proof, and you don't have to go into all this    detail when you write down your own proofs.}  \end{quote}  Suppose that $x \in B$ or $x \in C$. We have to show that $x \in D$  or $x \in E$. We distinguish cases.  Case 1: $x \in B$. By (c), $x \in D$. Thus, $x \in D$ or $x \in  E$. (Here we've made the inference discussed in the preceding  subsection!)        Case 2: $x \in C$. By (d), $x \in E$. Thus, $x \in D$ or $x \in E$. \end{proof}\subsection{Proving an Existence Claim}When asked to prove an existence claim, the question will usually beof the form ``prove that there is an~$x$ such that $\dots x \dots$'',i.e., that some object that has the property described by ``$\dots x\dots$''. In this case you'll have to identify a suitable object and showthat it has the required property.  This sounds straightforward, but aproof of this kind can be tricky. Typically it involves\emph{constructing} or \emph{defining} an object and proving that theobject so defined has the required property. Finding the right objectmay be hard, proving that it has the required property may be hard,and sometimes it's even tricky to show that you've succeeded indefining an object at all!{}Generally, you'd write this out by specifying the object, e.g., ``let$x$ be \dots'' (where \dots{} specifies which object you have inmind), possibly proving that $\dots$ in fact describes an object thatexists, and then go on to show that $x$ has the property~$Q$. Here's asimple example.\begin{prop}  Suppose that $x \in B$. Then there is an~$A$ such that $A \subseteq  B$ and $A \neq \emptyset$.\end{prop}\begin{proof}  Assume $x \in B$. Let $A = \{x\}$.  \begin{quote}    Here we've defined the set~$A$ by enumerating its    !!{element}s. Since we assume that $x$ is an object, and we can    always form a set by enumerating its !!{element}s, we don't have    to show that we've succeeded in defining a set~$A$ here.  However,    we still have to show that $A$ has the properties required by the    proposition. The proof isn't complete without that!{}  \end{quote}  Since $x \in A$, $A \neq \emptyset$.  \begin{quote}    This relies on the definition of $A$ as $\{x\}$ and the obvious    facts that $x \in \{x\}$ and $x \notin \emptyset$.  \end{quote}  Since $x$ is the only !!{element} of~$\{x\}$, and $x \in B$, every  !!{element} of~$A$ is also !!a{element} of~$B$. By definition  of~$\subseteq$, $A \subseteq B$.\end{proof}\subsection{Using Existence Claims}Suppose you know that some existence claim is true (you've proved it,or it's a hypothesis you can use), say, ``for some~$x$, $x \in A$'' or``there is an $x \in A$.''  If you want to use it in your proof, youcan just pretend that you have a name for one of the things which yourhypothesis says exist. Since $A$ contains at least one thing, thereare things to which that name might refer. You might of course not beable to pick one out or describe it further (other than that it is$\in A$). But for the purpose of the proof, you can pretend that youhave picked it out and give a name to it. It's important to pick aname that you haven't already used (or that appears in yourhypotheses), otherwise things can go wrong. In your proof, youindicate this by going from ``for some $x$, $x \in A$'' to ``Let $a\in A$.''  Now you can reason about~$a$, use some other hypotheses, etc.,until you come to a conclusion, $p$. If $p$ no longer mentions~$a$, $p$ isindependent of the asusmption that $a \in A$, and you've shown that itfollows just from the assumption ``for some $x$, $x \in A$.''\begin{prop}If $A \neq \emptyset$, then $A \cup B \neq \emptyset$.\end{prop}\begin{proof}  Suppose $A \neq \emptyset$. So for some $x$, $x \in A$.   \begin{quote}    Here we first just restated the hypothesis of the    proposition. This hypothesis, i.e., $A \neq \emptyset$, hides an    existential claim, which you get to only by unpacking a few    definitions. The definition of $=$ tells us that $A = \emptyset$    iff every $x \in A$ is also $\in \emptyset$ and every $x \in    \emptyset$ is also $\in A$. Negating both sides, we get: $A \neq    \emptyset$ iff either some $x \in A$ is $\notin \emptyset$ or some    $x \in \emptyset$ is $\notin A$. Since nothing is $\in \emptyset$,    the second disjunct can never be true, and ``$x \in A$ and $x    \notin \emptyset$'' reduces to just $x \in A$. So $x \neq    \emptyset$ iff for some $x$, $x \in A$. That's an existence    claim. Now we use that existence claim by introducing a name for    one of the !!{element}s of~$A$:  \end{quote}  Let $a \in A$.  \begin{quote}    Now we've introduced a name for one of the things~$\in A$. We'll    continue to argue about~$a$, but we'll be careful to only assume    that $a \in A$ and nothing else:  \end{quote}  Since $a \in A$, $a \in A \cup B$, by definition of~$\cup$. So for  some $x$, $x \in A \cup B$, i.e., $A \cup B \neq \emptyset$.  \begin{quote}    In that last step, we went from ``$a \in A \cup B$'' to ``for some    $x$, $x \in A \cup B$.'' That doesn't mention $a$ anymore, so we    know that ``for some $x$, $x \in A \cup B$'' follows from ``for    some $x$, $x \in A$ alone.'' But that means that $A \cup B \neq    \emptyset$.  \end{quote}\end{proof}It's maybe good practice to keep bound variables like ``$x$'' separatefrom hypothetical names like $a$, like we did. In practice, however, weoften don't and just use $x$, like so:\begin{quote}Suppose $A \neq \emptyset$, i.e., there is an $x \in A$. By definitionof $\cup$, $x \in A \cup B$. So $A \cup B \neq \emptyset$.\end{quote}However, when you do this, you have to be extra careful that you usedifferent $x$'s and $y$'s for different existential claims. Forinstance, the following is \emph{not} a correct proof of ``If $A \neq\emptyset$ and $B \neq \emptyset$ then $A \cap B \neq \emptyset$''(which is not true).\begin{quote}Suppose $A \neq \emptyset$ and $B \neq \emptyset$. So for some $x$, $x\in A$ and also for some $x$, $x \in B$. Since $x \in A$ and $x \inB$, $x \in A \cap B$, by definition of~$\cap$. So $A \cap B \neq\emptyset$.\end{quote}Can you spot where the incorrect step occurs and explain why theresult does not hold?\end{document}

content/methods/proofs/example-1.tex

% Part: methods% Chapter: proofs% Section: example-1\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mth}{prf}{ex1}\olsection{An Example} Our first example is the following simple fact about unions andintersections of sets.  It will illustrate unpacking definitions,proofs of conjunctions, of universal claims, and proof by cases.\begin{prop}For any sets $A$, $B$, and $C$, $A \cup (B \cap C) = (A \cup B)\cap (A \cup C)$\end{prop}Let's prove it!{}\begin{proof}We want to show that for any sets $A$, $B$, and $C$, $A \cup (B \capC) = (A \cup B) \cap (A \cup C)$\begin{quote}First we unpack the definition of ``$=$'' in the statement of theproposition. Recall that proving sets identical means showing that thesets have the same !!{element}s. That is, all !!{element}s of $A \cup(B \cap C)$ are also !!{element}s of $(A \cup B) \cap (A \cup C)$, andvice versa.  The ``vice versa'' means that also every !!{element} of $(A\cup B) \cap (A \cup C)$ must be !!a{element} of $A \cup (B \capC)$.  So in unpacking the definition, we see that we have to prove aconjunction.  Let's record this:\end{quote}By definition, $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ iffevery !!{element} of $A \cup (B \cap C)$ is also !!a{element} of $(A\cup B) \cap (A \cup C)$, and every !!{element} of $(A \cup B) \cap (A\cup C)$ is !!a{element} of $A \cup (B \cap C)$.\begin{quote}Since this is a conjunction, we must prove each conjunctseparately. Lets start with the first: let's prove that every!!{element} of $A \cup (B \cap C)$ is also !!a{element} of $(A\cup B) \cap (A \cup C)$.This is a universal claim, and so we consider an arbitrary !!{element}of $A \cup (B \cap C)$ and show that it must also be !!a{element} of$(A \cup B) \cap (A \cup C)$. We'll pick a variable to call thisarbitrary !!{element} by, say,~$z$.  Our proof continues:\end{quote}First, we prove that every !!{element} of $A \cup (B \cap C)$ is also!!a{element} of $(A \cup B) \cap (A \cup C)$. Let $z \in A \cup (B\cap C)$. We have to show that $z \in (A \cup B) \cap (A \cup C)$.\begin{quote}  Now it is time to unpack the definition of $\cup$ and~$\cap$. Forinstance, the definition of $\cup$ is: $A \cup B = \Setabs{z}{z \in A  \text{ or } z \in B}$.  When we apply the definition to ``$A \cup (B\cap C)$,'' the role of the ``$B$'' in the definition is now played by``$B \cap C$,'' so $A \cup (B \cap C) = \Setabs{z}{z \in A \text{ or }  z \in B \cap C}$.  So our assumption that $z \in A \cup (B \cap C)$amounts to: $z \in \Setabs{z}{z \in A \text{ or } z \in B \cap  C}$. And $z \in \Setabs{z}{\dots z\dots}$ iff \dots $z$ \dots, i.e.,in this case, $z \in A$ or $z \in B \cap C$.\end{quote}By the definition of $\cup$, either $z \in A$ or $z \in B \cap C$.\begin{quote}Since this is a disjunction, it will be useful to apply proof bycases. We take the two cases, and show that in each one, theconclusion we're aiming for (namely, ``$z \in (A \cup B) \cap (A \cupC)$'') obtains.\end{quote}Case 1: Suppose that $z \in A$.\begin{quote}There's not much more to work from based on our assumptions. So let'slook at what we have to work with in the conclusion. We want to showthat $z \in (A \cup B) \cap (A \cup C)$. Based on the definition of$\cap$, if we want to show that $z \in (A \cup B) \cap (A \cup C)$, wehave to show that it's in both $(A \cup B)$ and $(A \cup C)$. But $z\in A \cup B$ iff $z \in A$ or $z \in B$, and we already have (as theassumption of case~1) that $z \in A$. By the samereasoning---switching $C$ for $B$---$z \in A \cup C$. This argumentwent in the reverse direction, so let's record our reasoning in thedirection needed in our proof.\end{quote}Since $z \in A$, $z \in A$ or $z \in B$, and hence, by definitionof~$\cup$, $z \in A \cup B$. Similarly, $z \in A \cup C$.  But thismeans that $z \in (A \cup B) \cap (A \cup C)$, by definitionof~$\cap$.\begin{quote}This completes the first case of the proof by cases. Now we want toderive the conclusion in the second case, where $z \in B \cap C$.\end{quote}Case 2: Suppose that $z \in B \cap C$.\begin{quote}Again, we are working with the intersection of two sets. Let's applythe definition of~$\cap$:\end{quote}Since $z \in B \cap C$, $z$ must be !!a{element} of both $B$ and $C$, bydefinition of~$\cap$.\begin{quote}It's time to look at our conclusion again. We have to show that $z$ isin both $(A \cup B)$ and $(A \cup C)$. And again, the solution isimmediate.\end{quote}Since $z \in B$, $z \in (A \cup B)$. Since $z \in C$, also $z \in (A\cup C)$.  So, $z \in (A \cup B) \cap (A \cup C)$.\begin{quote}Here we applied the definitions of $\cup$ and $\cap$ again, but sincewe've already recalled those definitions, and already showed that if$z$ is in one of two sets it is in their union, we don't have to be asexplicit in what we've done.We've completed the second case of the proof by cases, so now we canassert our first conclusion.\end{quote}So, if $z \in A \cup (B \cap C)$ then $z \in (A \cup B) \cap (A \cup C)$.\begin{quote}Now we just want to show the other direction, that every !!{element}of $(A \cup B) \cap (A \cup C)$ is !!a{element} of $A \cup (B \capC)$. As before, we prove this universal claim by assuming we have anarbitrary !!{element} of the first set and show it must be in thesecond set. Let's state what we're about to do.\end{quote}Now, assume that $z \in (A \cup B) \cap (A \cup C)$. We want to showthat $z \in A \cup (B \cap C)$.\begin{quote}We are now working from the hypothesis that $z \in (A \cup B) \cap (A\cup C)$. It hopefully isn't too confusing that we're using thesame~$z$ here as in the first part of the proof.  When we finishedthat part, all the assumptions we've made there are no longer ineffect, so now we can make new assumptions about what $z$ is.  If thatis confusing to you, just replace $z$ with a different variable inwhat follows.We know that $z$ is in both $A \cup B$ and $A \cup C$, by definitionof~$\cap$. And by the definition of $\cup$, we can further unpack thisto: either $z \in A$ or $z \in B$, and also either $z \in A$ or $z \inC$. This looks like a proof by cases again---except the ``and'' makesit confusing. You might think that this amounts to there being threepossibilities: $z$ is either in $A$, $B$ or $C$. But that would be amistake.  We have to be careful, so let's consider each disjunction inturn.\end{quote}By definition of $\cap$, $z \in A \cup B$ and $z \in A \cup C$. Bydefinition of $\cup$, $z \in A$ or $z \in B$. We distinguish cases.\begin{quote}Since we're focusing on the first disjunction, we haven't gotten oursecond disjunction (from unpacking $A \cup C$) yet. In fact, we don'tneed it yet. The first case is $z \in A$, and !!a{element} of a set isalso !!a{element} of the union of that set with any other. So case~1is easy:\end{quote}Case 1: Suppose that $z \in A$. It follows that $z \in A \cup (B \capC)$.\begin{quote}Now for the second case, $z \in B$. Here we'll unpack the second$\cup$ and do another proof-by-cases:\end{quote}Case 2: Suppose that $z \in B$. Since $z \in A \cup C$, either $z \inA$ or $z \in C$. We distinguish cases further:Case 2a: $z \in A$. Then, again, $z \in A \cup (B \cap C)$.\begin{quote}Ok, this was a bit weird. We didn't actually need the assumptionthat~$z \in B$ for this case, but that's ok.\end{quote}Case 2b: $z \in C$. Then $z \in B$ and $z \in C$, so $z \in B \cap C$,and consequently, $z \in A \cup (B \cap C)$.\begin{quote}This concludes both proofs-by-cases and so we're done with the secondhalf.\end{quote}So, if $z \in (A \cup B) \cap (A \cup C)$ then $z \in A \cup (B \cap C)$.\end{proof}\end{document}

content/methods/proofs/example-2.tex

% Part: methods% Chapter: proofs% Section: example-2\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mth}{prf}{ex2}\olsection{Another Example} \begin{prop}If $A \subseteq C$, then $A \cup (C \setminus A) = C$.\end{prop}  \begin{proof}  Suppose that $A \subseteq C$.  We want to show that $A \cup (C  \setminus A) = C$.  \begin{quote}    We begin by observing that this is a conditional statement. It is    tacitly universally quantified: the proposition holds for all sets    $A$ and $C$. So $A$ and $C$ are variables for arbitrary sets. To    prove such a statement, we assume the antecedent and prove the    consequent.    We continue by using the assumption that $A \subseteq C$. Let's    unpack the definition of~$\subseteq$: the assumption means that    all !!{element}s of~$A$ are also !!{element}s of~$C$. Let's write    this down---it's an important fact that we'll use throughout the    proof.  \end{quote}  By the definition of~$\subseteq$, since $A \subseteq C$, for all  $z$, if $z \in A$, then $z \in C$.  \begin{quote}    We've unpacked all the definitions that are given to us in the    assumption. Now we can move onto the conclusion. We want to show    that $A \cup (C \setminus A) = C$, and so we set up a proof    similarly to the last example: we show that every !!{element} of    $A \cup (C \setminus A)$ is also !!a{element} of~$C$ and,    conversely, every !!{element} of $C$ is !!a{element} of $A \cup (C    \setminus A)$. We can shorten this to: $A \cup (C \setminus A)    \subseteq C$ and $C \subseteq A \cup (C \setminus A)$. (Here we're    doing the opposite of unpacking a definition, but it makes the    proof a bit easier to read.)  Since this is a conjunction, we have    to prove both parts. To show the first part, i.e., that every    !!{element} of $A \cup (C \setminus A)$ is also !!a{element}    of~$C$, we assume that $z \in A \cup (C \setminus A)$ for an    arbitrary~$z$ and show that $z \in C$. By the definition of    $\cup$, we can conclude that $z \in A$ or $z \in C \setminus A$    from $z \in A \cup (C \setminus A)$. You should now be getting the    hang of this.    \end{quote}  $A \cup (C \setminus A) = C$ iff $A \cup (C \setminus A) \subseteq  C$ and $C \subseteq (A \cup (C \setminus A)$.  First we prove that  $A \cup (C \setminus A) \subseteq C$.  Let $z \in A \cup (C  \setminus A)$. So, either $z \in A$ or $z \in (C \setminus A)$.  \begin{quote}    We've arrived at a disjunction, and from it we want to prove that    $z \in C$. We do this using proof by cases.  \end{quote}  Case 1: $z \in A$. Since for all $z$, if $z \in A$, $z \in C$, we  have that $z \in C$.  \begin{quote}    Here we've used the fact recorded earlier which followed from the    hypothesis of the proposition that $A \subseteq C$.  The first    case is complete, and we turn to the second case, $z \in (C    \setminus A)$.  Recall that $C \setminus A$ denotes the    \emph{difference} of the two sets, i.e., the set of all    !!{element}s of~$C$ which are not !!{element}s of~$A$.  But any    !!{element} of $C$ not in~$A$ is in particular !!a{element} of~$C$.  \end{quote}  Case 2: $z \in (C \setminus A)$.  This means that $z \in C$ and $z  \notin A$. So, in particular, $z \in C$.  \begin{quote}    Great, we've proved the first direction. Now for the second    direction. Here we prove that $C \subseteq A \cup (C \setminus    A)$.  So we assume that $z \in C$ and prove that $z \in A \cup (C    \setminus A)$.  \end{quote}  Now let $z \in C$. We want to show that $z \in A$ or $z \in C  \setminus A$.  \begin{quote}    Since all !!{element}s of $A$ are also !!{element}s of $C$, and $C    \setminus A$ is the set of all things that are !!{element}s of $C$    but not $A$, it follows that $z$ is either in $A$ or in $C    \setminus A$.  This may be a bit unclear if you don't already know    why the result is true.  It would be better to prove it    step-by-step.  It will help to use a simple fact which we can    state without proof: $z \in A$ or $z \notin A$. This is called the    ``principle of excluded middle:'' for any statement~$p$, either    $p$ is true or its negation is true. (Here, $p$ is the statement    that $z \in A$.)  Since this is a disjunction, we can again use    proof-by-cases.  \end{quote}  Either $z \in A$ or $z \notin A$. In the former case, $z \in A \cup  (C \setminus A)$. In the latter case, $z \in C$ and $z \notin A$, so  $z \in C \setminus A$.  But then $z \in A \cup (C \setminus A)$.  \begin{quote}    Our proof is complete: we have shown that $A \cup (C \setminus A) = C$.  \end{quote}\end{proof}\end{document}

content/methods/proofs/proof-by-contradiction.tex

% Part: methods% Chapter: proofs% Section: proof-by-contradiction\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mth}{prf}{con}\olsection{Proof by Contradiction} In the first instance, proof by contradiction is an inference patternthat is used to prove negative claims.  Suppose you want to show thatsome claim~$p$ is \emph{false}, i.e., you want to show~$\lnot p$.  Themost promising strategy is to (a) suppose that $p$~is true, and (b)show that this assumption leads to something you know to be false.``Something known to be false'' may be a result that conflictswith---contradicts---$p$ itself, or some other hypothesis of theoverall claim you are considering.  For instance, a proof of ``if $q$then $\lnot p$'' involves assuming that $q$~is true and proving~$\lnotp$ from it. If you prove $\lnot p$ by contradiction, that meansassuming $p$ in addition to~$q$. If you can prove $\lnot q$ from $p$,you have shown that the assumption~$p$ leads to something thatcontradicts your other assumption~$q$, since $q$~and $\lnot q$ cannotboth be true.  Of course, you have to use other inference patterns inyour proof of the contradiction, as well as unpacking definitions.Let's consider an example.\begin{prop}  If $A \subseteq B$ and $B = \emptyset$, then $A$ has no !!{element}s.\end{prop}\begin{proof}  Suppose $A \subseteq B$ and $B = \emptyset$. We want to show that  $A$ has no !!{element}s.  \begin{quote}    Since this is a conditional claim, we assume the antecedent and    want to prove the consequent. The consequent is: $A$ has no    !!{element}s. We can make that a bit more explicit: it's not the    case that there is an~$x \in A$.  \end{quote}  $A$ has no !!{element}s iff it's not the case that there is an~$x$  such that $x \in A$.  \begin{quote}    So we've determined that what we want to prove is really a    negative claim~$\lnot p$, namely: it's not the case that there is    an $x \in A$.  To use proof by contradiction, we have to assume the    corresponding positive claim~$p$, i.e., there is an $x \in A$, and    prove a contradiction from it.  We indicate that we're doing a    proof by contradiction by writing ``by way    of contradiction, assume'' or even just ``suppose not,'' and then state    the assumption~$p$.  \end{quote}  Suppose not: there is an $x \in A$.  \begin{quote}    This is now the new assumption we'll use to obtain a    contradiction. We have two more assumptions: that $A \subseteq B$    and that $B = \emptyset$. The first gives us that $x \in B$:  \end{quote}  Since $A \subseteq B$, $x \in B$.  \begin{quote}    But since $B = \emptyset$, every !!{element} of $B$ (e.g., $x$)    must also be !!a{element} of~$\emptyset$.  \end{quote}  Since $B = \emptyset$, $x \in \emptyset$. This is a contradiction,  since by definition $\emptyset$ has no !!{element}s.  \begin{quote}    This already completes the proof: we've arrived at what we need (a    contradiction) from the assumptions we've set up, and this means    that the assumptions can't all be true. Since the first two    assumptions ($A \subseteq B$ and $B = \emptyset$) are not    contested, it must be the last assumption introduced (there is an    $x \in A$) that must be false. But if we want to be thorough, we    can spell this out.  \end{quote}  Thus, our assumption that there is an $x \in A$ must be false, hence,  $A$ has no !!{element}s by proof by contradiction.\end{proof}Every positive claim is trivially equivalent to a negative claim: $p$iff $\lnot\lnot p$.  So proofs by contradiction can also be used toestablish positive claims ``indirectly,'' as follows: To prove~$p$,read it as the negative claim $\lnot\lnot p$. If we can prove acontradiction from $\lnot p$, we've established $\lnot\lnot p$ byproof by contradiction, and hence~$p$.In the last example, we aimed to prove a negative claim, namely that$A$ has no !!{element}s, and so the assumption we made for the purposeof proof by contradiction (i.e., that there is an $x \in A$) was apositive claim. It gave us something to work with, namely thehypothetical $x \in A$ about which we continued to reason until we gotto $x \in \emptyset$.When proving a positive claim indirectly, the assumption you'd makefor the purpose of proof by contradiction would be negative. But veryoften you can easily reformulate a positive claim as a negative claim,and a negative claim as a positive claim.  Our previous proof wouldhave been essentially the same had we proved ``$A = \emptyset$''instead of the negative consequent ``$A$ has no !!{element}s.'' (Bydefinition of $=$, ``$A = \emptyset$'' is a general claim, since itunpacks to ``every !!{element} of~$A$ is an !!{element} of~$\emptyset$and vice versa''.) But it is easily seen to be equivalent to thenegative claim ``not: there is an $x \in A$.''So it is sometimes easier to work with $\lnot p$ as an assumption thanit is to prove~$p$ directly.  Even when a direct proof is just assimple or even simpler (as in the next examples), some people prefer toproceed indirectly.  If the double negation confuses you, think of aproof by contradiction of some claim as a proof of a contradictionfrom the \emph{opposite} claim. So, a proof by contradiction of $\lnotp$ is a proof of a contradiction from the assumption~$p$; and proof bycontradiction of~$p$ is a proof of a contradiction from~$\lnot p$.\begin{prop}$A \subseteq A \cup B$.\end{prop}\begin{proof}  We want to show that $A \subseteq A \cup B$.  \begin{quote}    On the face of it, this is a positive claim: every $x \in A$ is    also in $A \cup B$.  The negation of that is: some $x \in A$ is    $\notin A \cup B$. So we can prove the claim indirectly by    assuming this negated claim, and showing that it leads to a    contradiction.    \end{quote}  Suppose not, i.e., $A \nsubseteq A \cup B$.  \begin{quote}    We have a definition of $A \subseteq A \cup B$: every $x \in A$ is    also $\in A \cup B$.  To understand what $A \nsubseteq A \cup B$    means, we have to use some elementary logical manipulation on the    unpacked definition: it's false that every $x \in A$ is also $\in    A \cup B$ iff there is \emph{some}~$x \in A$ that is $\notin C$.    (This is a place where you want to be very careful: many students'    attempted proofs by contradiction fail because they analyze the    negation of a claim like ``all $A$s are $B$s'' incorrectly.) In    other words, $A \nsubseteq A \cup B$ iff there is an $x$ such that    $x \in A$ and $x \notin A \cup B$. From then on, it's easy.  \end{quote}  So, there is an $x \in A$ such that $x \notin A \cup B$.  By  definition of $\cup$, $x \in A \cup B$ iff $x \in A$ or $x \in  B$. Since $x \in A$, we have $x \in A \cup B$. This contradicts the  assumption that $x \notin A \cup B$. \end{proof}\begin{prob}Prove \emph{indirectly} that $A \cap B \subseteq A$.\end{prob}\begin{prop}If $A \subseteq B$ and $B \subseteq C$ then $A \subseteq C$.\end{prop}\begin{proof}  Suppose $A \subseteq B$ and $B \subseteq C$. We want to show $A  \subseteq C$.  \begin{quote}    Let's proceed indirectly: we assume the negation of what we want    to etablish.  \end{quote}  Suppose not, i.e., $A \nsubseteq C$.  \begin{quote}    As before, we reason that $A \nsubseteq C$ iff not every $x \in A$    is also $\in C$, i.e., some $x \in A$ is $\notin C$.  Don't worry,    with practice you won't have to think hard anymore to unpack    negations like this.  \end{quote}  In other words, there is an~$x$ such that $x \in A$ and $x \notin C$.  \begin{quote}    Now we can use this to get to our contradiction. Of course, we'll    have to use the other two assumptions to do it.  \end{quote}  Since $A \subseteq B$, $x \in B$. Since $B \subseteq C$, $x \in  C$. But this contradicts $x \notin C$.\end{proof}\begin{prop}If $A \cup B = A \cap B$ then $A = B$.\end{prop}\begin{proof}  Suppose $A \cup B = A \cap B$. We want to show that $A = B$.  \begin{quote}    The beginning is now routine:  \end{quote}  Assume, by way of contradiction, that $A \neq B$.  \begin{quote}    Our assumption for the proof by contradiction is that $A \neq    B$. Since $A = B$ iff $A \subseteq B$ an $B \subseteq A$, we get    that $A \neq B$ iff $A \nsubseteq B$ \emph{or} $B \nsubseteq    A$. (Note how important it is to be careful when manipulating    negations!{}) To prove a contradiction from this disjunction, we    use a proof by cases and show that in each case, a contradiction    follows.  \end{quote}  $A \neq B$ iff $A \nsubseteq B$ or $B \nsubseteq A$. We distinguish  cases.  \begin{quote}    In the first case, we assume $A \nsubseteq B$, i.e., for some $x$,    $x \in A$ but $\notin B$. $A \cap B$ is defined as those    !!{element}s that $A$ and $B$ have in common, so if something    isn't in one of them, it's not in the intersection. $A \cup B$ is    $A$ together with $B$, so anything in either is also in the    union. This tells us that $x \in A \cup B$ but $x \notin A \cap    B$, and hence that $A \cap B \neq A \cup B$.  \end{quote}    Case 1: $A \nsubseteq B$. Then for some $x$, $x \in A$ but $x \notin  B$. Since $x \notin B$, then $x \notin A \cap B$. Since $x \in A$,  $x \in A \cup B$. So, $A \cap B \neq A \cup B$, contradicting the  assumption that $A \cap B = A \cup B$.  Case 2: $B \nsubseteq A$. Then for some $y$, $y \in B$ but $y \notin  A$. As before, we have $y \in A \cup B$ but $y \notin A \cap B$, and  so $A \cap B \neq A \cup B$, again contradicting $A \cap B = A \cup  B$. \end{proof}\end{document}

content/methods/proofs/reading-proofs.tex

% Part: methods% Chapter: proofs% Section: reading-proofs\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mth}{prf}{rea}\olsection{Reading Proofs}Proofs you find in textbooks and articles very seldom give all thedetails we have so far included in our examples. Authors often do notdraw attention to when they distinguish cases, when they give anindirect proof, or don't mention that they use a definition.  So whenyou read a proof in a textbook, you will often have to fill in thosedetails for yourself in order to understand the proof. Doing this isalso good practice to get the hang of the various moves you have tomake in a proof. Let's look at an example.\begin{prop}[Absorption]For all sets $A$, $B$,\[A \cap (A \cup B) = A\]\end{prop}\begin{proof}If $z \in A \cap (A \cup B)$, then $z \in A$, so $A \cap (A \cup B)\subseteq A$. Now suppose $z \in A$. Then also $z \in A \cup B$, andtherefore also $z \in A \cap (A \cup B)$.\end{proof}The preceding proof of the absorption law is very condensed. There isno mention of any definitions used, no ``we have to prove that''before we prove it, etc. Let's unpack it.  The proposition proved is ageneral claim about any sets $A$ and $B$, and when the proof mentions$A$ or $B$, these are variables for arbitrary sets.  The generalclaims the proof establishes is what's required to prove identity ofsets, i.e., that every !!{element} of the left side of the identity is!!a{element} of the right and vice versa.  \begin{quote}``If $z \in A \cap (A \cup B)$, then $z \in A$, so $A \cap (A \cup B)  \subseteq A$.''\end{quote}This is the first half of the proof of the identity: it establishesthat if an arbitrary~$z$ is !!a{element} of the left side, it is also!!a{element} of the right, i.e., $A \cap (A \cup B) \subseteq A$.Assume that $z \in A \cap (A \cup B)$. Since $z$ is an !!{element} ofthe intersection of two sets iff it is an !!{element} of both sets, wecan conclude that $z \in A$ and also $z \in A \cup B$. In particular,$z \in A$, which is what we wanted to show.  Since that's all that hasto be done for the first half, we know that the rest of the proof mustbe a proof of the second half, i.e., a proof that $A \subseteq A \cap(A \cup B)$.\begin{quote}``Now suppose $z \in A$. Then also $z \in A \cup B$, andtherefore also $z \in A \cap (A \cup B)$.''\end{quote}We start by assuming that $z \in A$, since we are showing that, forany~$z$, if $z \in A$ then $z \in A \cap (A \cup B)$.  To show that $z\in A \cap (A \cup B)$, we have to show (by definition of ``$\cap$'')that (i) $z \in A$ and also (ii) $z \in A \cup B$. Here (i) is justour assumption, so there is nothing further to prove, and that's whythe proof does not mention it again. For (ii), recall that $z$ is!!a{element} of a union of sets iff it is an !!{element} of at leastone of those sets. Since $z \in A$, and $A \cup B$ is the union of $A$and $B$, this is the case here. So $z \in A \cup B$. We've shown both(i) $z \in A$ and (ii) $z \in A \cup B$, hence, by definition of``$\cap$,'' $z \in A \cap (A \cup B)$.  The proof doesn't mentionthose definitions; it's assumed the reader has already internalizedthem.  If you haven't, you'll have to go back and remind yourself whatthey are. Then you'll also have to recognize why it follows from $z\in A$ that $z \in A \cup B$, and from $z \in A$ and $z \in A \cup B$that $z \in A \cap (A \cup B)$.Here's another version of the proof above, with everything madeexplicit:\begin{proof}{}[By definition of $=$ for sets, $A \cap (A \cup B) = A$ we have to  show (a) $A \cap (A \cup B) \subseteq A$ and (b) $A \cap (A \cup B)  \subseteq A$. (a): By definition of $\subseteq$, we have to show  that if $z \in A \cap (A \cup B)$, then $z \in A$.]  If $z \in A\cap (A \cup B)$, then $z \in A$ [since by definition of $\cap$, $z  \in A \cap (A \cup B)$ iff $z \in A$ and $z \in A \cup B$], so $A\cap (A \cup B) \subseteq A$. [(b): By definition of $\subseteq$, we  have to show that if $z \in A$, then $z \in A \cap (A \cup B)$.] Nowsuppose [(1)] $z \in A$. Then also [(2)] $z \in A \cup B$ [since by  (1) $z \in A$ or $z \in B$, which by definition of $\cup$ means $z  \in A \cup B$], and therefore also $z \in A \cap (A \cup B)$ [since  the definition of $\cap$ requires that $z \in A$, i.e., (1), and $z  \in A \cup B)$, i.e., (2)].\end{proof}\begin{prob}Expand the following proof of $A \cup (A \cap B) = A$, where youmention all the inference patterns used, why each step follows fromassumptions or claims established before it, and where we have toappeal to which definitions.\begin{proof}  If $z \in A \cup (A \cap B)$ then $z \in A$ or $z \in A \cap B$. If  $z \in A \cap B$, $z \in A$. Any $z \in A$ is also $\in A \cup (A  \cap B)$.\end{proof}\end{prob}\end{document}

content/methods/proofs/cant-do-it.tex

% Part: methods% Chapter: proofs% Section: cant-do-it\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mth}{prf}{cnt}\olsection{I Can't Do It!{}}We all get to a point where we feel like giving up. But you \emph{can}do it. Your instructor and teaching assistant, as well as your fellowstudents, can help. Ask them for help!{}  Here are a few tips to helpyou avoid a crisis, and what to do if you feel like giving up.To make sure you can solve problems successfully, do thefollowing:\begin{enumerate}\item \emph{Start as far in advance as possible.} We get busy  throughout the semester and many of us struggle with  procrastination, one of the best things you can do is to start your  homework assignments early. That way, if you're stuck, you have time  to look for a solution (that isn't crying).\item \emph{Talk to your classmates}.  You are not alone. Others in  the class may also struggle---but they may struggle with different  things. Talking it out with your peers can give you a different  perspective on the problem that might lead to a breakthrough.  Of  course, don't just copy their solution: ask them for a hint, or  explain where you get stuck and ask them for the next step. And when  you do get it, reciprocate. Helping someone else along, and  explaining things will help you understand better, too.\item \emph{Ask for help.} You have many resources available to  you---your instructor and teaching assistant are there for you and  \emph{want} you to succeed. They should be able to help you work out  a problem and identify where in the process you're struggling.\item \emph{Take a break.} If you're stuck, it \emph{might} be because  you've been staring at the problem for too long. Take a short break,  have a cup of tea, or work on a different problem for a while, then  return to the problem with a fresh mind. Sleep on it.\end{enumerate}Notice how these strategies require that you've started to work on theproof well in advance? If you've started the proof at 2am the daybefore it's due, these might not be so helpful.This might sound like doom and gloom, but solving a proof is achallenge that pays off in the end. Some people do this as acareer---so there must be something to enjoy about it. Like basicallyeverything, solving problems and doing proofs is something thatrequires practice.  You might see classmates who find this easy:they've probably just had lots of practice already.  Try not to givein too easily.If you do run out of time (or patience) on a particular problem:that's ok. It doesn't mean you're stupid or that you will never getit. Find out (from your instructor or another student) how it is done,and identify where you went wrong or got stuck, so you can avoid doingthat the next time you encounter a similar issue.  Then try to do itwithout looking at the solution.  And next time, start (and ask forhelp) earlier.\end{document}

content/methods/proofs/resources.tex

% Part: methods% Chapter: proofs% Section: resources\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mth}{prf}{res}\section{Other Resources}There are many books on how to do proofs in mathematics which may beuseful. Check out \emph{How to Read and do Proofs: An Introduction toMathematical Thought Processes} \citep{Solow2013} and \emph{How toProve It: A Structured Approach} \citep{Velleman2019} in particular.The\href{http://www.people.vcu.edu/~rhammack/BookOfProof/BookOfProof.pdf}{\emph{Bookof Proof}} \citep{Hammack2013} and\href{https://scholarworks.gvsu.edu/books/7/}{\emph{MathematicalReasoning}} \citep{Sandstrum2019} are books on proof that are freelyavailable online.  Philosophers might find\emph{MorePrecisely: The Math you need to do Philosophy} \citep{Steinhart2018} tobe a good primer on mathematical reasoning. There are also various shorter guides to proofs available on theinternet; e.g.,\href{https://math.berkeley.edu/~hutching/teach/proofs.pdf}{``Introduction  to Mathematical Arguments''} \citep{Hutchings2003} and\href{https://eugeniacheng.com/wp-content/uploads/2017/02/cheng-proofguide.pdf}{``How to  write proofs''} \citep{Cheng2004}.\subsection{Motivational Videos}Feel like you have no motivation to do your homework? Feeling down? Thesevideos might help!\begin{itemize}\item \url{https://www.youtube.com/watch?v=ZXsQAXx_ao0}\item \url{https://www.youtube.com/watch?v=BQ4yd2W50No}\item \url{https://www.youtube.com/watch?v=StTqXEQ2l-Y}\end{itemize}\end{document}