1
vote
2answers
37 views

Proving by induction, if the base case fails to meet the main condition, what do we do?

I have to determine the number $x$ of subsets with odd cardinalities of a set $S$ and then prove that I'm correct. I determined the number $x$ is obtained using the formula $2^{n-1}$ where $|S| = n$. ...
2
votes
2answers
69 views

If all mappings $f: A\to B$ are many-to-one, does there exist surjective $g: A\to B$?

Suppose sets $A$ and $B$ are such that all mappings $f: A\to B$ are many-to-one (i.e. not injective). Can we prove that there must exist a surjective $g: A\to B$? Ideally, I am hoping to be able to ...
0
votes
1answer
95 views

Proof Question involving Binary Strings & Sets

I'm just wondering about this question I've been working on for my review homework. I tried to solve it on my own and I feel my proof makes decent sense but not the best sense. Please try to give any ...
0
votes
1answer
23 views

Help explain the set being constructed in this Cantor-Schroder-Berstein proof

The Cantor-Schroder-Bernstein theorem states that: Suppose $A$ and $B$ are sets. If $|A|\le |B|$ and $|B|\le |A|$, then $|A|=|B|$ Proof: So, $|A|\le|B|$ implies we can choose an injection ...
2
votes
1answer
36 views

How to prove this version of the Cantor-Schroder-Bernstein theorem?

My text states the Cantor-Schroder-Bernstein theorem as follows: Suppose that $X$ and $Y$ are non-empty sets such that $|X|>|Y|$. Then, any function $f:X\rightarrow Y$ is not an injection, i.e. ...
1
vote
1answer
32 views

Introduction to Set Theory(Ordinal Numbers)

Lemma: If $\alpha$ is an ordinal number, then $\alpha \not \in \alpha$ Proof: If $\alpha \in \alpha$, then the linearly ordered set $(\alpha, \in_{\alpha})$ has an element $x=\alpha$ such that $x \in ...
8
votes
1answer
682 views

Cannot find a mistake in an incorrect proof.

I am reading an introductory book on proof-writing techniques. One of the exercises asks to demonstrate why the proof is incorrect. I spent quite a while thinking about it and still feel puzzled. ...
0
votes
5answers
169 views

The set of all finite subsets of the natural numbers is countable

Could someone verify my proofs? Proposition: the set of all finite subsets of $\mathbb{N}$ is countable Proof 1: Define a set $ X=\{A\subseteq\mathbb{N}\mid \text{$A$ is finite} \}$. We can have a ...
0
votes
0answers
25 views

Subset of a finite set is finite: base step

We can prove by induction that any subset of a finite step is finite. But I am confused by the step "Observe first that all subsets of $\emptyset$ and $\mathbf I_1$ are finite", which I think is the ...
0
votes
1answer
30 views

How to handle a function from a set of functions to another set of functions?

Given sets $X$ and $Y$ we denote the set of functions from $X$ to $Y$ by $\text{Fun}(X,Y)$. Let: $k,n \in \mathbb{Z}^+$ $X_1 = \{x_1,x_2\dots, x_{k+1}\}$ $Y = \{y_1, y_2, \dots , y_n\}$ Then, ...
2
votes
2answers
58 views

Surjectivity of a piecewise function $f:(-1,1)\to \mathbb R$

Function $f$ is defined as $f: (-1, 1) \to \mathbb{R}$. $$ f(x) = \begin{cases} -x/(x-1),&x\geq 0 \\ x/(x+1),&x \leq 0 \end{cases} $$ Let $y \in \mathbb{R}$. How would I prove that there ...
1
vote
3answers
44 views

Help with proof of contrapositive of well-ordering principle

Prove by induction on $n$ that if $A$ is a set of positive integers without a least element, then $\mathbb{N}_n \subseteq \mathbb{Z}^+ - A$ for every $n$ so that $A$ is the empty set. I don't ...
0
votes
1answer
35 views

Proving theorems on relations

I came across the following three statements about relations. I understand why the statements are true, but I am not sure how to demonstrate them mathematically. In the following, $A,B$ are sets and ...
1
vote
1answer
109 views

Question about proving that a finite intersection of big unions is a big union of finite intersections

Let $I_{1}$,...$I_{k}$ be index sets and for each $1 \leq m \leq k$ and each $j \in I_{m}$, let $U_{j}$ be a set. Prove that: $$(\bigcup\limits_{j_{1}\in I_{1}}U_{j_{1}}) \cap ... ...
1
vote
1answer
112 views

Proving the properties of big union of unions for indexed sets

Let $I$ be an index set, and for each $i \in I$, let $J_{i}$, be another index set. For each $i \in I$ and $j \in J_{i}$, let $U_{j}$ be a set. Set X = $\bigcup\limits_{i\in I}J_{i}$. Prove that: ...
1
vote
2answers
31 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: ...
1
vote
2answers
101 views

Prove: If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.

Can someone tell me if this proof is acceptable? Assume $A \not\subseteq C$. This means that there is an $x \in A$ such that $x \not\in C$. But since $\forall x \in A: x \in B$ and $\forall x \in B: ...
1
vote
2answers
74 views

Prove the reflexivity of $\subseteq$.

My professor gave me a list of exercises, I've been able to figure out what mechanism I should exploit to prove them, but I'd like to know if it's good. Until now we've been taught a little logic and ...
1
vote
1answer
63 views

How to prove that $f:\mathbb{N}\rightarrow X$ where $f$ maps to an element in a set, is a bijection?

Let $X$ and $Y$ be disjoint finite sets, $|X|=n$ and $|Y|=m$, so that we have the following bijections: $f:\mathbb{N}_n \rightarrow X$ and $g:\mathbb{N}_m \rightarrow Y$ I need to prove that ...
2
votes
4answers
95 views

Prove $A \subset \emptyset \iff A = \emptyset$

How does one prove this? Can one prove by contradiction by saying: Let $A$ be any set such that $A$ contains at least one element. Now assume $A \subset \emptyset$. This is clearly absurd by the ...
2
votes
2answers
32 views

Help to prove $f$ is surjective $\Leftrightarrow \forall y \in Y, (X \times \{y\} \cap G_f ) \ne \emptyset $

Let $f:X \rightarrow Y$ be a function with graph $G_f \subseteq X \times Y$. Prove that $f$ is surjective if and only if $\forall y \in Y, (X \times \{y\} \cap G_f ) \ne \emptyset $ I have some ...
1
vote
2answers
49 views

Proof on limit superior and limit inferior of a set

I understand the result intuitively but how can I prove this? For a given integral $n \ge 1$, let $A_n = \left\{\frac mn \mid m \in \mathbb Z\right\}$. Show that $\varlimsup_{n\to\infty} A_n = ...
1
vote
2answers
57 views

Wondering if proof is proper

so I have been working on learning some new math in order to prepare for next year. I have been trying to learn proofs, and doing practice questions however the only problem is there are not answers. ...
4
votes
1answer
49 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
19 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
38 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 ...
0
votes
2answers
55 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
37 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
45 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
151 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
43 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
63 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
150 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
70 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
41 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
53 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
54 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
31 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
303 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
46 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
30 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
84 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
137 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
48 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
20 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
19 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
53 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 ...