2
votes
1answer
89 views

Defining a partial order on $A\times B$, given partial orders on $A$ and on $B$

Let $(A,\preceq_A)$ and $(B,\preceq_B)$ be partially ordered sets. Define $C = A \times B$ and define the relation $\preccurlyeq$ on $C$ to be $(a,b) \preccurlyeq$ $(a',b')$ if and only if ...
1
vote
2answers
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: ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
60 views

Bijection on a component of a cartesian product

I have been recently studying relations and mappings and I have come across the following problem. Consider two non empty finite sets $I,J$ and their cartesian product $I\times J$. Let $f\colon ...
0
votes
1answer
37 views

Proving that $(a_1, b_1)\sim(a_2, b_2)\Leftrightarrow\ a_1=a_2\land b_1=b_2$

This assingment is preparation for exam. I need to prove with $(a_1, b_1)\sim(a_2, b_2)\Leftrightarrow\ a_1=a_2\land b_1=b_2$ that $\sim$ is equivalence relatio. Can you tell me how to do this. ...
1
vote
1answer
892 views

Prove that between every two rational numbers a/b and c/d that there is a rational number and there are an infinite number of rational numbers [duplicate]

So the full problem is Prove that between every two rational numbers $a/b$ and $c/d$ that: There is a rational number There are an infinite number of rational numbers I am having ...
5
votes
1answer
63 views

Question about sets of well-orders and isomorphisms between well-orders

I was thinking about this problem in trying to better get a feel for and understand well-orders (I'm trying to learn some set theory) - right now, I'm not really hoping for anybody to supply me with a ...
1
vote
1answer
25 views

Show that f is a symmetric relation on A

I am learning about relations and I come across this exercise. And I don't understand the problem. Let me first state the problem here: Let $f: A \rightarrow A$ be a function for which $f(f(x))=x$ ...
0
votes
1answer
60 views

Transitive closure of binary relation with proof of equivalence

On the set X = {1,2,3,4,5,6,7,8,9}, there is binary relation Q = {(1,9),(2,5),(3,7),(4,1),(5,8),(6,2),(7,3),(8,6),(9,4)}. Make a transitive closure T of the relation Q. Decide and prove whether the ...
0
votes
1answer
62 views

Find the number of subsets $S$ of $X$ (of any size) that satisfy the following property

Let $X=\{1,2,\dots,10\}$ define the relation $R$ on $X$ by: for all $a,b\in X$, $a\mathrel{R}b \iff ab$ is even. 1) Find the number of subsets $S$ of $X$ (of any size) that satisfy the ...
0
votes
2answers
76 views

Determining whether a relation is reflexive, symmetric, transitive.

Let $X=\{0,1,2,...,10\}.$ Define the relation $R$ on $X$ by: for all $a,b$ in $X$, $a\mathrel{R}b$ if and only if $a+b=10$ is $R$ reflexive? symmetric? transitive? $a\mathrel{R}a$ $a+a=10$ ...
1
vote
1answer
45 views

how many elements does Ia have?

Let $A=\{1,2,3,4\}$. Let $F$ be the set of all functions from $A$ to $A$. Let $R$ be the relation on $F$ defined by $f,g \in F$ $f R g \Leftrightarrow |f(A)|=|g(A)|$ $f(A)=\{f(x): x\in A\}$ ...
0
votes
2answers
77 views

Let S = {1,2…10} Let R be the relation on P(S), the power set of S, defined by: for any X,Y ∈ P(S),

Let S = {1,2....10} Let R be the relation on P(S), the power set of S, defined by: for any X,Y ∈ P(S), XRY <=> X∩Y=∅ is it true that ∀X∈P(S),∃Y∈P(S) so that (X,Y)∈R? I dont know what is (X,Y)? ...
0
votes
0answers
21 views

Prove that $R^*=R^+ \cup Id_A$

Let R be a relation on set A. Prove $R^*=R^+ \cup Id_A$, where $R^*$ is the reflexive transitive closure and $R^+$ is the transitive closure. In order to prove equality of the two sets you prove that ...
0
votes
1answer
33 views

Prove that symmetric closure of R $h_{sym}(R) = R \cup R^T$

I have a question about proving statements of the form in which the given is the union of two sets. Well first of all let me just write how I tried to prove the statement: To show that $h_{sym}(R) = ...
0
votes
1answer
45 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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
3
votes
2answers
45 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 ...
0
votes
2answers
39 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 ...
2
votes
1answer
62 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 ...
1
vote
1answer
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 ...
4
votes
1answer
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 ...
1
vote
1answer
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 ...
5
votes
1answer
72 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 ...
1
vote
2answers
253 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 ...
2
votes
2answers
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 ...
2
votes
2answers
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 ...
5
votes
2answers
301 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 ...
1
vote
1answer
327 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 ...
0
votes
1answer
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 ...
2
votes
1answer
65 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 ...
1
vote
2answers
317 views

Is cancellation of Cartesian product possible? I think so, but am having trouble with the proof…

So, Is a cancellation possible for the Cartesian product? ex. if you have two Cartesian products that are equal to eachother, do the 2nd sets for each product equal eachother? Lets say you have ...
3
votes
1answer
148 views

Prove transitivity of $\forall X( X\subseteq A\setminus\{a, b\}\rightarrow(X\cup \{a\}\in\mathcal{F}\rightarrow X\cup\{b\}\in\mathcal{F}))$

This one is from Velleman's "How to Prove It, 2nd Ed.", exercise 4.3.23. Suppose $A$ is set, and $\mathcal{F}\subseteq\mathcal{P}(A)$. Let $$R=\{(a,b)\in A\times A : \text{for every } X\subseteq ...
1
vote
1answer
48 views

Finding a mistake in the incorrect proof for $(S\setminus T)\circ R\subseteq (S\circ R)\setminus(T\circ R)$

This is from Velleman's "How to Prove It", exercise 4.2.11.b). The exercise requires finding a mistake in the proof, but everything looks good to me. Must be that I'm missing some important fact, but ...
2
votes
3answers
333 views

Proving that a relation is transitive

During one of my recent tests, I was given the following problem: "Let the relation $R$ be defined on all finite sets so that $ARB$ if and only if there exits a bijection from $A$ to $B$. Verify that ...
3
votes
3answers
3k views

Prove that the intersection of two equivalence relations is an equivalence relation.

I am reading this chapter 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 ...
0
votes
2answers
1k views

How can I prove that if a relation is symmetric then its inverse is also symmetric?

Prove that if $R$ is symmetric, then $R^{-1}$ is symmetric, $R$ being a relation over $A$, and $\lnot(A = \varnothing)$. This came as an exercise in my book. I couldn't do anything - there is ...
0
votes
3answers
53 views

What is $D$ in $G \cap G^{-1} \subseteq D$?

My book has an example that goes like this: $$A = \{1,2,3,4\}$$ $$R = (G,A,A)$$ Prove that $R$ is antisymmetric if and only if $G \cap G^{-1} \subseteq D$ We have to prove two implications. The ...
1
vote
2answers
1k views

Proving a relation is partial ordering

I have a problem proving that a very simple relation is partial ordering. It is defined explicitly (i.e. with pairs of numbers) and I have no idea how to do a formal proof for its antisymmetric ...
1
vote
3answers
1k views

How to show that two equivalence classes are either equal or have an empty intersection?

For $x \in X$, let $[x]$ be the set $[x] = \{a \in X | \ x \sim a\}$. Show that given two elements $x,y \in X$, either a) $[x]=[y]$ or b) $[x] \cap [y] = \varnothing$. How I started it is, if ...
3
votes
2answers
147 views

Prove whether a relation is an equivalence relation

Define a relation $R$ on $\mathbb{Z}$ by $R = \{(a,b)|a≤b+2\}$. (a) Prove or disprove: $R$ is reflexive. (b) Prove or disprove: $R$ is symmetric. (c) Prove or disprove: $R$ is transitive. For ...
2
votes
0answers
203 views

Examples of proofs by induction with respect to relations that are not strict total orders.

I have read this Wikipedia article and found it fascinating. I came across it after I tried to prove a certain statement with a method resembling induction in the set of natural numbers but ordered by ...
2
votes
3answers
867 views

Bijective Function between Uncountable Set of Real numbers and a set of all functions

Let $S$ be the set of all real numbers in $(0, 1)$ having a decimal representation which only uses the digits $0$ and $1$. So for example, the number $1/9$ is in $S$ because $1/9 = 0.1111\ldots$, ...
1
vote
1answer
84 views

Proving a relation is asymmetrical

Can someone please help? I am trying to answer the following: Consider the relation $T$ on $\mathbb{Z}$ given by $$xTy \Longleftrightarrow x + 1 \le y;$$ Is $xTy$ asymmetric? $xTy ...