Isomorphism between finite sets

  • Thread starter pivoxa15
  • Start date
  • #1
2,255
1
In general if two finite sets contain exactly the same number of unique elements than the two sets are isomorphic to each other. Is this correct?

An isomorphism => both 1-1 and onto. If two sets both have an equal number of unique elements than they must be onto because every element in one set is mappped to the other with none left. It is 1-1 because each unique element in one set maps to another unique element (that hasen't already been mapped).
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
In general if two finite sets contain exactly the same number of unique elements than the two sets are isomorphic to each other. Is this correct?
This is correct. And you're being redundant with the word "unique": the set {2, 2} has one element.

Your proof has the right idea, I think, but you need to work on its execution. Unfortunately I have to leave for work, but hopefully someone will explain in the meanwhile.
 
  • #3
matt grime
Science Advisor
Homework Helper
9,395
3
An isomorphism => both 1-1 and onto. If two sets both have an equal number of unique elements than they must be onto
'They'? Sets are not onto, a map is onto (or not).

because every element in one set is mappped to the other with none left. It is 1-1 because each unique element in one set maps to another unique element (that hasen't already been mapped).
What mapping? You're talking as if there is only one map (whatever the 'it' refers to in your sentence) between any two sets.


Firstly, what does it mean for a finite set to have n elements? It means that it is in bijection with the set {1,2,3..,n}. So the question is trivial by the definition of 'has n elements' and the transitivity of the relation 'are isomorphic'.
 
  • #4
2,255
1
'They'? Sets are not onto, a map is onto (or not).



What mapping? You're talking as if there is only one map (whatever the 'it' refers to in your sentence) between any two sets.


Firstly, what does it mean for a finite set to have n elements? It means that it is in bijection with the set {1,2,3..,n}. So the question is trivial by the definition of 'has n elements' and the transitivity of the relation 'are isomorphic'.
Interesting reply. I didn't know the definition of a finite set to have n elements is for there to exist a function that is a bijection with the set {1,2,3,..,n}.
 
  • #5
HallsofIvy
Science Advisor
Homework Helper
41,833
961
You never learned to count?:rolleyes:
 
  • #6
2,255
1
I guess I never learned to count formly, only intuitively.
 
  • #7
2,255
1
This is correct. And you're being redundant with the word "unique": the set {2, 2} has one element.

Your proof has the right idea, I think, but you need to work on its execution. Unfortunately I have to leave for work, but hopefully someone will explain in the meanwhile.
But what happens if sometimes you want a set to contain {2,2} such as in sampling and 2 people both donate 2 apples. So double 2 is significant and {2} would be incorrect in this case.

By the way, I would not use the word "isomorphic" with sets- I would say "equivalent". Isomorphic, to me, implies algebraic structure.
 
Last edited by a moderator:
  • #8
HallsofIvy
Science Advisor
Homework Helper
41,833
961
But what happens if sometimes you want a set to contain {2,2} such as in sampling and 2 people both donate 2 apples. So double 2 is significant and {2} would be incorrect in this case.
Then you are not talking about "sets". I don't know that there is a standard mathematical term ("multi-set"?) for such a thing but C programming calls them "bags"!
 
  • #9
matt grime
Science Advisor
Homework Helper
9,395
3
But what happens if sometimes you want a set to contain {2,2}
then you're completly abusing the definition of a set. So stop doing so and obey the rules.

by tthe way, I would not use the word "isomorphic" with sets- I would say "equivalent". Isomorphic, to me, implies algebraic structure.
then'y you are sadly mistaken, again. Sets are isomorphic precisely when they contain the same number of elements. This is a trivial consequence of the definitions of set, isomorphism and 'same number of elements'.
 
  • #10
HallsofIvy
Science Advisor
Homework Helper
41,833
961
matt, those are quotes from two different people. (So I'm not sure the word "again" applies here. Certainly, I have been "sadly mistaken" many times in the past but I think there's only one real howler on my part here!)

I will assert again that I had never seen the word "isomorphism" applied to "raw" sets without any other structure. I will concede that the general definition of isomorphism, an invertible function that preserves the algebraic structure, would still apply when there is NO algebraic structure to preserve!
 
  • #11
matt grime
Science Advisor
Homework Helper
9,395
3
They are not from two different people. They are from one person, and even from the same post, post 7. And not from you.

And you have seen the word isomorphism applied just to sets - the category SET. An isomorphism is precisely a bijection.
 
Last edited:
  • #12
2,255
1
matt, those are quotes from two different people. (So I'm not sure the word "again" applies here. Certainly, I have been "sadly mistaken" many times in the past but I think there's only one real howler on my part here!)

I will assert again that I had never seen the word "isomorphism" applied to "raw" sets without any other structure. I will concede that the general definition of isomorphism, an invertible function that preserves the algebraic structure, would still apply when there is NO algebraic structure to preserve!
They are not from two different people. They are from one person, and even from the same post, post 7. And not from you.

And you have seen the word isomorphism applied just to sets - the category SET. An isomorphism is precisely a bijection.

Funny because I clearly don't remember typing this "By the way, I would not use the word "isomorphic" with sets- I would say "equivalent". Isomorphic, to me, implies algebraic structure." It dosen't sound like me and definitely not in front of people like Matt and the mentors.
 
  • #13
matt grime
Science Advisor
Homework Helper
9,395
3
It appears in post 7 and nowhere before, so it can't be a quotation error (you know, when you quote a post, but get the [ quote ] and [/ quote] tags in the wrong place.

Hmm. But look at post 7 again. It says last edited by Halls of Ivy at... on the top. Why is Halls editing pixova's post? Very odd.
 
  • #14
HallsofIvy
Science Advisor
Homework Helper
41,833
961
They are not from two different people. They are from one person, and even from the same post, post 7. And not from you.
Odd, I was absolutely certain that I had made the remark about "isomorphism" applying only to sets with an algebraic structure.

And you have seen the word isomorphism applied just to sets - the category SET. An isomorphism is precisely a bijection.
Oh, you're talking about category theory! Never touch it! When I took my one course in it, the author of the textbook noted that category theory was also called "abstract nonsense"!
 
  • #15
HallsofIvy
Science Advisor
Homework Helper
41,833
961
Ah, I know what happened now! They let us "mentors" edit other people's posts (doesn't that raise your hackles!). I hit the 'edit' button instead of 'quote' without realizing it. The last paragraph was mine and was supposed to be added to a quote.
 
  • #16
matt grime
Science Advisor
Homework Helper
9,395
3
Oh, you're talking about category theory! Never touch it! When I took my one course in it, the author of the textbook noted that category theory was also called "abstract nonsense"!
Category theory is the theoretical underpinning of modern mathematics almost precisely because it is abstract nonsense. It is not an insult. It frequently gets to the real reason why things are true rather than relying unnecessarily on the ambient area in which you're reasoning.

Anyway, an isomrphism is an invertible morphism. In set that is a bijection. A monomorphism is a map with the left cancellation property, which in SET means injection. An epimorphism is a map with the right cancellation property, and that means surjection in SET. But not in RING. An epimorphism need not be surjective in RING. The canonical example is the inclusion of Z in Q. Any ring hom out of Q is completely determined by the image of Z in Q. Thus the inclusion is a non-surjective epimorphism.
 

Related Threads on Isomorphism between finite sets

  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
3
Views
3K
Replies
1
Views
438
Replies
1
Views
1K
Replies
8
Views
3K
  • Last Post
Replies
3
Views
1K
Replies
17
Views
6K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
8
Views
2K
Top