I have problems in understanding few concepts of elementary set theory. I've choosen a couple of problems (from my problems set) which would help me understand this concepts. To be clear: it's not a homework, I'm just trying to understand elementary set's theory concepts by reading solutions.

Problem 1

(I don't understand this; I mean - not at all)

Let $f: A \to B$, where $A,B$ are non-empty sets, and let $R$ be an equivalence relation in set $B$. We define equivalence relation $S$ in $A$ set by condition:

$aSb \Leftrightarrow f(a)R f(b)$ Determine, which inclusion is always true:

(a) $f([a]_S) \subseteq [f(a)]_R$

(b) $[f(a)]_R \subseteq f([a]_S)$


$[a]_S$ is an equivalence class

Problem 2

(I suppose, that (a) is true & (b) is false)

Which statement is true, and which is false (+ proof):

(a) If $f: A \xrightarrow{1-1} B$ and $f(A) \not= B$ then $|A| < |B|$

(b) If $|A| < |B|$ and $C \not= \emptyset$ then $|A \times C| < |B \times C|$

Problem 3

(I don't know, how to think about $\mathbb{Q}^{\mathbb{N}}$ and $\{0,1\}^∗$.)

Which sets have the same cardinality:

$P(\mathbb{Q}), \mathbb{R}^{\mathbb{N}},\mathbb{Z}, \mathbb{Q}^{\mathbb{N}}, \mathbb{R} \times \mathbb{R}, \{ 0,1 \}^*, \{ 0,1 \}^{\mathbb{N}},P(\mathbb{R})$

where $\{ 0,1 \}^*$ means all finite sequences/words that contains $1$ and $0$, for example $000101000100$ or $1010101010101$ etc. $P(A)$ is a Power Set.

Problem 4

(I don't understand this; I mean - not at all)

What are: maximum/minimum/greatest/lowest elements in set:

$\{\{2; 3; 3; 5; 2\}; \{1; 2; 3; 4; 6\}; \{3\}; \{2; 1; 2; 1\}; \{1; 2; 3; 4; 5\}; \{3; 4; 2; 4; 1\}; \{2; 1; 2; 2; 1\}\}$

ordered via subset inclusion

Problem 5

How many equivalence relations there are in $\mathbb{N}$ which also are partial order?

These are simple problems, but I really need to understand, how to solve this kind of problems. I would apreciate Your help.


closed as off-topic by Lord_Farin, egreg, user1337, Asaf Karagila, azimut Nov 28 '13 at 15:40

  • This question does not appear to be about math within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I don't understand problem 1 & 4 (I mean - not at all). I suppose, that in 2. (a) is true & (b) is false, but I'm not sure about that. In 3. I don't know, how to think about $\mathbb{Q}^{\mathbb{N}}$ and $\{ 0,1 \}^*$. I think, that in 5. there is a question about equality relation, but - again - I'm not sure. $\endgroup$ – lonyt Jan 12 '11 at 20:53
  • 5
    $\begingroup$ This question appears to be off-topic because it consists of multiple, unrelated questions. $\endgroup$ – Lord_Farin Nov 28 '13 at 10:05

Problem 1. Here's an example: take $A=\mathbb{N}$, $B=\{0,1,2,3\}$, and let $f\colon A\to B$ map the natural numbers to their remainder when divided by $4$ (so $f(3) = 3$, $f(15) = 3$, $f(21) = 1$, etc). Let $R$ be the equivalence relation on $B$ given by $aRb$ if and only if $a^2\equiv b^2 \pmod{4}$.

The relation $S$ is defined as follows: first map to $B$, then check $R$ for the images. If the images are related, then the original elements are related; if the images are not related, then the originals are not related. For example, to see whether $3R10$ holds, we take $f(3)=3$ and $f(10)=2$, and check whether $3R2$ holds or not; since $3^2 \not\equiv 2^2\pmod{4}$, then $3\not R2$; that is, $f(3)\not Rf(2)$, so $3\not S 2$. On the other hand, $7S9$ holds: because $f(7) = 3$, $f(9) = 1$, and $f(7)^2 = 9 \equiv 1 = f(9)^2\pmod{4}$, so $f(7)Rf(9)$ is true.

That's the idea.

Now, for a general case. First convince yourself that $S$ is in fact an equivalence relation on $A$.

Once you do that, in order to check (a), you want to see if $f([a]_S)\subseteq [f(a)]_R$. Well, take an element in $f([a]_S)$; this is a $b\in B$ such that $b=f(x)$ for some $x\in[a]_S$. that is, $xSa$ is true, and $f(x)=b$. So you want to see whether $b\in[f(a)]_R$; that is, whether $bRf(a)$. So, from assuming $xSa$ holds, you want to see whether you can always conclude that $f(x)Sf(a)$.

For (b), you proceed similarly; now take $b\in [f(a)]_R$, and you want to see whether $b\in f([a]_S)$. That is, assume that $bRf(a)$; must there exist an $x\in A$ such that $xSa$ and $f(x)=b$? If so, prove it; if not, give a specific counterexample with specific $A$, $B$, $f$, $R$, and $S$, and an exlicit $a$ and $b$.

Problem 2. (a) If your sets are finite, the your guesses are right; if your sets are not necessarily finite, you're in trouble. Consider $A=B=\mathbb{N}$ and $f(n) = 2n$.

For (b); you know there is a $1-1$ function from $A$ to $B$; see if you can construct a $1-1$ function from $A\times C$ to $B\times C$ (and see if you can spot why you need $C\neq\emptyset$). This will show that $|A|\leq|B|$ implies $|A\times C|\leq|B\times C|$. If you also know that there is no surjection between $A$ and $B$, then again you are going to have two different cases, depending on whether $C$ is "really big" (compared to $A$ and $B$) or not.

Problem 3. The set $A^B$ is the set of all functions from $B$ to $A$. So $\mathbb{Q}^{\mathbb{N}}$ is the set of all functions from $\mathbb{N}$ to $\mathbb{Q}$; this is the set of all rational sequences (sequences, each term a rational number). The set $\{0,1\}^{\mathbb{N}}$ is the set of all binary sequences (sequences, each term either $0$ or $1$). Hint. Think about binary expansion of real numbers between $0$ and $1$, or even better, the ternary expansion of the elements of the Cantor set to deal with $\{0,1\}^{\mathbb{N}}$. For $\{0,1\}^*$, can you count how many sequences of length $n$ there are, for each $n$? Add them all up then. For $\mathbb{Q}^{\mathbb{N}}$, can you exhibit at least as many sequences as there are real numbers?

Problem 4. You are comparing sets by inclusion. We say set $A$ is "smaller than or equal to" set $B$ if and only if $A\subseteq B$. So, for example, the set $\{3\}$ is smaller than or equal to the set $\{1,2,3,4,5\}$, but not smaller than the set $\{1,2\}$. When using this order, note that it is possible for you to have two sets, neither of which is smaller than or equal to the other (for example, neither of $\{3\}$ and $\{1,2\}$ is smaller than the other; they are incomparable). The maximum among the sets you are given would be a set that is greater than or equal (contains) all of the sets you are given; a minimum would be a set that is smaller than or equal (is contained in) all of the sets you are given. They may or may not exist. "Greatest" is the same as "maximum" in this context; "smallest" the same as minimum.

Problem 5. An equivalence relation is a collection of ordered pairs that is reflexive, symmetric, and transitive. A partial order is a collection of ordered pairs that is reflexive, *anti*symmetric, and transitive.

So the question is: how many equivalence relations on $\mathbb{N}$ are also antisymmetric? Or: how many relations are all of reflexive, transitive, symmetric, and antisymmetric? Think about what having both symmetry and antisymmetry means.


For problem 3, $\mathbb{Q^N}$ means the set of functions from $\mathbb{N}$ into $\mathbb{Q}$. So you need to decide how many of them there are. Certainly there are at least as many as functions from $\mathbb{N}$ into 2, which is $2^\mathbb{N}$, as you could just restrict the functions values to 0 and 1. Have you seen that before?

For problem 4, "ordered by subset inclusion" means $a \lt b \Leftrightarrow a \subset b$. So, for example, {3} < {1;2;3;4;6} and three others of the given sets. Now look at your definitions of maximum/minimum/greatest/least and see which sets satisfy them.

  • $\begingroup$ OK, I see now. Thank You. $\endgroup$ – lonyt Jan 12 '11 at 21:20

I'll do 1 and 5.

For one, the first inclusion is true. For let $x\in f([a]_b)$. We want to show that $x\in [f(a)]_r$, i.e., that $x$ $r$ $f(a)$. Since $x\in f([a]_s)$, there is a $b\in A$ such that $b$ $s$ $a$ and f(b) = x. Since $b$ $s$ $a$, we know $f(b)$ $r$ $f(a)$. Thus, $x$ $r$ $f(a)$ so $x\in [f(a)]_r$.

The reverse inclusion is false. Suppose $A = \{a\}$ and $B = \{b,c\}$ with $b$ and $c$ distinct. Use the relation $r = B\times B$ - all elements are $r$-related to all elements. Use the function $f:A\rightarrow B$ given by $f(a) = b$. Then it's not too hard to show that $c\in [f(a)]_r$ but $c\notin f([a]_s)$.

For 5, notice that the only difference between a partial order and an equivalence relation is in the symmetry/antisymmetry. In other words, if $r$ is an equivalence relation, then $a$ $r$ $b$ implies $b$ $r$ $a$. However, if $r$ is a partial order, then $a$ $r$ $b$ and $b$ $r$ $a$ implies $a = b$.

(To be clearer, I think there are several competing definitions of "partial order" - some, drop the antisymmetry condition. If that's the case, ignore my answer to number 5).

Now, suppose $r$ is an equivalence relation and a partial order. Given $a$, what are all the elements it can be related to?

Well, suppose $a$ $r$ $b$. Then we conclude that $b$ $r$ $a$ since $r$ is an equivalence relation. Since $r$ is a partial order, we conclue from this that $a = b$. Said another way, if $a\neq b$, then $a$ $r$ $b$ cannot be true. Thus, the only possibility to consider is whether or not $a$ $r$ $a$. But in an equivalence relation, this must be the case.

Hence, our relation $r$ is simply the set of all ordered pairs $(a,a)$ - there is a unique relation on $\mathbb{N}$ (or any set!) which is both an equivalence relation and a partial order.

  • $\begingroup$ I normally wouldn't have posted such a complete answer to problems which look like homework. However, the OP specifically said it's not homework, and I'm in the (perhaps stupid) habit of taking people at their word unless I have a reason not to trust them. If the general consensus is that I should edit this down to hints, just comment and let me know. $\endgroup$ – Jason DeVito Jan 12 '11 at 21:08
  • $\begingroup$ How could I prove, that it's not a homework? I can't. I could just wrote, that it's not a homework. $\endgroup$ – lonyt Jan 12 '11 at 21:19