QUESTION. If $S$ is any set, prove that it is impossible to find a mapping of $S$ onto $S^{\ast}$. ( $S^{\ast}$ is the set of all subsets of $S$).  MY PROOF:  I ask my proof is right or wrong.....  If $S$ has $n$ element then $S^{\ast}$ has $ 2^n$ elements. it means  $S^{\ast}$ have greater number of elements than $S$ so every member of  $S^{\ast}$ cannot be associated with an member of $S$ , because of pigeon hole principle which says, If $n &gt; m$ pigeons are put into $m$ pigeonholes, there's a hole with more than one pigeon. and if a member of $S$ associate more than one member of $S^{\ast}$ function not defined so for function to be defined some member of $S^{\ast}$ should not be associated with any member of $S$ so function is not onto.
15781
Show that: Let A be a set and let $P(A)$ be the set of all subsets of $A$. Then there is no surjection $f: A→P(A)$.  Here is what I thought:  if $A=\{a,b\}$ then it has only two elements where $P(A)=\{∅,\{a\},\{b\},\{a,b\}\}$ has 4 elements. Therefore $f:A→P(A)$ cannot be surjective. But I have some problems:  1) How is it possible that any $f$ function to take $\{a\}$ from set $A$ to $\{a,b\}$? Maybe because I am thinking mainly about functions with real values like $f(x)=2x$, I find it a little bit strange that a function to take an element of a set to another set which has more elements. Is it possible?  edit: Now I thought that if $f(x)$ is $\sqrt{x}$, then $f(4)=±2$ which means it took an element from a set to a set which has 2 elements. But still I find it kind of strange to denote $f(\{a\})=\{a,b,c,...\}$  2) How can I construct a explicit proof for this question?  Regards
1509
Suppose $X$ is a set and $f : X \to X$ is a function.  If $X$ is a finite set, prove that $f$ is injective if and only if $f$ is surjective. Show that when $X$ is an infinite set, the statement is not true in general.   For that, let $X = \mathbb{R}$ and find a function $f: \mathbb{R} \to \mathbb{R}$ which is injective but not surjective, and a function $g: \mathbb{R} \to \mathbb{R}$ which is surjective but not injective  My attempt at the first part   Suppose that the function is surjective but not injective. Let $a,b \in X$ such that $f(a)=f(b)$ but $a \not =b$. Now since this is a finite set mapping to itself then there are not enough elements in $X$ to map to $X$ since two elements were used to map to one element, thus the function can't be surjective. Therefore if the function is surjective it is also injective.   Now suppose that the function is injective but not surjective. Let $a \in X$ such that $f(b)\not =a$ for all $b \in X$. Since the function was assusmed to be injective each $a \in X$ must map to an element of $X$, thus must have two elemetns in $X$ mapping to the same element in $X$. Hence the function can't be injective, therefore if the function is injective it must be surjective.   Would an exponetial function work for injective but not surjective since can't map to negative numbers. And an example of a function that is surjective but not injective could be a log function since none of the negative numbers get mapped to anything?   Also I'm having trouble seeing why it has to be finite for the first part to work. I understand it has something to do with the pigeonhole principle but its not that clear to me.
75254
Let $n$ be a natural number and $X$ = {$1,2,...,n$}. For subsets $A$ and $B$ of $X$ we deﬁne $A\Delta B$ to be the set of all those elements of $X$ which belong to exactly one of $A$ and $B$. Let $F$ be a collection of subsets of $X$ such that for any two distinct elements $A$ and $B$ in $F$ the set $A∆B$ has at least two elements. Show that $F$ has at most $2^{n-1}$ elements. Find all such collections $F$ with $2^{n−1}$ elements.  I have no clue on how and where to start. Please help.
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$?
89132
Is it (and if yes how?) possible to define an an binary operation $*$ for an arbitrary set $M$ such that $(M,*)$ is a group?  If $M$ is finite or countable infinite this is trivial, but is it also possible for any other sets? And if yes how can you construct $*$? If no can you provide a counterexample?
99767
This is one question which has been asked in Velleman's How to prove book:     Suppose $A$ is a set, and for every family of sets $F$, if $\cup F = A$ then $A ∈ F$. Prove that $A$ has exactly one element   This question has been already proved  but isn't something like this an counterexample of the proof:  $ F = \{\{1\},\{2\},\{1,2\}\}$   $ A = \{1,2\} $        Now,  $ \cup F = \{1,2\}$  and also $A \in F$ but $A$ has more than one element.             Is my counterexample valid ?
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.
19724
Let $S$ be an arbitrary infinite set. As a part of our homework, I have the following question: Question: How can I construct an injection $\mathbb{N} \to S$? Intuitively, I understand that such an injection should exist but describing it explicitly is probably not possible. Therefore, I think we need to use the Axiom of Choice: If $X$ is a set of non-empty sets, then there exists a choice function $F$ on $X$, i.e. a function on $X$ such that for all $M \in X$, we have $F(M) \in M$. Our class was given the following hint: Construct a family of $A_n \subseteq S$ with $|A_n| = 2^n$ for all $n \in \mathbb{N}$. Next, construct a family $B_n \subseteq S$ of non-empty and pairwise disjoint subsets. However, I do not really know what to do with this hint. Maybe the condition $|A_n| = 2^n$ indicates that we should use the power set of some set with $n$ elements but that is just a vague idea. I would really appreciate it if you could help me advancing with this problem.
9688
Is this true?  If $A$ and $B$ are sets, then $A=\emptyset $ if and only if $B = A \bigtriangleup B$.  If $A=\emptyset$ then $B=\emptyset$ too?  Could someone help me please?
103623
In ZFC, for example, there is no universal set, so what does it mean to write $\forall x (\cdots)$, i.e., for all sets something is true? Does it avoid the problem by quantifying over all elements but not allowing those elements to form a set?  A related question I have is about quantifying over infinite sets. If $X$ is a finite set with $n$ elements $x_1, x_2, x_3, \ldots, x_n$, Then it is reasonable to define $\forall x\in X :P(x)$ to be the statement $P(x_1)\wedge P(x_2)\wedge\cdots\wedge P(x_n)$ (which can be formalized using a recursive definition). But what about infinite sets? It seems that if $Y$ is a countably infinite set with elements $y_1,y_2,\ldots$, then $\forall y\in Y: P(y)$ would mean $P(y_1)\wedge P(y_2)\wedge\cdots$, which we couldn't finish stating. For uncountable sets, we would miss an element in between every time we count upwards.
117817
I am curious about why the existence of inaccessible cardinals cannot be proven in ZFC.My intuitive proof is:  Suppose we can prove there is an inaccessible cardinal ϰ,then by definition we must show that for any cardinals b&amp;c which satisfying b&lt;ϰ and c&lt;ϰ,then b^c&lt;ϰ.Then if we consider the set S which is the union of all the cardinals less than ϰ and consider the power set of S--P(S).It follows that |P(S)|>=ϰ.This implies we can proof the existence of inaccessible cardinals under ZFC iff we can disprove it.Therefore we cannot prove the existence using ZFC.  Is this the intuitive idea behind the proof?  I only have learnt a little bit in set theory by self-studying.But I don't know any thing about mathematical logic.So I don't know the thing such as the second incompleteness theorem.This statement was found in my set theory book but without prrof it.So any comment and improvement of my work is welcome!
119976
I understand that if we define a set such that $A=\{A\}$ we have then a contradiction because of regularity axiom, thus, a set can not be a member of itself. My question is; how can it be so, if I define a set $A=\{A,b\}$ ($b$ disjoint from $A$)?  Thanks.
55492
Title says it all.  Prove the statement is false with a counter-example:  For all sets S, T and V, V ∪ (S ∩ T) = (V ∪ S) ∩ T  Explain thoroughly if possible. I'm new to this
2650
Theorem. Let $X$ and $Y$ be sets with $X$ nonempty. Then (P) there exists an injection $f:X\rightarrow Y$ if and only if (Q) there exists a surjection $g:Y\rightarrow X$.  For the P $\implies$ Q part, I know you can get a surjection $Y\to X$ by mapping $y$ to $x$ if $y=f(x)$ for some $x\in X$ and mapping $y$ to some arbitrary $\alpha\in X$ if $y\in Y\setminus f(X)$. But I don't know about the Q $\implies$ P part.  Could someone give an elementary proof of the theorem?
93389
Given an arbitrary set $X$, can one always find an element outside $X$? I think this question boils down to whether there exists a universal set that contains everything, including itself. But wiki says that assuming the existence of a universal set leads to . So given a set $X$, can one explicitly construct an element that does not belong to $X$? For example, is $\{X\}$ such an element?
101067
This is exercise 1.2.19 from Chang &amp; Keisler's Model Theory, which has been giving me a headache for some time now.  Let $\mathscr{S}$ be a given propositional language of any cardinality (i.e. the set of sentence symbols is allowed to have any cardinality). Call a theory simply any set $\Gamma$ of sentences from $\mathscr{S}$. A set $\Delta$ of sentences is said to be a set of axioms for $\Gamma$ iff $\Gamma$ and $\Delta$ have the same consequences (i.e. they are equivalent). Finally, a set $\Sigma$ of sentences is said to be independent iff for each $\sigma \in \Sigma$, $\sigma$ is not a consequence of $\Sigma - \{\sigma\}$. Exercise 1.2.19 asks us to prove that a theory $\Gamma$ always has an independent set of axioms.  Now, if $|\Gamma| \leq \omega$, the proof is more or less simple; for the finite case, cf. , whereas, if $\Gamma = \{\gamma_0, \gamma_1, \dots\}$, one first constructs a set $\Gamma' = \{\psi_0, \psi_1, \dots\}$ such that $\psi_0 = \sigma_0$ and $\psi_n = \bigwedge_{i \leq n} \sigma_n$ (i.e. the conjunction of all $\sigma_i$ such that $i \leq n$). Then one constructs another set $\Delta = \{\delta_0, \delta_1, \delta_2, \dots\}$ such that $\delta_0 = \psi_0$ and $\delta_{n+1} = \psi_n \rightarrow \psi_{n+1}$. It's not difficult to show that $\Gamma'$ is a set of axioms for $\Gamma$ and that $\Delta$ is an independent set of axioms for $\Gamma'$.  But I'm completely lost about how to proceed in the transfinite case. It's clear to me that the above construction will not work directly; any ideas about how to adapt that strategy? Or should I look for an entirely different strategy?  EDIT: Notice that this question is different from ; the other question (and answer) is only asking about the countable case, the solution of which I have already provided a rough sketch in my own question. The general case, however, for theories of any cardinality, is, as C&amp;K remark, much harder.
23495
I guess it is too difficult a question to ask about the cardinality of $S_{\mathbb{N}}$ so I would like to ask whether it is countable or not.  I tried to prove it is uncountable somewhat mimicking the Cantor's diagonal argument but failed.