My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
November 6th, 2018, 05:48 AM   #1
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 413
Thanks: 26

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{.}$$
AplanisTophet is offline  
 
November 7th, 2018, 09:00 AM   #2
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 413
Thanks: 26

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 09:06 AM.
AplanisTophet is offline  
November 7th, 2018, 11:59 AM   #3
Global Moderator
 
Joined: Dec 2006

Posts: 19,878
Thanks: 1835

As you haven't explained why your two uses of "must" are correct, your reasoning can't be checked in detail.
skipjack is online now  
November 7th, 2018, 02:24 PM   #4
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 413
Thanks: 26

Quote:
Originally Posted by skipjack View Post
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.
AplanisTophet is offline  
November 8th, 2018, 06:07 AM   #5
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 413
Thanks: 26

Quote:
Originally Posted by skipjack View Post
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 View Post
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 View Post
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.
AplanisTophet is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
fun, today



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
promise last one for today, -3+x/3 >= x/5-1 GIjoefan1976 Algebra 3 October 24th, 2016 02:12 AM
good day today goodlooking Geometry 1 April 2nd, 2015 08:10 AM
I need help please for today :) Queen Elementary Math 2 September 11th, 2009 11:42 AM
i need this one for school today (please) croatiandan Calculus 2 October 23rd, 2007 05:32 AM





Copyright © 2018 My Math Forum. All rights reserved.