8
$\begingroup$

The finite analogue of the axiom of choice is true, and it seems highly intuitive that it would be true for the infinite case. It is, however, undecidable. When explaining this to myself or to others, what I typically note is that our intuitions about finite sets don't necessarily hold over for infinite sets, and we should try to discard them. But this itself is an intuition that I'm looking to fortify. I thus ask, what are examples of theorems that hold true for finite sets, and to most people would seem to hold true for infinite sets, but don't. I.e., I'm looking for something that's provably false for infinite sets rather than merely undecidable.

$\endgroup$
5
  • $\begingroup$ Provably wrong in which axiomatization? $ZFC$? $ZF$? $ZF + \neg C$? Something else? $\endgroup$ Jul 5, 2015 at 23:54
  • $\begingroup$ An interesting alternative to your question is the following: Find examples of properties that are true for all finite subsets of a set E but not true for E. The converse, a property that, if it is true for all finite subsets of E, then is true for E, often appears in proof with AC, via Zorn Lemma. $\endgroup$
    – Taladris
    Jul 6, 2015 at 1:02
  • $\begingroup$ @Taladris When putting it this way, we should probably talk about a structure with universe $E$ and its substructures as otherwise the question remains the same. $\endgroup$ Jul 6, 2015 at 2:15
  • $\begingroup$ @Stefan I think all would be interesting, but ZF would probably be the most (to me). $\endgroup$ Jul 6, 2015 at 13:53
  • $\begingroup$ Thanks, a number of good responses here. I have (further) realized how relative the concept of "intuition" is. For many examples given, the statement seems as intuitively obviously false in the infinite case as it is true in the finite case. But of course, this is because I've been dealing with these concepts for a while and understand them well. The trick in explaining this to others is to find one of the examples below that's in their sweet spot - they have learned enough to build the finite intuition, but not yet enough to have learned why it doesn't hold in the infinite case. $\endgroup$ Jul 9, 2015 at 0:25

8 Answers 8

6
$\begingroup$

Take a set of rational numbers $A$ such that $$ \sum_{a\in A}=x<\infty. $$ If $A$ is finite, then $x$ is rational, which is not necessarily true if $A$ is infinite. This doesn't have as much to do with sets really, but shows how being closed under finitely many operations does not determine behavior under arbitrarily many operations. You could play this same game with intersections of closed sets.

You could also look at the power set of a set. The power set of $A$ is finite if and only if $A$ is finite, and is in fact uncountably infinite if $A$ is infinite.

Another option deals with functions from a set to itself. Let $f$ be a function from $A$ to itself. If $f$ is injective, then it is automatically bijective and hence invertible if $A$ is finite. However, this does not necessarily hold if $A$ is infinite.

One last example: any proper subset of a finite set has strictly less cardinality than the original set. However, this fails in the infinite case, as can be seen by looking at the set of integers and the subset of even integers.

$\endgroup$
3
$\begingroup$

Well, there are a lot of examples. As I'm not sure which axiomatization you would like to use, I will provide a few examples in different settings. And while you emphasized that you aren't interested in "undecidable" examples, I will list them where they show the necessity of (some form of) choice.

(Throughout, I'm assuming the consistency of $ZF$)

  • $ZF$(some choice?): Let $(a_n)_{n \in \mathbb N}$ be a sequence of reals s.t. $\sum_{n=1}^\infty a_n$ converges conditionally. Then for any permutation $\tau \colon \mathbb N \rightarrow \mathbb N$ with finite support (i.e. $\tau(n) \neq n$ for only finitely many $n \in \mathbb N$) $\sum_{n = 1}^\infty a_{\tau(n)}$ has the same value. On the other hand: For any $x \in \mathbb R$, there is a permutation $\sigma_x \colon \mathbb N \rightarrow \mathbb N$ s.t. $x = \sum_{n=1}^\infty a_{\sigma_x(n)}$. This is the Riemann series theorem and probably the first nontrivial example in this area that I have encountered.
  • $ZF$: Given a finite set $X$, every injective function $f \colon X \rightarrow X$ is surjective. This is false for some infinite sets. See Dedekind-infinite.
  • $ZFC$: The above is false for all infinite sets.
  • $ZFC$: For every finite (mathematical) game between two player, one of them has a winning strategy. This is false for infinite games. See Determinacy
  • $ZF+ \neg C$: It is consistent that for every infinite game one player has a winning strategy.
  • $ZF$: While every finite linear order is well-founded, there are infinite ill-founded linear orders (e.g. $(\mathbb Z, <)$)
  • $ZF$: Given nonempty sets $A_1 \supseteq A_2 \supseteq \ldots$, then for every $n \in \mathbb N$ $\bigcap_{i=1}^n A_i \neq \emptyset$. However, there are examples s.t. $\bigcap_{i=1}^\infty A_i = \emptyset$ (e.g. $A_i = \{i, i+1, \ldots \}$)
  • $ZF$: For a fixed finite cardinality $\kappa$, there is (up to order isomorphism) exactly one well order of size $\kappa$ (the "size" of a well-order $(X, \prec)$ denotes the cardinality of $X$). This is false for infinite cardinalities $\kappa$.
  • $ZF$ (actually, I'm note sure if some weak form of choice is used along the way...): Every finite field is perfect. There are infinite fields, that are not perfect.
  • $ZF$: For every finite field $K$, there are polynomials $f \neq g$ s.t. $f(x) = g(x)$ for all $x \in K$. This is false for some infinite field (<- some weak form of choice?).
  • $ZFC$: If $K$ is an infinite field and $f,g$ are polynomials s.t. $f(x) = g(x)$ for all $x \in K$, then $f=g$. In other words: The above is false for all infinite fields.
  • $ZFC$: For any finite number of $ZFC$-axioms, $\phi_1, \ldots, \phi_n$, there is a model $M \models \phi_1, \ldots, \phi_n$
  • The statement "there is a model of $ZFC$" is not provable in $ZFC$.
  • $ZF$: Two finite, elementary equivalent models $M$, $N$ are always isomorphic. This isn't true for infinite, elementary equivalent models.
  • ...
$\endgroup$
3
$\begingroup$

My examples are at a lower level than the other answers so far. Maybe your audience will be experienced enough with infinities to consider these statements obviously false in the infinite cases; if so, maybe you can remind them of a time when they didn't know so much, or point out that students do stumble on these issues on first encounter, or point out that some of these issues were difficult to resolve in actual history.

  • Addition is associative. True for finite sums; famously false in cases such as $1-1+1-1+\dotsb$.
  • Any bounded set has a minimum and a maximum element. (It does seem that people often expect this to be true for infinite sets. I personally don't remember expecting that — it was so long ago — but students frequently stumble on things like the nonexistence of a smallest positive number, and the perennial interest of the $0.999\ldots=1$ thing seems to arise in part from the same kind of expectation.)
  • If each step of a process leaves something unchanged, then the whole process leaves it unchanged. (The surprise of the perimeter paradox here relies on this kind of expectation failing in the infinite case. See this answer for a bit more on this particular example.)
  • There are lots more limit-related examples, e.g., the lightbulb that toggles on/off at times $0,\frac12,\frac34,\frac78,\dotsc$; is it on or off at time $1$? The expectation that there's a definite result to this process comes from experience with finite processes.

You might also be able to re-cast some famous paradoxes and weird examples in these terms, e.g., the St. Petersburg lottery, Gabriel's horn.

$\endgroup$
1
  • 1
    $\begingroup$ Oh, and I think your recommendation to "discard" our intuitions in the infinite case is a bit too strong. There's baby in that bathwater! The linked answer about circles is interesting because the intuition works really well in one case, and fails miserably in another. We don't want to lose the case where it works well. So... Test? Certainly. Adjust? Probably. Discard? Mm.... maybe not. $\endgroup$
    – user21467
    Jul 6, 2015 at 2:24
0
$\begingroup$

If $K$ is a Galois extension of the field $F$ with Galois group $G$, then every subgroup of Gal$\,(K/F)$ corresponds to an intermediate filed: this is true when the group $G$ is finite, and false for infinite case.

A polynomial in a single complex variable is completely determined by its location of roots and the value at $0$; however in the infinite degree case (power series) it is false.

$\endgroup$
2
  • $\begingroup$ Your second example is flawed: a polynomial is not determined by its value at $0$ if that value is itself $0$. $\endgroup$
    – TonyK
    Jul 6, 2015 at 9:13
  • $\begingroup$ Thanks TonyK, for pointing out the flaw, which I should have avoided. This flaw does not invalidate this approach. If we remove that case there is still non-trivial examples that OP wants. $\endgroup$ Jul 6, 2015 at 12:26
0
$\begingroup$

Terse version: the existence proof of nontrivial ultrafilters for infinite sets requires the axiom of choice.


Suppose there's a set $X$. Someone keeps handing you subsets of $X$, and you sort them into two piles, YES and NO. The method you use to sort them satisfies the following properties:

  • The empty set goes into the NO pile.
  • If they hand you two sets $A$ and $B$, and $A$ goes into the YES pile, and $B$ is a superset of $A$, then $B$ also goes into the YES pile.
  • If two sets go into the YES pile, then their intersection also goes into the YES pile.
  • If a set goes into the YES pile, its complement goes into the NO pile.

Then your method of sorting sets into piles is an ultrafilter.

If $X$ is a finite set, then your ultrafilter must consist of simply checking whether a certain element (call it $a$) of $X$ is present, and putting the subset in the YES pile if so, and the NO pile otherwise. This is the trivial ultrafilter with principal element $a$.

If $X$ is an infinite set, is this still true? In ZFC, the answer is no: there are other ultrafilters which are not trivial ultrafilters. (If you can give me an example of a non-trivial ultrafilter, I'll buy you a car.) In ZF, the answer is maybe: ZF is consistent with both the statement "there are non-trivial ultrafilters" and the statement "there are no non-trivial ultrafilters". (Separately, not together.)

I, personally, find it more intuitive to think that non-trivial ultrafilters do not exist, on the grounds that if I want to act as a non-trivial ultrafilter, I can't do this by checking any finite number of elements of $X$ for membership in the subset I'm given. I have to, somehow, make the decision based on information that can't be found this way, which I find suspicious.

$\endgroup$
0
$\begingroup$

How about the claim: a proper subset must have a smaller size than its proper superset.

$$A \subseteq B\ \land\ A \neq B \implies\lvert A\rvert < \lvert B\rvert$$

$\endgroup$
0
$\begingroup$

If $V$ is a finite dimensional vector space, then $V$ is isomorphic to its dual space $V^*$. This does not hold for infinite-dimensional vector spaces.

$\endgroup$
0
$\begingroup$

I've been thinking about one particular example on this topic this week, and I've made a video on the topic called "The inescapable Newton's Shells".

https://youtu.be/nQhnj_SdPb8

In the infinite case, you can put your center of symmetry at any point, Q, in the universe, and get a gravitational field towards that point. That would mean that the gravitational field at any given point is mostly, a matter of opinion about where to put your point of symmetry, Q.

In the finite case, though, Q is non-arbitrary. It is the center of an actual finite spherical distribution. So there is no "Choice" of Q. It is determined by the fact and presence of the matter in the vicinity of Q.

I posit that the gravitational field at any given point P, in the universe, is not subject to anyone's opinion of where to put some arbitrary point of symmetry.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .