DMAT_AS1

Assignment 1

1

FTSOC, assume $\mathbb{R}$ is a finite dimensional vector space over $\mathbb{Q}$. By definition, this implies that $\mathbb{R}$ has a finite spanning set $(r_1,r_2,\dots ,r_n)$, i.e, for all $r\in \mathbb{R}$, $r=\sum q_i{r}_i,q_i\in \mathbb{Q}$. Now, $|\left\{\sum q_i{r}_i|q_i\in \mathbb{Q}\right\}|\le |{\mathbb{Q}}^n|={\aleph }_0$. But, $|\mathbb{R}|>{\aleph }_0$, due to Cantor’s theorem. Thus, $\mathbb{R}$ is not a finite dimensional vector space over $\mathbb{Q}$.

2

For each Y, draw line segments connecting the outward tips to form a triangle. Note that the Y divides the triangle into 3 triangles. Pick a point, $q_i=(p_i,r_i)$, $q_1,q_2\in \mathbb{Q}$ in each triangle (this is possible since ${\mathbb{Q}}^2$ is dense in ${\mathbb{R}}^2$). Associate the Y with the set $\{q_1,q_2,q_3\}$. If any two Ys have are associated with the same set of rational points, they must intersect. Thus, no two Ys are associated with the same set of rational points. Thus, if $S$ is the set of all Ys on the plane, then $|S|\le {\mathbb{Q}}^3={\aleph }_0$, i.e, we can only place countably many Ys on the plane.

3

Consider the set $S\equiv \{a-b|a,b\in A\}$. Note that $|S|\le |A{|}^2=|A|$. Thus, $\mathbb{R}\setminus S\ne \varnothing$. Pick $r\in \mathbb{R}\setminus S$. Now, $(r+S)\cap S=\varnothing$, because otherwise we would have $r+a=b⟹r=b-a$ for $a,b\in S$.

4

Assume there exists such a set $A$. consider two points $p$ and $q$ of $A$. For each $d\in D$, draw a circle of radius $d$ centered at $p$, and another centered at $q$. Let $C$ be the set of all intersection points between the two circles. The cardinality of $C$ is $|D\times D|=|D|={\aleph }_0$. Note that any other point of $A$ must be in $C$.

5

Zorn’s Lemma: In a partial order, if every chain has an upper bound, then there exists a maximal element.

Axiom of Choice: For any set X of nonempty sets, there exists a choice function f that is defined on X and maps each set of X to an element of that set.

Set $X$ be a collection of non empty sets. Let $S$ be the set of all functions $f$ defined on a subset of $X$ such that $f(x)\in x$. We know that $S$ is non empty, since we can always define $f$ on a finite subset of $X$. Define a partial order $\le$ on $S$ by $f_1\le f_2$ if $f_1\subseteq f_2$. Consider a chain $C$ in $(S,\le )$. Let $f={\bigcup }_{f_i\in C}{f}_i$. The domain of $f$ is a union of subsets of $X$, and hence is a subset of $X$. $f$ is well defined, since for each $x$ in the domain of $f$, $x\in f_i$ for some $f_i\in C$, and $C$ being a chain forces $f_j(x)=f_i(x)$ for all $j$ whenever $f_j(x)$ is defined. Additionally, $f(x)=f_i(x)\in x$. Thus, $f\in S$, and every chain has an upper bound. From Zorn’s lemma, there must exist a maximal element $f^{\prime }$ in $S$. If the domain of $f^{\prime }$ is not $X$, it can be trivially extended to contradict the maximality of $f^{\prime }$. Thus, the domain of $f^{\prime }$ is $X$. Since $f\in S$, it satisfies the properties of a choice function.

6

Let $G=(V,E)$ be an infinite graph. Partition $G$ as $G=V_f\bigsqcup V_{\infty }$ where $V_f$ is the set of all points with finite neighborhoods and $V_{\infty }$ is the set of all points with infinite neighborhoods.

If $|V_f|=\infty$, we can construct an infinite independent set: Pick $v_1\in V_f$, $v_2\in V_f\setminus N_{v_1}$, $v_3\in V_f\setminus N_{v_1}\setminus N_{v_2}$, and so on. If we run out of elements at any point, it would mean $V_f$ is a finite union of finite sets, which is not possible.

If $|V_f|$ is finite, $|V_{\infty }|$ must be infinite. Pick $v_1\in V_{\infty }$, and consider $G_1\equiv N_{v_1}$ as an infinite subgraph of $G$. We can again partition $G_1=V_{f,1}\bigsqcup V_{\infty ,1}$. If $V_{f,1}$ is infinite, we can construct an infinite independent set in $G_1$, which will also be an infinite independent set of $G$. If $V_{f,1}$ is finite and $V_{\infty ,1}$ is infinite, we pick $v_2\in V_{\infty ,1}$ and consider $G_2\equiv N_{v_2}\cap N_{v_1}$ as an infinite subgraph of $G_1$. In this process, if we for some $n$ have $V_{f,n}$ to be finite, we can construct an independent set. If $V_{f,n}$ is never finite for all $n$, we get a sequence of points $v_1,v_2,v_3,\dots$, which form an infinite connected graph since $v_2,v_3,v_4\cdots \in N_{v_1}$ and $v_3,v_4,\cdots \in N_{v_2}$ and so on.

7

Suppose $X=(V,E)$ is an infinite graph that is not properly $k$-colorable for any positive integer $k$. It follows from the De Bruijn–Erdős theorem that for every positive integer $k$, $X$ has a finite subgraph $H_k$ which is not $k$ colorable. $H={\bigcup }_{k\in \mathbb{N}}{H}_k$ is a countable subgraph of $X$ which is not $k$ colorable for any positive integer $k$.

8

Let α ≤ β be two infinite cardinals and let |B| = β. An α-covering of
B is a collection of pairwise disjoint sets {Ai | i ∈ I} such that |Ai| = α
for each i ∈ I and B = ⋃
i∈I Ai. Does B have an α-covering? Justify
answer with proof.

Define $P\equiv \{(C,\mathbf{D}):C\subset B,\mathbf{D}\text{ is a alpha covereing of }C\}$. We know that $P$ is non empty, since subsets of $B$ of cardinality $\alpha$ have the trivial covering.
Define a partial order by $(C_1,{\mathbf{D}}_1)\le (C_2,{\mathbf{D}}_2)$ if $C_1\subset C_2$ and ${\mathbf{D}}_1\subset {\mathbf{D}}_2$.

Let $S$ be any chain in $(P,\le )$.
$S=\{(C_i,{\mathbf{D}}_i):i\in I\}$.
For all $i,j\in I$, either $(C_i,{\mathbf{D}}_i)\le (C_j,{\mathbf{D}}_j)$, or vice versa.
Let $C={\bigcup }_{i\in I}{C}_i$ and $\mathbf{D}={\bigcup }_{i\in I}{\mathbf{D}}_i$. It is easy to see that $\mathbf{D}$ is a $\alpha$-covering for $C$. $(C,\mathbf{D})\in P$, so Zorn’s lemma is applicable. Let $(\hat{C},\hat{\mathbf{D}})$ be the maximal element.

If $\hat{C}=B$, we are done.
If $\hat{C}$ is a proper subset of $B$, two cases:

• $|B\setminus \hat{C}|<\alpha$: Change the covering by appending the elements in $B\setminus \hat{C}$ to some ${\hat{\mathbf{D}}}_i$. Does not create a contradiction.
• $|B\setminus \hat{C}|\ge \alpha$: you can take a subset of cardinality $\alpha$ of $B\setminus \hat{C}$ and add it to $\hat{\mathbf{D}}$, contradicting the maximality of $(\hat{C},\hat{\mathbf{D}})$.

9

Bijective proof: We have to choose $k$ things from $n+k+1$ things, labeled $t_1,t_2,\dots ,t_{n+k+1}$. We can choose to either pick $t_{n+k+1}$, or choose not to. In the latter case, we would have to pick $k$ things from $t_1,t_2,\dots ,t_{n+k}$, which can be done in $\left(\genfrac{}{}{0ex}{}{n+k}{k}\right)$ ways. If we chose to include $t_{n+k+1}$, we are next faced with the question of whether to include $t_{n+k}$. If we do not include $t_{n+k}$, we will have to choose the remaining $k-1$ things from $t_1,t_2,\dots ,t_{n+k-1}$, the number of ways to do that being $\left(\genfrac{}{}{0ex}{}{n+k-1}{k-1}\right)$. If we include $t_{n+k}$, we then have to look at the cases of $t_{n+k-1}$ being included and not being included. Continuing with this iterative process, we get

$$\left(\genfrac{}{}{0ex}{}{n+k+1}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+k}{k}\right)+\left(\genfrac{}{}{0ex}{}{n+k-1}{k-1}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{n+1}{1}\right)+\left(\genfrac{}{}{0ex}{}{n}{0}\right).$$

Computational proof:
We know that

$$\left(\genfrac{}{}{0ex}{}{n}{r}\right)+\left(\genfrac{}{}{0ex}{}{n}{r+1}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{r+1}\right).$$

If we rewrite $\left(\genfrac{}{}{0ex}{}{n}{0}\right)$ as $\left(\genfrac{}{}{0ex}{}{n+1}{0}\right)$, we see that $\left(\genfrac{}{}{0ex}{}{n+1}{0}\right)+\left(\genfrac{}{}{0ex}{}{n+1}{1}\right)=\left(\genfrac{}{}{0ex}{}{n+2}{1}\right)$, and $\left(\genfrac{}{}{0ex}{}{n+2}{1}\right)+\left(\genfrac{}{}{0ex}{}{n+2}{2}\right)=\left(\genfrac{}{}{0ex}{}{n+3}{3}\right)$, and so on.

10

$n=6k$
Let the number of subsets of size congruent to 0, 1, and 2 mod 3 be $S_0$, $S_1$, and $S_3$ respectively. Then, we have $S_0+S_1+S_2=2^n$. Also,

$$\begin{array}{rl}1=(1+\omega {)}^n=& \left(\left(\genfrac{}{}{0ex}{}{n}{0}\right)+\left(\genfrac{}{}{0ex}{}{n}{3}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{n}{n}\right)\right)+\\ & \left(\left(\genfrac{}{}{0ex}{}{n}{1}\right)+\left(\genfrac{}{}{0ex}{}{n}{4}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{n}{n-2}\right)\right)\omega +\\ & \left(\left(\genfrac{}{}{0ex}{}{n}{2}\right)+\left(\genfrac{}{}{0ex}{}{n}{5}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{n}{n-1}\right)\right){\omega }^2\end{array}$$

So, $S_0+\omega S_1+{\omega }^2{S}_2=1$. Additionally, $S_1=S_2$. Thus, we have

$$\begin{array}{r}{S}_0+S_1(\omega +{\omega }^2)=S_0-S_1=1\end{array}$$

Combining with $S_0+2S_1=2^n$, we have

$$S_0=\frac{2^n+2}{3},S_1=\frac{2^n-1}{3},S_2=\frac{2^n-1}{3}.$$

$n=6k+1$
Again, $S_0+S_1+S_2=2^n$. Here, $S_0=S_1$. Hence, $2S_0+S_2=2^n$. Also,

$$\begin{array}{rl}(1+\omega {)}^{6k+1}=1+\omega & =S_0+S_1\omega +S_2{\omega }^2\\ & =S_0(1+\omega )+S_2{\omega }^2\\ & =(S_0-S_2)(1+\omega )\\ ⟹S_0=1+S_2& \end{array}$$

So,

$$S_0=\frac{2^n+1}{3},S_1=\frac{2^n+1}{3},S_2=\frac{2^n-2}{3}$$

$n=6k+2$
Here, $S_0=S_2$. $2S_0+S_1=2^n$.

$$\begin{array}{rl}(1+\omega {)}^{6k+2}=\omega & =S_0+S_1\omega +S_2{\omega }^2\\ & =S_0(1+{\omega }^2)+S_1\omega \\ ⟹S_1=1+S_0& \end{array}$$

So

$$S_0=\frac{2^n-1}{3},S_1=\frac{2^n+2}{3},S_2=\frac{2^n-1}{3}$$

$n=6k+3$
Again, $S_1=S_2$. But, $S_1=S_0+1$.

$$S_0=\frac{2^n-2}{3},S_1=\frac{2^n+1}{3},S_2=\frac{2^n+2}{3}.$$