Set theory - 2017-02-01

6:20 AM

No I mean, for bijective constructions between countably infinite sets and between finite sets, we can easily write down the resulting sequence to work out how to construct the bijective function

I know that I can verify that some real function is bijective. What I am trying to learn is how to find them no matter how crazy the uncountable set is. Unlike countable sets, the reals cannot be wrote into a sequence, and if you don't know the function beforehand, the only help from the diagram is you know what the required image of that function should be.

Re: "What I am trying to learn is how to find them no matter how crazy the uncountable set is."

I am not sure whether finding bijections between infinite sets really a necessary skill to do mathematics.

I think that this is what basic results about cardinal arithmetic and cardinalities are good for.

You know cardinalities of some basic sets; such as $\mathbb N$, $\mathbb Q$, $\mathbb R$, $\mathbb C$, etc.

It is often useful to know cardinality of some set. But usually you do not find this cardinality by explicitly constructing a bijection. Instead you usually use what you already know about cardinal arithmetics.

Some examples:

Cardinality of Borel sigma algebra

Cardinality of set of real continuous functions

Cardinality of bijections $\mathbb N\to\mathbb N$: Is symmetric group on natural numbers countable?

Typically you combine various facts about cardinal numbers to obtain both inequalities and use Cantor-Bernstein theorem.

Martin Sleziak

6:48 AM

in Mathematics, 5 mins ago, by Martin Sleziak

I will say one more thing: Even Cantor-Bernstein can be proved in such way that the proof is constructive. So if you found cardinality of some set using CB, you can read definition of some bijection from the estimates. But it will probably be rather cumbersome to write it down explicitly and the bijection will look ugly.

in Mathematics, 2 mins ago, by Martin Sleziak

Hmmm.... now I am not sure about what I wrote above. Probably depends on what people understand under constructive. I will post few links in set theory room.

Wikipedia: Schröder–Bernstein theorem "This theorem does not rely on the axiom of choice. However, its various proofs are non-constructive, as they depend on the law of excluded middle, and are therefore rejected by intuitionists."

MathOverflow: Is there a constructive proof of Cantor–Bernstein–Schroeder theorem ?

in Mathematics, 1 min ago, by Martin Sleziak

And you should probably ignore my suggestion about constructive proof of Cantor-Bernstein. Probably I should have said without use of Axiom of Choice instead of constructively. I will have to think about it a bit.

Martin Sleziak

7:13 AM

I guess you can find a few comments various questions on the main about this:

@Trevor: However, I agree that the context is a bit unclear, because for a lot of people "constructive" simply means without resorting to the axiom of choice (e.g. "partition the set into small parts, now choose the proper bijections ..." sort of argument), and in which case my answer shares your sentiment. The Cantor-Bernstein theorem is constructive "enough", and then it gets very easy. — Asaf Karagila Oct 2 '13 at 18:16

This answer starts by saying: "First note that the Cantor-Bernstein is constructive and does give us a bijection."

Are we talking about Cantor-Schroeder-Bernstein? Because if we are: "... An important feature of this theorem is that it does not rely on the axiom of choice. However, its various proofs are non-constructive, as they depend on the law of excluded middle, ...". I thought non-constructive meant that it doesn't give you the actual thing you're after (bijection in this case). The proof argues with infinite sequences of elements. I don't see how it gives me the bijection. Perhaps you could elaborate? Cheers mate. — Rudy the Reindeer Nov 1 '12 at 9:20

@Matt: There is an immense ambiguity as to what does "constructive proof" mean: Are you talking about defining an object; are you talking about using law of excluded-middle; are you talking about doing things within a particular constructive system? — Asaf Karagila Nov 1 '12 at 13:33

@Matt: There are people who reject the law of excluded middle. For them the proof of this theorem is not valid. Many of these people are doing what it is known as "constructive mathematics" in one way or another. This is a strong assertion than the common "define an object", in that aspect the proof is constructive because it tells you exactly how to define the bijection. However the proof relies on the fact that something is either true or false, which is rejected by some people. — Asaf Karagila Nov 1 '12 at 13:37

And similar discussions can be probably found at some other posts about finding explicit bijections.

Secret

6:51 PM

Proof and bizarre implications needed to be checked:

in Mathematics, 9 mins ago, by Secret

Consider the dedekind cut 0. This gives the subset $\mathbb{Q_{\leq 0}}$. Therefore the rationals are being partitioned by 0 into the nonpositves and the positives. Similarly for the naturals, there is also a partition of even and odd integers.

Since a bijection exists between rationals and naturals, dedekind 0 cut maps to $2\mathbb{N}$

Now consider some real number $s<0$. This gives a dedekind cut of $\mathbb{Q_{\leq 0}}-X$ where $X$ is the set of all rationals between s and 0, which is countable.

in Mathematics, 5 mins ago, by Secret

o and one more thing $Y \subsetneq 2\mathbb{N}$ using what we know about dedekind cuts and then map the result to $\mathbb{N}$ via the bijection

in Mathematics, 3 mins ago, by Secret

So this suggests we are literally deleted $|\mathbb{R}|$ elements in total to produce the chain

Further conjecture to be (dis)proved later:

Given $|X|=\aleph_{\alpha}$, hence $\mathscr{P}(X)=2^{\aleph_{\alpha}}$, the maximum chain length of inclusions is $2^{\aleph_{\alpha}}$

Secret

7:08 PM

in Mathematics, 10 mins ago, by DHMO

@Secret can you explain why there are $2^\Bbb N$ possible partitions of $\Bbb N$?

in Mathematics, 4 mins ago, by Secret

There are a total of $2^{\mathbb{N}}$ subsets in $\mathbb{N}$. Any deletions in $\mathbb{N}$ must produce one of them. In particular, any countable deletions that don't delete the whole set or left behind a finite set will produce one of the uncountably many infinite subsets. Now $\mathbb{Q}$ bijects with $\mathbb{N}$. Since we knew dedekind cuts from 0 partitions $\mathbb{Q}$ into positive and negative regions, and also the negative region gets smaller as we move from 0 down to the negative reals, the sets that produces are all infnite subsets of $\mathbb{Q}$ and there are uncountably man…

in Mathematics, 2 mins ago, by DHMO

@Secret how do you know "there are uncountably many of them"?

in Mathematics, 2 mins ago, by Secret

@DHMO because the real line interval $(-\infty,0]$ is in bijective correspondance with all of $\mathbb{R}$, thus the dedekind cut must produce uncountably many subsets and hence binary partitions of Q

in Mathematics, 2 mins ago, by DHMO

I'm asking for an intuitive explanation @Secret

in Mathematics, 1 min ago, by Secret

@DHMO I suspect there isn't any. You will not realise you can delete $2^{\mathbb{N}}$ elements from a countable set had the rationals not being countable and yet able to converge to any reals, thus allowing the bijective correspondance in the dedekind proof to be set up

in Mathematics, 32 secs ago, by Secret

@DHMO Of course, given such a weird implication, it is possible I might have a wrong reasoning somewhere I don't know. I will let Martin, alessandro, Ted and Tobias to check and see if they can find any holes in my proof

in Mathematics, 54 secs ago, by DHMO

@Secret well of course you can impose other orderings in $\Bbb N$...

in Mathematics, 38 secs ago, by DHMO

@Secret an example is the inversed lexicographic ordering, where 0<100000<10<2<4<9<999<8999

4

Q: Finding an uncountable chain of subsets the integers

How to find an uncountable subset of $P(\mathbb{N})$ such that every two elements of it can be compared. In fact, give an uncountable subset of $P(\mathbb{N})$ such that has totality property. We mean by $P(\mathbb{N})$, the powerset of natural numbers set $\mathbb{N}$.

Martin Sleziak

7:28 PM

@Secret Judging by the answers given here, this problem is probably not quite simple: Uncountable chains

Secret

So that means... we can throw away up to $2^{\aleph_{\alpha}}$ elements from a $< \aleph_{\alpha}$ sized set and still having the set of size $< \aleph_{\alpha}$...?

Martin Sleziak

7:57 PM

@Secret I do not really understand this last message. Are you talking about size of sets or size of chains?

It is clear that you cannot remove $2^{\aleph_\alpha}$ elements from a set of sizer $\aleph_\alpha$, since $\aleph_\alpha < 2^{\aleph_\alpha}$ by Cantor's theorem.

This MO post seems to be similar to the previous link I gave: Totally ordered chain in the powerset with big cardinality

Transcript for

$Mathematics$ Set theory