# Tagged Questions

27 views

### If $R$ is a transitive realation, then $R\circ R\subseteq R$

Here's the question I'm struggling with: Let R be a transitive relation on a set A. Prove the R composed with R is a subset of R. I'm kind of lost on how to prove this. I've started with saying: ...
29 views

### Rank Nullity and Dimension relation

How would one prove the relations: $rank S◦T = rankT-dim(kerS ∩ ImT)$ and $nullity S◦T = nullityT+dim(kerS ∩ ImT)$ I understand that the use of rank nullity theorem is required but am confused by ...
17 views

### Need help proving that $fRg \Leftrightarrow fg = f$ on $B^{n}$ to $B$ if and only if $f(b_1,…,b_n) \leq g(b_1,…,b_n)$

I'm trying to gather my thoughts for proving the following claim: For $fRg \Leftrightarrow fg = f$ on $B^{n}$ to $B$, show that $fRg$ if and only if for any input values $b_1,...,b_n$, we ...
29 views

### Need help with compositions of relations

Prove that given relations $R_1 \subseteq A \times B$, $R_2 \subseteq B \times C$, $R_3 \subseteq C \times D$ then $(R1 \circ R2) \circ R3 = R1 \circ (R2 \circ R3)$ I don't know where exactly to ...
60 views

44 views

### Proving that the relation $(x,y)S(x',y') \iff x - x' \in \mathbb{Z} \land y = y'$ is of equivalence.

The relation $S$ is of equivalence. I have to prove it. I managed to prove reflexibility and transitivity, but I'm having problems with symmetry. How can I prove it? The relation $S$ is defined ...
68 views

### Determining equivalence classes of certain pairs for the relation $(a,b)R(c,d) \iff a^2 + 7b^2 = c^2 +7d^2$

This is an equivalence relations exercise. It has two parts. The first is about proving that the relation is of equivalence, which seems to be fine to me, but I'll put it there anyway. With the second ...
21 views

### Finding order properties in the relation $aSb \iff \exists k \in \mathbb{N} : b = ak$

An order relations exercise I just did. I think it's fine, but the second proof felt a bit too wordy or discursive, instead of going straight to the point with brief and accurate statements. How could ...
44 views

### Determining the properties for the relation over $P(\mathbb{N})$ where $ARB \iff A \cup B \in H$

I had two problems with this exercise: I don't know the universe for doing $\overline{A}$ (I'll show below). I couldn't show that it was transitive, although I'm fairly sure it is. Can you assist ...
38 views

### Is my transitivity proof correct for the relation over $\mathbb{Z} \times \mathbb{Z}$ where $(a,b)R(c,d) \iff (a \le c \lor b \le d)$?

I'm having a hard time developing abstract thinking to solve problems regarding a relation's properties. I've spend quite an absurd amount of time on this one, but I think I finally grasped a bit of ...
61 views

### How can I determine that a relation lacks a property without using a counterexample?

When determining a relation's properties, you can show counterexamples to prove that it doesn't have such properties. But I'm interested in proving, without counterexamples, that a relation lacks a ...
46 views

### Properties of relation $R$ on $\mathbb{N} \times \mathbb{N}:\;(a,b)R(c,d) \iff a -c = b -d$

Still doing relation properties exercises, I'm now trying what seems to be a somewhat different type: now the relation is over a cartesian product $\mathbb{N} \times \mathbb{N}$. I normally have no ...
64 views

### Proving that the relation $a \le b \iff b - a \ge 0$ is antisymmetric and total.

Over $\mathbb{R}$ is defined a relation $\le$ in the following way: $$\forall a,b \in \mathbb{R} [a \le b \iff b - a \ge 0]$$ Demonstrate that $\le$ is a relation of total order. For a ...
39 views

### Proving a relation's inverse's properties by knowing the original's.

I'm getting fairly confused with two exercises related to proving a relation's inverse's properties by knowing the original's. I couldn't do either. Any hint is appreciated. If $R$ is a ...
70 views

### Let R be a relation on set A. Prove that $R^2 \subseteq R <=>$ R is transitive $<=> R^i \subseteq R ,\forall i \geq 1$

this is my first question here. I'm still relatively new to more advanced mathematics and don't have much experience with proofs yet. I'm self-studying at the moment and therefore have no one to check ...
250 views

### Equivalence Relations Proof dealing 3 dividing x + y

Consider the relation $S$ on the Natural Numbers defined by $\quad x\,S\,y\quad$ if $3$ divides $\quad x + y.\quad$ Prove $S$ is not an equivalence relation. I know an equivalence relation is one ...
61 views

### How can I further simplify $(a \le b) \lor (b \le a)$ to prove that it is a tautology?

Over $\mathbb{Z}$, $aRb \iff a \le b \lor a = 3b$. Determine if it is total. I think it is: Have arbitrary elements $a,b \in \mathbb{Z}$. We have to prove that $aRb \lor bRa$, which can be ...
64 views

### Proving that $aRb \iff a = b \lor a = b^2$ is antisymmetric.

Over $\mathbb{N}$, $aRb \iff a = b \lor a = b^2$. I'm having problems determining if this relation is antisymmetric. I think it is. I did the following: Direct proof attempt (got stucked) We ...
300 views

### Ordering the field of real rational functions

Perusing the Wikipedia article on ordered fields, I encountered an interesting statement, a variation of which I am now trying to prove. Basically, I am trying to show that the set of real rational ...
316 views

### Proving the transitivity of a relation

I want to prove that the relation $\sim$ on fractions given by $\frac{a}{b} \sim \frac{c}{d}$ if $ad = cb$, where $a, c \in \mathbb Z$ and $b, d \in \mathbb Z_{> 0}$, is transitive. (My last ...
64 views

### $R\subset S\times S$ for $S=\{1,2,3\}$: A Graph-Theoretic Approach

So I am given the relation $R=\{(1,1),(2,2),(3,3),(1,2),(1,3)\}$ and asked which of the properties reflexive, symmetric, or transitive are held in the relation, but what I am thinking is that this can ...
64 views

### Proof for a creating a partition of a countable set using chains in partial orders.

Definition: A partition of a set $A$ is a set of nonempty subsets of $A$ called the blocks of the partition, such that  every element of $A$ is in some block, and  if $B$ and $B'$ are different ...