How to convince a friend the equivalence of infinite sets

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
sparkyb
Posts: 1091
Joined: Thu Sep 06, 2007 7:30 pm UTC
Location: Camberville proper!
Contact:

How to convince a friend the equivalence of infinite sets

Postby sparkyb » Sun Jul 28, 2013 4:29 am UTC

I have an acquaintance who posted something on Facebook talking about how he doesn't believe that all infinite sets are the same size. I explained that there are indeed different infinities, countable infinity (aleph-zero) versus uncountable infinity, but that though it may seem counter-intuitive you can prove that all countably infinite sets (like whole numbers, even whole number, and even fractions) are equivalent. However, he didn't agree with the proof. Paraphrasing, it started with:

My friend wrote:I've been thinking.
Say you have an X-Y graph and you plot x=y starting at x=0. the area under that is infinite, right?
Then if you have x=2y starting at x=0. The area under that is also infinite.

The mathematical argument goes that both areas are equal because infinity is infinity and you can't have a greater or lesser infinity. I think that argument is bunk.


I responded:

I wrote:The even integers are also the same countable infinity as all the integers. It seems hard to believe but it can be proved. The proof is basically that if you can map every number from one set onto a unique number from another set, than the size of the sets are the same. So to map even integers onto the set of countable numbers, just divide by two (2->1, 4->2, 6->3, etc). It may be hard to wrap your head around, but that's just how infinity works.


He was unconvinced:

My friend wrote:That's the traditional argument used for number sets, but the fact is also that while you can match an even number with a non-even number, you can also fit all the odd numbers in between for the full set while you can't with just the even number set.

The real difference shows when you look at areas like in the x=y example. And yes, each point of infinity can be matched with another point of infinity, but the fact of the matter is that at any given value, the area under x=y is more than twice as great as the area under x=2y. ... Greater and lesser infinities.


I know his reasoning is faulty, but I'm not sure what the counterargument is. Anyone know?

lalop
Posts: 210
Joined: Mon May 23, 2011 5:29 pm UTC

Re: How to convince a friend the equivalence of infinite set

Postby lalop » Sun Jul 28, 2013 5:31 am UTC

There's a bijection (x,y) <-> (x,1/2y) between the two sets, making them "the same size".

The bijective definition of "same size" is actually pretty convincing once you understand it. And, of course, note that "X does not have a bijection with any {1,...,n}" <=> "X has a bijection with a proper subset of itself", so it's not so surprising that certain infinite sets should be contained completely within one another, yet still be of "the same size".

MostlyHarmless
Posts: 154
Joined: Sun Oct 22, 2006 4:29 am UTC

Re: How to convince a friend the equivalence of infinite set

Postby MostlyHarmless » Sun Jul 28, 2013 9:05 am UTC

I think the reason most people don't understand this concept is that their intuitive definition of size is not the same as the technical definition of cardinality. There are other ways to define the size of sets that do not have the same conclusions.

The real trick is therefore convincing your friend that bijections are a good way to decide if things are "the same size". My favorite explanation is to ask them how they would decide if two piles had the same number of objects if they couldn't count. The answer pretty much everyone will come up with is to take one thing from both piles over and over again until both are empty. If they don't finish one before the other one, then the piles are the same size. As long as the piles are finite, this is the same as finding a bijection between two sets. Once they agree that bijections are a good way to determine equivalence, your arguments should actually be convincing.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1448
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: How to convince a friend the equivalence of infinite set

Postby Xenomortis » Sun Jul 28, 2013 9:08 am UTC

Ask them to count something. Get a small collection of things, and have them count it.
Then point out that all he's doing is assigning natural numbers as labels in a systemic fashion.
Image

User avatar
firechicago
Posts: 621
Joined: Mon Jan 11, 2010 12:27 pm UTC
Location: One time, I put a snowglobe in the microwave and pushed "Hot Dog"

Re: How to convince a friend the equivalence of infinite set

Postby firechicago » Sun Jul 28, 2013 2:47 pm UTC

You can do a similar procedure to the mapping of naturals to evens to his geometric representation. Divide your Cartesian plane into 1x1 squares. Take all the squares that are in the first quadrant and entirely under the curve y=x and number them starting in the lower left working up in columns (so the square whose upper right corner is (2,1) is the first, then (3,1) then (3,2) then (4,1) etc.)

Now imagine cutting those squares out and pasting them over the graph of y=2x in the same procedure, only now you're pasting them on to any square in the first quadrant that has any part under the curve y=2x. (So it goes (1,1) (1,2) (2,1) (2,2) (2,3) (2,4) (3,1) ...)

If the area under y=2x is bigger than the area under y=x, which part of that area will end up uncovered by this procedure?

In fact, our naive assumptions about bigger and smaller would seem to lead us to conclude that the area under y=x is now bigger than the area under y=2x, because the way we've set up this procedure we're leaving part of the area under y=x unused and using full squares to cover over squares that are only partially under y=2x.

The problem that your friend is having is that he is confusing quantities which approach infinity, which is to say they are becoming arbitrarily large, with quantities that are actually infinite. The functions f(x)=x and g(x)=2x are usually only defined for real numbers, which are by definition finite. So we can certainly say that 2x is in some sense bigger as x approaches infinity, but if x is actually infinite, it breaks all the rules as we have defined them. It might be helpful to compare this to the behavior of h(x)=1/x as x becomes arbitrarily close to zero. We can say quite a bit about what happens with very small positive values of x, but those very small positive values of x don't tell us very much about what happens when x actually equals zero. (And if your friend gives you some version of "that's easy, 1/0 equals infinity" you can always ask him whether it's a positive or negative infinity, since very small negative values of x give us radically different results.)

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Re: How to convince a friend the equivalence of infinite set

Postby skullturf » Sun Jul 28, 2013 3:12 pm UTC

Seemingly reasonable premise #1: The whole is always strictly greater than the part.

Seemingly reasonable premise #2: Two sets have the same "size" if their elements can be put into one-to-one correspondence.

Those premises both seem plausible, and as far as I'm aware, I think that before Cantor, people tended to believe both of them. But if you believe both of them, then you can't really meaningfully assign "sizes" to infinite sets.

Although it might seem counter-intuitive at first, the key is to reject premise #1. In fact, one could say that infinite sets are precisely those sets that can be put into one-to-one correspondence with certain proper subsets of themselves!

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: How to convince a friend the equivalence of infinite set

Postby skeptical scientist » Sun Jul 28, 2013 3:42 pm UTC

Cardinality is one notion of the "size" of an infinite set, but not the only one mathematicians use. Others include measure, dimension, and density. What your friend is talking about sounds most like density. I think you'll do better if you explain that there are many notions of size, and that the one he is using is indeed one of them, and then get him to think about some of the others and whether his is really the best notion of size, or whether the others also make sense, and may even better match his expectations for how "size" should behave.

The reason why mathematicians generally think of cardinality as "size" and not the others, is that cardinality lets you compare any two sets. The other notions can only be used to compare sets that live in the same ambient space, or have extra structure (like metric spaces). Ask your friend which is bigger, the set of all natural numbers, or the set of all binary strings that start with 1. Point out there's a natural translation from numbers to binary strings, and back, and use that as evidence for them having the same size. In some ways, we're keeping the same set, just renaming/reinterpreting the elements. But the same works for decimal as well. So you've shown your friend that a part can be as big as a whole, using properties of "size" that he should respect.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Parralelex
Posts: 74
Joined: Sun Dec 02, 2012 8:10 am UTC
Location: Location Location

Re: How to convince a friend the equivalence of infinite set

Postby Parralelex » Sun Jul 28, 2013 7:11 pm UTC

The fault with his reasoning is he's not talking about equivalence of infinite sets, but equivalences of areas, which has nothing to do with the problem.
I put the "fun" in "mathematics".

And then I took it back out.

User avatar
MartianInvader
Posts: 808
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: How to convince a friend the equivalence of infinite set

Postby MartianInvader » Sun Jul 28, 2013 8:18 pm UTC

There's a very reasonable definition of "the same size" under which the areas beneath [imath]y=x[/imath] and [imath]y=2x[/imath] are the same size.

There's also a very reasonable definition of "the same size" under which the areas beneath [imath]y=x[/imath] and [imath]y=2x[/imath] are not the same size.

The real trick here is that you're arguing about a fuzzy, non-math term and essentially just applying different definitions to it. If he wants to consider "the same size" to mean the difference of the integrals approaches zero, or the ratio approaches one, let him. Its far more interesting to explore how these definitions relate to each other and what their consequences are than to argue over which is the "right" one.
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

User avatar
dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

Re: How to convince a friend the equivalence of infinite set

Postby dudiobugtron » Sun Jul 28, 2013 8:20 pm UTC

I think your friend understands bijections; however, the argument above used for finite sets actually has you create an injection (or surjection), and see if anything is left over. It's easy to get 'stuff left over' by creating an injection between two countably infinite sets, so your friend thinks the existence of a bijection shouldn't imply that they are the same size, any more than the existance of an injection should imply one is bigger than the other.

I think the real problem is that your friend thinks that the eyeballing the area is a good way to compare the two sets. My suggestion is that you show him an argument which 'shows' that the area under x is equal to or greater than the area under 2x. If he genuinely accepts that both areas are infinite, this should be possible to do.

Parralelex wrote:The fault with his reasoning is he's not talking about equivalence of infinite sets, but equivalences of areas, which has nothing to do with the problem.

Are you suggesting the areas are actually 'different sizes'? And that 'areas' aren't sets?
Surely both areas in question are infinite sets, and have the same cardinality.

-----
EDIT: Ninjaed by MartianInvader! :)
Image

Parralelex
Posts: 74
Joined: Sun Dec 02, 2012 8:10 am UTC
Location: Location Location

Re: How to convince a friend the equivalence of infinite set

Postby Parralelex » Sun Jul 28, 2013 8:41 pm UTC

dudiobugtron wrote:I think your friend understands bijections; however, the argument above used for finite sets actually has you create an injection (or surjection), and see if anything is left over. It's easy to get 'stuff left over' by creating an injection between two countably infinite sets, so your friend thinks the existence of a bijection shouldn't imply that they are the same size, any more than the existance of an injection should imply one is bigger than the other.

I think the real problem is that your friend thinks that the eyeballing the area is a good way to compare the two sets. My suggestion is that you show him an argument which 'shows' that the area under x is equal to or greater than the area under 2x. If he genuinely accepts that both areas are infinite, this should be possible to do.

Parralelex wrote:The fault with his reasoning is he's not talking about equivalence of infinite sets, but equivalences of areas, which has nothing to do with the problem.

Are you suggesting the areas are actually 'different sizes'? And that 'areas' aren't sets?
Surely both areas in question are infinite sets, and have the same cardinality.

-----
EDIT: Ninjaed by MartianInvader! :)


Here's the thing. I was actually going to argue that they were the same size, thusly:

Consider two functions, f(x) and g(x). f(x) is equal to 2x if x is between 0 and a, and 0 otherwise, for some chosen a. g(x) is equal to x if x is between 0 and sqrt(2)*a and 0 otherwise, for the same a. Both functions have the same area for any a. If you extend a to infinity, you get the two functions op's friend was talking about, and they have the same area.

The problem is he could argue that g(x) was extended to a "bigger" infinity, just as he argued it had a bigger area.
I put the "fun" in "mathematics".

And then I took it back out.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: How to convince a friend the equivalence of infinite set

Postby skeptical scientist » Sun Jul 28, 2013 8:44 pm UTC

Let's go back to the first example. Does your friend believe the region A = {(x,y) : 0 ≤ y ≤ x} is twice as big as the region B = {(x,y) : 0 ≤ y ≤ x/2}? Does your friend also believe that the area should stay the same under a rotation? Tell your friend to rotate both regions so that the x-axis cuts them in the middle. Then the rotated version of A is A' = {(x,y) : -.414x ≤ y ≤ .414x}, and the rotated version of B is B' = {(x,y) : -.236x ≤ y ≤ .236x}. The same logic then tells us that A' is only 75% larger than B'. This is another issue with the notion of "size" your friend is using.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

lalop
Posts: 210
Joined: Mon May 23, 2011 5:29 pm UTC

Re: How to convince a friend the equivalence of infinite set

Postby lalop » Sun Jul 28, 2013 9:14 pm UTC

Oh yeah. You can totally blow his mind. First, get him to agree that areas are preserved under rotation, translation.

Get him to agree that the area under y=x (0 < x,0<y) is smaller than the area (-1 < x,-1<y). Then do a simple translation to show that they are, in fact, the same area.


Elaborating on this, show that the area under y=1/2x is, in fact, "greater" than the area under y=x, by the following procedure:

  1. Note that the area under y = 1/2x, y > 1 is the same as the area under y = 1/2x, by a similar translation.
  2. In this manner, we've have leftover:
    1. A small triangle of area 1
    2. An "infinite rectangle" of height 1
  3. We use the infinite rectangle to fill in the area between y=x and y=1/2x, as follows. For every area difference between x = n,n+1, have him agree that that area difference will eventually be covered if we go right far enough down the "infinite rectangle". Better yet, find a formula for how far we need to go right.
  4. Thus, the area underneath y=1/2x is the "same as" the area underneath y=x, plus a triangle of area 1!

Finally, tell him about the Banach-Tarski paradox. That's right, the area of a sphere is equal to the area of two spheres.

Afterwards, you should also explain why his original assumption was problematic, but that's beyond the scope of this post.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: How to convince a friend the equivalence of infinite set

Postby Qaanol » Mon Jul 29, 2013 1:21 am UTC

Does your friend know about Hilbert’s hotel?

Because seriously, that is one of the best known ways to get people to understand basic properties of countable infinite.

Every room has a guest in it. Another guest arrives. So the existing guests each move to the next room, leaving room 1 empty. The new guest goes into room 1, and again every room has a guest in it.

Hilbert’s bus arrives, with countably-many seats and a person in each. The hotel guests each move to the room with double their number of their current room, so they all fit in the even-numbered rooms. The passengers on the bus each move to 2n+1, so they end up in the odd seats on the bus. Then the bus passengers go to the room with the same number as their seat.

Hilbert’s parking lot has countably-many spaces. A bus pulls into each spot, each with countably-many passengers. So the hotel guests each move to room 2ⁿ, the passengers on bus i each move to seat pᵢⁿ where pᵢ is the i’th odd prime. Then everyone from every bus goes to the room matching their seat number. So all the prime-power rooms have a guest, and all the rooms with multiple primes in their factorizations are empty (room 1 is also empty.)

Once your friend understands Hilbert’s hotel, then maybe move onto continuous sets.
wee free kings

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: How to convince a friend the equivalence of infinite set

Postby Xanthir » Mon Jul 29, 2013 7:06 am UTC

sparkyb wrote:
My friend wrote:That's the traditional argument used for number sets, but the fact is also that while you can match an even number with a non-even number, you can also fit all the odd numbers in between for the full set while you can't with just the even number set.

The real difference shows when you look at areas like in the x=y example. And yes, each point of infinity can be matched with another point of infinity, but the fact of the matter is that at any given value, the area under x=y is more than twice as great as the area under x=2y. ... Greater and lesser infinities.


I know his reasoning is faulty, but I'm not sure what the counterargument is. Anyone know?

dudiobugtron hit the right answer - your friend is familiar with normal logical arguments, where finding a single counter-example is sufficient to disprove something, and is naively attempting to apply it to this. He assumes that finding *an* assignment between the two sets where there's some left over in one means they can't be equal.

He needs to understand that infinite sets can always be paired to have one of them with leftovers, but when they're the same size, you can choose a pairing appropriately so that *either* set gets the leftovers. If you assume that the existence of leftovers means that that set is larger, then this shows that they're both larger than each other, a contradiction. In reality, the existence of leftovers shows that that set is greater than or equal in size, and if you can show they're both gte than the other, then the only possibility is that they're equal.

It's really simple to construct examples of this. One simple one is mapping the positive numbers to the full set of integers. By the simplest naive argument, the integers are twice the size - just pair up equal numbers in each set, and you only use up "half" the integers by the time you're done. But you can also do a simple mapping, where positive integers map to 4n in the positive numbers, and negative integers map to -4n-2 in the positive numbers. You use up every integer, pairing it with a unique positive number, but haven't touched any of the odd numbers, so you've only used up "half" of the positives!

My favorite is an easy proof of integer/rational size. Every integer maps to a rational trivially - just map it to the rational with the same numerator and a denominator of 1. Infinite amount of leftover rationals. To map rationals to integers, write out the digits of the numerator, a slash, then the digits of the denominator. Interpret this as a base-11 number, with the slash being the digit with value 10. This obviously maps every rational to a unique integer (if two different fractions mapped to the same int, it would mean they have the same numerator digits and the same denominator digits, which contradicts the assertion they were different fractions), and it obviously leaves an infinite number of integers as leftovers (you only claim base-11 numbers with exactly 1 "/" digit, all the rest are unmatched.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

Re: How to convince a friend the equivalence of infinite set

Postby dudiobugtron » Mon Jul 29, 2013 7:20 am UTC

That map isn't actually a bijection, since it maps the same rational to different integers depending on the representation you use. (eg: half maps to 1/2 and 2/4 and 3/6 etc...)

If you choose the representation with no common factors between the numerator and denominator then you're good to go. Which, of course, you already knew, but I thought for some reason it should be pointed out anyway. :)
Image

lalop
Posts: 210
Joined: Mon May 23, 2011 5:29 pm UTC

Re: How to convince a friend the equivalence of infinite set

Postby lalop » Mon Jul 29, 2013 9:17 am UTC

It's not a bijection even then, only an injection since numbers like 4A2 or 4A0 aren't hit. It's nontrivial that two injections lead to a bijection.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1448
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: How to convince a friend the equivalence of infinite set

Postby Xenomortis » Mon Jul 29, 2013 9:30 am UTC

lalop wrote:It's nontrivial that two injections lead to a bijection.

The notion is intuitive though; you've shown a way both sets "fit into each other".
The rest is merely a formality (a formality rejected, ironically, by intuitionists).
Image

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: How to convince a friend the equivalence of infinite set

Postby Xanthir » Mon Jul 29, 2013 3:00 pm UTC

dudiobugtron wrote:That map isn't actually a bijection, since it maps the same rational to different integers depending on the representation you use. (eg: half maps to 1/2 and 2/4 and 3/6 etc...)

If you choose the representation with no common factors between the numerator and denominator then you're good to go. Which, of course, you already knew, but I thought for some reason it should be pointed out anyway. :)

Yes, assume that the rationals are in reduced form when you do the printing out. It is a necessary detail.

lalop wrote:It's not a bijection even then, only an injection since numbers like 4A2 or 4A0 aren't hit. It's nontrivial that two injections lead to a bijection.

An injection from A to B automatically implies that size(B) >= size(A) (and this is intuitive, so it doesn't demand a rigorous proof to be convincing). Run an injection both ways, and then simple logic leads you to the fact that there must be *a* bijection of some kind.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: How to convince a friend the equivalence of infinite set

Postby Cauchy » Mon Jul 29, 2013 4:48 pm UTC

It would seem to me that the fastest way to undo the "leftovers implies strictly smaller" notion is to exhibit an injection with leftovers from an infinite set to itself. The standard example would be to take the natural numbers and map n to n+1, so that 0 is left over.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

fishfry
Posts: 135
Joined: Wed Dec 21, 2011 6:25 am UTC

Re: How to convince a friend the equivalence of infinite set

Postby fishfry » Mon Jul 29, 2013 11:13 pm UTC

If the question is how best to explain all this to someone, I would mention to someone that this is called Galileo's paradox. Galileo noticed in the year 1638 that the set of natural numbers 1, 2, 3, ... can be put into 1-1 correspondence with the set of square numbers 1, 4, 9, ... Today we understand that an infinite set is by definition a set that can be put into one-one correspondence with a proper (= smaller) subset of itself.

http://en.wikipedia.org/wiki/Galileo's_paradox

Not only does that impart a bit of the history of the subject; but it's also a subtle appeal to authority. Rather than the student trying to figure it all out for themselves and go down unproductive roads of incorrect visualizations; instead we put the subject in the context of something that smart people thought about hundreds of years ago ... so this is something to be learned, not something to be figured out on your own and argued about.

The cognitive leap in understanding mathematical infinity is to stop trying to figure it out, and just pay attention to the technical terms. "One-to-one correspondence,", "proper subset," and so forth. You have to completely forget your attachment to your vague ideas about the cosmic infinity of the universe; and realize that we're using our words in a very precise way. And that we're doing math, not physics or philosophy.

When you're explaining mathematical infinity to someone, you have to get them to forget their muddled ideas about infinity and just pay attention to the definitions. People instinctively want to make up philosophical woo-woo about their idea of infinity and then argue with you. But instead if you can contextualize the subject as a branch of learning that's been thought of by people before, then you have a chance that the listener will transition into a properly receptive frame of mind.

I think that mentioning Galileo is one way to do that. The game becomes, "Let me tell you about what mathematicians have been doing with this problem since the 17th century," as opposed to "Let's argue about your misunderstandings."

In other words it's mostly a psychological problem. Contextualizing the problem historically can be helpful; as can explaining that we are not talking about the cosmic, metaphysical infinity. We're just understanding how mathematicians have come to think of infinity since the time of Galileo.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: How to convince a friend the equivalence of infinite set

Postby Qaanol » Tue Jul 30, 2013 1:01 am UTC

fishfry wrote:Today we understand that an infinite set is by definition a set that can be put into one-one correspondence with a proper (= smaller) subset of itself.

That is not, to be precise, what is known as “true”.

An infinite set is by definition a set that cannot be put in one-to-one correspondence with any set of natural number of the form {1, 2, …, n} (with appropriate specifications on n being a successor of 0 in unbroken chain.)

What you are referring to is Dedekind-infinite. It is straight-forward to show that every Dedekind-infinite set has a countably-infinite subset, and hence is infinite. And of course, any set with a countably-infinite subset is easily shown to be Dedekind-infinite.

But for an arbitrary infinite set, to show it is Dedekind-infinite would require another axiom, such as one to the effect that “Every infinite set has a countably-infinite subset.” This is a very weak axiom, weaker even than the axiom of countable choice (which is itself weaker than the axiom of dependent choice, and that is still weaker than the full-fledged axiom of choice) but it, or something like it, is nonetheless required. Plain-vanilla ZF set theory leaves open the possibility of an infinite set which does not have a countably-infinite subset.
wee free kings

User avatar
dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

Re: How to convince a friend the equivalence of infinite set

Postby dudiobugtron » Tue Jul 30, 2013 1:33 am UTC

Qaanol wrote:Plain-vanilla ZF set theory leaves open the possibility of an infinite set which does not have a countably-infinite subset.

This is one of those situations where someone might post "mind = blown". I can't even begin to understand how such a set would work, given my ingrained notions about infinity and the natural numbers. Thanks for the 'awakening'!
Image

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: How to convince a friend the equivalence of infinite set

Postby skeptical scientist » Tue Jul 30, 2013 2:23 am UTC

Xanthir wrote:Run an injection both ways, and then simple logic leads you to the fact that there must be *a* bijection of some kind.

What simple logic? It is somewhat tricky to actually construct a bijection here. You seem to be implicitly assuming that sizes of infinite sets are totally ordered, but this is by no means obvious. Indeed, without choice, it may even be false!
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: How to convince a friend the equivalence of infinite set

Postby Qaanol » Tue Jul 30, 2013 2:31 am UTC

skeptical scientist wrote:
Xanthir wrote:Run an injection both ways, and then simple logic leads you to the fact that there must be *a* bijection of some kind.

What simple logic? It is somewhat tricky to actually construct a bijection here. You seem to be implicitly assuming that sizes of infinite sets are totally ordered, but this is by no means obvious. Indeed, without choice, it may even be false!

I think the proof-by-directed-graph is pretty nice, personally.
wee free kings

User avatar
phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: How to convince a friend the equivalence of infinite set

Postby phlip » Tue Jul 30, 2013 2:51 am UTC

dudiobugtron wrote:
Qaanol wrote:Plain-vanilla ZF set theory leaves open the possibility of an infinite set which does not have a countably-infinite subset.

This is one of those situations where someone might post "mind = blown". I can't even begin to understand how such a set would work, given my ingrained notions about infinity and the natural numbers. Thanks for the 'awakening'!

I seem to remember a page on Wikipedia that listed about half a dozen different definitions of "infinite set", including the basic "cardinality is not a natural number" and Dedekind-infinite, and explained that under ZFC they're all equivalent, but in plain ZF, each one implies the next, but not necessarily vice-versa. I can't find where the page was, though... the section may have been removed.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: How to convince a friend the equivalence of infinite set

Postby Xanthir » Tue Jul 30, 2013 6:23 am UTC

skeptical scientist wrote:
Xanthir wrote:Run an injection both ways, and then simple logic leads you to the fact that there must be *a* bijection of some kind.

What simple logic? It is somewhat tricky to actually construct a bijection here. You seem to be implicitly assuming that sizes of infinite sets are totally ordered, but this is by no means obvious. Indeed, without choice, it may even be false!

Yes, I am assuming that, but that's reasonable at the level being discussed. Further, as Qaanol noted, there's a neat and easy-to-understand construction for the bijection from two injections.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Xenomortis
Not actually a special flower.
Posts: 1448
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: How to convince a friend the equivalence of infinite set

Postby Xenomortis » Tue Jul 30, 2013 8:40 am UTC

dudiobugtron wrote:
Qaanol wrote:Plain-vanilla ZF set theory leaves open the possibility of an infinite set which does not have a countably-infinite subset.

This is one of those situations where someone might post "mind = blown". I can't even begin to understand how such a set would work, given my ingrained notions about infinity and the natural numbers. Thanks for the 'awakening'!


Yes, it's consistent with ZF that there exists a Dedekind-Finite set that is infinite in the usual sense.
The two notions are equivalent in ZFC, as a result of Well Ordering*. (in ZF, any well-ordered infinite set is Dedekind-infinite).
Countable choice is required to say that Aleph-Null is the smallest infinite cardinal.
But I have no idea how one would go about constructing a set that breaks all this, and what is required to do so.

And people say Choice leads to unintuitive results.

*Actually, you don't need full AC.

philip wrote:I seem to remember a page on Wikipedia that listed about half a dozen different definitions of "infinite set", including the basic "cardinality is not a natural number" and Dedekind-infinite, and explained that under ZFC they're all equivalent, but in plain ZF, each one implies the next, but not necessarily vice-versa. I can't find where the page was, though... the section may have been removed.

There's something similar on the Finite set page.
Image

lalop
Posts: 210
Joined: Mon May 23, 2011 5:29 pm UTC

Re: How to convince a friend the equivalence of infinite set

Postby lalop » Tue Jul 30, 2013 8:58 am UTC

Xenomortis wrote:But I have no idea how one would go about constructing a set that breaks all this, and what is required to do so.


From the finite set wiki:

when the axiom of choice fails badly, one may have an infinite family of socks with no way to choose one sock from more than finitely many of the pairs. That would make the set of such socks Dedekind finite: there can be no infinite sequence of socks, because such a sequence would allow a choice of one sock for infinitely many pairs by choosing the first sock in the sequence.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1448
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: How to convince a friend the equivalence of infinite set

Postby Xenomortis » Tue Jul 30, 2013 9:08 am UTC

So it simply requires the assertion that there exists an infinite set that does not permit a choice function?
(i.e. ¬C)
Image

lalop
Posts: 210
Joined: Mon May 23, 2011 5:29 pm UTC

Re: How to convince a friend the equivalence of infinite set

Postby lalop » Tue Jul 30, 2013 9:34 am UTC

The relevant characterization is an infinite set that admits no countably infinite subset. In the above example, such a subset is not possible because it would act as a choice function (via the natural numbers' well-ordering) on an infinite subset of that family.

As far as I best understand, that involves constructing a model of ZF wherein such a strict family exists: there is no choice function on any infinite subset.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: How to convince a friend the equivalence of infinite set

Postby skeptical scientist » Tue Jul 30, 2013 2:43 pm UTC

Xenomortis wrote:So it simply requires the assertion that there exists an infinite set that does not permit a choice function?
(i.e. ¬C)

No. Countable choice is sufficient to imply that every infinite set is Dedekind-infinite, and ZF+CC+¬C is consistent. The existence of an infinite set, no infinite subset of which permits a choice function, is a sufficient condition for the existence of an infinite set which is Dedekind-finite.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
Xenomortis
Not actually a special flower.
Posts: 1448
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: How to convince a friend the equivalence of infinite set

Postby Xenomortis » Tue Jul 30, 2013 2:57 pm UTC

Helps if I remember something I wrote minutes earlier.
Image


Return to “Mathematics”

Who is online

Users browsing this forum: Google [Bot] and 9 guests