Timeline for Uncountable family of infinite subsets with pairwise finite intersections
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 1, 2012 at 14:36 | history | edited | Valerio Capraro | CC BY-SA 3.0 |
added 1 characters in body
|
| Feb 27, 2012 at 7:57 | comment | added | Aaron Meyerowitz | I admire constructive mathematics and shun excluded middle, but I am no expert (so I hope this makes sense). Sure Cantor's Diagonal Argument (CDA) is constructive but what does it really show (constructively speaking)? Suppose I accept those and only only those binary sequences output by a finite algorithm? Then the set $B$ of binary sequences I accept is no larger than the set $P$ of programs ( finite strings of characters including total nonsense ones). I can easily enumerate $P$ but I can not enumerate $B$ (as show by CDA), it is not (recursively?) enumerable. | |
| Feb 26, 2012 at 22:55 | comment | added | Andrej Bauer | Every notion of constructive and non-constructive mathematics consider the binary sequences to form an uncountable set. This is so because Cantor's diagonal argument is constructive (and in fact expressible in a very weak system of logic). | |
| Feb 24, 2012 at 12:08 | comment | added | Vladimir Dotsenko | The last paragraph is my favourite way to visialise this example. It also gives a good visualisation of a similar construction asking for a family of subsets which are pairwise comparable with respect to inclusion! | |
| Feb 23, 2012 at 22:11 | history | edited | Aaron Meyerowitz | CC BY-SA 3.0 |
added 209 characters in body
|
| Feb 23, 2012 at 21:49 | comment | added | Aaron Meyerowitz | Better to start with 1, I fixed it. The sequence 011001... would code the set {1,2,5,11,22,44,89,...}. I start with one as a clumsy way to avoid having another set be {11,22,44,89,...} | |
| Feb 23, 2012 at 21:41 | history | edited | Aaron Meyerowitz | CC BY-SA 3.0 |
deleted 1 characters in body; added 1 characters in body
|
| Feb 23, 2012 at 20:46 | comment | added | MTS | Aaron, I don't quite understand what you mean. Is the following correct? You are saying that the desired family of countable sets is indexed by binary sequences. For a given binary sequence $(x_i)$, we are taking our countable set to be the set of sequences of nonnegative integers of the form $(0,a_1,a_2, \dots)$ such that for $i \ge 1$ we have $a_{i+1} = 2 a_i$ or $2 a_i +1$ according to whether $x_i = 0$ or $1$? What is the initial 0 needed for? | |
| Feb 23, 2012 at 18:40 | history | answered | Aaron Meyerowitz | CC BY-SA 3.0 |