User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 November 6th, 2018, 04:48 AM #1 Senior Member   Joined: Jun 2014 From: USA Posts: 528 Thanks: 43 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: 528 Thanks: 43 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,919 Thanks: 2202 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: 528
Thanks: 43

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: 528
Thanks: 43

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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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

Copyright © 2019 My Math Forum. All rights reserved.      