The below exercise and the axiom to which it pertains can be found in Tao's Analysis I, which I am currently self studying.      Axiom 3.11 (Power set Axiom) For any two sets $X$ and $Y$, there exists a set, denoted $Y^X$, which consists of all functions from $X$ to $Y$. Thus,    $$f\in Y^X \ \iff \ (f \ \text{is a function such that} \ f:X\to Y).$$   Exercise 3.4.6 Show that the above axiom implies the existence of the set   $$2^X:=\{S\mid S\subseteq X\},$$   which consists of all subsets of a set $X$. (Hint: start with the set $\{0,1\}^X$ and apply the , replacing each function $f$ with the object $f^{-1}(\{1\})$.    As the author suggested, we start with the set  $$\{0,1\}^X = \{f\mid f:X\to\{0,1\}\},$$ and replace its elements with subsets of $X$. Clearly, this procedure yields the set $2^X$ however, I am unsure how I can apply the axiom of replacement. How can I do this bit? Any hints or tips are greatly appreciated.   Edit: This question has been , I have just found.
81299
I'm stuck at one exercise from chapter of sets from Terence Tao's analysis book. I need to proof the lemma:  Lemma: Let $X$ be a set. Then the set $\{Y : Y \:\text{is a subset of}\: X\}$ is a set.  Note: The set $\{Y : Y \:\text{is a subset of}\: X\}$ is known as the power set of $X$, defined as  $2^X $  I can understand why the lemma is true, but I have no clue how to prove it. Furthermore, the author gave a hint that I found very confusing, it follows:  Hint: start with the set $\{0, 1\}^X$ and apply the replacement axiom, replacing each function $f$ with the object $f^{-1}(\{1\})$.
81180
I am trying to prove the following statement but have trouble  comprehending/going forward with some parts! Here is the statement:     If $A$ is any set, then  $|A|$ $&lt;$ $|P(A)|$   Here is what I have so far:  We need to show that there is an injection from $A$ to $P(A)$ but not a surjection.   A natural choice for an injection is the function $ f(x)$ $=$ $\{x \}$, which in plain English, takes any element $x$ (that is in $A$) and sends it to the one-element set $\{x \}$. Thus $f(x)$ is injective!  To show that there is no surjection, for the sake of contradiction, assume there is a surjection. Here is where I start to have trouble. Surjectivity means that every element of the co-domain is mapped to an element of the domain, correct? Consequently, in this particular case, we are "matching" sets (from $P(A)$) to elements (from $A$) right?  If the above is correct, my problem arises here. I am not sure how to prove that $f$ is not surjective. Unfortunately, I am easily confused by notation so please explain in English.  Thank you in advance!! :)
51507
Can someone give an argument, if possible using only the axioms of set theory, because I'm very weak there and have virtually no background, except the usual knowledge of the operation with sets one has to have when doing non-set theoretic non-research mathematics, why $\emptyset \in \emptyset$ or $\emptyset \subseteq \emptyset$ should or should not hold?
14706
Let $A$ and $B$ be sets, where $f : A \rightarrow B$ is a function. Show that the following properties are valid equivalent*:  $f$ is injective. For all $X, Y \subset A$ is valid: $f(X \cap Y)=f(X)\cap f(Y)$ For all $X \subset Y \subset A$ is valid: $f(X \setminus Y)=f(X) \setminus f(Y)$.   I do know what injective is, but I thought number (2.) and (3.) were valid for any kind of function. Just to see if I understood this right: $f(X\cap Y)$ means, first, make the intersection from $X$ and $Y$ and then map it to $B$ via $f$. $f(X)\cap f(Y)$ actually means, map all $f(X)$ and $f(Y)$ and intersect both. Aren't those both properties valid for all functions? I can't think of a counter example. Thanks in advance guys! *edited by SN.
71829
(1) Prove or disprove: For any sets $X,Y,Z$ and any maps $f:X \to Y$ and $g:Y \to Z$, if $f$ is injective and $g$ is surjective, then $g \circ f$ is surjective.  So i proved previously that $f$ is injective if $g \circ f$ is injective, but then i also proved that if $g \circ f$ is surjective then $g$ is surjective. then this question appears, so how do i prove it that it is true or false? I'm saying it's true, because $g \circ f$ is bijective, so how do i go around proving it? Or my idea is already wrong? I need some help thanks.  (2) Show that (it is true in general that) for any sets $A,B$, one has $P(A) \cup P(B) \subseteq P(A \cup B)$.  I know that power set has exactly all the subsets of $A$ for $P(A)$. but I dont know how to start.
29792
I'm trying to prove that the power set of $X$ and the set of functions from $X$ to $2$ are equinumerous. I think the best way to do so is to define a bijection between the two, but I'm not sure how to construct such a function. How do I do this?
87396
I am not very well versed on set theory or syntax, but I thought I knew the basics.  However, in a book about databases I am reading now, the author uses $2^x$ to signify "a set of $x$."  For example, $2^{\text{dogs}}$ is a set of $\text {dogs}$, etc.    The author never really explained this or why he does it, I just picked up the meaning from context.    I am not sure why the exponent operator is used, nor am I sure what the number $2$ has to do with it.  The sets being represented are NOT powers of $2$ (in size)... they come in all sizes.  Is this a valid notation?  I have not seen it anywhere before...
94485
I'm pretty sure I've asked way too many questions on sets already(still, a big thanks to everyone who helped) and even though I'm starting to see what's going on there are still some issues, for example this question:  Prove that $\bigcup P(X)=X$, where $P(X)$ is the power set for the set $X$  So, what I can do is the following:  $a \in \bigcup P(X) \implies \exists b \subset X$ s.t. $a\in b \implies a \in X$ and for the other direction I can take $b=X$.  However, I'm not sure whether this is correct, and in particular, the bit with $b \subset X, a\in b \implies a \in X$  If I take $X=\{\{1\},\{2\}\}$, then $P(X)=\{\emptyset,\{1\},\{2\},\{\{1\},\{2\}\}\}$, hence $\bigcup P(X)=\{1,2,\{1\},\{2\}\}$ which is not equal to $X$ by ZF$1$  Where's the problem?  Thanks
118284
I'm trying to prove that the Axiom of Choice is equivalent to the following statement:     Given a non-empty set $X, \ \exists \ f:\mathcal{P}(X) \setminus\{\emptyset\} \rightarrow X$ so that $f(B) \in B \ \ \forall \ B \in \mathcal{P}(X) \setminus \{\emptyset\}$   Proving $\implies$ is easy enough (I think):    Suppose we have a set $X \neq \emptyset$. Let $\{X\}_{\lambda \in \Lambda}$ denote the collection of sets given by $\mathcal{P}(X) \setminus \{\emptyset\}$. Then by the Axiom of Choice, there exists a choice function  $$ \{f: \mathcal{P}(X) \setminus \{\emptyset\} \rightarrow \cup_{\lambda \in \Lambda} X_{\lambda} : f(\lambda) \in X_{\lambda} \ \ \forall \ \ \lambda \in \Lambda\} $$ and then we notice that the union of the $X_{\lambda}$'s is simply $X$.     But I'm having a hard time proving $\impliedby$. I've tried taking the Axiom of Choice assumptions and allowing $X = \cup_{\lambda \in \Lambda} X_{\lambda}$ so that I can apply the statement above with $X$, but this power set is obviously larger than the union of my $X_{\lambda}$'s, so I'm not sure where to go from there with that approach.   My question is, how can I prove that the statement above implies the Axiom of Choice? A clarification on whether my idea would work or a hint for another approach would be appreciated.
105317
Theorem:  No set is equinumerous with its power set.  Proof:  Let $A$ be a set. We want to show that if $f: A \to \mathcal{P}A$ (a random function) then $f$ is not surjective.  We define the set $D=\{ x \in A: x \notin f(x)\}$ and obviously $D \in \mathcal{P}A$.  We assume that there is an $a \in A$ such that $f(a)=D$.  Then we have:  $$a \notin D \leftrightarrow a \notin f(a) \leftrightarrow a \in D, \text{ contradiction}$$  Therefore for each $x \in A, f(x) \notin D$, i.e. $f$ is not surjective.  Could you explain me the proof from the point where we assume that there is an $a \in A$ such that $f(a)=D$?  We have show that $D \in \mathcal{P}A$ and we want to show that $D \notin f(A)$ in order to show that $\mathcal{P}A$ isn't the image of $f$. Why do we do it like that? Why do we assume an $a \in A$ such that $f(a)=D$?
59678
Here's Prob. 21 in Sec. 17 of the book Topology by James R. Munkres, 2nd edition:  Consider the collection of all subsets $A$ of the topological space $X$. The operations of closure $A \to \overline{A}$ and complementation $A \to X-A$ are functions from this collection to itself. (a) Show that, starting with a given set $A$, one can form no more than $14$ distinct sets by applying these two operations successively. (b) Find a subset $A$ of $\mathbb{R}$ (in its usual topology) for which the maximum of $14$ is obtained.  My effort: Based on the feedback I've had from the valued Mathematics Stack Exchange community, I would like to ammend my effort as follows: Let $\mathcal{P} (X)$ denote the power set (i.e. the collection of all the subsets ) of $X$, and let the functions $f \colon \mathcal{P} (X) \to \mathcal{P} (X) $, $g \colon \mathcal{P} (X) \to \mathcal{P} (X) $, and $i \colon \mathcal{P} (X) \to \mathcal{P} (X) $ be defined as follows: $$f(A) \colon= \overline{A} \ \ \ \mbox{ for all } \ \ \ A \in \mathcal{P} (A),$$ $$g(A) \colon= X - A \ \ \ \mbox{ for all } \ \ \ A \in \mathcal{P} (A),$$ and $$i(A) \colon= \mathrm{Int} (A) \ \ \ \mbox{ for all } \ \ \ A \in \mathcal{P} (X).$$ Then we have the following couple of results $$f(f(A)) = f(A), \ \ \ i(i(A) = i(A), \ \ \ \mbox{ and } \ \ \ g(g(A)) = A \ \ \ \mbox{ for all } \ A \in \mathcal{P}(X).$$ Moreover, we also have the following two relations: $$f(g(A)) = g(i(A)) \ \ \ \mbox{ and } \ \ \ g(f(A)) = i(g(A)) \ \ \ \mbox{ for all } \ A \in \mathcal{P} (X).$$ How do we show that $$f(g(f(g(f(g(f(g(A)))))))) = f(g(f(g(A))))$$ and  $$g(f(g(f(g(f(g(f(A)))))))) = g(f(g(f(A))))$$ for all $A \in \mathcal{P} (X)?$. Please also refer to  link.
118987
I'm reading Guerino Mazzolla's Comprehensive Mathematics for Computer Scientists 1:     Axiom 3 (Axiom of Union) If $a$ is a set, then there is a set      $$\{x| \text{ there exists an element } b \in a \text{ such that } x\in b \}$$      This set is denoted by $\cup a$ and is called the union of $a$.    This axiom seems to take elements from inside of a set of sets, for example in the set: $a=\{\{u_1,u_2 \},\{u_3,u_4 \} \}$, there are two elements $b\in a$, then the mentioned set created by the axiom is $\{u_1,u_2,u_3,u_4 \}$.           The axiom seems to imply that the set $a$ must have a set inside of it for it to work, what if it  have an element that is not a set? (I'm not sure if this is possible, but I remember of having read something about the difference of sets and elements).         There's also an extension of my proposal, In the same book (and also in others) I've seen that the natural numbers are defined as:   $$\begin{eqnarray*}   {0}&amp;=&amp;{\emptyset} \\    {1}&amp;=&amp;{\{\emptyset\}} \\    {2}&amp;=&amp;{\{ \{\emptyset\}\}} \\    {3}&amp;=&amp;{\{ \{ \{\emptyset\}\}\}} \\   {\vdots}&amp;=&amp;{\vdots} \end{eqnarray*}$$  Then the singleton $\{ 3\}$ could be seen as $\{ \{ \{ \{\emptyset\}\}\}\}$, which could mean that   $$\cup \{ 3 \}=\cup\{ \{ \{ \{\emptyset\}\}\}\}= \{ \{ \{\emptyset\}\}\}=\{2 \}$$          Then the union could also be seen as the antecessor of a number?            Using the framework I provided, I see some ambiguity, look:   $$\{ \{ \{\emptyset\}\}\}=\{2 \}$$          I decided to interpretate it this way, but from the notation it's not clear in which pair of brackets I should stop, I guess that $\{ \{ \{\emptyset\}\}\}=\{2 \}$ but it could also be the case that $\{ \{ \{\emptyset\}\}\}=3$. I could want a singleton with a $2$ inside of it and a $3$ outside a set, no?
14900
Exercise 3.2.2 Use the axiom of regularity and the singleton set axiom to show that if $A$ is a set then $A \notin A$.  Axiom of Regularity: If $A$ is a non-empty set, then there is at least one element x of A which is either not a set, or is disjoint from A.  Singleton Set Axiom: If $a$ is an object, then there exists a set $\{a\}$ whose only element is $a$, we refer to $\{a\}$ as the singleton set whose element is $a$ Furthermore, if $a$ and $b$ are objects, then there exists a set $\{a,b\}$ whose only elements are $a$ and $b$    I think I can give the proof when A is the non-empty set which contains finite elements. However, can anyone give any hint for the general case?  Suppose $A \in A$   Then eixsts $x$ such that either $x$ is not a set or $x \cap A$=$\emptyset$  Then it is clear thar $x \ne A$ (if $x = A$, then $x \cap A \ne \emptyset$)  We observe that as an element, $A$ $\ne$ $x$, $A$ $\in$ $A$  Then $A$ $\in$ $A-x$   Define the new set $A-x$ as $A_1$  then exists $x_1$ such that $A \in A_1-x_1$  After finite steps  we find that $A \in \emptyset $  which leads to contradiction.
44329
Prove that   injective function $f:X\to Y$ exists surjective function $g:Y\to X$ exists   is equivalent.$(x,y\neq \emptyset)$   My approach  First,prove left to right.  If injective function $f:X\to Y$ exists, a set A can be defined like this. $$A=\{f(x):x\in X\}$$ then it is sure that $A\subset Y$, and $|A|=|X|$  And, if we define function $g$ like $$g(y)=\begin{cases}x &amp; \text{if $y\in A$ and } f(x)=y,\\x_0&amp; \text{if }y\notin A.\end{cases}$$ ($x_0$ is a fixed element of $X$)  Then, $g$ is a surjective function, so surjective function $g:Y\to X$ exists.  Now,prove right to left.  If surjective function $g:Y\to X$ exists, $\forall x \in X$, we can select a element $y\in Y$ that $g(y)=x$, which is clear that we can pick a different $y\in Y$ for $\forall x \in X$  if we define function $f$ as $f(x)=\text{one element in Y that g(that element)=$x$}$, f is a injective function, so injective function $f:X\to Y$ exists.    But, I am not sure that my approach is right, especially on proving right to left. Please check whether my approach is right, ways to improve it,  and some other ways of proving this question.
6443
My motivation for asking this question is that a classmate of mine asked me some kind of question that made me think of this one. I can't recall his exact question because he is kind of messy (both when talking about math and when thinking about math).   I'm kind of stuck though. I feel like the set $A^{\mathbb{N}} = \{f: \mathbb{N} \rightarrow A, f \text{ is a function} \}$ should have the same cardinality as the power set of A, if A is infinite. On the other hand, in this , it is stated that the sequences with real coefficients have the same cardinality as the reals.   It's easy to see that $A^{\mathbb{N}} \subseteq P(A)$, but (obviously) I got stuck on the other inclusion. Is there any general result that says anything else? References would be appreciated.  EDIT To clarify the intetion of this question: I want to know if there are any general results on the cardinality of $A^{\mathbb{N}}$ other that it is strictly less than that of the power set of A.   Also, I was aware that the other inclusion isn't true in general (as the post on here I linked to gave a counterexample), but thanks for pointing out why too. :)
10657
I need to prove that the set $\{A^n : n \in \mathbb{N} \}$ using the ZFC axioms (without Replacement).  My (rough) plan would be to construct some set containing "more" sets than necessary, then use the comprehension axiom to remove the undesirable sets. Something like: for some $Y$, $\{ X \in Y : \exists n \in \mathbb{N}, X = A^n\}$.  I know how to prove that any one of these sets (e.g., $A^2$), exists, but I have no idea how to prove that the set containing all of these powers exists.
27617
Show (within ZF Set Theory without choice) that for any sets $A,B,C:$   If $|A|^{|B|} = |B|$, then $|A| = 1 = |B|.$   That is, if there is a bijection from $|A|^{|B|}$ to $|B|$, then  $|A| = 1 = |B|.$  Please help me..