-
Notifications
You must be signed in to change notification settings - Fork 0
/
hwInf1.tex
225 lines (185 loc) · 8.1 KB
/
hwInf1.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
\documentclass[12pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amsthm,amssymb,amsfonts}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newenvironment{problem}[2][Problem]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
%If you want to title your bold things something different just make another thing exactly like this but replace "problem" with the name of the thing you want, like theorem or lemma or whatever
\begin{document}
%\renewcommand{\qedsymbol}{\filledbox}
%Good resources for looking up how to do stuff:
%Binary operators: http://www.access2science.com/latex/Binary.html
%General help: http://en.wikibooks.org/wiki/LaTeX/Mathematics
%Or just google stuff
\title{Infi1 Homework}
\author{KanHar}
\maketitle
\begin{problem}{1}
Prove: $\sqrt{3} \notin \mathbb{Q}$
\end{problem}
\begin{proof}{1}
We will prove: $\forall n \in \mathbb{N}: n \nmid 3 \implies n^2 \nmid 3$
\begin{proof}{1.1} \label{p1_1}
$$n \nmid 3 \implies n\bmod{3} \in \{1,2\}$$
Option A: $$n \bmod{3} = 1 \newline$$
$$n = (3m+1)$$
$$n^2 = 9m^2 + 6m + 1$$
$$9m^2\bmod3=0$$
$$6m\bmod3=0$$
$$n^2\bmod{3} = 0+0+1 = 1$$
Option B: $$n \bmod{3} = 2 \newline$$
$$n = (3m+2)$$
$$n^2 = 9m^2 + 12m + 4$$
$$9m^2\bmod3=0$$
$$12m\bmod3=0$$
$$4\bmod3=1$$
$$n^2\bmod{3} = 0+0+1 = 1$$
Therefore $n^2 \bmod{3} \ne 0 \implies n^2 \nmid 3$.
\end{proof}
Assume: $\sqrt{3} \in \mathbb{Q}$
$$\exists{n,m}\in \mathbb{N}: \frac{n}{m} = \sqrt{3} \land \gcd(n,m)=1$$
$$\frac{n^2}{m^2}=3$$
$$n^2 = 3m^2$$
By proof 1.1:
$$n^2 \mid 3 \implies n \mid 3$$
$$\exists k \in \mathbb{N}:n = 3k$$
$$n^2 = 9k^2$$
$$\frac{9k^2}{m^2}=3$$
$$9k^2 = 3m^2$$
$$m^2 = 3k^2$$
$$m^2 \mid 3 \implies m \mid 3$$
$$m \mid 3 \land n \mid 3 \implies \gcd(m,n) \ne 1$$
We have reached a contradiction. Therefore our assumption is false and $\sqrt{3} \notin \mathbb{Q}$.
\end{proof}
\begin{problem}{2}
Prove or falsify: $(x \ge 0 \in \mathbb{R}, \forall \epsilon > 0 \in \mathbb{R}: x<\epsilon) \implies x = 0$
\end{problem}
\begin{proof}{2}
Assume $ x \ne 0 \implies x > 0$
$$x \in R \implies \frac{x}{2} \in R$$
$$x > 0 \implies x > \frac{x}{2}$$
We have reached a contradiction, therefore, our assumption is wrong and $x=0$.
\end{proof}
\begin{problem}{3}
Prove:
$A \subseteq R, \exists \epsilon > 0: \forall a \in A: a > \epsilon \implies \lnot (0 = \inf A)$
\end{problem}
\begin{proof}{3}
Assume $\inf A = 0$: \newline
By the definition, $\epsilon$ is a lower bound of A. Therefore, 0 cannot be the infimum of the group as the infimum is defined as the highest lower bound, and $\epsilon > 0$ is a lower bound. \newline
We have reached a contradiction, therefore the assumption is wrong and $\inf A \ne 0 \implies \lnot (0 = \inf A)$.
\end{proof}
\begin{problem}{4}
$B = \{(-1)^{n-1}\cdot(2+\frac{3}{n})) | n \in \mathbb{N}\}$. Find upper and lower bounds, max and min.
\end{problem}
\begin{proof}{4}
The function $\frac{1}{n}$ is monotonically decreasing, therefore $2+\frac{3}{n}$ is monotonically decreasing.
There value of the expression $(-1)^{n-1}$ is dependent on $n \bmod{2} \in \{0,1\}$: \newline
There are 2 possibilities - Option A - $$n \bmod{2} = 0$$
$$\exists k \in \mathbb{N}: n = 2k$$
$$(-1)^{n-1}\cdot(2+\frac{3}{n}) = (-1)^{2k-1}\cdot(2+\frac{3}{2k}) = (-1)^{2k}\cdot(-1)^{-1}\cdot(2+\frac{3}{2k})$$
$$=-(2+\frac{3}{2k})$$
This expression is monotonicaly increasing so it's infimum is at $k = 1$.
$$\inf{-(2+\frac{3}{2k})}=-(2+\frac{3}{2})=-\frac{7}{2} \in B$$
This expression is always negative. \newline
Option B - $$n \bmod{2} = 1$$
$$\exists k \in \mathbb{N}: n = 2k-1$$
$$(-1)^{n-1}\cdot(2+\frac{3}{n}) = (-1)^{2k-2}\cdot(2+\frac{3}{2k-1}) = (2+\frac{3}{2k-1})$$
This expression is monotonicaly decreasing so it's suprimum is at $k=1$.
$$\sup{(2+\frac{3}{2k-1})} = (2+\frac{3}{2-1}) = 5 \in B$$
This expression is always positive.
As the first option is always negative and the second is always positive, the suprimum of the first option and the infimum of the second option hold for the whole expression. Both the suprimum and the infimum are inside the group so they are maximum and minimum
Therefore, $$\max B = 5, \min B = -\frac{7}{2}$$
\end{proof}
\begin{problem}{5}
$A, B \subseteq \mathbb{R}$ and $A,B \ne \emptyset$. $\forall a \in A : \forall b \in B: a \le b$.
\begin{problem}{5.a}
Prove: $\sup A \le \inf B$
\end{problem}
\begin{proof}{5.a}
Lets assume: $\sup A > \inf B$.
Lets define: $$\epsilon = \frac{\sup A - \inf B}{2} > 0$$
By the definition of suprimum and infimum $$\exists a \in A: \sup A - \epsilon < a \le \sup A, \exists b \in B: \inf B + \epsilon > b \ge \inf B$$
$$a > \sup A - \epsilon = \sup A - \frac{\sup A - \inf B}{2} = \frac{\inf A + \inf B}{2} = \inf B + \frac{\sup A - \inf B}{2} = \inf B + \epsilon > b$$
We derived $a > b$, and this is a contradiction with the given information. Therefore our assumption is false and $\sup A \le \inf B$.
\end{proof}
\begin{problem}{5.b}
Prove or falsify: $\sup A = \inf B \implies A \cap B \ne \emptyset$.
\end{problem}
\begin{proof}{5.b}
In the case of
$$A = (-\infty, 1), B = (1, \infty)$$
$$\sup A = \inf B = 1$$
$$A \cap B = \emptyset$$
And we have reached a contradiction. Therefore $\sup A = \inf B \not\implies A \cap B \ne \emptyset$
\end{proof}
\begin{problem}{5.c}
When is $A \cap B \ne \emptyset$
\end{problem}
\begin{proof}{5.c}
If and only if $\sup A \in A$ and $\inf B \in B$, Which means $$\sup A = \max A \land \inf B = \min B$$ $$A \cap B = \{\max A = \min B\}$$
\end{proof}
\end{problem}
\begin{problem}{6}
$A \subseteq \mathbb{R}, 0 \notin A$
\begin{problem}{6.a}
Prove or contradict: $\exists \sup A \implies \exists \sup A^{-1}$
\end{problem}
\begin{problem}{6.b}
Prove or contradict: $\exists \sup A \implies \exists \inf A^{-1}$
\end{problem}
\begin{proof}{6.a+b}
In the case of $$A = \{a | a \ne 0, -1 \le a \le 1\} \implies \sup A = 1 $$
$$ A^{-1} = (-\infty, -1] \cup [1,\infty) \implies \lnot \exists \sup A^{-1}, \lnot \exists \inf A^{-1}$$
\end{proof}
\begin{problem}{6.c}
Prove or contradict: $\exists \sup A^{-1} \implies \exists \sup A$
\end{problem}
\begin{problem}{6.d}
Prove or contradict: $\exists \sup A^{-1} \implies \exists \inf A$
\end{problem}
\begin{proof}{6.c+d}
In the case of $$A = (-\infty, -1] \cup [1,\infty) \implies \lnot \exists \sup A, \lnot \exists \inf A$$
$$ A^{-1} = \{a | a \ne 0, -1 \le a \le 1\} \implies \sup A^{-1} = 1, \inf A^{-1} = -1$$
\end{proof}
\end{problem}
\begin{problem}{7}
$A \subseteq \mathbb{R}, \sup A \in \mathbb{R}$. $B = \{-a | a \in A\}$. Prove: $\inf B = -\sup A$.
\end{problem}
\begin{proof}{7}
Assume $\inf B \ne -\sup A$. There are 2 cases: $\inf B > -\sup A$ or $\inf B < -\sup A$.
Case 1:
$$\inf B > -\sup A$$
Let $\epsilon = \frac{\inf B + \sup A}{2} > 0$
$$\exists b \in B: \inf B \ge b > \inf B - \epsilon$$
By the definition of B,
$$-b \in A \implies -b < \sup A$$
$$ -\sup A + \epsilon < -b < -\sup A$$
$$ -\sup A + \epsilon < -\sup A$$
$$ \epsilon < 0$$
We have reached a contradiction, therefore this case is impossible. In a similar way we can prove that the second case is impossible, and therefore we have a contradiction and our assumption is wrong. $\inf B = -\sup A$.
\end{proof}
\begin{problem}{8}
$A \subseteq \mathbb{R}, \forall a \in A: a > 0.$ \newline
$ A^{-1} = \{\frac{1}{a}|\forall a \in A\}$
\end{problem}
\begin{problem}{8.a}
Prove: $\forall a \in A : a > m \implies \forall b \in A^{-1}: b < \frac{1}{m}$
\end{problem}
\begin{proof}{8.a}
Assume $\exists b \in B: b > \frac{1}{m}$
$$\frac{1}{b} \in A \implies \frac{1}{b} > 0 \implies b > 0$$
$$\frac{1}{b} \in A, \frac{1}{b} < \frac{1}{\frac{1}{m}} = m$$
And we reached a contradiction, therefore our assumption is false and $\forall b \in A^{-1}: b < \frac{1}{m}$
\end{proof}
\begin{problem}{8.b}
Prove: $\forall a \in A: a > 0 \iff \lnot \exists K \in \mathbb{R}: (\forall b \in A^{-1}: |b| < K)$
\end{problem}
\begin{proof}{8.b}
In the case of $A = \{1\} \implies A^{-1} = 1$
$$\forall a \in A : a > 0$$
$$\forall b \in A^{-1}: |b| < 2$$
Therefore we have a contradiction and the question in the problem is falsified.
\end{proof}
\end{document}