Let $X$ be a finite set. $\mathcal{P}(X)$ denotes the set of all subsets of $X$.  Let $\Gamma$ be a sub-lattice of $\mathcal{P}(X)$, i.e. $\Gamma$ is a collection of subsets of $X$ closed under union and intersection. Suppose $\Gamma$ non-empty and $\Gamma$ not made only of the empty set.  Set $$n:=n(\Gamma):=\min\{m\geq1\,|\, \Gamma\text{ contains at least one set of cardinality }m\}$$ and suppose $n\geq2$. I would like to find a lattice $\Gamma'$ isomorphic to $\Gamma$, but with $n(\Gamma')=1$.  With this purpose I thought to define a map $\Phi\!:\Gamma\to\Phi(\Gamma)=:\Gamma'$ doing the following operations:   from each set $A\in\Gamma$ with cardinality $|A|=n$, choose $n-1$ elements and delete them; (Notice that all these sets $A$'s are pairwise disjoint, by the minimality of $n$ and since $\Gamma$ is closed under intersection) call $Y$ the set of all deleted elements; from each set $B\in\Gamma$ with cardinality $|B|&gt;n$, delete the elements of $Y$.   Clearly in this way one obtains $\Gamma'\subseteq\mathcal{P}(X')$, where $X':=X\smallsetminus Y$. By construction $n(\Gamma')=1$.  It is trivial that $\Phi$ is surjective. It is also easy to check that $\Phi$ is an homomorphism of lattices (i.e. $\Phi(A\cup B)=\Phi(A)\cup\Phi(B)\,$, $\,\Phi(A\cap B)=\Phi(A)\cap\Phi(B)\,$): it suffices to write $\Phi(A)=A\smallsetminus Y$ and apply elementary facts of set theory.  Therefore to conclude it remains only to prove that $\Phi$ is injective. I think it is true because I don't manage to build any counter-example. Can you help me to prove it?
122247
Let $X$ be a finite set. $\mathcal{P}(X)$ denotes the set of all subsets of $X$.  Let $\Gamma$ be a sub-lattice of $\mathcal{P}(X)$, i.e. $\Gamma$ is a collection of subsets of $X$ closed under union and intersection. Suppose $\Gamma$ non-empty and $\Gamma$ not made only of the empty set.  Set $$n:=n(\Gamma):=\min\{m\geq1\,|\, \Gamma\text{ contains at least one set of cardinality }m\}$$ and suppose $n\geq2$. I would like to find a lattice $\Gamma'$ isomorphic to $\Gamma$, but with $n(\Gamma')=1$.  With this purpose I thought to define a map $\Phi\!:\Gamma\to\Phi(\Gamma)=:\Gamma'$ doing the following operations:   from each set $A\in\Gamma$ with cardinality $|A|=n$, choose $n-1$ elements and delete them; (Notice that all these sets $A$'s are pairwise disjoint, by the minimality of $n$ and since $\Gamma$ is closed under intersection) call $Y$ the set of all deleted elements; from each set $B\in\Gamma$ with cardinality $|B|&gt;n$, delete the elements of $Y$.   Clearly in this way one obtains $\Gamma'\subseteq\mathcal{P}(X')$, where $X':=X\smallsetminus Y$, and $n(\Gamma')=1$. My questions are:   is $\Gamma'$ a sub-lattice of $\mathcal P(X')$ ? is the map $\Phi$ an isomorphism of lattices (i.e. $\Phi$ bijection, $\Phi(A\cup B)=\Phi(A)\cup\Phi(B)\,$, $\,\Phi(A\cap B)=\Phi(A)\cap\Phi(B)\,$) ?   Edit. It is trivial that $\Phi$ is surjective (by definition of $\Gamma'$). It seems also clear that $\Phi$ is an homomorphism of lattices: it suffices to write $\Phi(A)=A\smallsetminus Y$ and apply elementary facts of set theory. Therefore the only thing that remains to prove it that $\Phi$ is injective.
20559
This question was inspired by the question on .  From the discussion in the comments there, it seems there does not exist a set of all sets of a given cardinality.  To me, it seems easy to see that this is true for any nonzero finite cardinality $n$. Given any set $x$, you can always make a set of size $n$ by adding $n-1$ other sets to $x$ to make a set of size $n$, which exists by repeated use of the pairing axiom.   But how would you do this for infinite cardinalities? For suppose $\kappa$ is some given infinite cardinality. To show that the set of all sets of cardinality $\kappa$ does not exist, it seems you would have to show that for any set $x$, there exists a set of that size with $x$ as an element, and then you could take the union of that set to find the set of all sets, and thus a contradiction. But it doesn't seem reasonable to simply say, for a given set of size $\kappa$ if $x$ is in the set, we have no problem. If not, just take an element out of the set and put $x$ in. Something about that seems like it would not be allowed.  So how would you do this for infinite cardinalities?
61719
The book Theory of Functions of a Real Variable by I. P. Natanson, proves that a denumerable or finite union of pairwise disjoint sets of cardinality $c$ has cardinality $c$.  The proofs given in the book are fairly easy, using the axiom of choice. But then it is left as an exercise a generalization of the above theorems for not necessarily pairwise disjoint sets.  I have searched all over the web, but all the proofs found so far are for pairwise disjoint sets.  The proof given in the book relies on the fact that each set $A_k$ can be matched with a set like $[a_{k-1},a_k)$, with $a_k$ point of a partition of $[0,1]$, such that $\bigcup_{k=1}^{\infty\lor n}A_k=[0,1)$. So it is easy to guess the bijective function, but I can't generalize this proof.  Any help is highly appreciated. Thanks and regards.
112359
This is part of a bigger problem I'm trying to prove, but my argument relies of the validity of the following idea. Note that when I say countable, I don't mean finite -- I mean countable infinity.   Consider the set of natural numbers, $\mathbb{N}$. Now take a countable subset of them, call it $\mathsf{S}_1$. Then take a countable subset of $\mathbb{N}\setminus{\mathsf{S}_1}$ and call it $\mathsf{S}_2$. Then take a countable subset of $\mathbb{N}\setminus\{{\mathsf{S}_1}\cup{\mathsf{S}_2}\}$ and call it $\mathsf{S}_3$. Continue in this manner to construct $\mathsf{S}_i$'s such that ${\mathsf{S}_i}\cap{\mathsf{S}_j}=\emptyset$ for $i≠j$.  My question is this: is it necessarily the case that eventually there will be finitely many $\mathsf{S}_i$'s with $\mathbb{N}\setminus\bigcup_{i}{\mathsf{S}_i}={P}$ where $P$ is either empty or finite? My guess is yes, but I'm not how to prove it or how to find a counterexample.
84873
Theorem Any class $\mathcal{A}$ of subsets of a nonempty set $X$ is the subbase for a unique topology $\tau$ on $X$. That is to say, the finite intersections of members of $\mathcal{A}$ form a base for the topology $\tau$ on $X$. Example Consider $X=\{a,b,c,d\}$ Let $\mathcal{A}=\{\{a,b\},\{b,c\},\{d\}\}$ The finite intersection of members of $\mathcal{A}$ give us: $$\mathcal{B}=\{\{a,b\},\{b,c\},\{d\},\{b\},\varnothing,X\}$$  How is it true that $X \in \mathcal{B}$ ? By definition of subbase, the finite intersection of members of $\mathcal{A}$ are the members of some base $\mathcal{B}$. But for $a_i \in \mathcal{A}, \displaystyle\bigcap a_i \neq X$ for any finite intersection of $a_i$'s. Look: $\{a,b\}\cap\{b,c\}\cap \{d\} \neq \{a,b,c,d\}$ nor do any other intersection of elements of $\mathcal{B}$ result in $X$. Anybody know what's going on here? Why is $X \in \mathcal{B}$?
93120
This is a homework problem for class credit and I would appreciate a hint.  Let $A$ be an infinite set and suppose $x, y$ and $z$ are points in $A$. Show that $A$ has the same cardinality as $A\setminus\{x,y,z\}$.  So far I am trying to solve this for the more general case, let $A$ be an infinite set and $B$ be a finite subset of $A$, show that $A$ has the same cardinality as $A\setminus B$.  If $B$ is finite and $A$ is infinite, then $A\setminus B$ is infinite because if $A\setminus B$ were finite then $A = A\setminus B \cup B$, the union of two finite sets and hence $A$ would be finite.  Using Cantor-Bernstein we know that if there is a one-to-one function from $A$ to $A\setminus B$ and a one-to-one function from $A\setminus B$ to $A$, then $A$ and $A\setminus B$ are equivalent.  It is easy to define a function $f:A\setminus B \to A$ that is one-to-one, $f(x) = x$.  Now I need to define a function $g:A \to A\setminus B$ that is one-to-one.  I have a feeling that this involves using the axiom of choice.  Is this the right strategy?  Have I made any errors?  And can anyone give me a hint on how to define a one to one function from $A$ to $A\setminus B$?
119909
I am only a first semester undergraduate (of mathematics) so I would appreciate the answers to not be too complicated. Also English is not my first language, so my explanations might be a little off.    While trying to prove that the Powerset $\mathcal{P}(\mathbb{N})$ is uncountable I ran into something that I wasn't able to understand.  So, I define the set $$ \mathbb{N}_n=\{\{a_1,a_2,\ldots,a_n\}:a_i\in \mathbb{N} \; \forall i \text{ and } a_i \neq a_j \; \forall i \neq j\} \text{ for } n \in \mathbb{N} $$ basically the set goes like this $$ \mathbb{N}_0=\{ \emptyset \} \\ \mathbb{N}_1=\{ \{1\},\{2\},\{3\},\ldots \} \\ \mathbb{N}_2=\{ \{1,2\},\{1,3\},\{2,3\},\{1,4\},\ldots \} \\ \vdots $$ and we can conclude that $$ \text{if } \mathbb{N}_i \cap \mathbb{N}_j = \emptyset \text{ then } i \neq j \\ \bigcup\limits_{i \in \mathbb{N} \cup \{0\}} \mathbb{N}_i = \mathcal{P}(\mathbb{N}) $$ Okay, so there are a countable number of sets $\mathbb{N}_i$. Also the set $\mathcal{P}(\mathbb{N})$ is uncountable. Also as briefly mentioned in yesterdays lecture (at my university), a countably infinite union of countable sets is a countable set. From this I have concluded that:  $ \text{There exists an } i \in \mathbb{N} \text{ such that the set } \mathbb{N}_i \text{ is uncountable.} $  Now, there is the possibility of a mistake that I have made in a previous statement. But in the case that I haven't, this last statement seems very counter intuitive to me. I have also tried proving / disproving it but failed.  My question is where have I either made a mistake, or if I haven't how do I prove or disprove my final statement.
57200
Proof that the following equality is wrong: $$\mathcal{P}(A\Delta B) \setminus \{\emptyset\} = \mathcal{P}(A) \Delta\mathcal{P}(B) $$ I choose elements of sets $A$ and $B$ so that they are separate.  $A = \{1, 2\}$ $ \mathcal{P}(A) = \{\{1\}, \{2\}, \{1, 2\}, \emptyset\}$ $B = \{3, 4\}$ $\mathcal{P}(B) = \{\{3\}, \{4\}, \{3, 4\}, \emptyset\}$ $A\cup B = \{1, 2, 3, 4\}$ $A\cap B = \emptyset$  Now I see that: On the left side: $\mathcal{P}(A\Delta B) = \mathcal{P}((A\cup B) \setminus (A\cap B)) = \mathcal{P}((A\cup B) $ $ \mathcal{P}((A\cup B) =\{\{1\}, \{2\}, \{3\}, \{4\}, \{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\}, \{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}, \{2, 3, 4\}, \{1, 2, 3, 4\},\emptyset \} $ $ \mathcal{P}((A\cup B) \setminus \{\emptyset\} =\{\{1\}, \{2\}, \{3\}, \{4\}, \{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\}, \{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}, \{2, 3, 4\}, \{1, 2, 3, 4\}\} $ On the right side: $\mathcal{P}(A) \Delta\mathcal{P}(B) = (\mathcal{P}(A) \cup \mathcal{P}(B)) \setminus (\mathcal{P}(A) \cap \mathcal{P}(B)) = \{ \{1\}, \{2\}, \{3\}, \{4\}, \{1, 2\}, \{3, 4\} \} $ Therefore: $\{\{1\}, \{2\}, \{3\}, \{4\}, \{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\}, \{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}, \{2, 3, 4\}, \{1, 2, 3, 4\}\} \neq \{ \{1\}, \{2\}, \{3\}, \{4\}, \{1, 2\}, \{3, 4\} \} $ i.e. $\mathcal{P}(A \,\Delta\,B) \setminus \{\emptyset\} \neq \mathcal{P}(A) \Delta\mathcal{P}(B)$. Is my proof valid? Are there any errors? I could take smaller $A$ and $B$ sets but I was scared that it wouldn't be so obvious that way.
81524
Let $A$ be a set of $n$ elements. Then, in how many ways, can we choose an ordered pair $(B,C)$, where $B,C$ are disjoint subsets of $A$?  Let A={1}, then B can be {phi} and C can be {1}. So, one ordered pair.   Let A={1,2}, then B can be {phi}, {1} and C can be {1},{2}. So three ordered pairs.   Let A={1,2,3}. Then B can be {phi},{1},{2} and C can be {1},{2},{3}.   So six pairs ? Am I going in the right direction ?
16175
Is it true that if $X$ and $Y$ are sets and there is a bijection between $\mathcal{P}(X)$ and $\mathcal{P}(Y)$ then there is a bijection from $X$ to $Y$ ?. I believe this should be obvious, but I can't see why this is so. A proof or a counter example would be highly appreciated.   Thanks.
114384
Lets define the following:  Let A be a set. A is innumerable if and only if there exists a bijective function from A to $\mathbb{N}$  Proof that there exists an innumerable set $B \subseteq \mathcal P \left({\mathbb{N}}\right)$ such that it has the following properties:  1) $X\cap Y =\emptyset$ for all $X,Y \in B$ such that $X \neq Y$  2) $\mathbb{N}= \bigcup B$  3) All elements of B are innumerable.  Any help is appreciated. I don´t know how to find this set ...
99750
Let $\mathcal F$ be a field. Suppose that there is a set $P \subset \mathcal F$ which satisfies the following properties:   For each $x \in \mathcal F$, exactly one of the following statements holds: $x \in P$, $-x \in P$, $x =0$.  For $x,y \in P$, $xy \in P$ and $x+y \in P$.    If such a $P$ exists, then $\mathcal F$ is an ordered field.   Define $x \le y \Leftrightarrow y -x \in P \vee x = y$.   Exercise: Prove that the field of complex numbers $\mathbb C$ cannot be given the structure of an ordered field.   My Work So Far: (Edit 1 note: This section and the Question is at the beginning, simply leaving this up for reference as to where I started)  Let $i$ be such that $i \in P, i \ne 0 \Rightarrow i &gt; 0$. But $i^2 = -1 \notin P$.   My Question: I am not sure how much I need to redefine, and how I go about rigorously making this patchwork argument airtight. I am aware that I have not addressed how I assumed that $-1 \notin P$, but I'm not sure how to distinguish between $1$ and $i$ in this proof.     Edit #1    1st Step: Showing that $-1 \notin P$, observe that $(-1)(-1) = 1$ therefore if $-1 \in P$, both $x, -x \in P$, a contradiction.   2nd Step: To show $i \notin P$, we have that if $i \in P \Rightarrow i^2 \in P$, but $i^2 = -1 \notin P$, so $i \notin P$.   3rd Step: To show $-i \notin P$, we have $(-i)(-i) = i^2 \notin P$, so $-i$ cannot be in $P$.   Conclusion: Since $i \ne 0$, and $i, -i \notin P$, there is no set $P \subset \mathbb C$ that satisfies the above properties, thus $\mathbb C$ is not ordered.   Thank you André Nicolas and Eric Stucky for your help!
66551
A quick preface to the below question: this is my first post on math.se! I am excited to begin participating in such a wonderful community. Any feedback as to how I can improve this or subsequent posts is certainly feedback from which I could benefit.      (Exercise 3.2.2 of Tao's Analysis I) Use the  (and the singleton set axiom, which guarantees the existence of the singleton set) to show that if $A$ is a set, then $A\notin A{. \kern 0.05em}^\text{1}$ Furthermore, show that if $A$ and $B$ are sets, then $A\notin B$ or $B\notin A$.    Thoughts: Consider some set $A$ and the singleton $\{A\}$. By the axiom of regularity, the only element of $\{A\}$, namely $A$, is not a set or disjoint from $\{A\}$. Clearly, $\{A\}\cap A=\emptyset$ and thus, $A\notin A$.   Moreover, suppose $B$ is some other set such that $\neg(A\notin B \lor B\notin A)$, i.e. $A\in B\land B\in A$. This implies, in very vauge notation, that $A=\{\{A,\dots\},\dots\}$ and $B=\{\{B,\dots\},\dots\}$. Can I get a contradiction out of this? In the case of $A$, we get that $x\in\{A,\dots\}\lor x\in \{a\}$ for some $x\in A$ and all other objects $a\in A$. How can I prove that there exists no element of $A$ (and $B$) that is not a set unless it is disjoint from $A$. I would greatly appreciate any hints as to how I can complete my argument.     1 This first problem has been discussed on this site times before (see  and ). I include a solution only because the context demands it, but to avoid a duplicate question, I ask that it not be discussed here.
23162
From wikipedia:     Equivalently, a set P is a partition of X if, and only if, it does not contain the empty set and:         The union of the elements of P is equal to X. (The elements of P are said to cover X.)      The intersection of any two distinct elements of P is empty. (We say the elements of P are pairwise disjoint.)      I clearly understand that the intersection between partition is empty (point 2), but how can the union of a partition can be the all elements in the set?  If it is a partition, shouldnt they be just a part?  I imagine a set divided in 3 and the elements in the first part are not all the elements of the second part.  How do you explain this?
16420
My attempt to prove the following is below:     Let X be an infinite set. Show that $\mathscr{T}_1=\{U \subseteq X : U = \emptyset $ or $ X\setminus U $ is finite $ \}$   My book calls this set the ""  I just want to know if this proof is correct. (I intuitively understand why its a topology, but I'm not sure if I'm showing it properly)  Using the definition of topology:     $\mathscr{T}$ is a topology on X if and only if the following are true:   (i) X and Ø are elements of $\mathscr{T}$.   (ii) $\mathscr{T}$ is closed under finite intersections.   (iii) $\mathscr{T}$ is closed under arbitrary unions.   Let:$V_k \subseteq X$ be any finite set. (ie: $V_1, V_2...$ are all finite sets)  So Then, $U_k = X \setminus V_k$, would be the subsets of $\mathscr{T}$.   Now to verify the definition.     (i) X and Ø are elements of $\mathscr{T}$.   Ø is given in the definition of $\mathscr{T}_1$. Also, the empty set is considered finite, with cardinality zero. Thus $X$ is in $\mathscr{T}_1$ because its complement is finite.      (ii) $\mathscr{T}$ is closed under finite intersections.   $U_k \cap U_j = X \setminus (V_k \cup V_j) $, due to De Morgan's law. Since the Union of two finite sets is also finite, this set is still in $\mathscr{T}_1$. Or Symbolically (using bars || for cardinality): If $|V_k \cup V_j| &lt; |\mathbb{N}|  $, then $(U_k \cap U_j) \in \mathscr{T}_1$. This reasoning can be extended to any finite amount of intersections.       (iii) $\mathscr{T}$ is closed under arbitrary unions.   $U_k \cup U_j = X \setminus (V_k \cap V_j) $, due to De Morgan's law.Since the Intersection of two finite sets is also finite, this set is still in $\mathscr{T}$. Or Symbolically: If $|V_k \cap V_j| &lt; |\mathbb{N}|  $, then $(U_k \cup U_j) \in \mathscr{T}_1$. This reasoning can be extended to any finite amount of Unions.  Now let's consider the infinite case: $V_k \cap ... \cap V_j$ will only contain points that are in EVERY set being intersected. So if $V_k \cap ... $ was infinite, that would imply the every $V_k$ being intersected is also infinite, but $V_k$ is specifically defined as being finite. Thus even with infinite Unions, $\mathscr{T}_1$ is still closed.
85029
I was wondering if this proof of this basic topological result concerning the  closure works.  Proposition: Let $A \subseteq (X,\tau)$. Then, $A$ is dense in $X$ if and only if every non-empty open subset of $X$ intersects $A$ non trivially. Proof: [only if] Assume that $A$ is dense in $X$. This means that $A \cup A' = X$, where $A'$ denotes the set of all the limit points of $A$. Let $G \in \tau$ be non-empty. Thus, $G \subseteq (A \cup A') = X$. Hence, either $G \cap A \neq \varnothing$, which establishes the result, or $G \cap A' \neq \varnothing$, which leads to a contradiction. [if] Assume that $A$ is not dense in $X$. Thus, there is a $x^* \in X \setminus (A \cup A')$. Notice, that $X \setminus (A \cup A')$ is open, because $A \cup A'$ is closed, and it is not empty. Hence, we can conclude by realizing that $X \setminus (A \cup A') \cap A = \varnothing$, which completes the proof. $\square$  It is one of the first proofs I attempt in topology, and I am not planning to see how it is proved in the book I am reading (unless you answer me that my proof is completely wrong). Thus, I am really looking forward to any feedback, also contentwise. Thank you for you time.
59894
Note that $\mathcal{P}(x)$,$\mathcal{P}(y)$ are power sets.  My proof.$\left( \Rightarrow \right)$ Let $t\in x$. Then, $t\in y$. So, since $t\in x$, $t\in \mathcal{P}(x)$. Also, since $t\in \mathcal{P}(x)$, $t\in\mathcal{P}(y)$. Thus, $x\subseteq y \Rightarrow  \mathcal{P}(x)\subseteq\mathcal{P}(y)$.  $(\Leftarrow )$. Similar.  Can you check my proof?