Let X be a set. A partition of X is a subset

  • Thread starter Thread starter laminatedevildoll
  • Start date Start date
  • Tags Tags
    Partition Set
AI Thread Summary
A partition of a set X is defined as a subset π of the power set P(X) such that each element x in X belongs to exactly one subset A in π. An equivalence relation R on X generates a partition π_R, consisting of the equivalence classes R(x) for each x in X. The relation R_π, formed from the union of pairs in each subset A of π, is proven to be an equivalence relation by demonstrating reflexivity, symmetry, and transitivity. To complete the proof, it is necessary to show that π_(R_π) equals π and R_(π_R) equals R. The discussion emphasizes the importance of verifying the properties of equivalence relations and the conditions for proving these statements.
laminatedevildoll
Messages
211
Reaction score
0
Let X be a set. A partition of X is a subset \pi \subseteq P(X) so

that for every x \in X there is precisely one A \in \pi so

that x\in A. If R is an equivalence relation on X, then

\pi_R = {R(x): x \in X}is a partition.

If \pi is partition of X then

R_\pi= \bigcup A x A is an equivalence

relation, where

A\in \pi Furthermore,

\pi_(R_\pi)=\pi where \pi_(R_\pi) (pi sub R sub pi)

R_(\pi_R)= R

To prove this theorem, I have started out by proving that R_\pi is

an equivalence relation, for reflexitivity, symmetry, and transitivity. In order

to complete the proof, do I need to prove \pi_(R_\pi)=\pi

R_(\pi_R)= R

Do I do that by using the following conditions?

1. x \in R(X) for each x \in X

2. If y \in R(x), then x \in R(y)

3. If R(x) \cap R(y) \noteq \empty, then R(x)= R(y)
 
Last edited:
Physics news on Phys.org
Your two statements (which are two be proved) can be interpreted as,
1. Given that R is an equivalence relation, show that the collection of relative sets R(x) form a partition
2. Given that P(pi) is a partition, show that the above described relation is an equivalence relation.

So yes, i guess you need to show these statements as true.
The conditions you want to use will be useful but just remember the three properties of equivalence relation and use whatever you can accordingly.

-- AI
 
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...
Back
Top