-
Notifications
You must be signed in to change notification settings - Fork 0
/
nst_solutions.html
914 lines (913 loc) · 59.2 KB
/
nst_solutions.html
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
<html><head><title>niplav</title>
<link href="./favicon.png" rel="shortcut icon" type="image/png"/>
<link href="main.css" rel="stylesheet" type="text/css"/>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type"/>
<!DOCTYPE HTML>
<style type="text/css">
code.has-jax {font: inherit; font-size: 100%; background: inherit; border: inherit;}
</style>
<script async="" src="./mathjax/latest.js?config=TeX-MML-AM_CHTML" type="text/javascript">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
extensions: ["tex2jax.js"],
jax: ["input/TeX", "output/HTML-CSS"],
tex2jax: {
inlineMath: [ ['$','$'], ["\\(","\\)"] ],
displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
processEscapes: true,
skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
},
"HTML-CSS": { availableFonts: ["TeX"] }
});
</script>
<script>
document.addEventListener('DOMContentLoaded', function () {
// Change the title to the h1 header
var title = document.querySelector('h1')
if(title) {
var title_elem = document.querySelector('title')
title_elem.textContent=title.textContent + " – niplav"
}
});
</script>
</head><body><h2 id="home"><a href="./index.html">home</a></h2>
<p><em>author: niplav, created: 2019-03-20, modified: 2022-07-23, language: english, status: in progress, importance: 2, confidence: likely</em></p>
<blockquote>
<p><strong><a href="https://en.wikipedia.org/wiki/Naive_Set_Theory_(book)">“Naive Set
Theory”</a>
by <a href="https://en.wikipedia.org/wiki/Paul_Halmos">Paul Halmos</a> is a short
introduction to set theory. Here, I present solutions to the explicitely
stated exercises and problems in that book.</strong></p>
</blockquote><div class="toc"><div class="toc-title">Contents</div><ul><li><a href="#Section_3">Section 3</a><ul><li><a href="#Exercise_1">Exercise 1</a><ul></ul></li></ul></li><li><a href="#Section_4">Section 4</a><ul><li><a href="#Exercise_1_1">Exercise 1</a><ul></ul></li></ul></li><li><a href="#Section_5">Section 5</a><ul><li><a href="#Some_Easy_Exercises">Some Easy Exercises</a><ul></ul></li><li><a href="#Exercise_1_2">Exercise 1</a><ul></ul></li><li><a href="#Exercise_2">Exercise 2</a><ul></ul></li></ul></li><li><a href="#Section_6">Section 6</a><ul><li><a href="#A_NonTrivial_Exercise">A Non-Trivial Exercise</a><ul></ul></li><li><a href="#Exercise_1_3">Exercise 1</a><ul></ul></li></ul></li><li><a href="#Section_7">Section 7</a><ul><li><a href="#Exercise_1_4">Exercise 1</a><ul></ul></li><li><a href="#Exercise_2_1">Exercise 2</a><ul></ul></li></ul></li><li><a href="#Section_8">Section 8</a><ul><li><a href="#Exercise_1_5">Exercise 1</a><ul></ul></li><li><a href="#Exercise_2_2">Exercise 2</a><ul></ul></li></ul></li><li><a href="#Section_9">Section 9</a><ul><li><a href="#Exercise_1_6">Exercise 1</a><ul><li><a href="#Other_Failing_Ways_of_Interpreting_the_Exercise">Other Failing Ways of Interpreting the Exercise</a><ul></ul></li></ul></li><li><a href="#Exercise_2_3">Exercise 2</a><ul></ul></li><li><a href="#Exercise_3">Exercise 3</a><ul></ul></li></ul></li><li><a href="#Section_10">Section 10</a><ul><li><a href="#Exercise_1_7">Exercise 1</a><ul></ul></li><li><a href="#Exercise_2_4">Exercise 2</a><ul></ul></li><li><a href="#Exercise_3_1">Exercise 3</a><ul></ul></li><li><a href="#Query_1">Query 1</a><ul></ul></li><li><a href="#Exercise_4">Exercise 4</a><ul></ul></li><li><a href="#Query_2">Query 2</a><ul></ul></li><li><a href="#Exercise_5">Exercise 5</a><ul></ul></li></ul></li><li><a href="#Section_11">Section 11</a><ul><li><a href="#Exercise_1_8">Exercise 1</a><ul></ul></li></ul></li><li><a href="#Section_12">Section 12</a><ul><li><a href="#Exercise_1_9">Exercise 1</a><ul></ul></li><li><a href="#Exercise_2_5">Exercise 2</a><ul></ul></li><li><a href="#Exercise_3_2">Exercise 3</a><ul></ul></li><li><a href="#Exercise_4_1">Exercise 4</a><ul><li><a href="#None">Lemma: Any Successor of $n$ Contains $n$</a><ul></ul></li></ul></li></ul></li><li><a href="#Section_13">Section 13</a><ul><li><a href="#Stray_Exercise_1">Stray Exercise 1</a><ul></ul></li><li><a href="#Exercise_1_10">Exercise 1</a><ul></ul></li><li><a href="#Exercise_2_6">Exercise 2</a><ul></ul></li><li><a href="#Exercise_3_3">Exercise 3</a><ul></ul></li><li><a href="#Exercise_4_2">Exercise 4</a><ul></ul></li></ul></li><li><a href="#Section_14">Section 14</a><ul><li><a href="#Exercise_1_11">Exercise 1</a><ul></ul></li><li><a href="#Stray_Exercise_1_1">Stray Exercise 1</a><ul></ul></li></ul></li><li><a href="#Section_15">Section 15</a><ul><li><a href="#Stray_Exercise_1_2">Stray Exercise 1</a><ul></ul></li><li><a href="#Stray_Exercise_2">Stray Exercise 2</a><ul><li><a href="#I">I.</a><ul></ul></li><li><a href="#II">II.</a><ul></ul></li><li><a href="#I_1">I.</a><ul></ul></li><li><a href="#II_1">II.</a><ul></ul></li></ul></li></ul></li></ul></div>
<h1 id="Solutions_to_Nave_Set_Theory"><a class="hanchor" href="#Solutions_to_Nave_Set_Theory">Solutions to “Naïve Set Theory”</a></h1>
<h2 id="Section_3"><a class="hanchor" href="#Section_3">Section 3</a></h2>
<h3 id="Exercise_1"><a class="hanchor" href="#Exercise_1">Exercise 1</a></h3>
<p>It seems like there is no way one could use either insetting (putting
a given set into another set) and pairing or pairing on two different
inputs to obtain the same set. However, if one sees pairing the same set,
then pairing <code>$\emptyset$</code> with <code>$\emptyset$</code> would result in <code>$\{\emptyset\}$</code>,
which is also the result of insetting <code>$\emptyset$</code>.</p>
<p>Proof:</p>
<p>Insetting and pairing must have different results because insetting
will always result in a set with 1 element, and pairing will always
result in a set with 2 elements. Therefore, they can't be the same set.</p>
<p>Pairing the sets a, b and c, d can't result in the same set unless
<code>$a=c$</code> and <code>$b=d$</code> or <code>$a=d$</code> and <code>$b=c$</code>. Otherwise, <code>$\{a,b\}$</code> would contain
at least one element not in <code>$\{c,d\}$</code>.</p>
<p>□</p>
<h2 id="Section_4"><a class="hanchor" href="#Section_4">Section 4</a></h2>
<h3 id="Exercise_1_1"><a class="hanchor" href="#Exercise_1_1">Exercise 1</a></h3>
<p>I am not exactly sure what I'm supposed to do here. I guess
"observe" means "prove" here, so "prove that the condition
has nothing to do with the set B".</p>
<p>Proof:</p>
<div>
$$(A \cap B) \cup C = A \cap (B \cup C) \Leftrightarrow C \subset A\\
(A \cup C) \cap (B \cup C) = A \cap (B \cup C) \Leftrightarrow C \subset A\\
A \cup C = A \Leftrightarrow C \subset A$$
</div>
<p>The last statement is trivially true.</p>
<p>□</p>
<h2 id="Section_5"><a class="hanchor" href="#Section_5">Section 5</a></h2>
<h3 id="Some_Easy_Exercises"><a class="hanchor" href="#Some_Easy_Exercises">Some Easy Exercises</a></h3>
<p><code>$A-B=A \cap B'$</code></p>
<p>Proof:</p>
<p><code>$A-B=\{a | a \in A \land a \not \in B\}=\{a | a \in A \land a \in B'\}=A \cap B'$</code></p>
<p>□</p>
<p><code>$A \subset B \hbox{ if and only if } A-B=\emptyset$</code></p>
<p>Proof:</p>
<div>
$$A \subset B \Leftrightarrow \forall a \in A:\\
a \in B \Leftrightarrow \exists C:\\
B=A \cup C \Leftrightarrow A-(A \cup C)=\emptyset \Leftrightarrow A-B=\emptyset$$
</div>
<p>□</p>
<p><code>$A-(A-B)=A \cap B$</code></p>
<p>Proof:</p>
<div>
$$ A-(A-B)=\\
A-(A \cap B')=\\
A \cap (A \cap B')'=\\
A \cap (A' \cup B)=\\
A \cap A' \cup A \cap B=\\
\emptyset \cup A \cap B=\\
A\cap B$$
</div>
<p>□</p>
<p><code>$A \cap (B-C)=(A \cap B)-(A \cap C)$</code></p>
<p>Proof:</p>
<div>
$$(A \cap B)-(A \cap C)=\\
(A \cap B) \cap (A \cap C)'=\\
(A \cap B) \cap (A' \cup C')=\\
(A \cap B \cap A') \cup (A \cap B \cap C')=\\
A \cap B \cap C'=\\
A \cap (B-C)$$
</div>
<p>□</p>
<p><code>$A \cap B \subset (A \cap C) \cup (B \cap C')$</code></p>
<p>Proof:</p>
<div>
$$A \cap B \subset (A \cap C) \cup (B \cap C')\\
=((A \cap C) \cup B) \cap ((A \cap C) \cup C')\\
=((A \cap C) \cup B) \cap ((A \cup C') \cap (C \cup C'))\\
=((A \cap C) \cup B) \cap (A \cup C')\\
=(A \cup B) \cap (C \cup B) \cap (A \cup C')$$
</div>
<p><code>$A \cap B \subset (A \cup B) \cap (C \cup B) \cap (A \cup C')$</code> is true
because <code>$A \subset (A \cup B)$</code> and <code>$B \subset (C \cup B)$</code> and
<code>$A \subset (A \cup C')$</code>.</p>
<p>□</p>
<p><code>$ (A \cup C) \cap (B \cup C') \subset A \cup B $</code></p>
<p>Proof:</p>
<div>
$$ (A \cup C) \cap (B \cup C')\\
= ((A \cup C) \cap B) \cup ((A \cup C) \cap C')\\
= ((A \cup C) \cap B) \cup A\\
= (A \cap B) \cup (C \cap B) \cup A \subset A \cup B $$
</div>
<p>This is the case because <code>$(A \cap B) \cup (C \cap B) \subset B$</code> (since
intersections with <code>$B$</code> are subsets of <code>$B$</code>), and the union with <code>$A$</code>
doesn't change the equation.</p>
<p>□</p>
<h3 id="Exercise_1_2"><a class="hanchor" href="#Exercise_1_2">Exercise 1</a></h3>
<p>To be shown: The power set of a set with n elements has <code>$2^n$</code> elements.
Proof by induction.</p>
<p>Proof:</p>
<p>Induction base: The power set of the empty set contains 1 element:</p>
<p><code>$|P(\emptyset)|=|{\emptyset}|=1=2^0=2^{|\emptyset|}$</code></p>
<p>Induction assumption:</p>
<p><code>$|P(A)|=2^{|A|}$</code></p>
<p>Induction step:</p>
<p>To be shown: <code>$|P(A \cup \{a\}|=2*2^{|A|}=2^{|A|+1}$</code>.</p>
<p><code>$P(A \cup \{a\})$</code> contains two disjunct subsets: <code>$P(A)$</code> and <code>$N=\{\{a\}\cup S | S \in P(A)\}$</code>.
Those are disjunct because every element in <code>$N$</code>
contains <code>$a$</code> (<code>$\forall n \in N: a \in n$</code>), but there is no element of
<code>$P(A)$</code> that contains <code>$a$</code>. Also, it holds that <code>$P(A) \cup N=P(A \cup\{a\})$</code>,
because elements in the power set can either contain <code>$a$</code>
or not, there is no middle ground. It is clear that <code>$|N|=|P(A)|$</code>,
therefore <code>$|P(A \cup \{a\})|=|P(A)|+|N|=2*|P(A)|=2*2^{|A|}=2^{|A|+1}$</code>.</p>
<p>□</p>
<h3 id="Exercise_2"><a class="hanchor" href="#Exercise_2">Exercise 2</a></h3>
<p>To be shown:</p>
<p><code>${\cal{P}}(E) \cap {\cal{P}}(F)={\cal{P}}(E \cap F)$</code></p>
<p>Proof:</p>
<p>If <code>$S \in {\cal{P}}(E \cap F)$</code>, then <code>$\forall s \in S: s \in E \cap F$</code>. Therefore,
<code>$S \subset E$</code> and <code>$S \subset F$</code> and thereby <code>$S \in {\cal{P}}(E)$</code> and <code>$S \in {\cal{P}}(F)$</code>.
This means that <code>$S \in {\cal{P}}(E) \cap {\cal{P}}(F)$</code>.</p>
<p>If <code>$S \in {\cal{P}}(E) \cap {\cal{P}}(F)$</code>, then a very similar proof
can be written: <code>$S \subset E$</code> and <code>$S \subset F$</code>, so
<code>$\forall s \in S:s \in E$</code> and <code>$\forall s \in S: s \in F$</code>.
Then <code>$S \subset E \cap F$</code> and therefore <code>$S \in {\cal{P}}(E \cap F)$</code>.</p>
<p>□</p>
<p>To be shown:</p>
<p><code>${\cal{P}}(E) \cup {\cal{P}}(F)\subset{\cal{P}}(E \cup F)$</code></p>
<p>Proof:</p>
<p>If <code>$S \in {\cal{P}}(E) \cup {\cal{P}}(F)$</code>, then
<code>$S \in {\cal{P}}(E) \Leftrightarrow S \subset E$</code> or
<code>$S \in {\cal{P}}(F) \Leftrightarrow S \subset F$</code>. Since it
is true for any set <code>$X$</code> that <code>$S \subset E \Rightarrow S \in {\cal{P}}(E \cup X)$</code>,
it is true that <code>$S \in {\cal{P}}(E \cup F)$</code>
(similar argumentation if <code>$S \subset F$</code>).</p>
<p>□</p>
<p>A reasonable interpretation for the introduced notation:
If <code>${\cal{C}}={X_1, X_2, \dots, X_n}$</code>, then</p>
<p><code>$\bigcap_{X \in \cal{C}} X=X_1 \cap X_2 \cap \dots X_n$</code></p>
<p>Similarly, if <code>${\cal{C}}={X_1, X_2, \dots, X_n}$</code>, then</p>
<p><code>$\bigcup_{X \in \cal{C}} X=X_1 \cup X_2 \cup \dots X_n$</code></p>
<p>The symbol <code>${\cal{P}}$</code> still stands for the power set.</p>
<p>To be shown:</p>
<p><code>$\bigcap_{X \in \cal{C}} {\cal{P}}(X)={\cal{P}}(\bigcap_{X \in \cal{C}} X)$</code></p>
<p>Proof by induction.</p>
<p>Induction base:</p>
<p><code>${\cal{P}}(E) \cap {\cal{P}}(F)={\cal{P}}(E \cap F)$</code></p>
<p>Induction assumption:</p>
<p><code>$\bigcap_{X \in \cal{C}} {\cal{P}}(X)={\cal{P}}(\bigcap_{X \in \cal{C}} X)$</code></p>
<p>Induction step:</p>
<div>
$${\cal{P}}(Y) \cap \bigcap_{X \in \cal{C}} {\cal{P}}(X)\\
={\cal{P}}(Y) \cap {\cal{P}}(\bigcap_{X \in \cal{C}} X)\\
={\cal{P}}(Y \cap \bigcap_{X \in \cal{C}} X)$$
</div>
<p>The last step uses <code>${\cal{P}}(E) \cap {\cal{P}}(F)={\cal{P}}(E \cap F)$</code>,
since <code>$\bigcap_{X \in \cal{C}} X$</code> is also just a set.</p>
<p>□</p>
<p>To be shown:</p>
<p><code>$\bigcup_{X \in \cal{C}} {\cal{P}}(X) \subset{\cal{P}}(\bigcup_{X \in \cal{C}} X)$</code></p>
<p>Proof by induction.</p>
<p>Induction base:</p>
<p><code>${\cal{P}}(E) \cup {\cal{P}}(F) \subset {\cal{P}}(E \cup F)$</code></p>
<p>Induction assumption:</p>
<p><code>$\bigcup_{X \in \cal{C}} {\cal{P}}(X) \subset {\cal{P}}(\bigcup_{X \in \cal{C}} X)$</code></p>
<p>Induction step:</p>
<div>
$${\cal{P}}(Y) \cup \bigcup_{X \in \cal{C}} {\cal{P}}(X)\\
\subset {\cal{P}}(Y) \cup {\cal{P}}(\bigcup_{X \in \cal{C}} X)\\
\subset {\cal{P}}(Y \cup \bigcup_{X \in \cal{C}} X)$$
</div>
<p>The last step uses <code>${\cal{P}}(E) \cup {\cal{P}}(F) \subset {\cal{P}}(E\cup F)$</code>,
since <code>$\bigcup_{X \in \cal{C}} X$</code> is also just a set.</p>
<p>□</p>
<p>To be shown:</p>
<p><code>$\bigcup {\cal{P}}(E)=E$</code></p>
<p>Proof:</p>
<p><code>$\forall X \in {\cal{P}}(E): X \subset E$</code>. Furthermore, <code>$E \in {\cal{P}}(E)$</code>.
Since <code>$A \subset E \Rightarrow A \cup E=E$</code>, it holds
that <code>$E=\bigcup_{X \in {\cal{P}}(E)}=\bigcup {\cal{P}}(E)$</code>.</p>
<p>□</p>
<p>And "E is always equal to <code>$\bigcup_{X \in {\cal{P}}(E)}$</code> (that is
<code>$\bigcup {\cal{P}}(E)=E$</code>), but that the result of applying <code>${\cal{P}}$</code>
and <code>$\bigcup$</code> to <code>$E$</code> in the other order is a set that includes E as a
subset, typically a proper subset" (p. 21).</p>
<p>I am not entirely sure what this is supposed to mean. If it means
that we treat <code>${\cal{E}}$</code> as a collection, then
<code>$\forall X \in {\cal{E}}:\bigcup_{E \in {\cal{E}}} E \subset X$</code>.
But that doesn't mean that
<code>${\cal{E}} \subset {\cal{P}}(\bigcup_{E \in {\cal{E}}}E)$</code>:
If <code>${\cal{E}}=\{\{a,b\},\{b,c\}\}$</code>, then <code>$\bigcup_{E \in {\cal{E}}} E=\{b\}$</code>,
and
<code>${\cal{E}}=\{\{a,b\},\{b,c\}\} \not\subset {\cal{P}}(\{b\})=\{\{b\},\emptyset\}$</code>.</p>
<p>If we treat <code>$E$</code> simply as a set, then <code>$\bigcup E=E$</code>, and it is of course
clear that <code>$E \subset {\cal{P}}(E)$</code>, as for all other subsets of <code>$E$</code>.</p>
<p>□</p>
<h2 id="Section_6"><a class="hanchor" href="#Section_6">Section 6</a></h2>
<h3 id="A_NonTrivial_Exercise"><a class="hanchor" href="#A_NonTrivial_Exercise">A Non-Trivial Exercise</a></h3>
<p>"find an intrinsic characterization of those sets of subsets of A that
correspond to some order in A"</p>
<p>Let <code>${\cal{M}} \subset {\cal{P}}({\cal{P}}(A))$</code> be the set of all possible
orderings of <code>$A$</code>. In the case of <code>$A=\{a, b\}$</code>, <code>$\cal{M}$</code> would be
<code>$\{\{\{a\}, \{a, b\}\}, \{\{b\}, \{a, b\}\}\}$</code>.</p>
<p>Some facts about every element <code>$M \in \cal{M}$</code>:</p>
<p><code>$\bigcap M=\{min\}$</code>, where <code>$\{min\}$</code> is the smallest element in the ordering
<code>$M$</code>, the element in <code>$M$</code> for which there is no other element <code>$a \in M$</code>
so that <code>$a \subset \{min\}$</code> (which means that <code>$\emptyset \not \in M$</code>).</p>
<p><code>$\bigcup M=A$</code>. <code>$A$</code> must therefore be in <code>$M$</code> and be the biggest element
(no element <code>$a \in M$</code> so that <code>$a \supset A$</code>).</p>
<p>For all elements <code>$m \in M$</code> except <code>$\{min\}$</code> there exists at least one
element <code>$n \in M$</code> so that <code>$n \subset m$</code>.</p>
<p>Similarly, for all elements <code>$m \in M$</code> except <code>$A$</code> there exists at least
one element <code>$n \in M$</code> so that <code>$n \supset m$</code>.</p>
<p>For every <code>$m \in M$</code> except <code>$A$</code> and <code>$\{min\}$</code>, there exist two unique
elements <code>$x,y \in M$</code> so that <code>$m$</code> is the only set in <code>$M$</code> for which it
is true that <code>$x \subset m \subset y$</code>.</p>
<p>For every <code>$a \in A$</code>, there must exist two sets <code>$m,n \in M$</code> so that
<code>$n=m \cup \{a\}$</code> (except for <code>$min$</code>). This means that the <code>$|A|=|M|$</code>,
the size of <code>$A$</code> is the size of <code>$M$</code>.</p>
<p>These conditions characterise <code>$\cal{M}$</code> intrinsically and are the solution
to the question.</p>
<h3 id="Exercise_1_3"><a class="hanchor" href="#Exercise_1_3">Exercise 1</a></h3>
<p>(i) To be shown: <code>$(A \cup B) \times X=(A \times X) \cup (B \times X)$</code></p>
<p>Proof:</p>
<div>
$$(A \cup B) \times X=\\
\{(e, x): e \in A \lor e \in B, x \in X\}=\\
\{(e, x): e \in A, x \in X\} \cup \{(e, x): e \in B, x \in X\}=\\
(A \times X) \cup (B \times X)$$
</div>
<p>□</p>
<p>(ii) Te be shown: <code>$(A \cap B) \times (X \cap Y)=(A \times X) \cap (B \times Y)$</code></p>
<div>
$$(A \times X) \cap (B \times Y)=\\
\{(x,y), x \in A, y \in X\} \cap \{(v,w), v \in B, w \in Y\}=\\
\{(x,y), x \in A \land x \in B, y \in X \land y \in Y\}=\\
\{(x,y), x \in A \cap B, y \in X \cap Y\}=\\
(A \cap B) \times (X \cap Y)$$
</div>
<p>□</p>
<p>(iii) To be shown: <code>$(A-B) \times X = (A \times X)-(B \times X)$</code></p>
<p>Two-sided proof by contradiction:</p>
<p>1. <code>$(A-B)\times X \subset (A \times X)-(B \times X)$</code></p>
<p>Let <code>$(u,v) \in (A-B) \times X$</code>. Then <code>$u \in (A-B)$</code>, and <code>$v \in X$</code>.
Suppose <code>$(u, v) \not \in (A \times X)-(B\times X)$</code>. Then
<code>$(u,v) \in (A \times X) \cap (B \times X)$</code>. Then <code>$(u,v) \in (A \cap B) \times (X \cap X)$</code>.
Then <code>$u \in A \cap B$</code> and <code>$v \in X$</code>. But if <code>$u \in A \cap B$</code>,
then <code>$u \not \in A-B$</code>! Contradiction.</p>
<p>2. <code>$ (A \times X)-(B \times X) \subset (A-B)\times X$</code></p>
<p>Let <code>$(u,v) \in (A \times X)-(B\times X)$</code>. Then <code>$(u,v)\in(A \times X)$</code>
and <code>$(u,v)\not \in (B \times X)$</code>. Because <code>$v$</code> must be in <code>$X$</code>, and there
is no flexibility there, <code>$u \not \in B$</code>. Suppose <code>$(u,v)\not \in (A-B) \times X$</code>.
Since necessariliy <code>$v \in X$, $u \not \in A-B$</code>. But if <code>$u \not \in A-B$, $u$</code>
must be an element of <code>$A\cap B$</code>. Then <code>$u \in B$</code>,
and there is a contradiction.</p>
<p>□</p>
<h2 id="Section_7"><a class="hanchor" href="#Section_7">Section 7</a></h2>
<h3 id="Exercise_1_4"><a class="hanchor" href="#Exercise_1_4">Exercise 1</a></h3>
<p>Reflexive, but neither symmetric nor transitive (symmetry violation:
<code>$(b,a)\not\in$</code>, transitivity violation: <code>$(a,c)\not\in$</code>):
<code>$\{(a,a),(a,b),(b,b),(b,c),(c,c)\}$</code></p>
<p>Symmetric, but neither reflexive nor transitive (reflexivity violation:
<code>$(a,a)\not\in$</code>, transitivity violation: <code>$(a,c)\not\in$</code>):
<code>$\{(a,b),(b,a),(b,c),(c,b)\}$</code></p>
<p>Transitive, but neither reflexive nor symmetric (reflexivity
violation: <code>$(a,a)\not\in$</code>, symmetry violation: <code>$(b,a)\not\in$</code>):
<code>$\{(a,b),(b,c),(a,c)\}$</code></p>
<h3 id="Exercise_2_1"><a class="hanchor" href="#Exercise_2_1">Exercise 2</a></h3>
<blockquote>
<p>We shall write <code>$X/R$</code> for the set of all equivalence classe. (Pronounce
<code>$X/R$</code> as “X modulo R,“ or, in abbreviated form, “X mod R.“ Exercise:
show that <code>$X/R$</code> is indeed a set by exhibiting a condition that specifies
exactly the subset <code>$X/R$</code> of the power set <code>${\cal{P}}(X)$</code>).</p>
</blockquote>
<p><em>— <a href="https://en.wikipedia.org/wiki/Paul_Halmos">Paul Halmos</a>, <a href="https://en.wikipedia.org/wiki/Naive_Set_Theory_(book)">“Naïve Set Theory“</a> p. 38, 1960</em></p>
<p>To be honest, I'm not quite sure what exactly I am supposed to do here.
<code>$X/R$</code> has been defined as being a set, how can I prove a definition?</p>
<p>But I can try and construct <code>$X/R$</code> from <code>${\cal{P}}(X)$</code>:</p>
<p><code>$X/R=\{E: (\forall x, y \in E: x R y) \land E \in {\cal{P}}(X) \} \subset {\cal{P}}(X)$</code></p>
<p>□, I guess?</p>
<h2 id="Section_8"><a class="hanchor" href="#Section_8">Section 8</a></h2>
<h3 id="Exercise_1_5"><a class="hanchor" href="#Exercise_1_5">Exercise 1</a></h3>
<p>Basically, the question is "Which projections are one-to-one", or,
"Which projections are injective"?</p>
<p>The answer is: A projection <code>$p: X\times Y \mapsto X$</code> is injective iff
<code>$\forall (x,y)\in X \times Y: \nexists (x,z) \in X \times Y: z \neq y$</code>.
Or, simpler: Every element of <code>$X$</code> occurs at most once in the relation.
This can be extended easily to relations composed of more than 2 sets.</p>
<h3 id="Exercise_2_2"><a class="hanchor" href="#Exercise_2_2">Exercise 2</a></h3>
<p>(i) To be shown: <code>$Y^{\emptyset}=\{\emptyset\}$</code></p>
<p>1. <code>$\emptyset:\emptyset \rightarrow Y$</code> (the empty set is a function
from <code>$\emptyset$</code> to <code>$Y$</code>).</p>
<p>This is true because <code>$\emptyset$</code> is a relation so that
<code>$\emptyset \subset \emptyset \times Y$</code>, and <code>$\forall x \in \emptyset: \exists (x,y) \in \emptyset$</code>.
Or: <code>$\emptyset$</code> is a set of pairs that maps all elements in
<code>$\emptyset$</code> to <code>$X$</code>, and therefore a function from <code>$\emptyset$</code> to
<code>$X$</code>.</p>
<p>2. Assume <code>$\exists x \in Y^{\emptyset}: x \neq \emptyset$</code></p>
<p>Then <code>$x: \emptyset \rightarrow Y$</code>, and <code>$x \subset \emptyset \times Y$</code>.
But <code>$\emptyset \times X$</code> can only be <code>$\emptyset$</code>, but it was assumed
that <code>$x \neq \emptyset$</code>. Therefore, no such <code>$x$</code> can exist.</p>
<p>(ii) To be shown: <code>$X \neq \emptyset \Rightarrow \emptyset^{X}=\emptyset$</code></p>
<p>Assume <code>$\exists f \in \emptyset^{X}$</code>. Then
<code>$f \subset X \times \emptyset \land \forall x \in X: \exists (x,y) \in f: y \in \emptyset$</code>
(or: <code>$f$</code> maps all elements of <code>$X$</code> to an element in
<code>$\emptyset$</code>). However there are no elements in the empty set (that I
know of), so <code>$f$</code> can't exist.</p>
<p>However, if <code>$X=\emptyset$</code>, then (i) applies. So <code>$\emptyset^{\emptyset}=\{\emptyset\}$</code>.</p>
<h2 id="Section_9"><a class="hanchor" href="#Section_9">Section 9</a></h2>
<h3 id="Exercise_1_6"><a class="hanchor" href="#Exercise_1_6">Exercise 1</a></h3>
<p>Here, the reader is asked to formulate and prove the commutative law
for unions of families of sets.</p>
<p>For context, the associative law for unions of families of sets is
formulated as follows:</p>
<blockquote>
<p>Suppose, for instance, that <code>$\{I_{j}\}$</code> is a family of sets with
domain <code>$J$</code>, say; write <code>$K=\bigcup_{j} I_{j}$</code>, and let <code>$\{A_{k}\}$</code> be
a family of sets with domain <code>$K$</code>. It is then not difficult to prove that</p>
<div>
$$\bigcup_{k \in K} A_{k}=\bigcup_{j \in J}(\bigcup_{i \in I_{j}} A_{i}) $$
</div>
</blockquote>
<p>Okay, this is all fine and dandy, but where am I going with this? Well,
I have probably misunderstood this, because the way I understand it,
the correct way to formulate the commutative law for unions of families
does <em>not</em> hold.</p>
<p>Let's say <code>$X$</code> is a set indexed by <code>$I$</code>, or, in other words, <code>$x_{i}$</code>
is a family. Let's then define a new operator index-union to make these
expressions easier to read: <code>$I໔X$</code> as <code>$\bigcup_{i \in I} X_{i}$</code>.</p>
<p>The associative law then expanded reads as</p>
<div>
$$\bigcup_{k \in \bigcup_{j \in J} I_{j}} A_{k}=\bigcup_{j \in J}(\bigcup_{i \in I_{j}} A_{i})$$
</div>
<p>or, simpler, as <code>$(J໔I)໔A=J໔(I໔A)$</code>.</p>
<p>Then, simply, the commutative version of the law would be <code>$A໔B=B໔A$</code>.</p>
<p>Then there is a very simple counterexample:</p>
<p><code>$A=\{1,2\}$</code>, <code>$B=\{a,b\}$</code>. Then a family from A to B could
be <code>$\{(1,\{a\}),(2,\{b\})\}$</code> and a family from B to a could
be <code>$\{(a,\{1\}),(b,\{2\})\}$</code>. Then
<code>$A໔B=\bigcup_{a \in A} B_{a}=\{1,2\}$</code>
and <code>$B໔A=\bigcup_{b \in B} A_{b}=\{a,b\}$</code>, and those
two are different sets.</p>
<p>Despite my obvious love for unnecessarily inventing new notation,
I'm not a very good mathematician, and believe (credence <code>$\ge 99\%$</code>)
that I have misunderstood something here (the rest is taken up by this
being an editing/printing mistake). I am not sure what, but would be
glad about some pointers where I'm wrong.</p>
<h4 id="Other_Failing_Ways_of_Interpreting_the_Exercise"><a class="hanchor" href="#Other_Failing_Ways_of_Interpreting_the_Exercise">Other Failing Ways of Interpreting the Exercise</a></h4>
<p>Other ways of interpreting the exercise also have obvious
counter-examples.</p>
<p>If <code>$f, g$</code> are two families in <code>$X$</code> (as functions:
<code>$f: X \rightarrow X, g: X \rightarrow X$</code>), then the
counterexample is</p>
<div>
$$X=\{a,b\}\\
f_{a}=b, f_{b}=b\\
g_{a}=a, g_{b}=a\\
f໔g=\{b\}\\
g໔f=\{a\}$$
</div>
<p>If <code>$f, g$</code> are two families of sets in <code>$X$</code> (as functions:
<code>$f: X \rightarrow {\cal{P}}(X), g: X \rightarrow {\cal{P}}(X)$</code>), then the
counterexample is</p>
<div>
$$X=\{a,b,c\}\\
f_{a}=\{b\}, f_{b}=\{b\}, f_{c}=\{b\}\\
g_{a}=\{a\}, g_{b}=\{c\}, g_{c}=\{c\}\\
f໔g=\{b\}\\
g໔f=\{c\}$$
</div>
<h3 id="Exercise_2_3"><a class="hanchor" href="#Exercise_2_3">Exercise 2</a></h3>
<p>To be shown:</p>
<p>(i): <code>$(\bigcup_{i \in I} A_{i}) \cap (\bigcup_{j \in J} B_{j})=\bigcup_{(i,j) \in I \times J} (A_{i} \cap B_{j})$</code></p>
<p>1. <code>$(\bigcup_{i \in I} A_{i}) \cap (\bigcup_{j \in J} B_{j}) \subset \bigcup_{(i,j) \in I \times J} (A_{i} \cap B_{j})$</code></p>
<p>Let <code>$e \in (\bigcup_{i \in I} A_{i}) \cap (\bigcup_{j \in J} B_{j})$</code>.
Then there exists an <code>$i_{e} \in I$</code> so that <code>$e \in A_{i_{e}}$</code> and a
<code>$j_{e} \in J$</code> so that <code>$e \in B_{j_{e}}$</code>.
Then <code>$(i_{e}, j_{e}) \in I \times J$</code>, and furthermore <code>$e \in A_{i_{e}} \cap B_{j_{e}}$</code>.
Since <code>$A_{i_{e}} \cap B_{j_{e}} \subset \bigcup_{(i,j) \in I \times J} (A_{i} \cap B_{j})$</code>,
<code>$e$</code> is contained in there as well.</p>
<p>Only in this case I will attempt to write out the the proof more formally:</p>
<div>
$$e \in (\bigcup_{i \in I} A_{i}) \cap (\bigcup_{j \in J} B_{j}) \Rightarrow \\
e \in (\bigcup_{i \in I} A_{i}) \land e \in (\bigcup_{j \in J} B_{j}) \Rightarrow \\
(\exists i_{e} \in I: e \in A_{i_{e}}) \land (\exists j_{e} \in J: e \in B_{j_{e}}) \Rightarrow \\
\exists i_{e} \in I: \exists j_{e} \in J: e \in A_{i_{e}} \land e \in B_{j_{e}} \Rightarrow \\
\exists (i_{e}, j_{e}) \in I \times J: e \in (A_{i_{e}} \cap B_{j_{e}}) \Rightarrow \\
e \in \bigcup_{(i,j) \in I \times J} (A_{i} \cap B_{j})$$
</div>
<p>2. <code>$(\bigcup_{i \in I} A_{i}) \cap (\bigcup_{j \in J} B_{j}) \supset \bigcup_{(i,j) \in I \times J} (A_{i} \cap B_{j})$</code></p>
<p>Let <code>$e \in \bigcup_{(i,j) \in I \times J} (A_{i} \cap B_{j})$</code>.
Then there exists <code>$(i_{e}, j_{e}) \in I \times J$</code> so that
<code>$e \in (A_{i_{e}} \cap B_{j_{e}})$</code>.
But then <code>$e \in \bigcup_{i \in I} A_{i}$</code> and <code>$e \in \bigcup_{j \in J} B_{j}$</code>,
which means that <code>$e$</code> is also in their intersection.</p>
<p>□</p>
<p>(ii): <code>$(\bigcap_{i \in I} A_{i}) \cup (\bigcap_{j \in J} B_{j})=\bigcap_{(i,j) \in I \times J} (A_{i} \cup B_{j})$</code></p>
<p>1. <code>$(\bigcap_{i \in I} A_{i}) \cup (\bigcap_{j \in J} B_{j}) \subset \bigcap_{(i,j) \in I \times J} (A_{i} \cup B_{j})$</code></p>
<p>Let <code>$e \in (\bigcap_{i \in I} A_{i}) \cup (\bigcap_{j \in J}B_{j})$</code>.
Then <code>$e$</code> is an element of all of <code>$A_{i}$</code> or an element of all of
<code>$B_{j}$</code> (or both). Since that is the case, <code>$e$</code> is always an element of
<code>$A_{i} \cup B_{j}$</code>. Then <code>$e$</code> is also an element of the intersection
of all of these unions <code>$\bigcap_{(i,j) \in I \times J} (A_{i} \cup B_{j})$</code>.</p>
<p>This can be written down more formally as well:</p>
<div>
$$e \in (\bigcap_{i \in I} A_{i}) \cup (\bigcap_{j \in J} B_{j}) \Rightarrow \\
e \in (\bigcap_{i \in I} A_{i}) \lor e \in (\bigcap_{j \in J} B_{j}) \Rightarrow \\
\forall i \in I: e \in A_{i} \lor \forall j \in J: e \in B_{j} \Rightarrow \\
\forall i \in I: \forall j \in J: e \in A_{i} \lor e \in B_{j} \Rightarrow \\
\forall i \in I: \forall j \in J: e \in A_{i} \cup B_{j} \Rightarrow \\
e \in \bigcap_{(i,j) \in I \times J} (A_{i} \cup B_{j})$$
</div>
<p>2. <code>$(\bigcap_{i \in I} A_{i}) \cup (\bigcap_{j \in J} B_{j}) \supset \bigcap_{(i,j) \in I \times J} (A_{i} \cup B_{j})$</code></p>
<p>Let <code>$e \in \bigcap_{(i,j) \in I \times J} (A_{i} \cup B_{j})$</code>. Then
for every <code>$i$</code> and <code>$j$</code>, <code>$e \in A_{i} \cup B_{j}$</code>. That means that
for every <code>$i$</code>, <code>$e \in A_{i}$</code>: if there is just one <code>$j$</code> so that <code>$e \not \in B_{j}$</code>,
for the last sentence to be true, <code>$A_{i}$</code> must compensate for that. Or,
if not an <code>$e$</code> in every <code>$A_{i}$</code>, then this must be true for every
<code>$B_{j}$</code> (with a similar reasoning as for <code>$A_{i}$</code>). But if <code>$e$</code> in
every <code>$A_{i}$</code> or every <code>$B_{j}$</code>, it surely must be in their union.</p>
<p>□</p>
<h3 id="Exercise_3"><a class="hanchor" href="#Exercise_3">Exercise 3</a></h3>
<p>To be proven:</p>
<p><code>$(\bigcup_{i} A_{i}) \times (\bigcup_{j} B_{j})=\bigcup_{i,j}(A_{i} \times B_{j})$</code></p>
<div>
$$ e \in \bigcup_{i,j}(A_{i} \times B_{j}) \\
(e_{1},e_{2}) \in \bigcup_{i,j}(A_{i} \times B_{j}) \Leftrightarrow \\
\exists i \in I, j \in J: (e_{1},e_{2}) \in A_{i} \times B_{j} \Leftrightarrow \\
\exists i \in I, j \in J: (e_{1} A_{i}) \land (e_{2} \in B_{j}) \Leftrightarrow \\
\exists i \in I: (e_{1} A_{i}) \land \exists j \in J: (e_{2} \in B_{j}) \Leftrightarrow \\
(e_{1} \in \bigcup_{i} A_{i}) \land (e_{2} \in \bigcup_{j} B_{j}) \Leftrightarrow \\
(e_{1}, e_{2}) \in (\bigcup_{i} A_{i}) \times (\bigcup_{j} B_{j}) \Leftrightarrow \\
e \in (\bigcup_{i} A_{i}) \times (\bigcup_{j} B_{j}) $$
</div>
<p>One can say that
<code>$(e_{1}, e_{2}) \in (\bigcup_{i} A_{i}) \times (\bigcup_{j} B_{j}) = \exists i \in I, j \in J: e_{1} \in A_{i} \land e_{2} \in B_{j}$</code>
because there must be at least one <code>$i$</code> so that <code>$e \in A_{i}$</code>, and
because all combinations of elements are chosen from <code>$A$</code> and <code>$B$</code>.</p>
<p>□</p>
<p>To be proven:</p>
<p><code>$(\bigcap_{i} A_{i}) \times (\bigcap_{j} B_{j})=\bigcap_{i,j}(A_{i} \times B_{j})$</code></p>
<div>
$$ e \in \bigcap_{i,j}(A_{i} \times B_{j}) \\
(e_{1},e_{2}) \in \bigcap_{i,j}(A_{i} \times B_{j}) \Leftrightarrow \\
\forall i \in I, j \in J: (e_{1},e_{2}) \in A_{i} \times B_{j} \Leftrightarrow \\
\forall i \in I, j \in J: (e_{1} A_{i}) \land (e_{2} \in B_{j}) \Leftrightarrow \\
\forall i \in I: (e_{1} A_{i}) \land \forall j \in J: (e_{2} \in B_{j}) \Leftrightarrow \\
(e_{1} \in \bigcap_{i} A_{i}) \land (e_{2} \in \bigcap_{j} B_{j}) \Leftrightarrow \\
(e_{1}, e_{2}) \in (\bigcap_{i} A_{i}) \times (\bigcap_{j} B_{j}) \Leftrightarrow \\
e \in (\bigcap_{i} A_{i}) \times (\bigcap_{j} B_{j}) $$
</div>
<p>□</p>
<p>To b proven:</p>
<p><code>$\bigcap_{i} X_{i} \subset X_{j} \subset \bigcup_{i} X_{i}$</code></p>
<p>Proof:</p>
<div>
$$ e \in \bigcap_{i} X_{i} \Rightarrow \\
\forall i: e \in X_{i} \Rightarrow \\
\forall i: \exists j: {i,j} \subset I \land i=j \land e \in X_{i} \Rightarrow \\
\forall i: \exists j: i \in I \land j \in J \land i=j \land e \in X_{j} \Rightarrow \\
e \in X_{j} \Rightarrow \\
\exists j \in I: e \in X_{j} \Rightarrow \\
\exists i \in I: e \in X_{i} \Rightarrow \\
e \in \bigcup_{i} X_{i} $$
</div>
<p>□</p>
<h2 id="Section_10"><a class="hanchor" href="#Section_10">Section 10</a></h2>
<h3 id="Exercise_1_7"><a class="hanchor" href="#Exercise_1_7">Exercise 1</a></h3>
<p>(i) To be shown: <code>$f(\bigcup_{i} A_{i}) = \bigcup_{i} f(A_{i}$</code></p>
<p>If <code>$e \in f(\bigcup_{i} A_{i})$</code>, then there exists an <code>$i$</code> for which
<code>$e \in f(A_{i})$</code>. Then also <code>$e \in \bigcup_{i}f(A_{i})$</code> (since the
same set of indices is iterated over).</p>
<p>If otherwise <code>$e \in \bigcup_{i} f(A_{i})$</code>, then there is also an <code>$i$</code>
for which <code>$e \in f(A_{i}$</code>. Then <code>$e$</code> is at least once an element of
<code>$f(\bigcup_{i} A_{i})$</code>.</p>
<p>(ii) To be shown: <code>$f(\bigcap_{i} A_{i}) \neq \bigcap_{i} f(A_{i}$</code></p>
<p>Example:
<code>$I=\{1, 2\}, A_1=\{1\}, A_2=\{2\}, f(\{1\})=\{a\}, f(\{2\})=\{a\}, f(\emptyset)=\emptyset, f(\{1,2\})=\{a\}$</code></p>
<p>Then <code>$f(\bigcap_{i} A_{i})=f(\{1\} \cap \{2\})=f(\emptyset)=\emptyset$</code>,
but <code>$\bigcap_{i} f(A_{i})=\{a\} \cap \{a\}=\{a\}$</code>.</p>
<h3 id="Exercise_2_4"><a class="hanchor" href="#Exercise_2_4">Exercise 2</a></h3>
<blockquote>
<p>A necessary and sufficient condition that <code>$f$</code> map <code>$X$</code> onto <code>$Y$</code>
is that the inverse image under <code>$f$</code> of each non-empty subset of <code>$Y$</code>
be a non-empty subset of <code>$X$</code>. (Proof?)</p>
</blockquote>
<!--TODO: with "maps onto", he probably means "surjective", i.e. all
values are mapped to-->
<p>But that's—false? Unless I understand something different by "map"
(which I just take as relates from one set to another, possibly in a
many-to-one relation).</p>
<p>Example:</p>
<p><code>$X=\{1,2\}, Y=\{a,b\}$</code>. <code>$f(\{1\})=\{a\}, f(\{2\})=\{a\}$</code>, etc for
all subsets of $X$. Then <code>$f^{-1}(\{b\})=\emptyset$</code>.</p>
<h3 id="Exercise_3_1"><a class="hanchor" href="#Exercise_3_1">Exercise 3</a></h3>
<p>To be proven: $h(gf)=(hg)f$</p>
<p>Proof:</p>
<p>$((hg)f)(x)=((hg)(f(x)))=h(g(f(x)))=h(gf(x))$</p>
<h3 id="Query_1"><a class="hanchor" href="#Query_1">Query 1</a></h3>
<blockquote>
<p>what do <code>$R^{-1}$</code>, <code>$S^{-1}$</code>, <code>$RS$</code>, and <code>$R^{-1}S^{-1}$</code> mean?"</p>
</blockquote>
<p><code>$yR^{-1}x$</code>: <code>$y$</code> father of <code>$x$</code>, <code>$z S^{-1}y$</code>: <code>$z$</code> is brother of
<code>$y$</code>. <code>$$xRSy$</code>: <code>$x$</code> nephew of <code>$y$</code>. <code>$xR^{-1}S^{-1}$</code>.</p>
<h3 id="Exercise_4"><a class="hanchor" href="#Exercise_4">Exercise 4</a></h3>
<p>To be proven: <code>$(SR)^{-1}=R^{-1}S^{-1}$</code></p>
<p>Proof:</p>
<p>Let <code>$(z,x) \in (SR)^{-1}$</code>. Then <code>$xSRz$</code>. Then <code>$\exists y: xSy \land yRs$</code>.
Then <code>$yS^{-1}x$</code> and <code>$zR^{-1}y$</code>, and then <code>$zR^{-1}S^{-1}x$</code>.</p>
<h3 id="Query_2"><a class="hanchor" href="#Query_2">Query 2</a></h3>
<blockquote>
<p>is there a connection among I, <code>$RR^{-1}$</code>, and <code>$R^{-1}R$</code>?</p>
</blockquote>
<p>Shouldn't <code>$I=RR^{-1}$</code>? No. Because if <code>$xRy$</code> and <code>$zRy$</code>, then
<code>$xRR^{-1}z$</code>. But <code>$I \subset RR^{-1}$</code>, and <code>$I \subset R^{-1}R$</code>. I think
alsso that <code>$RR^{-1}=(R^{-1}R)^{-1}$</code>, and <code>$R^{-1}R=(RR^{-1})^{-1}$</code>
(which is true by the previously proven theorem). I don't think there's
any further connections here.</p>
<h3 id="Exercise_5"><a class="hanchor" href="#Exercise_5">Exercise 5</a></h3>
<p>(i) Given <code>$g: Y \rightarrow X$</code> and <code>$gf(x)=x$</code>, then <code>$f$</code> is "one-to-one"
and "<code>$g$</code> maps <code>$Y$</code> onto <code>$X$</code>".</p>
<p>Judging from what I understand, "<code>$f$</code> is one-to-one" would mean that <code>$f$</code>
is <a href="https://en.wikipedia.org/wiki/Injective_function">injective</a>,
and "<code>$g$</code> maps <code>$X$</code> onto <code>$X$</code>" just means that <code>$g$</code> is
<a href="https://en.wikipedia.org/wiki/Surjective_function">surjective</a>?</p>
<p>Wikipedia agrees with these hunches.</p>
<p><code>$\forall x_1, x_2 \in X: x_1 \neq x_2 \Leftrightarrow f(x_1) \neq f(x_2)$</code>,
because if <code>$f(x_1)=f(x_2)=y$</code> for <code>$x_1 \neq x_2$</code>, then
<code>$f(y)=x_1$</code> and $f(y)=x_2$, which is not possible.</p>
<p>$g$ is surjective, since every element in <code>$\hbox{dom } f \subset Y$</code> has
exactly one corresponding element in $X$ through $g$, but elements in <code>$Y - \hbox{dom } f$</code>
must also be mapped to $X$ (it could be that
<code>$Y - \hbox{dom } f=\emptyset$</code>, but that is not guaranteed).</p>
<p>□</p>
<p>(ii) To be proven: <code>$f(A \cap B)=f(A) \cap f(B)$</code> iff for all subsets of
<code>$A$</code> and <code>$B$</code>, <code>$f$</code> injective.</p>
<p>First case: <code>$f$</code> injective <code>$\Rightarrow f(A \cap B) = f(A) \cap f(B)$</code>.</p>
<p>Let <code>$y \in f(A \cap B)$</code>, then there exists exactly one <code>$x \in X$</code>
so that <code>$f(x)=y$</code>.
That means <code>$x \in A \land x \in B$</code>. Then <code>$e \in f(A) \land e \in f(B)$</code>.</p>
<p>Second case: <code>$f(A \cap B)=f(A) \cap f(B) \Rightarrow f$</code> injective.</p>
<p>More formal:</p>
<p><code>$f(A \cap B)=f(A) \cap f(B) \Rightarrow \forall x_1 \neq x_2 \in X, f(x_1) \neq f(x_2)$</code>.</p>
<p>Let then <code>$x_1 \neq x_2 \in X$</code>, so that <code>$f(x_1)=f(x_2)=y$</code>. Let then
<code>$A, B$</code> so that <code>$x_1 \in A \backslash B$</code> and <code>$x_2 \in B \backslash A$</code>.</p>
<p>Then <code>$y \in f(A) \cap f(B)$</code>, but <code>$y \not \in f(A \cap B)$</code>. So those
<code>$x_1, x_2$</code> can't exist, therefore f is injective.</p>
<p>□</p>
<p>(iii) To be proven: f injective <code>$\Leftrightarrow f(X-A) \subset Y-f(A)$</code>
for all subsets of A.</p>
<p>First case: f inj. <code>$\Rightarrow f(X-A) \subset Y-f(A)$</code></p>
<p>Let <code>$e \in f(X-A)$</code> and <code>$e \not \in Y-f(A)$</code>. Then <code>$\exists x \in X-A$</code>
so that <code>$f(x)=e$</code>, and there is no <code>$x_2 \in A: f(x_2)=e$</code>
(since f is injective). But since <code>$e \in Y$</code> (by definition) and <code>$e \not \in f(A)$</code>,
e must be in <code>$Y-f(A)$</code>.</p>
<p>Second case: <code>$f(X-A) \subset Y-f(A) \Rightarrow f$</code> inj.</p>
<p>Assume <code>$x_1, x_2 (x_1 \not = x_2)$</code> so that <code>$f(x_1)=f(x_2)=y$</code>. Let
then <code>$x_1 \not \in A$</code> and <code>$x_2 \in A$</code>. Then <code>$y \in f(X-A)$</code>
(since <code>$x_1 \in X-A$</code>). But since <code>$y \in f(A)$</code>, <code>$y \not \in Y-f(A)$</code>.
Contradiction, f must be injective.</p>
<p>□</p>
<p>(iv) To be shown: <code>$\forall y : \exists x: f(x)=y \Leftrightarrow Y-f(A) \subset f(X-A)$</code></p>
<p>First case: f surj. <code>$\Rightarrow \forall A \subset X: Y-f(A) \subset f(X-A)$</code></p>
<p>Assume <code>$y \in Y$</code> and <code>$y \not \in fNA)$</code>. If <code>$y \not \in f(X-A)$</code>, then
<code>$\lnot \exists x \in X-A$</code> so that <code>$f(x)=y$</code>. But since f is surjective,
there must be an x so that <code>$f(x)=y$</code> and <code>$x \not \in A$</code>! Contradiction.</p>
<p>Second case:
<code>$\forall A \subset X: Y-f(A) \subset f(X-A) \Rightarrow \forall y: \exists x: f(x)=y$</code>.</p>
<p>Assume <code>$ \exists y \in Y: \lnot \exists x: f(x)=y$</code>. Then <code>$y \in Y-f(A)$</code>
for all A, but <code>$y \not \in f(X-A)$</code> (since y is not in the
range). Contradiction of the assumption, such a y can't exist.</p>
<h2 id="Section_11"><a class="hanchor" href="#Section_11">Section 11</a></h2>
<h3 id="Exercise_1_8"><a class="hanchor" href="#Exercise_1_8">Exercise 1</a></h3>
<blockquote>
<p>Since the intersection of every (non-empty) family of successor sets
is a successor set itself (proof?)</p>
</blockquote>
<p>Let <code>$\{S_i\}$</code> be a family of successor sets.</p>
<p>Every <code>$s_i \in \{S_i\}$</code> is a successor set, then it is guaranteed that
<code>$0 \in s_i$</code>. One can assume that <code>$\forall s_i \in \{S_i\}: x \in s_i$</code>,
which implies that <code>$x \in \bigcap_{i \in I} s_i$</code>. But since all <code>$s_i$</code>
are successor sets, <code>$x^+$</code> must also be an element of all <code>$s_i$</code> Then
<code>$x^+ \in \bigcap_{i \in I} s_i$</code>, and the intersection of the family
is a successor set.</p>
<p>□</p>
<p>However, remember the definition of a family: a family of sets is
a function that maps from an index set into the powerset of a set,
so this function is <code>$f: I \rightarrow \mathcal{P}(A)$</code>.</p>
<p>In this case, we could set <code>$I=\{\emptyset\}$</code> and
<code>$\hbox{ran} f=\{\{\{\emptyset, \{\emptyset\}\}\}\}$</code>,
with <code>$f(\emptyset)=\{\{\emptyset, \{\emptyset\}\}\}$</code>. That
would make f a non-empty family, but
<code>$\bigcap_{i \in I} s_i=\{\{\{\emptyset, \{\emptyset\}\}\}\}$</code>,
which is definitely not a successor set. Since the solution I presented
above seems exactly like the thing Halmos would want me to do, I guess
I have misunderstood the definition for "family of sets".</p>
<h2 id="Section_12"><a class="hanchor" href="#Section_12">Section 12</a></h2>
<h3 id="Exercise_1_9"><a class="hanchor" href="#Exercise_1_9">Exercise 1</a></h3>
<blockquote>
<p>Prove that if $n$ is a natural number, then <code>$n \not = n^{+}$</code></p>
</blockquote>
<p>For <code>$n=0=\emptyset$</code>, <code>$n \not = n^+$</code>:</p>
<div>
$$n^+=\\
n \cup \{n\}=\\
\emptyset \cup \{\emptyset\}=\\
\{\emptyset\}\not =\\
\emptyset=\\
n$$
</div>
<p>Let <code>$n^-$</code> be the number such that <code>${n^-}^+=n$</code>, and assume that
<code>$n^- \not =n$</code>.</p>
<p>Then for <code>$n^+=n \cup \{n\}=n^- \cup \{n^-\} \cup \{n\}$</code> to be equal to
<code>$n$</code>, <code>$\{n\}$</code> would need to be equal to <code>$n^-$</code> or <code>$\{n^-\}$</code>.
That would contradict the assumption, so <code>$n^+ \not =n$</code>.</p>
<p>□</p>
<p>This would be much easier to prove if the <a href="https://en.wikipedia.org/wiki/Axiom_of_regularity">Axiom of
Regularity</a> had
been introduced: if we know that it can't be that <code>$a \in a$</code>, then
<code>$n^+=n \cup \{n\}$</code> would need to be <code>$\{n\}$</code> for <code>$n^+$</code> to be equal
to <code>$n$</code>, which could only be the case if <code>$n \in n$</code>, violating
the axiom.</p>
<h3 id="Exercise_2_5"><a class="hanchor" href="#Exercise_2_5">Exercise 2</a></h3>
<blockquote>
<p>Prove that if <code>$n$</code> is a natural number, […] if <code>$n \not = 0$</code>, then
<code>$n=m^+$</code> for some natural number <code>$m$</code>.</p>
</blockquote>
<p>This feels true almost by definition?</p>
<p>On pg. 44 a natural number is defined as "an element of the minimal
successor set <code>$ω$</code>". Then, if <code>$n \in ω$</code>, there must be an element
<code>$n^-$</code> of <code>$ω$</code> so that <code>${n^-}^+=n$</code> (by the second Peano axiom and
the condition that <code>$ω$</code> can contain no superfluous elements, which
would be the third Peano axiom).</p>
<h3 id="Exercise_3_2"><a class="hanchor" href="#Exercise_3_2">Exercise 3</a></h3>
<blockquote>
<p>Prove that <code>$ω$</code> is transitive.</p>
</blockquote>
<p>I don't understand what is being asked from me here. <code>$ω$</code> is not a
relation since it's not a set of ordered sets with two elements (tuples),
so this question is underspecified.</p>
<h3 id="Exercise_4_1"><a class="hanchor" href="#Exercise_4_1">Exercise 4</a></h3>
<blockquote>
<p>Prove that if <code>$E$</code> is a non-empty subset of some natural number, then
there exists an element <code>$k$</code> in <code>$E$</code> such that <code>$k \in $</code> whenever
<code>$m$</code> is an element of <code>$E$</code> distinct from <code>$k$</code>.</p>
</blockquote>
<p>Trying to decode this first into first-order logic and then natural
language again, I get that if <code>$E \subset N \in ℕ$</code>, then
<code>$∃k\in E: ∀ m \not = k \in E: k \in m$</code>. Decoding into natural
language, this roughly means that for every subset of the natural numbers,
that subset has a minimum.</p>
<h4 id="None"><a class="hanchor" href="#None">Lemma: Any Successor of <code>$n$</code> Contains <code>$n$</code></a></h4>
<p>Statement: <code>$n \in n^{+_k}$</code> for all <code>$k$</code>.</p>
<p>Basis: For <code>$k=1: n \in \{n\} \subset n^+$</code>.</p>
<p>Assume this holds for <code>$k-1$</code>.</p>
<p>Step <code>$n^{+_k}=n^{+_{k-1}} \cup \{n^{+_{k-1}}\}$</code>. <code>$n \in \{n^{+_{k-1}}\}$</code>,
so <code>$n \in n^{+_k}$</code>.</p>
<hr/>
<p>Assume such a <code>$k$</code> did not exist. Then for every <code>$k_i$</code>, it would hold
that there is some <code>$m_i \not= k$</code> so that <code>$k_i \not \in m_i$</code>.</p>
<p>But then it must hold that <code>$m_i \in k_i$</code> (it can't be that <code>$m_i \not \in k_i$</code>
and <code>$k_i \not \in m_i$</code> for natural numbers). If that isn't
the case (so <code>$m_i \not \in k_i$</code>), then there must exists some <code>$r_i$</code>
that <code>$m_i \not \in r_i$</code>. But since <code>$E$</code> contains only finitely many
elements, this leads to a cycle (which is not possible, since that would
mean that <code>$k_i \not \in k_j$</code> and <code>$k_j \not \in k_i$</code>). So such a
<code>$k$</code> must exist.</p>
<h2 id="Section_13"><a class="hanchor" href="#Section_13">Section 13</a></h2>
<h3 id="Stray_Exercise_1"><a class="hanchor" href="#Stray_Exercise_1">Stray Exercise 1</a></h3>
<blockquote>
<p>The discovery and establishment of the properties of powers, as well
as the detailed proofs of the statements about products, can safely be
left as exercises to the readers.</p>
</blockquote>
<p>To be shown: <code>$k \cdot (m+n)=k \cdot m+k \cdot n$</code>.</p>
<p>Induction over <code>$n$</code>.</p>
<p>Induction base: <code>$k \cdot (m+0)=k \cdot m=k \cdot m+k \cdot 0$</code>.</p>
<p>Induction assumption: <code>$k \cdot (m+n)=k \cdot m+k \cdot n$</code>.</p>
<p>Induction step: <code>$k \cdot (m+n^+)=k \cdot (m+n)^+=k \cdot (m+n)+k=(k \cdot m+k\cdot n)+k=k \cdot m+(k \cdot n + k)=k \cdot m + k \cdot n^+$</code></p>
<hr/>
<p>To be shown: <code>$m \cdot n=n \cdot m$</code>.</p>
<p>First, <code>$1 \cdot n=n$</code> because <code>$1 \cdot 0=0$</code>, and if <code>$1 \cdot n=n$</code>,
then <code>$1 \cdot n^+=(1 \cdot n)+1=n+1=n^+$</code>.</p>
<p>Second, <code>$m^+ \cdot n=(m \cdot n)+m$</code> for <code>$n \ge 1$</code>, because
<code>$m^+ \cdot n=(m+1) \cdot n=(m \cdot n)+m$</code> (as per distributivity).</p>
<p>Induction over <code>$m$</code>.</p>
<p>Induction base: If <code>$m=0$</code>, then <code>$m \cdot n=0 \cdot n=0=n \cdot 0=n \cdot m$</code>.</p>
<p>Induction assumption: <code>$m \cdot n=n \cdot m$</code>.</p>
<p>Induction step: <code>$m^+ \cdot n=(m \cdot n)+n=(n \cdot m)+n=n \cdot m^+$</code>
(as per definition of the product).</p>
<hr/>
<p>To be shown: <code>$(k \cdot m) \cdot n=k \cdot (m \cdot n)$</code>.</p>
<p>Induction over <code>$n$</code>.</p>
<p>Induction base: If <code>$n=0$</code>, then <code>$(k \cdot m) \cdot 0=0=k \cdot (m \cdot 0)$</code>
(since <code>$p_{k \cdot m}(0)=0$</code>).</p>
<p>Induction assumption: <code>$(k \cdot m) \cdot n=k \cdot (m \cdot n)$</code></p>
<p>Induction step: <code>$k \cdot (m \cdot n^+)=k \cdot ((m \cdot n)+m)=k \cdot (m \cdot n)+k \cdot m=(k \cdot m) \cdot n+k \cdot m=(k \cdot m) \cdot n^+$</code> (using distributivity).</p>
<hr/>
<p>As for the properties of the power, I don't really want to spend much
time and energy proving them. Let it suffice to say that the powers are
neither associative (counterexample: <code>$2^{(3^2)}=512 \not =64=(2^3)^2$</code>)
nor commutative (counterexample: <code>$2^3=8\not =9=3^2$</code>) nor distributive
over either addition (counterexample: <code>$2^{3+4}=128 \not =24=2^3+2^4$</code>)
or multiplication (counterexample: <code>$2^{3 \cdot 4}=4068 \not=128=2^3 \cdot 2^4$</code>).</p>
<p>They have two interesting properties: <code>$a^{b\cdot c}=(a^b)^c$</code>, and
<code>$a^{b+c}=a^b \cdot a^c$</code>. <!--TODO: prove these someday--></p>
<p>For commutative hyperoperators, see <a href="https://observablehq.com/@ishi/arithmetic" title="Hyperlogarithmic Arithmetic">Ghalimi 2019</a>.</p>
<h3 id="Exercise_1_10"><a class="hanchor" href="#Exercise_1_10">Exercise 1</a></h3>
<p>To be shown: if <code>$m<n$</code>, then <code>$m+k < n+k$</code></p>
<p>Induction over <code>$k$</code></p>
<p>Induction base: If <code>$k=0$</code>, then <code>$m+k=m<n=n+k$</code></p>
<p>Induction assumption: <code>$m+k<n+k$</code></p>
<p>Induction step:</p>
<div>
$$m+k^+ < n+k^+ \Leftrightarrow \\
(m+k)^+ < (n+k)^+ \Leftrightarrow \\
\{m+k\} \cup (m+k) \subset \{n+k\} \cup (n+k)$$
</div>
<p>We know that <code>$m+k \subset n+k$</code>.</p>
<p>We can prove that <code>$\{m+k\} \subset n+k$</code>:</p>
<p>In the base case, <code>$m+k^+=(m+k)^+=\{m+k\} \cup (m+k)=n+k$</code>, in which
<code>$\{m+k\} \subset n+k$</code> clearly holds. Assume that <code>$m+k \subset n+k$</code>.
Then <code>$n+k^+=(n+k)^+=\{n+k\} \cup (n+k) \supset n+k \supset m+k$</code>.</p>
<p>Therefore, we know that <code>$\{m+k\} \subset n+k$</code> and therefore
<code>$m+k \subset n+k$</code> and therefore <code>$m+k < n+k$</code>.</p>
<hr/>
<p>To be shown: if <code>$m<n$</code> and <code>$k \not =0$</code>, then <code>$m \cdot k<n \cdot k$</code>.</p>
<p>Induction over <code>$k$</code>. Base case: <code>$m \cdot 1=m<n=n \cdot 1$</code> (I don't
think the text proves that <code>$p_1(n)=n$</code>, but I also don't think it would
be <em>that</em> useful for me to do that here).</p>
<p>Induction assumption: <code>$m \cdot k<n \cdot k$</code>.</p>
<p>Induction step:
It must hold that
<code>$m \cdot k^+=p_m(k)+m=(m \cdot k)+m<(n \cdot k)+n=p_n(k)+n=n \cdot k^+$</code>.
In general, if <code>$m<n$</code> and <code>$k<l$</code>, then <code>$m+k<n+l$</code> because
<code>$m+k<n+k=k+n<l+n$</code> (two applications of the theorem above, and using
the commutativity of addition), so <code>$(m \cdot k)+m<(n \cdot k)+n$</code>.</p>
<p>Therefore, <code>$m \cdot k<n \cdot k$</code>.</p>
<hr/>
<p>To be shown: Ever non-empty set <code>$E \subset ℕ$</code> has a minimum.</p>
<p>(I tried to prove this constructively, but the result was some weird
amalgam of a constructive and and an inductive proof. Oh well.)</p>
<p>Let <code>$e \in N$</code> be any element in <code>$E$</code>. Then if <code>$e=\emptyset$</code>,
then there can be no element of <code>$E$</code> smaller than <code>$e$</code>, and <code>$e$</code>
is smaller than any other natural number.</p>
<p>If <code>$e \not=\emptyset$</code>, then for any <code>$e \in N$</code>, if we know that <code>$e \not \in E$</code>
and <code>$e^+ \in E$</code>, then <code>$e^+$</code> is the number so that no natural number
smaller than <code>$e^+ \in E$</code>, since we know that all numbers <code>$< e^+$</code>
are not in <code>$E$</code>.</p>
<h3 id="Exercise_2_6"><a class="hanchor" href="#Exercise_2_6">Exercise 2</a></h3>
<p>Assume that there exists a bijection <code>$f$</code> between <code>$ω$</code> and some finite
natural number <code>$n$</code>. Then <code>$n \subset ω$</code>, but <code>$ω \not \subseteq n$</code>,
since <code>$n \subset n^+=\{n\} \cup n \subseteq ω$</code>. Then, by the <a href="https://en.wikipedia.org/wiki/pigeonhole_principle">pigeonhole
principle</a>, <code>$f$</code>
can't exist: there is at least one element too many in <code>$ω$</code> to be
matched to <code>$n$</code>.</p>
<p>Therefore, such an <code>$n$</code> can't exist, <code>$ω$</code> is infinite.</p>
<h3 id="Exercise_3_3"><a class="hanchor" href="#Exercise_3_3">Exercise 3</a></h3>
<p>The proof here is the same as the one in exercise 2.</p>
<h3 id="Exercise_4_2"><a class="hanchor" href="#Exercise_4_2">Exercise 4</a></h3>
<p>To be shown: the union of a finite set of finite sets is finite (wouldn't
this better be if it was a finite family of finite sets? Whatever.).</p>
<p>Proof: Let <code>$\mathcal{S}$</code> be our set, and <code>$\bigcup_{S \in \mathcal{S}} S$</code>
be the union of the finitely many elements of <code>$\mathcal{S}$</code>.</p>
<p>If <code>$\#(\mathcal{S})=0$</code>, then the union is the empty set <code>$\emptyset$</code>,
which is clearly finite (equivalent to <code>$0$</code>.</p>
<p>If <code>$\#(\mathcal{S})=1$</code>, then the resulting set is just the only element
of <code>$\mathcal{S}$</code>, which is per definition finite.</p>
<p>Assume that <code>$\#(\mathcal{S})=n$</code>, and that <code>$\bigcup_{S \in \mathcal{S}}
S$</code> is finite. Let then <code>$\mathcal{S}'=\mathcal{S} \cup \{S_+\}$</code>,
where <code>$S_+$</code> is a finite set. Then
<code>$\bigcup_{S \in \mathcal{S}'} S=S_+ \cup \bigcup_{S \in \mathcal{S}} S$</code>.
Since we know that both <code>$\bigcup_{S \in \mathcal{S}} S$</code> and <code>$S_+$</code>
are finite, we know that <code>$\bigcup_{S \in \mathcal{S}'} S$</code> is therefore
also finite, per the statement in the text that the union of two finite
sets is also finite.</p>
<p>But we can also prove that <code>$E \cup F$</code> is finite if <code>$E$</code> and <code>$F$</code> are
finite: If <code>$f \in F$</code>, then <code>$E \cup \{f\}$</code> is still finite (either
<code>$\#(E \cup \{f\})=\#(E)$</code> or <code>$\#(E \cup \{f\})=(\#(E))^+$</code>). We can
then set <code>$F:=F \backslash \{f\}$</code> and <code>$E:=E \cup \{f\}$</code>. Since we can
repeat this only finitely many times, the resulting <code>$E$</code> must be still
finite when <code>$F=\emptyset$</code> (this is one of my very few constructive
proofs, be gentle please).</p>
<hr/>
<p>To be shown: if <code>$E$</code> is finite, then <code>$\mathcal{P}(E)$</code> is finite, and
<code>$\#(\mathcal{P}(E))=2^{\#(E)}$</code>.</p>
<p>Proof: This was shown in <a href="./nst_solutions.html#Exercise_1_2">Exercise 2 in Section
5</a> (I use the notation of <code>$|E|$</code>
for the size of a set there). Since we can construct the size of
<code>$\mathcal{P}(E)$</code>, it is equivalent to some natural number, and
therefore finite.</p>
<hr/>
<p>To be shown: If <code>$E$</code> is a non-empty finite set of natural numbers, then
there exists an element <code>$k$</code> in <code>$E$</code> such that <code>$m \le k$</code> for all
<code>$m$</code> in <code>$E$</code>.</p>
<p>We start and set <code>$k:=0$</code>. We then choose an element from <code>$m \in E$</code>,
and set <code>$E:=E \backslash \{m\}$</code>.
If <code>$k \le m$</code>, we set <code>$k:=m$</code>. Else we do nothing.
We know this process is repeated finitely many times, and once we end
up with <code>$E=\emptyset$</code>, we have created a <code>$k$</code> such that <code>$m \le k$</code>
for all <code>$m \in E$</code>.</p>
<p>(Is this a constructive proof? It feels like one, but also like writing
code.)</p>
<h2 id="Section_14"><a class="hanchor" href="#Section_14">Section 14</a></h2>
<h3 id="Exercise_1_11"><a class="hanchor" href="#Exercise_1_11">Exercise 1</a></h3>
<p>Totality: <code>$R \cup R^{-1}=X \times X$</code></p>
<p>Antisymmetry: <code>$R \cap R^{-1}=\{(x,x)| x \in X\}$</code></p>
<h3 id="Stray_Exercise_1_1"><a class="hanchor" href="#Stray_Exercise_1_1">Stray Exercise 1</a></h3>
<blockquote>
<p>A set <code>$E$</code> may have no lower bounds or upper bounds at all, or it may
have many; in the latter case it could happen that none of them belongs to
<code>$E$</code>. (Examples?)</p>
</blockquote>
<p>Example for set without lower & upper bounds is <code>$X=∅$</code> (where always
<code>$E=∅$</code>), if <code>$X=\{a,b,c,d\}$</code> and the partial order on <code>$X$</code> is
<code>$a<b<d$</code> and <code>$a<c<d$</code> and <code>$E=\{d\}$</code> then the lower bounds are
<code>$\{a,b,c\}$</code>, if <code>$E=∅$</code>, then every element of <code>$X$</code> is a lower
bound of <code>$E$</code> (since the empty all-quantification is true), but none
of them are in <code>$E$</code>.</p>
<h2 id="Section_15"><a class="hanchor" href="#Section_15">Section 15</a></h2>
<h3 id="Stray_Exercise_1_2"><a class="hanchor" href="#Stray_Exercise_1_2">Stray Exercise 1</a></h3>
<p>To be proven: The Cartesian product of a finite family of sets
<code>$\{X_i\}$</code>, at least one of which is empty, is necessarily and
sufficiently also empty.</p>
<p>Base case: As suggested by the book, I start the induction at 1: In
this case <code>$\{X_i\}=\{\{\}\}$</code>, the set containing the empty set. The
Cartesian product of <code>$\{\}$</code> with no other set is also the empty set.</p>
<p>Induction assumption: If <code>$\{X_i\}$</code> is a family of sets with <code>$n$</code>
elements, at least one of which is empty, then
<code>$X_1 \times X_2 \times \dots \times X_n=\emptyset$</code>.</p>
<p>Induction step: If <code>$\{X_i\}$</code> is a family of sets with <code>$n+1$</code> elements,
at least one of which is the empty set, then either <code>$X_{n+1}$</code> is the
empty set, or the empty set is is the first <code>$n$</code> elements.</p>
<p>Let <code>$X_{\star}=X_1 \times X_2 \times \dots \times X_n$</code>.
Then in the former case we know that
<code>$X_{\star} \times X_{n+1}=X_{\star} \times \emptyset=\emptyset$</code>
(as per the text). In the latter case we know that
<code>$X_{\star} \times X_{n+1}=\emptyset \times X_{n+1}=\emptyset$</code>,
so in both cases we get the empty set as a result.</p>
<h3 id="Stray_Exercise_2"><a class="hanchor" href="#Stray_Exercise_2">Stray Exercise 2</a></h3>
<p>To prove:</p>
<h5 id="I"><a class="hanchor" href="#I">I.</a></h5>
<blockquote>
<p>there exists a function <code>$f$</code> with domain <code>$\mathcal{C}$</code> such that if
<code>$A \in \mathcal{C}$</code>, then <code>$f(A) \in A$</code></p>
</blockquote>
<p>and</p>
<h5 id="II"><a class="hanchor" href="#II">II.</a></h5>
<blockquote>
<p>if <code>$\mathcal{C}$</code> is a collection of pairwise disjoint non-empty sets,
then there exists a set <code>$A$</code> such that <code>$A \cap C$</code> is a singleton for
each <code>$C$</code> in <code>$\mathcal{C}$</code></p>
</blockquote>
<p>are equivalent to the axiom of choice:</p>
<blockquote>
<p><strong>Axiom of choice.</strong> The Cartesian product of a non-empty family of
non-empty sets is non-empty.</p>
</blockquote>
<h4 id="I_1"><a class="hanchor" href="#I_1">I.</a></h4>
<p>We need to prove two directions: <code>$\text{I} \Rightarrow \text{AOC}$</code>
and <code>$\text{AOC} \Rightarrow \text{I}$</code>.</p>
<p>For <code>$\text{AOC} \Rightarrow \text{I}$</code>, let <code>$\mathcal{C}^{\times}=C_1
\times C_2 \times \dots$</code>. Let <code>$C^{\times}$</code> be any element of
<code>$\mathcal{C}^{\times}$</code> (Can we do that? Or does this then circularly
depend on a choice function on <code>$\mathcal{C}^{\times}$</code>?<!--TODO-->). Then
we can define <code>$f$</code> by <code>$f(C_i)=C^{\times}(i)$</code> (since <code>$C^{\times}$</code>
is a tuple).</p>
<p>For <code>$\text{I} \Rightarrow \text{AOC}$</code>, we can construct at least one
element of the Cartesian product of <code>$\mathcal{C}$</code> by constructing
the element <code>$(f(C_1), f(C_2), f(C_3), \dots)$</code>. This tuple must be an
element of the Cartesian product of the elements in <code>$\mathcal{C}$</code>,
therefore that Cartesian product can't be empty.</p>
<h4 id="II_1"><a class="hanchor" href="#II_1">II.</a></h4>
<p>This is actually a special case of I: we just define <code>$f(C)=C \cap
A$</code>. This gives us the results from above.</p>
</body></html>