2

I was told that if we want to prove a definition is well defined, usually what we should do is to prove the existence and uniqueness of the definition. For the question below, what we should do is to prove the intersection is nonempty, and if there are more than one result of the definition, they must contain the same elements, so finally they are the same set. But I am confused by the first hint, and can't figure out a solution with the help of the second. Example I read here are usually about topology. And my question are: (1) is the first hint problematic? (2) can I emulate the idea in this answer? Topology, closure definition - well defined?

Problem: Let $R$ be a binary relation on $W$. We used to defined the reflexive closure of $R$ to be $R \cup \{(u,u)|u\in W\}$. But we can also define it as

$$R^r = \bigcap\{R' \mid R' \; \text{is a reflexive binary relation on} \; W \land R \subseteq R'\}$$

Explain why this new definition is well defined.

PrincessEev
  • 43,815
  • 1
    This is a strict definition, using aspects of set theory that are already well-defined. Given a set $W$ and an $R\subseteq W\times W,$ you can, by set theory, create a unique subset of $\mathcal P(W\times W)$ of all the $R'.$ Then you need to know that the intersection of any non-empty collection of reflexive relationships on $W$ is a reflexive relation on $W.$ – Thomas Andrews Mar 28 '19 at 18:36
  • Thank you very much! ^-^ – Alexandra Mar 29 '19 at 06:26

1 Answers1

1

Let $S$ be the set of reflexive binary relations on $W$ that have $R$ as a subset. This uniquely defines $S$ as a specific set of subsets of $W\times W.$

Now $S\ne \emptyset$ because $W\times W\in S.$

If $u\in W$ and $R'\in S$ then $(u,u) \in R',$ so $R'\supset \{(u,u):u\in W\},$ and also $R'\supset R.$

So $\forall R'\in S\,(\,R'\supset R\cup \{(u,u):u\in W\}\,).$ And since $S$ is not empty, this implies $$\cap S\supset R\cup \{(u,u):u\in W\}.$$ Now prove that $R\cup\{(u,u):u\in W\}\in S,$ so $$\cap S\subset R\cup \{(u,u):u\in W\}.$$

BTW. You often see the phrase "generated by". The sentence "$A$ is the widget generated by $B$" means (i) $A$ is a widget and $A\supset B$ and (ii) If $A'$ is a widget and $A'\supset B$ then $A'\supset A.$ (It is implicit that for $A$ to exist it is necessary that some widget $A'$ satisfies $A'\supset B.$)

  • Another example: Let $T$ be a topology on a set $X$. For any $B\subset X,$ define $\overline B={p\in X: \forall U\in T,(,p\in U\implies U\cap B \ne \emptyset ,)}.$ Then we have $ \overline B=\cap {C\subset X: (B\subset C\land X\setminus C\in T}.$ That is, $\overline B$ is equal to the intersection of all the closed sets that have $B$ as a subset. – DanielWainfleet Apr 03 '19 at 19:04