Here is an exercise from this book.

  1. Consider the sets $A$ and $B$ , where $$A = \{3, |B|\}$$ and $$B = \{1, |A|, |B|\}$$ . What are the sets?

Here is the solution from the book:

We need to be a little careful here. If $B$ contains 3 elements, then $A$ contains just the number 3 (listed twice). So that would make $$|A| = 1$$ , which would make $$B = \{1, 3\}$$ , which only has 2 elements. Thus $$|B| \ne 3$$ . This means that $$|A| = 2$$ so $B$ contains at least the elements 1 and 2. Since $$|B| \ne 3$$ , we must have $$|B| = 2$$ which agrees with the definition of $B$ . Therefore it must be that $$A = \{2,3\}$$ and $$B = \{1, 2\}$$ .

I do not understand how the solution ended. If at the end $A$ now has 2 elements, $B$ should be updated as well. Previously $B$ knows that $A$ is just $\{3\}$ with $$|A| = 1$$ , but since $A$ now has two elements 2 and 3, then $|A| = 2$ and $B$ must be $\{1, 2, 3\}$ . The last $3$ is the new cardinality of $B$ .

Of course, if I go this route, then $A$ must be updated as well because now $$|B| = 3$$ , making $A$ go back to $\{3\}$ . Thus we go back to the original forms of the sets, namely $$A = \{3\}$$ and $$B = \{1,2\}$$ and so on.

It seems to me, finding both cardinalities leads to never ending transformations. There must be something that I am missing. Why is it correct to end the sets such that $$A = \{2,3\}$$ and $$B = \{1,2\}$$ . It seems to only respect the cardinality of $B$ but did not continue to respect the cardinality of $A$. But continuing on this reasoning will lead to an infinite loop. Can someone explain what is wrong in my thinking?

  • 1
    $\begingroup$ "and $B$ must be $\{1,2,3\}$". Why? If $|A|=2$, it is clear that $1,2\in B$. But you cannot conclude that $3\in B$. $\endgroup$ Nov 26 '21 at 15:53
  • $\begingroup$ "Of course, if I go this root" *route $\endgroup$ Nov 27 '21 at 0:17

You don’t go in circles: a set has fixed elements and a fixed cardinality, so you don’t go back and forth on what its members are or what its cardinality is. The solution shows that if B has 3 elements, then B has 2 elements. From this, we can conclude that B cannot have 3 members, because it having 3 members would lead to a contradiction (and not to some kind of infinite loop). And, once you have established that, the rest follows.

And no, with A being $\{2,3\}$, $B$ does not become $\{1,2,3\}$: We know that $B$ has to contain $1$ and $2$ (the $2$ being yhe cardinality of $A$), so if the cardinality of $B$ is either $1$ or $2$, then that is not a new element. And indeed, with the cardinality of $B$ being $2$, that works out exactly right.

  • $\begingroup$ "The solution shows that if B has 3 elements, then B has 2 elements." - I am not sure if I understand fully. For example, if we have a completely separate set $C = \{|C|\}$ . Does this mean that $|C| = 0$ ? $\endgroup$ Nov 26 '21 at 16:25
  • $\begingroup$ @lightning_missile The solution says: Ok, it * looks* like $B$ has 3 elements: 1, |A|, and |B|. But if we suppose that these are indeed all three different numbers, then ….. [bunch of inferences] … B will end up with just 2 elements. (So: if B has 3 elements, then B has 2 elements) This means that B in fact cannot have 3 elements, for then B would have both 2 and 3 elements, which is a contradiction. $\endgroup$
    – Bram28
    Nov 26 '21 at 16:31
  • $\begingroup$ I am unfortunately not sure what you are trying to show with your C set example. …but I can tell you tgat C cannot be empty, since its own cardinality is definitely something, and hence an element of C. And, it is also clear that C cannot have any other elements, so C has one element, and so |C|=1, and C ={1} $\endgroup$
    – Bram28
    Nov 26 '21 at 16:34
  • $\begingroup$ Are you maybe thinking that we are somehow subtracting 1 from the cardinality of a set if its cardinality is an element if itself? If so: No, that is not what the solution is doing: the solution points out that with the cardinality of B being the same as the cardinality of A, the elements |A| and |B| are the same, and hence where 1,|A|,|B| look like 3 different elements, there are actually just 2 $\endgroup$
    – Bram28
    Nov 26 '21 at 16:38
  • $\begingroup$ your last comment is exactly right. I am confused by how |B| is constructed. Can we backtrack a bit? According to the solution, when |B| is originally 3, |A| becomes 1 with {3} so B becomes {1, 3}. This is not in the solution, but I think along the way B gets transformmed into {1,1,3} = {1,2} because 1 is repeated and removing the duplecate element gives |B| = 2. Let us call this transformation T1 because I think this is the problem. Now, since |B| is changed, A becomes {2,3}. (CONT) $\endgroup$ Nov 26 '21 at 17:24

While the notation $\{x,y,z,\ldots\}$ is often used as a way of "building" a set by enumeration of its elements, I think it is a mistake to approach the equations \begin{align} A &= \{3, \lvert B\rvert\}, \tag1\\ B &= \{1, \lvert A\rvert, \lvert B\rvert\} \tag2 \end{align} as if this were an exercise in constructing sets by enumeration.

Instead, you are meant to deduce what sets $A$ and $B$ might possibly satisfy these two equations simultaneously. We know that \begin{align} A &= \{2,3\},\\ B &= \{1,2\} \end{align} is a solution because when we substitute $\{2,3\}$ for $A$ and substitute $\{1,2\}$ for $B$ simultaneously into Equations $(1)$ and $(2)$, we get two true equations. There is no "infinite loop" here; we just list the elements of the proposed sets $A$ and $B$, plug everything in, and (boom!) we're done. It works.

All other proposed assignments of $A$ and $B$ can be proved not to be solutions because they lead to contradictions. Again, there is no need for an "infinite loop"; once you find a contradiction you know the proposed assignment is not a solution, and you do not have to continue to look for additional contradictions to that solution.

It will not always be the case that there is a unique solution for such a set of equations. For example, consider \begin{align} C &= \{1, \lvert D\rvert\}, \\ D &= \{1, \lvert C\rvert, \lvert D\rvert\}. \end{align} One solution of this set of equations is $C = \{1,2\},$ $D = \{1,2\},$ because then $\lvert C\rvert = \lvert D\rvert = 2.$ But another solution is $C = \{1\},$ $D = \{1\},$ in which $\lvert C\rvert = \lvert D\rvert = 1.$ So we can say the system of equations has a solution, but we cannot point uniquely to the solution of the equations.

As another example, consider \begin{align} E &= \{1, 2, \lvert F\rvert\}, \\ F &= \{2, \lvert E\rvert, \lvert F\rvert\}. \end{align} Clearly $\lvert F\rvert$ can only be one of the numbers $1, 2, 3.$ But in the case $\lvert F\rvert = 1$, we see that $F$ has at least the two elements $1$ and $2,$ which contradicts $\lvert F\rvert = 1.$ In the case $\lvert F\rvert = 2$, we see that $\lvert E\rvert = 2,$ which implies that $F = \{2\},$ which contradicts $\lvert F\rvert = 2.$ And in the case $\lvert F\rvert = 3$, we see that $\lvert E\rvert = 3,$ which implies that $F = \{2,3\},$ which contradicts $\lvert F\rvert = 3.$ So there is no solution at all.

The fact that we were able to apparently "define" $A$ and $B$ according to the solution of the original problem is due merely to a "fortunate" choice of equations that happen to have a solution and happen to have only one solution.

Getting back to the original question, we have the statement, "If at the end A now has 2 elements, B should be updated as well."

In fact this is not how it works for any solution of any system of equations, whether the objects on each side of the equation are sets, or algebraic expressions of numbers such as in the equation $x = 2y - x + 3,$ or matrix expressions, or some other kind of mathematical object. A solution to a system of equations is a solution not because it results from following a correct procedure, but simply because when you plug it in, it makes the equations true. Conversely, any proposed "solution" that makes the equations false when you plug it in is not a solution. There is no "update" step; either the solution works as presented, or it doesn't.

This is a very useful fact to keep in mind when solving various problems, especially problems where there is not a direct solution method that leads unerringly to one and only one correct solution.

What might appear to be an "update" step in the given solution of the original problem is actually a dead end: having assumed that the solution has a particular property, such as $\lvert B\rvert = 3,$ we reach a contradiction, hence the statement $\lvert B\rvert = 3$ must be false. But when this case is ruled out, we learn something about the set $A.$ And that leads to further deductions, finally reducing all the candidates for the assignment of the contents of the sets $A$ and $B$ to just one possible assignment.


Previously B knows that A is just {3} with |A|=1

No, previously an assumption was made from which it followed that $A=\{3\}$. It was shown that that led to a contraction. It was then concluded that the assumption that led to $A$ being $\{3\}$ was false. So we're now no longer making that assumption. The author is engaging in proof by contradiction: they are provisionally making an assumption, showing that assumption leads to a contradiction, and then concluding that the assumption is false. Everything after that is proceeding from that conclusion that the assumption is false.

It might help (or maybe make things more confusing, but it's worth a try) to consider the riddle "Alice and Bob are both from an island where everyone either always tells the truth or always lies. Alice says 'Bob said he's a liar'. What you can conclude?" If Alice is telling the truth, then Bob apparently is a liar. But if he is a liar, then he was telling the truth when he said he was a liar, so he's not a liar. So he's a truth-teller. Which means he lied about being a liar. Which means he's a liar. But he can't be. The assumption "Alice told the truth" leads to a paradoxical loop, so our assumption was wrong. We then conclude that Alice was lying, and the paradox disappears.

It seems to only respect the cardinality of B but did not continue to respect the cardinality of A.

It's completely consistent with all that was stated about $A$ and $B$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.