In set theory, what does it mean for a set to be transitive, and what does it have to do with transitivity of a relation?
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ Transitive set is related to transitivity of the membership ($\in$) relation (that, of course, is a relation "from outside" on the universe of sets). $\endgroup$– Mauro ALLEGRANZAMar 21, 2017 at 16:44
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
A set $X$ is transitive means that $Y \in X$ implies $Y \subset X$. In other words, a set $X$ is transitive whenever $Y \in X$ and $Z \in Y$ implies $Z \in X$. Thus, the $\in$ relation is transitive in this case.
-
-
$\begingroup$ @fleablood that is true, thank you for your correction. Was unable to edit my comment since the 5-minute edit-window expired. You identified what I initially thought was "off" about the notation, in that the implication was wrong. Worth noting: another way of defining a transitive set $X$ is that every element of $X$ is also a subset of $X$ (as the implication $Y \in X \Rightarrow Y \subseteq X$ is equivalent to. $\endgroup$– hausdorkMar 21, 2017 at 17:13
-
$\begingroup$ Actualy I may have been wrong in my comment. $\endgroup$ Mar 21, 2017 at 17:21
$\begingroup$
$\endgroup$
2
From what I read on wikipedia
A transitive set is one in which inclusion "$\in$" is transitive.
So $A$ is transitive, if whenever for sets $X$ and $Y$ if $Y \in X$ and $X \in A$ then $Y \in A$.
This statement is equivalent to and can be restated as:
$A$ is transitive, if whenever the set $X \in A$, it follows that $X \subset A$.
Notice that this refers to elements that are sets, and not urelements (elements that are not sets).
.....
Also, I believe, I could be wrong, that if $A$ is transitive and $X \in A|X \subset A$, that $X$ need not be transitive. A counter example could be $X=${{1,{2,3}}, 1,{2,3},2,3}.
$X$ has two set elements, {1,{2,3}} and {2,3} which are both subsets of $X$. {2,3} is vacuously transitive as it has not set elements (only urelements). But {1,{2,3}} is not transitive as {2,3} $\in$ {1,{2,3}} but {2,3} $\not \subset$ {1,{2,3}}.
I'd appreciate it if someone would correct me if I am wrong and if the definition of transitive would require $X \in A$ be that $X$ is also transitive. (And if so was wikipedia wrong?). So to make my set "regressively" transitive I'd need $X=$ {{1,{2,3},2,3},1,{2,3},2,3}.
$A$ is transitive if for any set $x$ that is an element of $A$ ($x \in A$) then $x \subset A$.
This impies that if $y \in x$, $x \in A$ and $y$ is a set, then $y \in A$. Hence the name "transitive". Inclusion is transitive.
-
$\begingroup$ Hmm, seems I'm correct. Subsets/elements of subsets of transitive sets need not be be transitive. If they are it is called "hereditarily" transitive sets. The ordinals in set theory are all hereditarily trasitive sets that have no urelements. $\endgroup$ Mar 21, 2017 at 17:52
-
1$\begingroup$ Hmm the first paragraph seems incorrect. The set $A=\{0,2,4\}$ is a set where "∈" is a transitive relation , but $A$ is not a transitive set, since $4$ is not a subset of $A$. Here $0,2,4$ are natural numbers defined as in Von Neumann ordinals, using the successor $S(a) = a ∪ \{a\} $, $0=∅, 2=S(S(∅)), 4=S(S(2))$. $\endgroup$– am70Apr 25, 2022 at 7:15