4
votes
1answer
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 ...
2
votes
0answers
14 views

Set with relative complement forms partition

Prove that if $S$ is a set and $ \emptyset \subsetneq A \subsetneq S $ then $\Pi = \{A , S-A \}$ is a partition of $S$. Proposed Solution: Since $ A \subsetneq S$ , we have $S - A \neq ...
0
votes
3answers
25 views

Help to prove $(A \times B)\cup (C \times D) \subseteq (A\cup C) \times (B\cup D)$

Prove $(A \times B)\cup (C \times D) \subseteq (A\cup C) \times (B\cup D)$ My attempt: $\begin{align} (x,y) \in (A \times B) \cup (C \times D) & \Rightarrow & (x,y) \in (A \times B) \vee ...
1
vote
2answers
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 ...
1
vote
1answer
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?
1
vote
2answers
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 ...
1
vote
3answers
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 ...
2
votes
1answer
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 ...
2
votes
0answers
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. ...
0
votes
4answers
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 ...
2
votes
3answers
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 ...
2
votes
0answers
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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.
0
votes
2answers
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.
0
votes
1answer
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 ...
1
vote
1answer
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)$. ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
0
votes
2answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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.
3
votes
0answers
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 ...
0
votes
3answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
4
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
0answers
26 views

Selecting a unique pair satisfying a condition $\varphi$ with an ordering

Given a finite structure $\mathfrak{A}$ with Universe $|A| < \infty$ and signature $\tau$. We say a pair $(a,a') \in A$ satisfies a $\tau$-formular $\varphi$ iff $$ \mathfrak{A} \models ...
2
votes
4answers
97 views

$f:X\to Y$, $A,B,\subseteq X$. Show that $f(A\setminus B)=f(A)\setminus f(B)$ iff $f(A\setminus B)\cap f(B) =\emptyset$

I tried to prove this but I am not sure if its correct. Please help me out with any tips or advice on how to improve. Here it is: First let $f(A\setminus B)\cap f(B)=\emptyset$. Now $$f(A\setminus ...
0
votes
1answer
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 ...
1
vote
1answer
52 views

Proving via axioms, that for given set $A$, $P(P(A))$ exists

The question itself: For a given set A, prove P(P(A)) exists. You may only use the axiom of pairing, axiom of union and axiom of empty set. This is how I solved it: Let A be the given set. ...
0
votes
2answers
80 views

Cardinality of Integers, Positive Integers, and Rational Numbers all equal $\aleph_0$

Prove that $|\mathbb{Z}|=|\mathbb{Z}^+|=|\mathbb{Q}|=\aleph_0$ I am to use cardinal addition and multiplication to reduce this to finding an injection $\mathbb{Q}^+ \to ...
1
vote
3answers
40 views

Altering an Infinite Set does not change cardinality

Let X be an infinite set. Show that adding or subtracting a single point does not change its cardinality. I have a plan but need help writing the actual proof. I need to show that it doesn't matter ...
0
votes
1answer
38 views

Initial Segments and Isomorphism

Let $f:X \to Y$ be an order isomorphism and A be an initial segment of X. Show that $f[A]$ is an initial segment of Y. I believe this has something to do with Cantor's theorem but can't quite ...
0
votes
1answer
43 views

Union and Intersection of families of initial segments

I'm trying to show that unions and intersections of families of initial segments are initial segments. An initial segment of a partially ordered set X is a subset of A such that, for every x$\in$X ...
0
votes
0answers
52 views

Injection or Surjection Proof

Show that, given sets X and Y, there is an injection or a surjection X -> Y. I have a plan to prove this but struggle with the small details and writing the actual proof. 1) I will assume that ...
1
vote
2answers
55 views

Injective Equivalence

I'm trying to prove that these two statements are equivalent. I've already proven that $f$ injective implies that $$f^{-1} \left(f(B)\right) = B$$ but I need to show that $$f^{-1} \left(f(B)\right) = ...
0
votes
1answer
47 views

Surjection Equivalence [duplicate]

I'm trying to show that if a function $f:X\to Y$ is surjective it's equivalent to saying that $f \left(f^{-1}(B)\right) = B$ for each $B \subseteq Y$. The definition of surjective that I'm using is ...
-1
votes
2answers
91 views

Totally Ordered Set successor and predecessor unique

I'm trying to prove that, in a totally ordered set, an element can have at most one successor and at most one predecessor. I know that if x < y and there is no z $\in$ X with x < z < y then ...
0
votes
1answer
46 views

Transitive Class

Prove that every nonempty transitive class has $\emptyset$ as a member. A class is transitive if each of its members is a subset of it. i.e. if t $\in$ T then t $\subseteq$ T. This is what I have ...
0
votes
1answer
83 views

Unions and intersections of indexed families of transitive sets are transitive

Let $\{ T_a \}_{a \in A}$ be a family of transitive sets. Prove that $\bigcup_{a \in A} T_a$ and $\bigcap_{a \in A} T_a$ are transitive. Assume $A \neq \emptyset$. I'm not sure how to apply the ...
-1
votes
3answers
56 views

Class Transitivity Proof

Prove that a class $T$ is transitive iff $\bigcup_{t \in T},\, t \subseteq T$ iff $a \in t$ whenever $a \in b$ and $b \in T$. I know that I need to begin by proving the first statement implies ...
1
vote
2answers
74 views

Set Theory and Equality

Let $A$ and $X$ be sets. Show that $X\setminus(X\setminus A)\subseteq A$, and that equality holds if and only if $A\subseteq X$. I understand why this holds but am not sure how to 'show' this. Any ...
-1
votes
1answer
45 views

Proof that two sets have the same cardinality.

Let J be the set of all even finite subsets of a set M, and U the set of the odd. Show that J and U have the same cardinality. To tell the truth, I haven't gotten far. I would appreciate any help!
0
votes
2answers
62 views

Prove that set contains least element.

Let $A\not=\emptyset ,A\subset \mathbb{Z}$ and if $(\exists d\in \mathbb{Z})(\forall a\in A):d\le a$ then set A contains least element. How do I prove this? I understand I can use WOP principle. What ...
6
votes
1answer
200 views

Intuition behind proof and verification partially ordered sets

Hi everyone in the book that I read I have trouble to understand the argument of the proof at the below proposition. There is a lot of point which are left as exercises, which is great. One of these ...
1
vote
1answer
62 views

How do i do this process *precisely*?

Let $[a,b)\times [c,d)$ be a rectangle $R$ in $\mathbb{R}^2$. Let $\{[u_k,v_k)\times [p_k,q_k)\}_{1≦k≦n}$ be a mutually disjoint finite sequence whose union is $R$. Then we can decompose this into ...