Timeline for Quasi-disjoint subsets of an infinite set and $\neg \mathsf{AC}$
Current License: CC BY-SA 3.0
25 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| Mar 7, 2015 at 11:44 | history | edited | Goldstern |
added tag: axiom of choice
|
|
| Mar 4, 2015 at 10:00 | comment | added | Asaf Karagila♦ | @bof: Ah, yes. In any case, yes this is what I had in mind last night when I first laid eyes on this question. Some $\Delta$-system or some coloring argument (color each pair in $S$ by the intersection, if you can find a homogeneous set of size $|S|$ we can derive a contradiction). But those, of course, require choice in the general case. | |
| Mar 4, 2015 at 9:57 | comment | added | bof | I believe I've seen quasidisjoint family used as a synonym for $\Delta$-system, i.e., a family of sets in which each pair has the same intersection. | |
| Mar 4, 2015 at 9:51 | comment | added | bof | @AsafKaragila: Choose $a,b\in X,\ a\ne b.$ Define $f:X\times X\to S$ as follows. Let $f(x,x)=\{x\}.$ Let $f(a,b)=\emptyset.$ If $x\ne y$ and $(x,y)\ne(a,b),$ let $f(x,y)$ be the unique member of $S$ containing $\{x,y\}$ if there is one, otherwise let $f(x,y)=\emptyset.$ The range of $f$ is a superset of $S$. | |
| Mar 4, 2015 at 9:32 | comment | added | Asaf Karagila♦ | @bof: Yes, that is a classical example. | |
| Mar 4, 2015 at 9:31 | comment | added | bof | @AsafKaragila: Let $A=\mathbb R$ and $B=\mathbb R\cup\omega_1$. There is a surjection from $A$ to $B$ but it's consistent that $|A|\lt|B|$. | |
| Mar 4, 2015 at 9:26 | comment | added | Asaf Karagila♦ | @bof: You're right, it doesn't imply there is no surjection. I think this particular question is still open, if it's even possible to have such surjection. I don't see how there is a surjection from $X^2$ onto $S$ under the assumptions in the question, though. | |
| Mar 4, 2015 at 9:25 | comment | added | bof | @AsafKaragila: This choiceless stuff always confuses me. Does $|A|\lt|B|$ imply that there is no surjection from $A$ to $B$? | |
| Mar 4, 2015 at 9:19 | comment | added | bof | @AsafKaragila: Well then, that answers Dominic van der Zypen's question, doesn't it? If $S$ is a "quasi-disjoint" (as defined here) family of subsets of $X$, then there is a surjection from $X\times X$ to $S$, right? | |
| Mar 4, 2015 at 9:00 | comment | added | Asaf Karagila♦ | @bof: No, this is impossible. You can find this in Jech's The Axiom of Choice, if I remember correctly. If $|X|>5$ then, $2^{|X|}>|X|^2$. | |
| Mar 4, 2015 at 8:39 | comment | added | Dominic van der Zypen | Very interesting, @bof, I suggest you put this as a new question on MO | |
| Mar 4, 2015 at 8:34 | comment | added | bof | As a weaker version of your question, is it consistent that there exist an infinite set $X$ and a surjection from $X\times X$ to $\mathcal P(X)$? | |
| Mar 4, 2015 at 7:03 | history | edited | Dominic van der Zypen | CC BY-SA 3.0 |
Title: "cardinal" replaced by "set"
|
| Mar 4, 2015 at 6:55 | comment | added | Dominic van der Zypen | Thanks Joel & Andres for making the question much clearer & better! | |
| Mar 3, 2015 at 20:36 | comment | added | Andrés E. Caicedo | @Joel Yes, you are right. Would you mind retouching the question, please? | |
| Mar 3, 2015 at 19:57 | comment | added | Joel David Hamkins | In the second paragraph, you say "such a pair of sets", but I think you no longer intend here that $S$ has the same size as $P(X)$, which was one of the properties in the first paragraph. | |
| Mar 3, 2015 at 19:52 | comment | added | Andrés E. Caicedo | I have edited the question slightly based on the comments. | |
| Mar 3, 2015 at 19:51 | history | edited | Andrés E. Caicedo | CC BY-SA 3.0 |
added 263 characters in body
|
| Mar 3, 2015 at 19:26 | comment | added | Joel David Hamkins | More clearly: is it consistent with ZF that there is an infinite set $X$ and an injection $f:P(X)\to P(X)$ such that $|f(A)\cap f(B)|\leq 1$ whenever $A\neq B$? | |
| Mar 3, 2015 at 18:19 | comment | added | Joel David Hamkins | In that case, the question should be edited. To start out by saying, "Let $X$ be an infinite set..." suggests that one has a universal quantifier, but really the question is: Is it consistent with ZF that there is a set $X$ and a collection $S$, such that...? | |
| Mar 3, 2015 at 18:10 | comment | added | Andrés E. Caicedo | Hi Joel, Yes, the statement being asked is whether it is consistent to have any instances of this situation. | |
| Mar 3, 2015 at 17:47 | comment | added | Joel David Hamkins | The statement is clearly false when $S$ is finite (or empty), and you haven't imposed any requirement preventing that. So could you clarify the precise statement about which you are asking? It doesn't make sense to ask for consistency when $X$ and $S$ are already-fixed parameters, so I imagine you have in mind a statement quantifying over $X$ and $S$. The statement is also false when $S$ simply consists of all the singleton sets. Perhaps you are asking whether it is consistent that there is any instance of this at all? | |
| Mar 3, 2015 at 16:41 | comment | added | Andrés E. Caicedo | Perhaps it is worth pointing out that it is definitely consistent that $|X|<|S|$. Is "cset" a typo? | |
| Mar 3, 2015 at 14:27 | history | asked | Dominic van der Zypen | CC BY-SA 3.0 |