Tagged Questions

2
votes
1answer
25 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
77 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
94 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
34 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
79 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 ...
0
votes
2answers
200 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
45 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
165 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
254 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
104 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
139 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
528 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
78 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 ...