My Math Forum Today's Fun

 Number Theory Number Theory Math Forum

 November 6th, 2018, 04:48 AM #1 Senior Member   Joined: Jun 2014 From: USA Posts: 525 Thanks: 40 Today's Fun Sometimes I like to think of a little question in the morning and ponder it here and there throughout the day. I'm sure there is probably a fairly easy answer to the following and I'll come up with it later, but until then I thought I would share 'today's fun' with the forum if anyone cares to take a crack at it too. Let $A$ equal the set of infinite binary strings. Let $B$ equal the set of finite binary strings. Let $f: A \rightarrow C$ be bijective (where, trivially, $C$ is simply the image of function $f$ across $A$): $$f(x = x_1x_2x_3\dots) = \{ x_1, x_1x_2, x_1x_2x_3, \dots \}$$ $$\text{E.g., }f(10101...) = \{ 1, 10, 101, 1010, 10101, \dots \}$$ Question: Is it possible to have a subset $T$ of $A$ where: $$1) \bigcup f\{T\} = B \text{, and }$$ $$2) \text{ omitting any one element } q \text{ of } f\{T\} \text{ from the union would imply that } \bigcup (f\{T\} \setminus \{q\}) \neq B \text{.}$$
 November 7th, 2018, 08:00 AM #2 Senior Member   Joined: Jun 2014 From: USA Posts: 525 Thanks: 40 It seems that no set $T$ having the above properties can exist. Assuming the existence of $T$ allows for a proof by contradiction. If there is an $x \in T$ such that $\bigcup (f\{T\} \setminus \{f(x)\}) \neq B$, then there must be an infinite subset of $f(x)$ that is not a subset of $\bigcup(f\{T\} \setminus \{f(x)\})$. Such an infinite subset of $f(x)$ implies that $\bigcup f\{T\} \neq B$ because some elements of $B$ that are not in $f(x)$ must also not be in $\bigcup (f\{T\} \setminus \{f(x)\})$. Last edited by AplanisTophet; November 7th, 2018 at 08:06 AM.
 November 7th, 2018, 10:59 AM #3 Global Moderator   Joined: Dec 2006 Posts: 20,641 Thanks: 2084 As you haven't explained why your two uses of "must" are correct, your reasoning can't be checked in detail.
November 7th, 2018, 01:24 PM   #4
Senior Member

Joined: Jun 2014
From: USA

Posts: 525
Thanks: 40

Quote:
 Originally Posted by skipjack As you haven't explained why your two uses of "must" are correct, your reasoning can't be checked in detail.
Sorry, I wasn’t looking for a check on my reasoning here, but I am happy to post the proof instead of just the mere overview above if anyone is curious.

November 8th, 2018, 05:07 AM   #5
Senior Member

Joined: Jun 2014
From: USA

Posts: 525
Thanks: 40

Quote:
 Originally Posted by skipjack As you haven't explained why your two uses of "must" are correct, your reasoning can't be checked in detail.
Here is the detail for each 'must':

Quote:
 Originally Posted by AplanisTophet If there is an $x \in T$ such that $\bigcup (f\{T\} \setminus \{f(x)\}) \neq B$, then there must be an infinite subset of $f(x)$ that is not a subset of $\bigcup(f\{T\} \setminus \{f(x)\})$.

By the definition of $T$, we're given that $\exists x \in T$ such that $\bigcup (f\{T\} \setminus \{f(x)\}) \neq B$. We can then list the elements of $f(x)$ by their length so as to find the first element of the list, $x_j$, such that $x_j \notin \bigcup (f\{T\} \setminus \{f(x)\})$. Where $x_j$ is not in the union, we know that $x_{j+i}$ is also not in the union for any $i \in \mathbb{N}$ (this is because $x_{j+i}$ can only be in the union if $x_j$ is in the union by the definition of function $f$). We are left with our infinite subset of $f(x)$ that is not a subset of $\bigcup(f\{T\} \setminus \{f(x)\})$:

$$\{ x_i \in f(x) : i \in \mathbb{N} \text{ and } i \geq j \}$$

Quote:
 Originally Posted by AplanisTophet Such an infinite subset of $f(x)$ implies that $\bigcup f\{T\} \neq B$ because some elements of $B$ that are not in $f(x)$ must also not be in $\bigcup (f\{T\} \setminus \{f(x)\})$.
Where $x_{j+1} \in f(x)$ and $x_{j+1} \notin \bigcup (f\{T\} \setminus \{f(x)\})$, we can find an element $b \in B$ that is not in either $f(x)$ or $\bigcup (f\{T\} \setminus \{f(x)\})$. We find $b$ by changing the last binary digit of $x_{j+1}$ to a $0$ if it is a $1$ or a $1$ if it is a $0$. We then know that $b \notin f(x)$ by the definition of $b$. We also know that $b \notin \bigcup (f\{T\} \setminus \{f(x)\})$ because $b$ can only be in the union if $x_j$ is in the union given the definition of function $f$. That is, $b$ is a successor of $x_j$ and cannot appear in $f(q)$ for any $q \in T$ unless $x_j$ is also in $f(q)$.

If $b \in B$, $b \notin f(x)$, and $b \notin \bigcup (f\{T\} \setminus \{f(x)\})$, then $\bigcup f\{T\} \neq B$. This is a contradiction because $\bigcup f\{T\} = B$ by the definition of $T$, so $T$ cannot exist.

 Tags fun, today

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post GIjoefan1976 Algebra 3 October 24th, 2016 01:12 AM goodlooking Geometry 1 April 2nd, 2015 07:10 AM Queen Elementary Math 2 September 11th, 2009 10:42 AM croatiandan Calculus 2 October 23rd, 2007 04:32 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top