# Tagged Questions

36 views

### Proving a Subset Identity

Working on part A of this problem: I worked out the first part like this: 1) If $A$ is a subset of $B$ then $\forall~x~[x\in A \implies x\in B]$ 2) Same goes for $C$ being a subset of $D$ (If ...
14 views

27 views

### Proof that the subset relation is reflexive and transitive

I'm teaching myself set theory, and I'm not sure how detailed I should be when asked to prove things. Here is my proof that $A\subseteq A$ (the subset relation is reflexive): $A \subseteq B$ iff ...
34 views

### Prove that if sets A and B satisfy this relation, then they have a common element.

I have done the proof by drawing the picture and explaining it by using an example, but how could I start a more formal proof for this example without the use of a numeric example?
43 views

### Is there a direct proof of the following?

I have been warned by my Lecture as well as several other sources that while proof by contradiction is useful and is certainly needed in some cases, it is often overused. In a effort to learn, I ...
146 views

### Proposed proof of set theoretic result

I am tasked with proving the following: $$(A - B)\cap (B-A) = \varnothing$$ My Attempt: Suppose there exist a $x \in (A - B)\cap (B-A)$ then: \begin{align*} x \in (A - B)\cap (B-A) &\iff ...
33 views

### Set difference between power sets

Show that if $A$ and $B$ are sets then $\varnothing \notin \mathcal P(A) − \mathcal P(B)$ . My Attempt: If $A$ and $B$ are sets, then $\varnothing \subseteq A$ since the empty set is subset of ...
55 views

### Simple Proofs in ZFC Set Theory

So I'll keep this real short and simple. In this document on page 23 there is a list of axioms. On page 24 there is a list of theorems that come from said axioms. I can prove them all except 3 and 5. ...
146 views

### Singleton sets are a subset

I am tasked with prove the following elementary result. I am concerned about being rigours enough in my proof: $$a\in S \iff \{a\} \subseteq S$$ My Attempt: Suppose $\{a\} \subseteq S$ . Then ...
55 views

### Metric Space, Induced topology

I'm trying to show that the metric topology is indeed a topology. To do so, I want to show the following three statements are true: $\emptyset$ and X are in $\tau$ finite intersections of open sets ...
31 views

### Velleman's How to prove it. Partial order proof.

Theorem: Suppose that $R$ is a partial order on $A$, $B_1 ⊆ A$, $B_2 ⊆ A$, $x_1$ is the least upper bound of $B_1$, and $x_2$ is the least upper bound of $B_2$. Prove that if $B_1 ⊆ B_2$ then ...
44 views

### Suppose $F$ and $G$ are families of sets.

Suppose $F$ and $G$ are families of sets. Prove that $\bigcup F$ and $\bigcup G$ and are disjoint iff for all $A∈F$ and $B∈G$ , $A$ and $B$ are disjoint. It has been suggested to use contrapositive ...
25 views

### How to prove a bijection?

I know what a bijection is and how to prove it when given a function, but how to do it when you are only given sets.
50 views

### Equivalence relations and equivalence classes

I dont know how to start this proof? Also, our professor did not explain equivalence classes fully so I am not understanding them very well.
24 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 ...
27 views

### Let $A =[a,b,c,f,g,i], B=[b,f,h]$ and $C = [a,k,l,m]$ Show that $\backslash$ is not associative

Question : Let $A =[a,b,c,f,g,i], B=[b,f,h]$ and $C = [a,k,l,m]$ Show that $\backslash$ is not associative by comparing $(A \backslash B) \backslash C$ with the set $A \backslash(B \backslash C)$. ...
269 views

### induction proof for kleene star

i am going through some past exam paper questions on regular languages for some revision, and i am having a bit of trouble with converting general ideas into formal mathematical proofs. the question ...
41 views

### one to one positive integers and positive rationals

How would you go about proving that there is a 1 : 1 correspondence between the set of positive integers and the set of positive rationals. I know there are a lot of ways to do this but I am looking ...
29 views

### Set theory injective function&partition proof

Suppose $f:A\rightarrow B$ is an injective function and $\{A_i\}_{i\in I}$ is a partition of $A$. Prove that $\{f(A_i)\}_{i\in I}$ is a partition of $f(A)$. This is a homework proof question and I ...
15 views

### If $X$ is a finite set of cardinality $n$, where $n$ exists in $P$, show that the following conditions on a function $f: X \to X$ are equivalent: [duplicate]

(a) $f$ is an injection (b) $f$ is a surjection (c) $f$ is a bijection I know that (c) implies (a) and (b) and (a) and (b) imply (c). I also have the following definition that I've been playing ...
68 views

### Power Set, Bijection Function, Equivalence Relation

Let $S$ be a set and $P(S)$ the power set of $S$. For sets $A,B⊆P(S)$, we say that $A \sim B$ if there exists a bijective function $f: A \rightarrow B$. Show that $\sim$ is an equivalence relation.
129 views

### Prove $f_\infty: A_\infty \rightarrow B_\infty$ is a bijection

Update: I was given some hints at how to approach this problem $A_\infty$ and $B_\infty$ are sets, not maps. (which is strange because there are function definitions coming into play here) The ...
46 views

### Proof that $X^C \cap Y^C= \;(X \cup Y)^c$

Proof that if $X \subset S,\; Y\subset S,\;$ then $\;X^C \cap Y^C= \;(X \cup Y)^c:$ It must be shown that the two sets have the same elements, that each element of the set on the left is an element ...
18 views

### Are these Cartesian Product equalities true?

Let $A, B, C, D$ be sets. (i): (A x B) $\cup$ (C x D) = (A $\cup$ C) x (B $\cup$ D) (ii): (A x B) $\cap$ (C x D) = (A $\cap$ C) x (B $\cap$ D) I have to prove these later for homework if true, and ...
17 views

### Diagonal Relation as a poset I - establishing the result by vacous truth

I have a problem with the logic behind the fact that, given a nonempty set X, the diagonal relation $D_X := \{ (x,x) : x \in X \}$ is a partial order on $X$. More specifically, my problem is with ...
45 views

### Problems with a proof that -in a linear order- a minimal element is the smallest element

I have a problem with a proof I found in Velleman's "How to prove it". This is sort of interesting, because it is the very first time I cannot see the structure of a proof presented in the book. The ...
85 views

### Prove for every two sets $A$ and $B$

Prove for every two sets $A$ and $B$ that $A-B$, ${B-A}$ and $A \cap B$ are pairwise disjoint. I'm really stuck on this one. I know pairwise disjoint means no two elements in $A$ and $B$ are ...
60 views

### $A=(A \cap B) \cup(A \cap B^\mathsf{c})$

I would like to know if this proof is correct. If not, what would I have to change to make it rigorous? This set equality seems really obvious, and because of that I am not sure if I have given enough ...
18 views

### Partial Order proof with operation on a set

Let X be a set and let $f$ be an operation on X (i.e. it is a function from X $\times$ X to X), which we will denote with $f(x, y) = xy$. In addition, $x \le y$ iff $f(x, y) = x$. Suppose further that ...
26 views

28 views

### Finite and Infinite Cardinality Representation

Let X be a set. Show that the cardinality of the set of finite sequences with elements from X has cardinlity $\aleph_o$ if X is finite and cardinality $|X|$ if X is infinite. I was given the hint ...