I had a similar question just now and it peaked my interest on binary relations. Solving i) &quot;Assuming R and S are reflexive so: Let x ∈ A.  Then (x, x) ∈ R and (x, x) ∈ S (reflexive property of R and S). R ∪ S would then be reflexive as well, since (x,x) ∈ R ∪ S.&quot; Does that make any sense? As in, is this correct to assume? How would one go about proving it for R ∩ S? If R ∩ S = (x,x) it'd also be reflexive, wouldn't it? What about the symmetry and transitivity of R ∩ S?
109455
I am reading  of the Book of Proof, and I'm stuck at the Exercise 10 of section 11.2. It is as follows.  Suppose $R$ and $S$ are two equivalence relations on a set $A$. Prove that $R \cap S$ is also an equivalence relation.  Thanks for helps!
118245
Is the solution correct for this?   Problem: Find necessary and sufficient conditions on sets $A$ and $B$ such that the following relation holds among the power sets: $P(A)\cup P(B) = P(A\cup B)$.  Answer: Suppose first that $A\nsubseteq B$ and $B\nsubseteq A$. Then there exists $a \in A \setminus B$ and $b \in B \setminus A$. The subset, {a,b} of $A \cup B$ is not a subset of $A$, nor is it a subset of $B$. Thus, we do not have equality.  Suppose that $A\subseteq B$, then $A \cup B = B$. So, $P(B) \subseteq P(A) \cup P(B)$ by the definition of power sets. Moreover, all subsets of $A$ are subset of $B$, thus you arrive to $P(A) \cup P(B) = P(A \cup B)$. It is the same if $B \subseteq A$.  Thus, the condition is that $A \subseteq B$ or $B\subseteq A.$
55029
Let $A,B$ be any two sets. I really think that the statement $|A|\leq|B|$ or $|B|\leq|A|$ is true. Formally:     $$\forall A\forall B[\,|A|\leq|B| \lor\ |B|\leq|A|\,]$$   If this statement is true, what is the proof ?
32422
I understand that why a partially ordered set needs to be antisymmetric and transitive. I just can't see the logic behind why it has to be reflexive?
114859
My book on set theory says     Prove that is a set $A$ is transitive, then $\mathcal{P}(A)$ is also transitive, where $\mathcal{P}(A)$ is the power set of $A$.   I don't know understand how. Let $A=\{a,b\}$. Clearly it is transitive. Now $\mathcal{P}(A)=\{\{a\},\{b\},\{a,b\},\emptyset\}$. This is clearly not transitive.
15730
This is a total noob question.  I am reading , and I'm having difficulty to understand something which seems to be trivial.  In the first chapter he writes:     If $x$ belongs to $A$ ($x$ is an element of $A$, $x$ is contained in $A$), we shall write      $x\in A$   I understand this.  Then, he write:     If $A$ and $B$ are sets and if every element of $A$ is an element of $B$, we say that $A$ is a subset of $B$, or $B$ includes $A$, and we write:      $A \subset B$   I understand this too.  Then he says:     The working of the definition implies that each set must be considered to be included in itself ($A \subset A$); this fact is described by saying that set inclusion is reflexive.   I understand this too.  But then:     Observe that belonging ($\in$) and inclusion ($\subset$) are conceptually very different things indeed. One important difference has already manifested itself above: inclusion is always reflexive, whereas it is not at all clear that belonging is ever reflexive. That is: $A \subset A$ is always true;  is $A\in A$ ever true? It is certainly not true of any reasonable set that anyone has ever seen.   And this is where I don't think I understand anything.  There is not more elaboration on this point in the text.  I tried to skip this but it seems it is quite fundamental for understanding what follows in the book.  Could someone explain what is meant here?
22626
Can you give an example of a relation that is symmetric and transitive, but not reflexive?   By definition,   $R$, a relation in a set $X$, is reflexive if and only if $\forall x\in X$, $x\,R\,x$.  $R$ is symmetric if and only if $\forall x, y\in X$,  $x\,R\,y\implies y\,R\,x$. $R$ is transitive if and only if $\forall x, y, z\in X$, $x\,R\,y\land y\,R\,z\implies x\,R\,z$.    I can give a relation $\leqslant$, in a set of real numbers, as an example of reflexive and transitive, but not symmetric. But I can't think of a relation that is symmetric and transitive, but not reflexive.
59185
I'm wrestling with the elementary implications of the Axiom of Regularity.  The axiom:  $∀A(A≠∅→(∃x∈A)(A∩x=∅))$  implies that every set A either has $∅∈A$, or it has some element $x$ such that $x∩A=∅$.  My questions: (1) If $x∈A$, and $x$ is not a subset (or, x is a subset that consists of only one element, i.e. {1}), then does $x∩A=∅$? I'm trying to understand how $x∩\{1,2,3\}=∅$   (2)How does this guarantee no infinitely descending sequences?   Thank you for your time.
87213
Let $S$ be the equivalence relation defined on $\wp(\{1, 2, 3, 4\})$ defined by: $$XSY\text{ if and only if } |X|\equiv|Y|\;\mod 2$$ Write down the equivalence classes of S.  I understand that equivalence classes have relations where it is reflexive, symmetric and transitive but how are you supposed to write equivalence classes?
53010
Let $A$ be a ring and $S$ a multiplicative closed set. Then the localization of $A$ with respect to $S$ is defined as the set $S^{-1}A$ consisting of equivalence classes of pairs $(a, s)$ where to such pairs $(a,s), (b,t)$ are said to be equivalent if there exists some $u$ in $S$ such that  $$u(at-bs)=0$$ Now, in the  about the localization of a ring, it says that the existence of that $u\in S$ is crucial in order to guarantee the transitive property of the equivalence relation.   I've seen the proof that the equivalence relation defined above is indeed an equivalence relation, but I fail to see how crucial the existence of $u$ is. For example, why doesn't it work if we simply say that two pairs $(a,s),(b,t)$ are equivalent iff $at - bs = 0$? I tried to come up with a counterexample for such case, but failed in the attempt.
59981
Why is it always the case that, given an equivalence relation R on a set X and a $x \in X$, that x is equivalent to itself?  According to my book, this is due to the reflexivity of $R$ and consequently $x \in [x]_R$, but isn't an equivalence relation supposed to be reflexive, symmetric and transitive - not just reflexive?  I've cross-checked this with some other books, and they all say the same thing. I don't get it, how can $x \in [x]$ if x only satisfies reflexivity?
31652
Problem:  If a set $A$ has $n$ elements in it, how many reflexive relations can be defined on it?  My solution  Is the answer  summation of (n^2 - n)C(i)  for i=0 to n^2 -n  $$\sum_{i=0}^{n^2-n} C(n^2-n,i) = \sum_{i=0}^{n^2-n} \binom{n^2-n}i$$  How? well if i make a matrix $n\times n$  now the diagonal elements have to be selected,out of remaining $n^2-n$ any number of elements can be selected.
25434
Definition: Given a set $X$, a relation $R$ on $X$ is any subset of $X\times X$.  A relation $R$ on $X$ is said to be  reflexive if $(x,x) \in R$ for all $x \in X$, irreflexive if $(x,x) \not\in R$ for all $x \in X$, transitive if $(x,y) \in R$ and $(y,z) \in R$ implies that $(x,z)\in R$, intransitive (or antitransitive) if $(x,y) \in R$ and $(y,z) \in R$ implies that $(x,z)\not\in R$, symmetric if $(x,y) \in R$ implies that $(y,x) \in R$, antisymmetric if $(x,y) \in R$ and $(y,x) \in R$ implies that $x=y$.   Given any combination of the properties listed above, is there a nontrivial (i.e. nonempty) relation which satisfies that combination of properties?
122680
Find total number of relations that are equivalence as well as partial order set. Assume set contains total $n$ elements.     My attempt:  As equivalence relation has property reflexive, symmetric and transitive and POSET has property reflexive, antisymmetric and transitive.  Symmetric and antisymmetric will cancle each other except reflexive relation and transitive relation can case antisymmetric, so it's also absent on resultant relation.  Therefore, all diagonal element should be present to satisfy conditions of equivalence as well as POSET.  So, it's independent of number of total number of element of set and answer will be $1$.     Can you explain in formal way, please?
11873
I'm not exactly sure how to go about doing this question. I've attempted it but I'm not exactly sure if it's correct.  Question: Let $S$ be the union of disjoint sets $A_1, \cdots, A_k$. Let $R$ be the relation consisting of pairs $(x, y) \in S \times S$ such that $x, y$ belong to the same member of $\{A1, \cdots, A_k\}$. Prove that $R$ is an equivalence relation on $S$.  The three axioms are: reflexivity, symmetry, transitivity,  I have a brief idea of how to do the first 2, however, for transitivity, I don't have any ideas. Could anyone help out on this please?
53008
Let $A$ be a ring (commutative with $1$), let $S$ be a multiplicatively closed subset of $A$, i.e $S$ is contained in $A$ , $1\in S$ and $a,b\in S$ implies $ab\in S$, for every $a,b\in A$. Consider the following relation defined in $A\times S$: $$(a,s)\equiv(b,t) \iff \exists u\in S:u(at-bs)=0$$ I proved this relation to be reflexive and symmetric, but i have difficulties in proving its transitivity. Can someone suggest me a trick?
99529
we translate "if $A⊆B$ then $A⋃B=B$" to $$∀x( ( x∈A → x∈B) → ((x∈A ∨ x∈B) ↔ (x∈B)))$$  My work: we need to prove $A⋃B⊆B$ first.  1) $∀x( x∈A → x∈B)$ (given)  2)$x∈A$  3)$x∈A$ ∨ $x∈B$  --- (addition laws)  4)$x∈B$ ∨ $x∈B$  --- (1,3 implication)  5)$x∈B$ ---(Idempotent laws)  6)($x∈A$ ∨ $x∈B$) → ($x∈B$) ---(3,5condition proof)  7)$∀x((x∈A$ ∨ $x∈B$) → ($x∈B$)) ---(universal generalization)  then we proved that $A⋃B⊆B$.  we need to prove $B⊆A⋃B$.  1)$x∈B$  2)$x∈B ∨ x∈A$ --- (addition laws)  3)$x∈B → (x∈B ∨ x∈A)$ ---(1,3 condition proof)  4)$∀x(x∈B → (x∈B ∨ x∈A)$) ---(universal generalization)  then we proved that $B⊆A⋃B$.  Therefore, $A⋃B=B$ when $x∈A$.  However,what if $x∉A$?  The statement $( x∈A → x∈B)$ still hold true if $x∉A$ ,should i also prove that when $x∉A$ ,it will not make the consequence $((x∈A ∨ x∈B) ↔ (x∈B))$ be false?  There are two possibility for $∀x( ( x∈A → x∈B) )$:  $x∉A → x∈B$ (because F → T = T)  $x∉A → x∉B$ (because F → F = T)  Actually,Do we need to prove these?