Quotient set of an equivalence relation

AI Thread Summary
The discussion focuses on defining an equivalence relation on the set of integers Z, where m is related to n if m - n is divisible by a fixed integer k. The goal is to demonstrate that the quotient set under this relation consists of the equivalence classes {[0], [1], ..., [k-1]}. Clarifications were made regarding the notation and the nature of equivalence classes, emphasizing that these classes represent integers that share a common remainder when divided by k. Examples were provided to illustrate how each equivalence class can be expressed in terms of multiples of k. The conclusion reinforces that the quotient set accurately reflects the defined equivalence relation.
Luna=Luna
Messages
16
Reaction score
0
On the set of Z of integers define a relation by writing m \triangleright n for m, n \in Z.

m\trianglerightn if m-n is divisble by k, where k is a fixed integer.

Show that the quotient set under this equivalence relation is:

Z/\triangleright = {[0], [1], ... [k-1]}

I'm a bit new the subject of Set Theory so I'm a bit unsure as to how to go about solving this.
 
Last edited:
Physics news on Phys.org
Luna=Luna said:
On the set of Z of integers define a relation by writing m \triangleright n for m, n \in Z.

If m-n is divisble by k, where k is a fixed integer then show that the quotient set under this equivalence relation is:

Z/\triangleright = {[0], [1], ... [k-1]}

I'm a bit new the subject of Set Theory so I'm a bit unsure as to how to go about solving this.
\triangleright seems to be undefined. You say it is a relationship without saying what it is.
 
sorry it wasn't clear from my post, I've rewritten the post to be a bit more clear.

The relationship is:
m\trianglerightn, if m-n is divisble by k, where k is a fixed integer.
 
But you also haven't said what "[1]", "[2]", ... "[k]" are. Of course, they are the equivalence classes but unless your question is "why are there k classes" rather than "why are the classes what they are", you need to specify "what they are"! Essentially what you wrote was that you want to prove that the "quotient set" is the "set of equivalence classes" which is basically the definition of "quotient set"!
(Similar to writing "Luna= Luna"!)

Start with k= 1. All numbers in the same equivalence class with it ([1]) are numbers n such that n- 1 is divisible by k. That is the same as saying "n- 1= mk" for some m or n= mk+ 1. That is, all numbers that are 1 more than a multiple of k: [1]= {..., -2k+ 1, -k+ 1, 1, k+ 1, 2k+ 1, ...}. Similarly, [2]= {..., -2k+ 2, -k+ 2, 2, k+ 2, 2k+ 2, ...}. You can do that until you get to [k]= {..., -2k, -k, 0, k, 2k, ...} which is the same as [0]. If we try to do the same thing with k+ 1, we get [k+1]= {..., -2k+ (k+1), -k+ (k+1), k+ 1, k+ (k+ 1), 2k+ (k+ 1), ...}= {..., -k+ 1, 1, k+ 1, 2k+ 1, 3k+ 1, ...} which is exactly the same as [1].
 
  • Like
Likes 1 person
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

Similar threads

Back
Top