I asked a similar question yesterday about well ordered sets, now I am having troubles with equivalence relations.   Could someone suggest an injection from a well known set of cardinality $2^{\aleph_{0}}$ to the set of all equivalence relations of $\mathbb{N}$?  Many thanks in advance!
75969
I came across this long proof on this site:    But I would like to know whether my direction can work.  Say we want to find the cardinality of all equivalence relations in $\mathbb{N}$. Since it is a subset of all relations in $\mathbb{N}$, I conclude it has a cardinality smaller or equal to $\aleph$. Now, define an injective function from $P(\mathbb{N})$ to the set of equivalence relations by matching each subset of $\mathbb{N}$ with the identity relation (which is an equivalence relation in $\mathbb{N}$.  Therefore the cardinality of all equivalence relations in $\mathbb{N}$ is greater or equal to $\aleph$ and using CSB we get the desired result.  Seems legit?
4721
So I answered this question:  I believe my answer is correct, however one thing I couldn't explain fully, and which is bugging me, is why the rationals $\mathbb Q$, integers $\mathbb Z$ and naturals $\mathbb N$ all have cardinality $| \mathbb Q |=| \mathbb Z | = |\mathbb N| = \aleph_0$, when $\mathbb N \subsetneq \mathbb Z \subsetneq \mathbb Q$.  The basic proof of the other question, from my answer, is that for any $r$ in $\mathbb Q$ there is a single function $f(r)$ such that $f(r) \in \mathbb Z$, and the same holds between $\mathbb Z$ and $\mathbb N$. Because there is this 1:1 transformation possible, there must be the same number of numbers in the three sets, because otherwise there would be a number in one set for which the bijection could not produce a number of the other set, and this is not so.  Now, Belgi explained why $1&lt;2$ in the other question by defining the value 0 as the cardinality of the empty set $\emptyset$, 1 as the cardinality of a set of sets containing only the empty set, and 2 as the set of sets containing the empty set and a set containing the empty set, then proceeding as follows:     Now that we have defined the natural numbers we can define when one number   is smaller than another. The definition is $x&lt;y$ is $x\subset y$   and $x\neq y$ .      Clearly $\{\emptyset\}\neq\{\emptyset,\{\emptyset\}\}$ and $\{\emptyset\}\subset\neq\{\emptyset,\{\emptyset\}\}$   So this a proof, by definition, of why $1&lt;2$.   ... however, by the same definition, because $\mathbb N \subsetneq \mathbb Z \subsetneq \mathbb Q$, then $| \mathbb N | &lt; | \mathbb Z | &lt; |\mathbb Q|$ and thus a maximum of one of these quantities can be the ordinal quantity $\aleph_0$.
46860
Let $M$ be the set $\{1,2,3\}$. How many Equivalence relations $R \subset M \times M$ exists?  My idea is to count the disjoint partitions of M:  $K_1= \{\{1\},\{2\},\{3\}\}\Leftrightarrow\{(1,1),(2,2),(3,3)\}$  $K_2= \{\{1,2\},\{3\}\} \Leftrightarrow\{(1,1),(1,2),(2,1),(2,2),(3,3)\} $  $K_3=  \{\{1,3\},\{2\}\}\Leftrightarrow\{(1,1),(1,3),(3,1),(2,2),(3,3)\}$  $K_4= \{\{1\},\{2,3\}\}\Leftrightarrow\{(1,1),(2,3),(3,2),(2,2),(3,3)\}$  $K_5=\{1,2,3\}\Leftrightarrow K_5=M^2$  So the answer would be $5$. Is this correct? Reflexivity and Symmetry are obvious, but how can i check the right side for Transitivity?
45887
Let $A$ be a set with card($A$)=$a$. What is the cardinal number of the set of countably infinite subsets of $A$?   I see that this problem is equivalent to finding the cardinal number of the set of injective functions from $\mathbb{N}\rightarrow{A}$. I also know that the cardinal number of the set of bijections from $A\rightarrow{A}$ is $a^{a}$.   Hints and general heurisitcs would be greatly appreciated.
96259
For $x,y\in I:=[0,1]$ define the relation on $I$ as $x-y\in \Bbb Q$. How big (using cardinal number) is the cardinality of the equivalence class $[1/\sqrt2]$?  I have tried to solve it by finding the equivalence class but I'm not sure about the method that I can solve the question. Please, can you help me to solve it.
8768
This is problem #6 from Section 1.2 of Ash's Real Variables With Basic Metric Space Topology.   I am asked to show that it is impossible to list the rational numbers in increasing order.   While I know it is possible to list a finite subset of the rational numbers in increasing order, I was wondering if the reason for the impossibility in this case is because there is no least element of $\mathbb{Q}$?   I mean, it's possible to impose an ordering on $\mathbb{Q}$ (correct me if I'm wrong, but it seems possible to compare any two rationals).  But the set $\mathbb{Q}$ is of course, a subset of itself, and the Well-Ordering Principle says that a set $S$ is Well-Ordered only if any subset of $S$ contains a minimal element. Since $\mathbb{Q}$ does not contain a minimal element, it does not appear that it is a Well-Ordered set.   Is this the correct idea as to why it's impossible? If not, could somebody explain to me what the correct idea is and a strategy for proving it?  Thank you ahead of time.
28071
I know that the usual ordering of $\mathbb R$ is not a well-ordering but is there an uncountable $S\subset \mathbb R$ such that S is well-ordered by $&lt;_\mathbb R$?   Intuitively I'd say there is no such set but intuitively I'd also say there is no well-ordered uncountable set at all, which is obviously wrong. I still struggle to grasp the idea of an uncountable, well-ordered set.
90635
Given a well-orderable infinite set $A$, can we always say that the set $$\left\{R\subset A\times A:\langle A,R\rangle\, \text{is a well-ordering}\right\}$$ has cardinality $2^{|A|}$? How much Choice is required for the proof of this? I believe that where $A$ is countably infinite, we can proceed without any use of Choice. Is that correct?
88973
R is an equivalence relation defined as $xRy \Leftrightarrow a - b$ is an integer.  What is the cardinality of the quotient of $\mathbb R$ in respect to R? How would you prove it?  I thought about a bijection between $[0,1)$ to the quotient of $\mathbb R$ in respect to R, but can't figure out to prove it formally.
61184
In textbook it says that every well-orderable set is equipotent to an initial ordinal number. However, of course unwell-orderable cannot equipotent to any ordinal number, but is there any set is unwell-orderable? By axiom of regularity we know that every set is well-founded, so can we conclude that every set is well-orderable? If not, which set is unwell-orderable?
111618
Given a set of natural numbers ($\Bbb N$), and the relation $R=\{(a,b)\in\Bbb N^2: 5\mid (2a+3b)\}$. Is $R$ an equivalent relation?   My answer: Yes, because $2a + 3b$ is divisible by $5$, if and only if, $2a + 3b − 5b$ is divisible by $5$.  Is my reasoning right?   If it is not, then how do I prove that this is an equivalent relation?
13176
I'm having difficulty grasping a couple of set theory concepts, specifically concepts dealing with relations. Here are the ones I'm having trouble with and their definitions.  1) The collection of equivalence classes w.r.t. $R$     Def: Let $R$ be an equivalence relation in a set $X$. The collection of equivalence classes w.r.t. $R$ is the set:   $$[X]/R =\{S|(\exists x)(x\in X\land S=[x]/R)\}=\{[x]/R|x\in X\}$$   2) Partition     Def: Let $X$ be a set. A collection of sets $C$ is a partition of $X$ if:   (i) $$\bigcup_{S\in\ C} S=X.$$   (ii) $$\forall S \in C, S \neq \varnothing$$   (iii) $$\forall S, S' \in C, S' \neq S \Rightarrow S \cap S' = \varnothing$$   3) Relation induced by     Def: Let $C$ be a partition of $X$. The relation induced by $C$, denoted by $X/C$, is a relation in $X$ such that $$X/C = \{(x,y) | (\exists S \in C)(\exists x \in S \land \exists y \in S)\}$$
54541
A relation is a subset of the Cartesian product of two sets, if "have the same cardinality", denoted as $R$, is a relation, then there must exist set $A, B$, such that $R \subset A \times B$. What are $A, B$ then? They cannot be "set of all sets", because there is no such set according to axiom of regularity (ZFC set theory).  Did I miss something?  Thanks.
93710
Statement: There are uncountably many surjections from $\mathbb N$ to $\mathbb N$.  Is the following proof valid:  The real numbers are uncountable.   There exists a bijection between the set of real numbers and the set of all functions from $\mathbb N$ to $\{0,1\}$.   Given a function, $f$, from $\mathbb N$ to $\{0,1\}$, construct a surjection from $\mathbb N$ to $\mathbb N$, denoted $g$, as follows:  We map the $n$th composite number to $n$, and the nth prime, to $f(n)$.   Clearly this is a surjection since the composite numbers are countable. Clearly different functions $f$ lead to different surjections $g$. Since there are uncountably many $f$s, there are uncountably many surjections $g$.
19530
Let $X$ be an infinite set of cardinality $|X|$, and let $S$ be the set of all finite subests of $X$. How can we show that Card($S$)$=|X|$? Can anyone help, please?
109455
I am reading  of the Book of Proof, and I'm stuck at the Exercise 10 of section 11.2. It is as follows.  Suppose $R$ and $S$ are two equivalence relations on a set $A$. Prove that $R \cap S$ is also an equivalence relation.  Thanks for helps!
122680
Find total number of relations that are equivalence as well as partial order set. Assume set contains total $n$ elements.     My attempt:  As equivalence relation has property reflexive, symmetric and transitive and POSET has property reflexive, antisymmetric and transitive.  Symmetric and antisymmetric will cancle each other except reflexive relation and transitive relation can case antisymmetric, so it's also absent on resultant relation.  Therefore, all diagonal element should be present to satisfy conditions of equivalence as well as POSET.  So, it's independent of number of total number of element of set and answer will be $1$.     Can you explain in formal way, please?