-
Notifications
You must be signed in to change notification settings - Fork 0
/
lec_notes.tex
7700 lines (6422 loc) · 304 KB
/
lec_notes.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass[12pt]{article}
% Basic stuff
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage[parfill]{parskip}
\usepackage[utf8]{inputenc}
% Skip one line between paragraphs
\parskip1em
% Standard things to include for math
\usepackage{amsmath,amssymb,amsfonts,amsthm,mathrsfs}
% Other stuff
\usepackage{wasysym}
\usepackage{stmaryrd}
\usepackage{hyperref}
\usepackage{datetime} \usdate
\usepackage[shortlabels,inline]{enumitem}
\usepackage{changepage}
\usepackage{tcolorbox}
\usepackage{tikz}
\usepackage{xcolor}
\hypersetup{
colorlinks,
linkcolor={red!50!black},
citecolor={blue!50!black},
urlcolor={blue!80!black}
}
% Some of Ebrahim's definitions
%\newcommand{\note}[1]{[#1]}
\newcommand{\note}[1]{[This portion has yet to be written.]}
\newcommand{\done}{\\\hspace*{0pt}\hfill$\blacksquare$}
\def\N{\mathbb{N}}
\def\R{\mathbb{R}}
\def\Q{\mathbb{Q}}
\def\Z{\mathbb{Z}}
\def\e{\varepsilon}
\def\d{\delta}
\newcommand{\seq}[1]{\left(#1\right)_{n\in\N}}
\renewcommand{\emptyset}{\{\hspace{-2pt}\}}
\newcommand{\powerset}[1]{\mathcal{P}(#1)}
\newcommand{\dom}[1]{\operatorname{dom}(#1)}
\newcommand{\ran}[1]{\operatorname{ran}(#1)}
\newcommand{\rev}[1]{{#1}^{\dashv}}
\newcommand{\drev}[1]{{#1}^{\dashv\dashv}}
\newcommand{\injrightarrow}{\xrightarrow{\text{inj}}}
\newcommand{\surjrightarrow}{\xrightarrow{\text{surj}}}
\newcommand{\bijrightarrow}{\xrightarrow{\text{bij}}}
\newcommand{\AND}{\wedge}
\newcommand{\OR}{\vee}
\newcommand{\ARR}{\Rightarrow}
\newcommand{\DARR}{\Leftrightarrow}
%\newcommand{\REL}{\leadsto}
\newcommand{\REL}{\sim}
\newcommand{\MODREL}[1]{#1/\hspace{-3pt}\REL{}}
\newcommand{\CLASS}[2]{[#1]_{#2}}
\def\bbel{
\,
\raisebox{-2pt}{\includegraphics[scale=0.8]{bbel.pdf}}
\,
}
\newcommand{\ALL}[2]{\left(\,\forall{#1}\,\bbel\,#2\,\right)}
\newcommand{\EXIST}[2]{\left(\,\exists{#1}\,\bbel\,#2\,\right)}
\newcommand{\COLL}[2]{\left\{\, {#1} \,\bbel\, {#2} \, \right\}}
\newcommand{\settext}[2]{\COLL{#1}{\text{#2}}}
\newcommand{\SUB}[1]{\mathcal{P}(#1)}
\newcommand{\occ}[1]{\operatorname{occ}(#1)}
\newcommand{\id}[1]{\textrm{id}_{#1}}
\renewcommand{\next}[1]{\operatorname{next}({#1})}
\newcommand{\addone}{\ddag}
\DeclareFontFamily{OT1}{pzc}{}
\DeclareFontShape{OT1}{pzc}{m}{it}{<-> s * [1.10] pzcmi7t}{}
\DeclareMathAlphabet{\mathpzc}{OT1}{pzc}{m}{it}
\newcommand{\add}{\mathpzc{ADD}}
\newcommand{\eqnm}{\approx} % equinumerous
\newcommand{\injex}{\preceq} % an injection exists
\newcommand{\injnobij}{\prec} % an injection exists but no bijection exists
%\newcommand{\SUBST}[3]{{#1}\left[{#2}\mapsto{#3}\right]}
%\newcommand{\SUBST}[3]{{#1}_{{#2}\mapsto{#3}}}
\newcommand{\SUBST}[3]{{#1}_{[{#2}\rightarrow{#3}]}}
%\newcommand{\SUBST}[3]{{#1}\,\text{replacing}\,{#2}\,\text{by}\,{#3}}
%\newcommand{\SUBST}[3]{{#1}\ \text{replacing}\ {#2}\ \text{by}\ {#3}}
%\newcounter{exercise}[subsection]
\newcounter{exercise}
\newcounter{rule}
\newcounter{theorem}
%\def\theexercise{\thesubsection.\arabic{exercise}}
\def\putExerciseHeading{\refstepcounter{exercise} \textbf{Exercise \theexercise}}
\def\putRuleNumber{\refstepcounter{rule}\therule}
\def\putThmNumber{\refstepcounter{theorem}\thetheorem}
\newcommand{\ex}[1]{ \putExerciseHeading: #1}
\newcommand{\indented}[1]{\begin{adjustwidth}{1em}{}#1\end{adjustwidth}}
\def\thmcolonspace{\hspace{0.2em}}
\def\proofnewline{\\[0.75em]} % Separates theorem box from proof, no new paragraph expected.
\def\thmStartNewline{\\[0.3em]} % Vertically separates theorem heading from theorem statement, sometimes used.
\def\proofsep{\\[-0.5em]} % Separates different proofs (e.g. to diff parts of same theorem). No new paragraph expected.
\renewcommand\qedsymbol{$\blacksquare$}
\def\done{\qed\\[0em]} % QED with newline so that QED symbol is flushed to the right. IDK why newline is needed for this to happen.
\newcommand{\thmbox}[1]{\fbox{\parbox{\textwidth}{{#1}}}}
\newcommand{\THMMOCK}[2]{\thmbox{\textbf{Theorem:} \thmcolonspace #1} \proofnewline \textit{Proof:} #2\done}
\newcommand{\THMP}[2]{\thmbox{\textbf{Theorem \putThmNumber:} \thmcolonspace #1} \proofnewline\textit{Proof:} #2\done}
\newcommand{\THMPL}[3]{\thmbox{\textbf{Theorem \putThmNumber{#3}:} \thmcolonspace #1} \proofnewline\textit{Proof:} #2\done}
\newcommand{\THMNP}[3]{\thmbox{\textbf{Theorem \putThmNumber\ (#1):} \thmcolonspace #2} \proofnewline\textit{Proof:} #3\done}
\newcommand{\THM}[1]{\thmbox{\textbf{Theorem \putThmNumber:} \thmcolonspace #1}}
\newcommand{\THMN}[2]{\thmbox{\textbf{Theorem \putThmNumber\ (#1):} \thmcolonspace #2}}
\newcommand{\AXIOM}[1]{\thmbox{\textbf{Axiom \putThmNumber:} \thmcolonspace #1}}
\newcommand{\AXIOMN}[2]{\thmbox{\textbf{Axiom \putThmNumber\ (#1):} \thmcolonspace #2}}
\newcommand{\AXIOMMOCK}[1]{\thmbox{\textbf{Axiom:} \thmcolonspace #1}}
\newcommand{\AXIOMNMOCK}[2]{\thmbox{\textbf{Axiom (#1):} \thmcolonspace #2}}
\newcommand{\DEFN}[2]{\thmbox{\textbf{Definition \putThmNumber\ (#1):} \thmcolonspace #2}}
\newcommand{\DEF}[1]{\thmbox{\textbf{Definition \putThmNumber:} \thmcolonspace #1}}
\newcommand{\RULE}[2]{\begin{tcolorbox}[title=Rule \putRuleNumber: #1,colbacktitle=white,coltitle=black,colback=white]#2\end{tcolorbox}}
\newcommand{\DRULE}[2]{\begin{tcolorbox}[title=Derived Rule \putRuleNumber: #1,colbacktitle=white,coltitle=black,colback=white]#2\end{tcolorbox}} % IDK if derived rules will be different
\newcommand{\DRULEPF}[3]{\begin{tcolorbox}[title=Derived Rule \putRuleNumber: #1,colbacktitle=white,coltitle=black,colback=white] {#2} \tcblower \textbf{Proof:} {#3} \end{tcolorbox}}
\newcommand{\DRULEPZ}[2]{\begin{tcolorbox}[title=Derived Rule \putRuleNumber: #1,colbacktitle=white,coltitle=black,colback=white] {#2} \tcblower \textbf{Proof:}
\putExerciseHeading. \end{tcolorbox}}
\def\pA{\Phi}
\def\pB{\Psi}
\def\pC{\Omega}
\def\pD{\Sigma}
\def\pE{\Gamma}
\def\pF{\Delta}
\begin{document}
\ \vfill
\begin{center}
{\Huge \scshape Proofs and Mathematical Writing}
\vspace{2em}
\textit{\Large Ebrahim Ebrahim}
\end{center}
\vfill
{
Proofs and Mathematical Writing © 2021 by Ebrahim Ebrahim is licensed under CC BY 4.0. To view a copy of this license, visit
\href{http://creativecommons.org/licenses/by/4.0/}{\color{blue!80!black}http://creativecommons.org/licenses/by/4.0/}
\vspace{2em}
This document was compiled on \today\ at\ \currenttime.
}
\thispagestyle{empty}
\newpage
\tableofcontents
\newpage
\paragraph{Layout}
Section \ref{sec:logic} will develop mathematical logic and show you how logical arguments factor into writing.
We will not yet have anything to argue \emph{about}, so our ``proofs'' in section \ref{sec:logic} will be about nothing in particular.
Section \ref{sec:sets} will then give some mathematical objects to talk about, and we will then put
content into the empty skeleton arguments of section \ref{sec:logic}.
Section \ref{sec:sets} will take you from the axioms of set theory up through a construction of the natural numbers and more.
We start in section \ref{sec:lang} with an introduction to formal axiomatic systems and informal proofs.
\section{Mathematical Language}
\label{sec:lang}
%\note{what to put here:
%this course is about both set theory and writing.
%set theory is axiomatic. describe what i mean by that, why we would do that, and the historical relevance of it.
%why rigor anyway?
%logic can also be done this way, but we will not.
%we will follow a more intuitive and informal writing-focused approach for logic,
%saving our rigor-enegery for set theory.
%perhaps include a discussion levels of rigor and formality, with one level relegating the rigor to other levels.
%mention the importance of writing and the roughness of this transition for many people.
%mention the value of forgetting what you knew before, but not really forgetting it all.}
%an illustration containing two towers, one of the math t hey built up till now, and one new tower starting here of the math they are now building
%a comment on hyperlinks in this document and the usefulness of having a back button
%\note{Write the general intro here later.}
\subsection{Parts of Speech}
\label{sec:parts_of_speech}
In a language, a \emph{part of speech} is a collection of words that share grammatical properties.
For example here are some common English parts of speech: pronouns, nouns, verbs, adjectives, and adverbs.
Different languages can have different parts of speech that are useful for describing their grammar.
To build up the grammar of a language, one can specify how parts of speech fit together to form larger
\emph{constituents}, such as noun phrases and clauses. One can further describe how
constituents fit together to form even more complex constituents, eventually grammatical sentences.
Mathematics is a language, and so it makes sense to build up its grammar (its \emph{syntax}) using this same strategy.
Instead of pronouns, nouns, verbs, noun phrases, sentences, and so on, there are just four constituents in
mathematics. Two are basic parts of speech and two are more complex constituents:
\begin{itemize}
\item \emph{Variables} are a basic part of speech.
\item \emph{Constants} are a basic part of speech.
\item \emph{Terms} can be built out of variables, constants, other terms, and propositions.
\item \emph{Propositions} can be built out of variables, constants, terms, and other propositions.
\end{itemize}
Let's go through each of these in detail.
\def\sp{\hspace{1em}}
\paragraph{Variables}
Variables serve as placeholders, waiting to be replaced by other symbols.
They are most like pronouns in English.
For example the pronoun ``it'' is a placeholder referring to something in a discussion, but what it refers to depends on the context of the discussion.
Variables are like that.
Here are some variables:
\begin{center}
$a$ \sp $b$ \sp $A$ \sp $f$ \sp $q$ \sp $x$\sp $\alpha$\sp $\beta$
\end{center}
Variables are copies of letters coming from an alphabet (usually Latin or Greek) and written in ink/chalk/pixels.
\def\sp{\hspace{1em}}
\paragraph{Constants}
\hypertarget{hl:constants}{Constants} are used as fixed names for specific mathematical objects.
They are most like \emph{proper} nouns in English.
Here are some constants:
\begin{center}
$0$ \sp $1$ \sp $2$ \sp $3$ \sp $4$ \sp $5$ \sp $6$ \sp $7$ \sp $8$ \sp $9$ \sp $\N$ \sp $\R$ \sp $\emptyset$
\end{center}
The difference between constants and variables is that constants are not meant to be substituted for.
The constant ``$2$'' refers to a specific thing, rather than being a placeholder for something.
Note that when we discuss parts of speech here, we are mainly talking about \emph{elements of language} and not about what those elements \emph{refer} to.
Germany is not a noun, it's a country. ``Germany'' is, however, a noun.
Similarly, we can say that $2$ is not a constant, but rather ``$2$'' is.
And $x$ is not a variable, but rather ``$x$'' is.
Quotation marks help us make the distinction between a symbol and what the symbol refers to
(though I will often be lazy and drop the quotation marks).
\def\sp{\hspace{1em}}
\paragraph{Terms}
Terms are strings of marks (expressions) that refer to \emph{mathematical objects}.
Since variables and constants refer to mathematical objects, they are special cases of terms.
But you can also have more complicated terms that are built out of simpler ones.
Terms are most like \emph{noun phrases} in English.
For example the phrase ``the cup that you drank from'' is a noun phrase--
it doesn't make any assertion but rather it just refers to a \emph{thing}.
Here are some terms:
\begin{itemize}[label=\sp]
\item $x$
\item $7$
\item $\{2,3,a,7\}$
\item $f(x)$
\item $\{(z,w)\} \circ g$
\item $S\times Q$
\item the square of the seventh prime number
\item a triangle
\item twelve dimensional euclidean space
\item the collection of even integers
\item $\settext{n}{$n\in\Z$ and $n$ is even}$
\item $\settext{n}{$(n\in\Z)\AND (\exists k\,|\,(k\in\Z)\AND(2k=n))$}$
\end{itemize}
The last three terms actually refer to the same mathematical object; this will soon become clear
when we get into \emph{how} the symbols refer to objects (semantics). For now we are only looking at
\emph{which} strings of symbols \emph{can} refer to objects (syntax).
You can see that some terms are more ``symbolic,'' while others are more ``Englishy.''
The formal language of mathematics is purely symbolic,
but we almost never use the language in its purest form.
Typically, we communicate by some combination of English and mathematics.
\def\sp{\hspace{1em}}
\paragraph{Propositions}
Propositions are strings of marks (expressions) that \emph{make assertions}.
They are most like \emph{sentences} in English (\emph{declarative} sentences, to be precise).
Propositions can be true or false.
Here are some propositions:
\begin{itemize}[label=\sp]
\item $x\in S$.
\item $5\notin x$.
\item $0=2$.
\item $(x\neq y) \AND (x\neq z) \AND (y\neq z)$.
\item $x$, $y$, and $z$ are distinct.
\item Either $A\subseteq P$ or $x\in S$, but not both.
\item $f:X\rightarrow Y$.
\item If $x\in S$, then we either have $x\notin W$ or we have $x\in\Z$.
\item $\neg(X\times Y \subseteq Z)$.
\item Every integer is even.
\item $\ALL{n}{(n\in\Z)\ARR \EXIST{k}{(k\in\Z)\AND(2k=n)}}$.
\end{itemize}
The last two propositions are actually saying the same thing, as we will see when we get into semantics.
Again, you can see that some propositions are more ``symbolic,'' while others are more ``Englishy.''
Typically, we make mathematical assertions by using some combination of English and mathematics.
The English that we use is a crude, but human-friendly, stand-in for formal mathematical statements.
\ex{
Determine whether each of the following is a term or a proposition.
\begin{enumerate}
\item $n$
\item $1+1=0$
\item $n$ is an odd integer
\item an odd integer
\item $f$ is a function with domain $S$
\item $1+(2+3)$
\item the empty set
\item the sum of two vectors is another vector
\item the zero vector
\item the evenness of $2$ % this one is a trick, it's neither unless you are doing metamathematics
\end{enumerate}
}
\subsection{Theorems and Proofs}
Mathematics is ultimately about propositions.
Propositions \emph{say} things, sometimes true things and sometimes false things.
We want to know: Which propositions are true? What does ``true'' even mean?
We will not exactly define ``true,'' but we will define ``provable,''
and provability will be our notion of truth.
The rules of logic allow us to make deductions and \emph{prove} new propositions
from already proven propositions.
Those already proven propositions themselves had to be proven via a sequence of logical deductions
that was applied to other previously proven propositions.
And so on...
but where does it all start?
\paragraph{Axioms}
Some propositions are declared to be \emph{axioms},
which makes them serve as starting points in our mathematical system.
The next paragraph will clarify this.
\paragraph{Proofs}
A \emph{proof} is a sequence of propositions such that each proposition is either
(1) an axiom,
(2) an already proven proposition,
or, (3) the result of applying the rules of logic to \emph{previous} propositions in the sequence.
A proposition that appears in a proof is said to be \emph{proven}.
\paragraph{Theorems}
A \emph{theorem} is a proposition which is asserted to have a proof.
\def\ES{\settext{x}{$x\neq x$}}
\paragraph{Example}
Here is an example of a proof of the proposition ``$(\forall x\,|\,x\notin\ES)$'':
\begin{adjustwidth}{1cm}{}
$(x\in\ES)\Longrightarrow (x\neq x)$\\
$(x=x)\Longrightarrow (x\notin \ES)$\\
$x=x$\\
$x\notin\ES$\\
$(\forall x\,|\,x\notin\ES)$
\end{adjustwidth}
Do not worry about interpreting what the propositions are trying to \emph{say}--
I just want to make a point about formal proofs. What you see above is a sequence of five propositions, ending with the
one I claimed to be proving, namely ``$(\forall x\,|\,x\notin\ES)$''.
To really be convinced that we are looking at a proof, we would need a \emph{justification}
for each of the five propositions-- for each proposition we need to either point out that it is
an axiom, or we need to verify that it follows logically from the previous propositions.
In this example, two of the propositions are axioms, and the other three are logical deductions;
here is a schematic depiction of these relationships:
\begin{center}
\includegraphics[scale=0.25]{img/proofFlow.pdf}
\end{center}
Again, don't worry yet about understanding why this works.
What I want you to take away from this is the general structure:
we have axioms serving as starting propositions, and we use logic to ``flow'' out from
the starting points and prove other propositions.
Given a bunch of axioms to start with, what theorems can we deduce?
To answer this question is to do math.
\paragraph{Remark about Axioms}
Axioms often serve to \emph{give meaning} to symbols.
For example, the axiom $x=x$ (along with some other axioms related to equality)
gives meaning to the symbol ``$=$''.
Without the axiom, we would still be able to form propositions like $a=b$ but we would never be able to
prove anything about them.
Suppose you ``disagree'' with the axiom $x=x$ and instead use some other propositions related to ``$=$'' as axioms.
That's perfectly fine-- you would just be giving a different meaning to the symbol ``$=$'' and it would serve a different purpose in your language.
\paragraph{Math is for Humans}
The five-line proof given above is a \emph{formal proof}-- it is written in pure mathematical language
with absolutely no English.
This is great if you want absolute rigor, but
it is not friendly to read if you are not a computer.
The main purpose of a mathematical proof is for it to convince a \emph{human} that a theorem is true.
But formal proofs make for really inefficient communication between humans.
Thus we are faced with a trade-off:
we can sacrifice some rigor to gain efficiency of communication.
\emph{Informal proofs} use a mixture of English and mathematics to make arguments.
For an example, look ahead a few paragraphs for an informal version of the five-line proof above.
We need to find a good balance between rigor and efficient communication.
Finding that balance is one of the great challenges when you first learn how to write proofs.
If we sacrifice too much rigor in an argument, then we can lose confidence in its correctness.
Or worse, we can start to prove false things!
When developing a new mathematical theory, it's generally good to err on the side of being more rigorous.
Then, as the theory develops and common patterns of arguments become routine,
one can slowly relax the rigor in favor of efficiency.
That's what this text is all about.
While it is partly giving you some specific mathematical content like set theory,
this text is mainly about how to communicate proofs in that balanced way-- rigorous, yet informal and efficient.
Here is an informal version of the five-line proof from above.
\THMMOCK{The set $\ES$ has no elements.}{
If $\ES$ did have an element, say $x$, then we would have $x\neq x$.
But in fact it is an axiom that $x=x$. Thus $\ES$ cannot have any elements.
}
The arguments are essentially the same ones that appeared in the five-line formal proof.
But, compared to the formal proof, it's much easier to process the arguments
in the informal proof
(though I'm still not expecting you to do so just yet).
% The key is to only omit rigorous details when you are tired of saying them,
% and never because you don't know what needs to be said.
\newpage
\def\s{0.25}
\newcommand{\rb}[1]{\raisebox{-0.2em}{#1}}
\ex{
In this exercise we will work with a made-up deductive language which works as follows:
\begin{itemize}
\item Propositions are the only part of speech. The propositions are $3\times 3$ grids in which each square is either blank or contains a dot. Here are three random example propositions:
\begin{center}\includegraphics[scale=\s]{img/gridgame/gridgame1.pdf}\end{center}
\item There are two logical rules in this language.
The first rule is that if a particular proposition holds, then
its clockwise rotation by ninety degrees follows. So if
\rb{\includegraphics[scale=\s]{img/gridgame/gridgame2.pdf}}
holds, then you can deduce that
\rb{\includegraphics[scale=\s]{img/gridgame/gridgame3.pdf}}.
The second rule is that if two propositions $\pA$ and $\pB$ hold, then you can deduce a third proposition
which contains a dot in any square that has a dot in either $\pA$ or $\pB$, but not both.
So for example if you have the two propositions
\rb{\includegraphics[scale=\s]{img/gridgame/gridgame6.pdf}}
and
\rb{\includegraphics[scale=\s]{img/gridgame/gridgame7.pdf}},
then you can deduce from them that
\rb{\includegraphics[scale=\s]{img/gridgame/gridgame5.pdf}}.
\item There are only two axioms in this language, and they are as follows:
\begin{center}
\includegraphics[scale=\s]{img/gridgame/gridgame8.pdf}
\hspace{2em}
\includegraphics[scale=\s]{img/gridgame/gridgame9.pdf}
\end{center}
\end{itemize}
As a demonstration of this deductive language, here is a proof that
\rb{\includegraphics[scale=\s]{img/gridgame/gridgame11.pdf}}\ :
\begin{center}
\includegraphics[scale=\s]{img/gridgame/gridgame10.pdf}
\end{center}
Can you see how this proof is correct?
These annotations may help:
\begin{center}
\includegraphics[scale=\s]{img/gridgame/gridgame12.pdf}
\end{center}
Now...
\begin{enumerate}
\item
How many propositions are there in this language?
How many propositions do you think there are in mathematics?
How many sentences are there in English?
\item
Give a completely formal proof that
\rb{\includegraphics[scale=\s]{img/gridgame/gridgame0.pdf}}.
To help out your reader, annotate the proof with arrows like in the example above.
\item (Open-ended) Can you think of a way to write an \emph{informal} version of your proof?
It would be an English description of your proof that does not explain every detail but still captures the essence of your formal proof.
%One way to think of an informal proof is: it somehow gives the reader \emph{instructions} for how to come up with the formal proof.
\item (Irrelevant but fun) Can you figure out how many propositions in this language are provable and how many are not?
\end{enumerate}
}
\section{Logic and Writing Mathematical Arguments}
\label{sec:logic}
The rest of this course will introduce logic and set theory, starting with logic in this section.
Our goal with logic is not only to understand the rules of deduction,
but also to gain the ability to \emph{write} paragraph-style deductive arguments-- informal proofs.
Logic is all about manipulating \emph{propositions}, so you will not see many \emph{terms} showing up in this section.
In fact, we will find ourselves having to discuss proofs while having nothing in particular to prove anything about.
Mathematical propositions are supposed to say things about mathematical objects;
without any mathematical objects in hand, we cannot form any actual mathematical propositions.
We will proceed with the discussion anyway, using two strategies:
First, we will use the following capital Greek letters as placeholders for mathematical propositions:
$$
\pA,
\pB,
\pC,
\pD,
\pE,
\pF.
$$
When you see these capital Greek letters, remember that they are \emph{not variables},
at least not in the sense of mathematical variables. They are not to be replaced by mathematical \emph{objects}.
Rather, they are meant to be replaced by \emph{propositions}.
When they appear in English sentences, they will take the grammatical role of independent clauses.
So, for example, we accept the following as grammatically correct English sentences:
\begin{adjustwidth}{2em}{}
I believe that $\pA$.\\
They thought that $\pA$, but in fact $\pB$.\\
$\pA$.
\end{adjustwidth}
Our second strategy
%for discussing logic without the ability to form mathematical propositions
is to apply the rules of logic to English sentences.
Even though $\pA$, $\pB$, etc. are supposed to stand for \emph{mathematical} propositions,
we will allow ourselves to replace them by declarative sentences in \emph{English}.
For example, replacing $\pA$ by ``Jim stole the car'' and $\pB$ by ``Jim is an upstanding guy'' in the above examples, we get the sentences
\begin{adjustwidth}{2em}{}
I believe that Jim stole the car.\\
They thought that Jim stole the car, but in fact Jim is an upstanding guy.\\
Jim stole the car.
\end{adjustwidth}
Later when we reach section
\ref{sec:sets}, we will start to work with actual mathematical propositions.
Section \ref{sec:logic_summary}
contains a reference table summarizing the logical constructions that are about to show up;
you can look there to get a sense for what is to come.
\ex{
Which of the following are grammatically correct? Hint: replace Greek letters with English sentences and see what makes sense.
\begin{enumerate}
\item She said that $\pC$, and I think she's onto something.
\item Take that, you accursed $\pA$!
\item Why don't we just $\pB$?
\item To $\pA$, or not to $\pA$, that is the question.
\item Whether $\pC$ or $\pD$, it will always be the case that $\pA$.
\item $\pD$ and $\pF$, but not $\pB$.
\item Despite all the $\pE$, they still wanted to $\pF$.
\item Whenever $\pC$, it turns out that $\pE$.
\item It is not true that $\pA$.
\end{enumerate}
}
\subsection{And, Or, and Not}
\paragraph{Conjunction}
\hypertarget{hl:AND}{Given} propositions $\pA$ and $\pB$, we can form their \emph{conjunction}
$$
\pA \AND \pB,
$$
which is expressed in English as ``$\pA$ and $\pB$.''
\hypertarget{hl:ANDUSE}{From} the conjunction $\pA\AND\pB$, you can deduce $\pA$ and you can deduce $\pB$.
\hypertarget{hl:ANDPV}{In} order to prove that $\pA\AND\pB$, you must prove both that $\pA$ and that $\pB$.
The following diagram, showing what you can deduce from $\pA\AND\pB$, kind of looks like the ``$\AND$'' symbol:
\begin{center}\includegraphics[scale=0.5]{img/andDiagram.pdf}\end{center}
Order does not matter for $\AND$; we consider $\pA\AND\pB$ and $\pB\AND\pA$ to be the same.
\paragraph{Disjunction}
\hypertarget{hl:OR}{Given} propositions $\pA$ and $\pB$, we can form their \emph{disjunction}
$$
\pA \OR \pB,
$$
which is expressed in English as ``$\pA$ or $\pB$.''
\hypertarget{hl:ORPV}{In} order to prove that $\pA\OR\pB$, you can either prove that $\pA$ or you can prove that $\pB$.
So if $\pA$ and $\pB$ happen to both hold, then you can still deduce that $\pA\OR\pB$
(unlike the way ``or'' is sometimes used in English).
The following diagram, showing what you can use to deduce $\pA\OR\pB$, kind of looks like the ``$\OR$'' symbol:
\begin{center}\includegraphics[scale=0.5]{img/orDiagram.pdf}\end{center}
Order does not matter for $\OR$; we consider $\pA\OR\pB$ and $\pB\OR\pA$ to be the same.
If you know that $\pA\OR\pB$, then how can you use this fact in your arguments?
You cannot deduce $\pA$ and you cannot deduce $\pB$, so how do you proceed if you want to prove some other proposition $\pC$?
\hypertarget{hl:ORUSE}{The} rule that lets you proceed is called \emph{proof by cases}:
\RULE{Proof by cases}{
Suppose that you can prove $\pC$ by assuming $\pA$, and you can also prove $\pC$ by assuming $\pB$.
Then you can deduce $\pC$ from $\pA\OR\pB$.
}
In a written proof, the format of a proof by cases ends up like this:
\THMMOCK{Assuming that either $\pA$ or $\pB$ holds, we have $\pC$.}{
Assume that either $\pA$ or $\pB$ holds.\\
Case 1: Suppose that $\pA$ holds.
\indented{[insert argument here convincing the reader that $\pC$ holds]}
Case 2: Suppose that $\pB$ holds.
\indented{[insert argument here convincing the reader that $\pC$ holds]}
Since $\pC$ holds in both cases, we can conclude that $\pC$ holds.
}
Let's do an example using English sentences.
Say you are hiking with your friend, and you see your friend brush past a plant with three-leaf bunches. You're not sure if it's poison ivy or poison oak, but you
know that it is one of them, and you know that both plants will cause a rash when touched.
So you argue to your friend: ``Suppose that plant was poison ivy. Then you would get a rash.
Now suppose the plant was poison oak. Then you would also get a rash. I'm sure that the plant was either poison ivy or it was poison oak, so you can expect a rash my friend.''
%Suppose you see a plant with three-leaf bunches and you're sure that it's either poison ivy or poison oak, but you don't know which.
%Well, you do know that poison ivy is poisonous and that poison oak is poisonous, so you can at least conclude that the plant you see is poisonous, even
%if you don't know which type of plant it is.
That's a proof by cases.
To make the proof structure apparent in
the formatting given above, replace $\pA$ by ``the plant is poison ivy,'' replace $\pB$ by ``the plant is poison oak,'' and replace $\pC$ by ``you will get a rash.''
%You get something like this:
%\THM{Assuming that the plant is either poison ivy or poison oak, we can conclude that it is poisonous.}{
%Assume that the plant is either poison ivy or poison oak.\\
%Case 1: Suppose the plant is poison ivy.
%\indented{[insert argument convincing the reader that poison ivy is poisonous.]}
%Case 2: Suppose the plant is poison oak.
%\indented{[insert argument convincing the reader that poison oak is poisonous.]}
%Since the plant is poisonous either way, we can conclude that the plant is poisonous.
%}
\paragraph{Negation}
\hypertarget{hl:NOT}{Given} a proposition $\pA$, we can form its \emph{negation}
$$
\neg \pA,
$$
which is expressed in English as ``it is not the case that $\pA$.''
To prove $\neg\pA$ is to disprove $\pA$, and in fact this is what ``disprove'' means.
When $\pA$ holds we say that $\pA$ is \emph{true}, and when $\neg\pA$ holds we say that $\pA$ is \emph{false}.
We consider $\neg\neg\pA$ to be the same as $\pA$.
%It should never be the case that a proposition holds while its negation also holds.
%We hope, at least, that $\pA\AND\not\PA$ is not provable.
A proposition of the form $\pA\AND\neg\pA$ is called a \emph{contradiction}.
If something can both be and not be the case, then our entire deductive system is certainly broken.
We hope that no contradiction is provable in our language.
\hypertarget{hl:NOTPV}{This} leads us to accept the following as a way of proving a negation $\neg\pA$:
%Further, we explicitly deem contradictions to be \emph{impossible}, in the sense that any assumption
%that leads one to deduce a contradiction must be rejected as false.
%In order to prove that $\neg\pA$, you can assume that $\pA$ does hold and then show that this leads to a contradiction.
%This is called a \emph{proof by contradiction}:
\RULE{Proof by contradiction}{
If assuming $\pA$ allows you to deduce a contradiction, then it must be that $\neg\pA$.
}
In a written proof, the format of a proof by contradiction ends up like this:
\THMMOCK{$\neg\pA$.}{
Suppose, for the sake of obtaining a contradiction, that $\pA$ holds.
\indented{[insert argument convincing reader that a contradiction, something of the form $\pB\AND\neg\pB$, now follows]}
Since this is a contradiction, we conclude that $\neg\pA$.
}
Let's do an example using English sentences.
Say you're investigating a crime and you are considering a particular suspect.
Assuming the suspect did commit the crime, you can deduce that the suspect must have been at the crime scene on that day.
Upon questioning witnesses, you discover that the suspect was at work and could not have been at the crime scene that day.
This contradiction leads you to reject the original assumption; the suspect must not have committed the crime.
Making an assumption so that you can reject it after deducing an impossible situation-- that is a proof by contradiction.
To make the proof structure apparent in
the formatting given above, replace
$\pA$ by ``the suspect committed the crime'' and replace $\pB$ by ``the suspect was at the crime scene that day''.
The proof by contradiction rule rejects that a mathematical proposition can be both true and false.
There's
another rule involving negation which
enforces that mathematical propositions must be either true or false:
\RULE{Excluded middle}{
$\pA\OR\neg\pA$
}
There is no ``middle ground'' in which a proposition is neither true nor false.
% go back and do a better job presenting rules in terms of formatting, and separatign susbsections perhaps with illustrated titles
% exercise that helps to understand how in english you can have inclusive and exclusive or, while math is inclusive.
% exercise that shows how parentheses are needed in and-or combinations
% in the same exercise you can show how and distributes over or and vice versa
% maybe the ex can be structured like this: for each of the following deductions, decide whether it is valid or not. if not valid, then justify by...
% uhhh truth table? or maybe you can give them some sample true and false english facts to put in, and do an example.
% some kind of exercise involving demorgan's law. or maybe you should write about that above
% idea: a deduction of demorgan's law going one way, and have them prove it going the other way
% maybe an exercise involving truth tables, having them fill one out for basic things and then for more complicated props
\ex{
The ``or'' of mathematical logic sometimes behaves differently from the English ``or.''
Describe a situation in which
\begin{center} ``The cake is flavored with either vanilla or chocolate.'' \end{center}
would pretty much be considered false, while
\begin{center} ``The cake is flavored with vanilla''\ $\OR$\ ``The cake is flavored with chocolate''. \end{center}
would be true.
}
\ex{
Suppose we know the following three facts:
\begin{itemize}
\item Whenever it rains over night, the grass gets wet.
\item On a night that it doesn't rain, the sprinklers are run.
\item Whenever sprinklers are run, the grass gets wet.
\end{itemize}
Now write a proof of the following statement: ``The grass got wet last night.''
To make your argument, apply excluded middle to the statement ``It rained last night,''
and then do a proof by cases.
Follow the formatting given in this section for proof by cases.
}
\ex{
Suppose we know the following four facts:
\begin{itemize}
\item Whenever it rains over night, the grass gets wet.
\item On a night that it doesn't rain, the sprinklers are run.
\item Whenever sprinklers are run, \emph{as long as they are not broken}, the grass gets wet.
\item The grass was dry last night.
\end{itemize}
Now write a proof of the following statement: ``It did not rain last night and the sprinklers are broken.''
To make your argument,
do a proof by contradiction to establish ``it did not rain last night,''
and do another proof by contradiction to establish ``the sprinklers are broken.''
Once both are established you can conclude the conjunction.
Follow the formatting given in this section for proof by contradiction.
}
\newcommand{\truthtablefour}[5]{
\begin{tabular}{|c|c|c|}
\hline
$\pA$ & $\pB$ & #1 \\ \hline
F & F & #2 \\ \hline
F & T & #3 \\ \hline
T & F & #4 \\ \hline
T & T & #5 \\ \hline
\end{tabular}
}
\newcommand{\truthtabletwo}[3]{
\begin{tabular}{|c|c|}
\hline
$\pA$ & #1 \\ \hline
F & #2 \\ \hline
T & #3 \\ \hline
\end{tabular}
}
\def\sp{\hspace{1em}}
\ex{
Thanks to the law of excluded middle, there are only two possibilities for a single proposition $\pA$: it is either true or false.
For \emph{two} propositions $\pA$ and $\pB$, there are \emph{four} possibilities, which we can list in a nice table:
\begin{center}
\begin{tabular}{|c|c|}
\hline
$\pA$ & $\pB$ \\ \hline
F & F \\ \hline
F & T \\ \hline
T & F \\ \hline
T & T \\ \hline
\end{tabular}
\end{center}
For three propositions there are eight possibilities, and so on.
This suggests a useful way to think about the logical operators $\AND$, $\OR$, and $\neg$:
\begin{center}
\truthtablefour{$\pA\AND\pB$}{F}{F}{F}{T}
\sp
\truthtablefour{$\pA\OR\pB$}{F}{T}{T}{T}
\sp
\truthtabletwo{$\neg\pA$}{T}{F}
\end{center}
Here we are simply listing all the possibilities for the component propositions $\pA$, $\pB$, etc.,
and then we are indicating whether the complex proposition is true or false in each case. These are called \emph{truth tables}.
\begin{enumerate}
\item
Write out a truth table for $\neg(\pA\AND\pB)$. It should have four rows.
\item
Write out a truth table for $(\pA\AND\pB)\OR\pC$, and also for $\pA\AND(\pB\OR\pC)$.
The table should have eight rows, and you can feel free to make just one table in which
there is a column for $(\pA\AND\pB)\OR\pC$ and a column for $\pA\AND(\pB\OR\pC)$.
\item
Your answer to the above should convince you that it's a terrible idea to write something like ``$\pA\AND\pB\OR\pC$.''
Replace $\pA$, $\pB$, and $\pC$ by English sentences in $\pA\AND\pB\OR\pC$ such that you get an ambiguous English sentence.
Explain the ambiguity in your sentence.
\item \label{itm:truthtables:first_equiv}
Write out a truth table for $(\pA\AND\pB)\AND\pC$, and also for $\pA\AND(\pB\AND\pC)$.
The answer should convince you that there is no trouble at all with writing $\pA\AND\pB\AND\pC$,
though you were probably convinced anyway since $\pA\AND\pB\AND\pC$ can obviously only mean:
``$\pA$, $\pB$, and $\pC$ are all true.''
\item
Write out a truth table for $(\pA\AND\pB)\OR\pA$. This one should just have four rows.
Looking at the table, do you see a way to ``simplify'' the complex proposition $(\pA\AND\pB)\OR\pA$?
\item
Write out a truth table for $(\pA\AND\pB)\OR\pC$, and also for $(\pA\OR\pC)\AND(\pB\OR\pC)$.
This should show you that $\OR$ can ``distribute'' over $\AND$.
\item
Write out a truth table for $(\pA\OR\pB)\AND\pC$, and also for $(\pA\AND\pC)\OR(\pB\AND\pC)$.
This should show you that $\AND$ can ``distribute'' over $\OR$.
\item \label{itm:truthtables:last_equiv}
Write out a truth table for $\neg(\pA\AND\pB)$, and also for $(\neg\pA)\OR(\neg\pB)$.
\end{enumerate}
In parts \ref{itm:truthtables:first_equiv} through \ref{itm:truthtables:last_equiv},
you see that certain propositions are ``equivalent'' in some sense. The formal meaning of ``equivalent'' will be
discussed in the next section.
}
\subsection{If and Iff}
\paragraph{Implication}
\hypertarget{hl:ARR}{Given} propositions $\pA$ and $\pB$, we can form the \emph{implication}
$$
\pA\ARR\pB,
$$
which is expressed in English as ``$\pA$ implies $\pB$'' or ``if $\pA$, then $\pB$.''
The ``$\pA$'' part of an implication $\pA\ARR\pB$ is called the \emph{hypothesis},
and the ``$\pB$'' part is called the \emph{conclusion}.
\hypertarget{hl:ARRPV}{To} prove $\pA\ARR\pB$,
start by assuming $\pA$ and
then give an argument that $\pB$ follows.
That is, assume the hypotheses and then argue that the conclusion follows.
Such a proof ends up structured like this:
\THMMOCK{If $\pA$, then $\pB$.}{
Assume that $\pA$.
\indented{[insert argument convincing reader that $\pB$ holds]}
Thus, $\pA\ARR\pB$.
}
\hypertarget{hl:ARRUSE}{The} rule that allows us to use $\pA\ARR\pB$ is modus ponens:
\RULE{Modus Ponens\label{rule:mp}}{
Given $\pA\ARR\pB$ and $\pA$, you can deduce $\pB$.
}
Here is also another great rule for using an implication (this one can be derived from modus ponens via a proof by contradiction):
\DRULE{Modus Tollens}{
Given $\pA\ARR\pB$ and $\neg\pB$, you can deduce $\neg\pA$.
}
\paragraph{Logical Equivalence}
\hypertarget{hl:DARR}{Given} propositions $\pA$ and $\pB$, we can form the \emph{logical equivalence}
$$
\pA\DARR\pB,
$$
which is expressed in English as ``$\pA$ if and only if $\pB$,'' often shortened to ``$\pA$ iff $\pB$.''
An equivalence holds when two propositions are forced to be true or false \emph{together}--
that is, when they are either both true or both false.
\hypertarget{hl:DARRPV}{To} prove an equivalence $\pA\DARR\pB$, simply prove both of the implications $\pA\ARR\pB$ and $\pB\ARR\pA$.
The proof will be structured like this:
\THMMOCK{$\pA\DARR\pB$.}{
Assume that $\pA$.
\indented{[insert argument convincing reader that $\pB$ holds]}
Now assume that $\pB$.
\indented{[insert argument convincing reader that $\pA$ holds]}
}
\hypertarget{hl:DARRUSE}{Using} an equivalence works a lot like modus ponens, except it goes in both directions.
If you know that $\pA\DARR\pB$, then you can deduce $\pA$ from $\pB$, $\neg\pA$ from $\neg\pB$,
$\pB$ from $\pA$, and $\neg\pB$ from $\neg\pA$.
\def\sp{\hspace{1em}}
Here are the truth tables for $\ARR$ and $\DARR$:
\begin{center}
\truthtablefour{$\pA\ARR\pB$}{???}{???}{F}{T}
\sp
\truthtablefour{$\pA\DARR\pB$}{T}{F}{F}{T}
\end{center}
There should be nothing surprising there, except that I've left some question marks in position where I think you might be surprised.
If $\pA$ is false, then what of the proposition $\pA\ARR\pB$?
It has to be either true or false (due to excluded middle), so which is it?
Put another way: Suppose you say ``If $3$ is even, then $3$ is divisible by $2$.''
Knowing that $3$ is not even, are you a liar? Is your statement true or false?
The answer is that it's \emph{true}!
Here is the completed truth table for $\ARR$:
\begin{center}
\truthtablefour{$\pA\ARR\pB$}{T}{T}{F}{T}
\end{center}
\hypertarget{hl:vacuous}{Putting} T there is not an arbitrary choice-- if you agreed with all the previous logical rules then you \emph{must} agree
that $\pA\ARR\pB$ is \emph{true} when $\pA$ is false.
Let me try and convince you. First we need to revisit contradictions.
\def\vsp{\\[0.5em]}
Recall how \emph{proof by contradiction} works:
If an assumption leads to a contradiction, then the assumption is rejected as false.
If you assume $\pB$, and then after some argumentation you deduce $\pA\AND\neg\pA$, then
you can back out of your original assumption and conclude without a doubt that $\neg\pB$.
Now let's think, hypothetically, what would happen if a contradiction $\pA\AND\neg\pA$ were actually \emph{true}?
If $\pA\AND\neg\pA$ holds, then we can prove $\pB$ by contradiction as follows:
\indented{
Suppose, for the sake of contradiction, that $\neg\pB$ holds.\vsp
Since $\pA\AND\neg\pA$ has already been assumed to hold, we've already reached a contradiction.\vsp
We conclude that $\neg\neg\pB$, and therefore $\pB$, must hold.
}
Let's be clear about what just happened: from the assumption $\pA\AND\neg\pA$, we were able to prove an \emph{arbitrary proposition}!
This mechanism was always present in the proof by contradiction rule, but it is worth highlighting:
\DRULE{\label{rule:contradictions}Contradictions are powerful!}{
From $\pA\AND\neg\pA$ you can deduce \emph{any} proposition $\pB$.
}
Now back to the question of how to treat $\pA\ARR\pB$ when $\pA$ is false.
Recall that in order to prove $\pA\ARR\pB$, one can assume $\pA$ and then deduce $\pB$.
If we know that $\pA$ is false to start with, then here is a proof that $\pA\ARR\pB$:
\indented{
Assume $\pA$.\vsp
Since $\pA$ is known to be false, we now have a contradiction $\pA\AND\neg\pA$.\vsp
Using ``contradictions are powerful,'' we can now deduce anything we want! In particular, we can deduce $\pB$.
}
Thus if you accept proofs by contradiction as valid, then you must accept that $\pA\ARR\pB$ is true when $\pA$ is false.
An implication that is true because its hypothesis is false is sometimes said to be \emph{vacuously true}.
\ex{
Assume that we know the following facts:
\begin{itemize}
\item Alice is an accountant and holds no other profession.
\item Bob has brown hair.
\item Charles loves chocolate and despises all other foods.
\end{itemize}
Determine whether each of the following is true or false.
\begin{enumerate}
\item %3
If
Bob's hair is purple
then
Charles loves chocolate.
\item %2
If
Alice is an accountant
then
Charles likes green beans.
\item %6
Alice is an accountant
if and only if
Alice is a doctor.
\item %1
If
Bob has brown hair
then
Charles loves chocolate.
\item %7
Charles likes baked salmon