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
October 11th, 2018, 07:28 AM   #1
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 422
Thanks: 26

My Opus

I assume there may be something wrong and this isn't actually my opus because the result of this work is to show that two sets of equal cardinality do not have equal cardinality (a contradiction) using only standard theory that can be adapted to a model of ZF. ZF would therefore be inconsistent.

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:
$$f(x = x_1x_2x_3\dots) = \{ x_1, x_1x_2, x_1x_2x_3, \dots \} $$
Let $g: A \rightarrow D$ be bijective:
$$g(x = x_1x_2x_3\dots) = \{ x_1, x_1x_2, x_1x_2x_3, \dots \} \cup \{ x \}$$
Let $\mathcal{P}(B)$ denote the powerset of $B$.

Let $v: \mathcal{P}(B) \rightarrow E$ be surjective:
$$v(x) = \{ p \in A : f(p) \subset x \}$$
Let $w: \mathcal{P}(B) \rightarrow F$ be surjective:
$$w(x) = \bigcup \{ g(p) : p \in v(x) \}$$
Let $k: \mathcal{P}(B) \rightarrow G$ be bijective:
$$k(x) = x \cup w(x)$$
Let $r: D \rightarrow G$ be any arbitrary surjective function.

Let $H = \bigcup \{ x \in D : x \not\subset r(x) \} \in G$
$$x \subset H \implies x \not\subset r(x) = H$$
$$x \not\subset H \implies x \subset r(x) = H$$
$$\not\exists x \in D \text{ such that } r(x) = H \implies \text{ function } r \text{ is not surjective}$$
$$|D| < |G|$$
This is a contradiction because we know that $|D| = |G| = |\mathcal{P}(\mathbb{N})|$.

The above proof can be done in a model of ZF, so ZF is inconsistent.

Last edited by AplanisTophet; October 11th, 2018 at 08:16 AM.
AplanisTophet is offline  
 
October 11th, 2018, 09:18 AM   #2
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 422
Thanks: 26

I would like to add one line for clarity that doesn't otherwise change the proof:

Let $H = \bigcup \{ x \in D : x \not\subset r(x) \} \in G$

Add this line $\downarrow$
$$\text{Function } r \text{ is surjective } \implies \exists x \in D \text{ such that } r(x) = H$$
$$x \subset H \implies x \not\subset r(x) = H$$
$$x \not\subset H \implies x \subset r(x) = H$$
$$\not\exists x \in D \text{ such that } r(x) = H \implies \text{ function } r \text{ is not surjective}$$
AplanisTophet is offline  
October 11th, 2018, 09:59 AM   #3
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 284
Thanks: 86

Math Focus: Algebraic Number Theory, Arithmetic Geometry
After a cursory glance, it's not clear to me why $H$ is an element of $G$. Would you mind explaining this? Or at least confirming that it'll be obvious if I work through the details?
cjem is offline  
October 11th, 2018, 10:25 AM   #4
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 422
Thanks: 26

Quote:
Originally Posted by cjem View Post
After a cursory glance, it's not clear to me why $H$ is an element of $G$. Would you mind explaining this? Or at least confirming that it'll be obvious if I work through the details?
Yes, $H$ must be an element of $G$ by definition.

The set $H$ will be the union of elements of $D$, so it will contain both finite and infinite binary strings. For each infinite binary string $x$ in $H$, we can be assured that $f(x)$ is also a subset of $H$. In turn, $H$ must be an element of $G$.

We can note that for any elements $p \in G$ and $q \in A$, $q \in p \iff f(q) \subset p \iff g(q) \subset p$.
AplanisTophet is offline  
October 11th, 2018, 11:39 AM   #5
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 284
Thanks: 86

Math Focus: Algebraic Number Theory, Arithmetic Geometry
That seems to make sense, thanks. I'll have proper think about it in a while. I guess another issue I have is with the following implications:

Quote:
Originally Posted by AplanisTophet View Post
$$x \subset H \implies x \not\subset r(x) = H$$
$$x \not\subset H \implies x \subset r(x) = H$$
For the first, $x \subset H$ just means that, for any string $y \in x$, there exists $z \in D$ such that $y \in z$ and $z \not\subset r(z)$. I can't quite see how this implies the (potentially) stronger statement that $x \not\subset r(x)$.

Edit: I'm happy with the second implication, actually.

Last edited by cjem; October 11th, 2018 at 11:52 AM.
cjem is offline  
October 11th, 2018, 11:47 AM   #6
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 422
Thanks: 26

I figured out the error. The following is a counterexample:

Let $K = k_1, k_2, k_3, …$ be a listing of the elements of $A$ that contain an infinite number of 0's but only a finite number of 1's.

We then have $L = \{ g(k) : k \in K \} \subset D$ and $\bigcup L = B \cup K \implies B \subset \bigcup L$.

Assume function $r$ is such that $l \not\subset r(l) \iff l \in L$ so that $H = \bigcup L$. In this case, $H \notin G$ because the only element $g$ of $G$ such that $B \subset g$ is $k(B) = g = B \cup A$.

Therefore, the following line of the proof was incorrect because $H = \bigcup L \notin G$ when $\{ x \in D : x \not\subset r(x) \} = L$:

Let $H = \bigcup \{ x \in D : x \not\subset r(x) \} \in G$
AplanisTophet is offline  
October 11th, 2018, 11:48 AM   #7
Senior Member
 
Joined: Aug 2012

Posts: 2,099
Thanks: 604

Quote:
Originally Posted by AplanisTophet View Post
I assume there may be something wrong ...
My first issue: You didn't bother to define C or D. Since you are trying to make a cardinality argument, you have to be very precise about the sets you're using.

Also your notation for f and g is unclear. f seems to map a sequence to a set. g maps a sequence to another set that's the union of two sets.

I'm sure you must have an idea in there somewhere but your notation is incoherent.

Last edited by Maschke; October 11th, 2018 at 12:04 PM.
Maschke is offline  
October 11th, 2018, 12:34 PM   #8
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 422
Thanks: 26

Quote:
Originally Posted by AplanisTophet View Post
I figured out the error. The following is a counterexample:
Quote:
Originally Posted by Maschke View Post
I'm sure you must have an idea in there somewhere...
Yup. I'm satisfied. I incorrectly assumed $H$ would have to be in $G$ for any choice of function $r$, but I figured it out. Otherwise, it was a fun little exercise imho.

Thanks.
AplanisTophet is offline  
October 11th, 2018, 12:46 PM   #9
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 422
Thanks: 26

Quote:
Originally Posted by cjem View Post
For the first, $x \subset H$ just means that, for any string $y \in x$, there exists $z \in D$ such that $y \in z$ and $z \not\subset r(z)$. I can't quite see how this implies the (potentially) stronger statement that $x \not\subset r(x)$.
Each element of $D$ contains an element that isn't in any other element of $D$. Therefore, it is true that $x \subset H \implies x \not\subset r(x) = H$.

I thought $H$ would be an element of $G$ for any possible $H$. That isn't true, so that is where the proof breaks down.

Thank you also.
AplanisTophet is offline  
October 11th, 2018, 01:14 PM   #10
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 284
Thanks: 86

Math Focus: Algebraic Number Theory, Arithmetic Geometry
Quote:
Originally Posted by AplanisTophet View Post
Each element of $D$ contains an element that isn't in any other element of $D$.
Oh, duh. I considered this, but I mixed $C$ and $D$ up in my mind (and it's not true if you swap the "$D$"s with "$C$"s). Thanks.

Quote:
Originally Posted by AplanisTophet View Post
I thought $H$ would be an element of $G$ for any possible $H$. That isn't true, so that is where the proof breaks down.

Thank you also.
Interesting. Given that the rest of the argument looks fine (and assuming ZF is consistent), this means $H$ isn't an element of $G$ for any surjection $r$. It seemed plausible to me that $H$ would at least sometimes be an element of $G$, even if I wasn't convinced it always would be.
cjem is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
opus



Thread Tools
Display Modes






Copyright © 2018 My Math Forum. All rights reserved.