0
votes
0answers
23 views

Math challenge(Infinite sets): Bottles of Beer

Imagine a counter with stools that stretch across the room(infinite). All the stools are occupied. Two drunks come in and want to squeeze in to sit down. Drunk #1 walks in and tells the person on the ...
0
votes
2answers
25 views

Having trouble showing the cardinality of two infinite sets is the same

We just learned about Aleph-naught today and I read about it on wikipedia but I do not know how to go about solving this problem in my homework: Prove that N(natural numbers) has the same ...
0
votes
0answers
24 views

Beginner proof of image of functions and functions of sets

This is the third time I got my proofs handed back from my teacher. She won't tell me what's wrong except I have to redo it. I am running out of luck and I need help towards the right direction! The ...
0
votes
1answer
50 views

Proving that these two sets are denumerable.

(a) $S_k=\{A\subset\mathbb{N}: |A|=k\}$ for $k\in\mathbb{N}$ (b) $S = \bigcup_{k=1}^\infty S_k$ Work: For (a), I am not too sure about what approach I should use. I think finding a bijective ...
0
votes
1answer
27 views

Prove a statement for the infinite matrix

We are given infinite two dimensional matrix $\{a_{i,j}\}_{i,j=1}^\infty$. And we know that matrix contain only natural values and each number appears in the matrix exactly 8 times. Task is to prove ...
4
votes
0answers
28 views

Prove that for every 2 elements in the set F of all functions from N to N, there's an element in F that's bigger than both

let there be $\ F$ the set of all functions from $\ N \rightarrow N$. K is a relation on F, for every f,g$\in$F , (f,g)$\in$K $\leftrightarrow$ for all $\ n\in N$, $\ f(n)\leq g(n)$ Prove that for ...
0
votes
1answer
50 views

Proving a relation is transitive

I am trying to understand transitive relations. I understand given that a set may have $\{(a,b)(b,c)\}$ it must contain $(a,c)$ for it to be transitive. But for longer sets I am getting confused in ...
0
votes
0answers
49 views

Please give feedback to my answers (sets) [duplicate]

Prove or find a counter-example to the claim that for all sets $A, B,C$ if $A\cap B = B\cap C = A\cap C = \varnothing$ then $A\cap B\cap C \neq\varnothing$. Solution False. Let $A = ...
0
votes
0answers
34 views

Proving equality with finite and pairwise disjoints

I'm having some problems proving this. Let $A_1,A_2,.....A_n$ be finite and pairwise disjoints. So any two sets are disjoint. How do we prove that $$|A_1 ∪ A_2 ∪ ....A_n| = |A_1|+|A_2|+....|A_n|$$
0
votes
1answer
65 views

Number of surjective functions from $\{1,2,…,n\}$ to $\{a,b,c\}$

Ok so following questions are given in my text book Let $A = \{1, 2, 3,...., n\}$ and $B =\{a, b, c\}$ then the number of functions form $A$ to $B$ that are onto is. I have no idea how to find ...
0
votes
1answer
30 views

$\left\{\frac{\pi}{6}+\frac{2K\pi}{3}\Big\vert K\in\mathbb {Z}\right\}\cap\left\{\frac{\pi}{3}+\frac{K\pi}{2}\Big\vert K\in\mathbb {Z}\right\}=$?

$$\left\{\frac{\pi}{6}+\frac{2K\pi}{3}\,\Big\vert\, K\in\mathbb {Z}\right\}\cap\left\{\frac{\pi}{3}+\frac{K\pi}{2}\,\Big\vert\vert\, K\in\mathbb {Z}\right\}=\varnothing$$ Is my answer right? If not, ...
-4
votes
1answer
69 views

Counterexamples in set theory [duplicate]

I have a question which states that: Prove or find a counterexample of sets $A, B, C$ such that $A\cap B = B\cap C = A\cap C =\emptyset$ but $A\cap B\cap C \neq\emptyset$ I know ...
1
vote
3answers
56 views
+100

Show that if the projection of a set is negligible, then the set is negligible as well

I'd like a hint in the right direction, im drawing a complete blank. let $E \subset \mathbb R^2$. We'll define the projection of $E$ unto the $x$ axis as: $P_x(E)=\{x| \exists y \in \mathbb R s.t ...
-1
votes
1answer
46 views

Symmetric Difference Quesions [closed]

Let $A$ and $B$ be sets. The symmetric difference of $A$ and $B$ is denoted by $AΔB$. Prove that: (a) $AΔB ⊆ A$ iff $B ⊆ A$ (b) $AΔB ⊆ B$ iff $ A ⊆ B $ (c) If $A$ and $B$ are finite sets, ...
0
votes
1answer
125 views

Show that a particular set is a poset

I would like to know if my understanding of the concept of a poset is correct. From what I've learnt from the class: A poset must be transitive, reflexive, and antisymmetric. Am I right? Therefore, ...
0
votes
2answers
37 views

Cardinality of two sets cross-multiplied

Let $A$ and $B$ be sets. Prove that $ \#(A \times B) = \#(B \times A)$. What I have done: There exist an element $m$ in $A$ such that the element also exists in $B$. If $\#A = \#B$, then $\#B = ...
1
vote
0answers
49 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.
1
vote
2answers
63 views

Cardinality, Finite Sets Proof

Let $S$ and $T$ be finite sets. Prove that if $|T-S| = |S-T|$, then $|S| = |T|$.
2
votes
0answers
108 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
1answer
43 views

Basic topology questions with cantor's set

I have 3 questions in toplogy, one of which I managed to solve (but would appreciate input regardless) and 2 which are more difficult. I'd like a push in the right direction. Define $K$ as ternary ...
1
vote
1answer
61 views

What's wrong with my proof?

Let $f:A\to B$ be a function. Let $T_1$ and $T_2$ be subsets of $B$. Show that if $f$ is onto, then $$f^{-1}(T_1)\subset f^{-1}(T_2) \implies T_1\subset T_2$$ I proved it as follows. Let $x\in ...
0
votes
1answer
30 views

Prove that if there exists f: X to a finite set is bijective, then X is finite

I was given that X is finite if any function that maps X to X is surjective and injective. Also, the problem specifies the finite set n as a set with n elements. Now, I only know that there exists ...
0
votes
1answer
46 views

Cardinality of the set of all functions from A to B

Given two sets $A$ and $B$, let $F(A, B)$ denote the set of all functions $f : A → B $ (no assumptions about injectivity or surjectivity – all functions from $A$ to $B$ are included). Let $|S|$ denote ...
2
votes
2answers
80 views

Prove that the cardinality of $\{0,1\}^R$ is not equal to that of $R$

From what I understood $\{0,1\}^R$ is the set of all functions from $\{0,1\}$ to $R$. I would be happy not only for the proof but a good and maybe simplified explanation of the concept of Aleph's and ...
3
votes
1answer
32 views

Union and set notation

I was reading my notes and came across this example... A = {z: z is a number, z is ≤ 20} B = {y: y is an even number} ...
0
votes
1answer
53 views

Can you conclude that A = B if A, B, and C are sets such that…

a. A ∪ C = B ∪ C b. A ∩ C = B ∩ C c. A ∩ C = B ∩ C and A ∪ C = B ∪ C My method of solving this was to convert everything to propositional logic, then to solve it to show that none of the above are ...
-1
votes
1answer
49 views

Let $X \neq \emptyset$, define the relation$A\sim B$ if there exists a bijection $f : A \to B$, Show that $\sim$ is an equivalence relation on $X$.

A question on my last proofs midterm, I know I must prove injectivity and surjectivity, but there aren't really any obvious conditions or descriptions on S that helped me to manipulate it to try and ...
2
votes
2answers
43 views

Using zorn's lemma to prove aleph 0 is the least infinite cardinal

I understand zorn's lemma, but it is confusing me on how to apply it to an infinite set. I am asked to prove that if A is an infinite set, then there exists an injection from $\mathbb{N}$->A using ...
1
vote
1answer
27 views

explicit choice function without axiom of choice

This is probably quite simple and I am just missing something. I am asked to define a choice function for the collection of all nonempty subsets of $\mathbb{Z}$ without using the axiom of choice. We ...
1
vote
3answers
73 views

Why a unit set is not the same as its element? $\{x\} \ne x$?

I was solving a list of exercises from homework and I answered one question wrong because I thought that a singleton set and its element were the same thing... I found only a few results from a ...
0
votes
0answers
58 views

proving that $f:\mathbb N\to\mathbb N\times\mathbb N$ is countable using Cantor's diagonal method

I need to prove using Cantor's diagonal method that the function $\mathbb N\to\mathbb N\times\mathbb N$ ($\mathbb N$ being all natural numbers) is countable. I have read this question(Does anyone ...
1
vote
2answers
26 views

Counting Venn Diagram problem

"In a survey of 185 university students, 91 were taking a history course, 75 were taking a biology course, and 37 were taking both. How many were taking a course in exactly one of these subjects?" I ...
1
vote
1answer
41 views

What is $\bigcup_{r\in(0,1)}[0,r]$?

Question: for any real number $r$, let $C_r$ be the closed interval $[0,r]$. Let $J$ be the open interval $(0,1)$. what is $\bigcup_{j\in J} C_j$? So far I have attempted a double inclusion proof to ...
1
vote
1answer
40 views

Subtraction of elements from $\mathbb Z$

Let $M_n$ be the set of integers which are integer multiples of $n$. If $\mathbb N = {1,2,3...}$ What would $$ \mathbb Z - \bigcup_{n\in\mathbb N}M_{2n+1} $$ be? I know that $M_{2n+1}$ represents ...
3
votes
2answers
46 views

Proof that a given projection map restricted to a subset is closed.

$\pi_{1}:\mathbb{R}^2\rightarrow\mathbb{R}, (x,y)\mapsto x$ is a projection map from $\mathbb{R}^2$ with the standard eulcidean topology, $\mathscr{T}_E$ to $\mathbb{R}$ with it's usual euclidean ...
0
votes
0answers
76 views

For the non-empty sets A, B and C, let $f : A \to B$ and $\,g : B \to C$. Prove or disprove the following statements:

(a) If $f$ is onto then $g\circ f$ is onto. (b) If $g$ is onto then $g\circ f$ is onto. (c) If $f$ is one-to-one then $g\circ f$is one-to-one. (d) If $g$ is one-to-one then ...
1
vote
1answer
32 views

If $cf(\alpha)<cf(\beta)$, how to show that every increasing $h:\alpha \to \beta$ has a range that is bounded in $\beta$?

The problem Let $\alpha$ and $\beta$ be two limit ordinals. Show that $1$. $\implies$ $2$., where $\qquad 1$. $cf( \alpha)$ < $cf(\beta )$ $\qquad 2$. Every increasing $h: \alpha \to \beta $ ...
-1
votes
2answers
38 views

Consider the function h where $h(x,y) = (x+y,x-y)$, $h : \mathbb N\times \mathbb N\to \mathbb N\times\mathbb N$ [duplicate]

Is the function h onto and one to one? Prove this. Online bonus question on a recent proofs quiz on the topic of one-to-one and onto functions. Gave me a bit of grief (the mapping stuff). Also ...
1
vote
3answers
72 views

Let X and Y be finite non empty sets such that $|X| = |Y|$. Show that a function $f : X \to Y$ is onto if it is one to one.

Hello this is a recent question posted on my course website for bonus marks. I am not exactly an expert at proving bijection (our current topic of study) and the definitions of onto and one-to-one are ...
0
votes
1answer
31 views

For an $f:\omega_1 \to \omega_1$, how to prove $\alpha = f(\alpha)$ for uncountably many $\alpha$?

My homework question reads: Let $\omega_1$ be the first uncountable ordinal, and let $f:\omega_1 \to \omega_1$ be s.t. If $\alpha < \beta < \omega_1$, then $f(\alpha) < f(\beta)$. ...
3
votes
2answers
53 views

How to show existence and uniqueness of an $f: R(\omega) \to \omega$, where $R(\omega)$ is the cumulative hierarchy?

My questions For part A (see below), is my reasoning correct? Is it enough to just show that $f(x) \in \omega \ \ \forall x \in R(\omega)$? I'm very new to axiomatic set theory, in particular to the ...
0
votes
2answers
30 views

Use of “for all” in definition of reflexive and symmetric relations.

My book says that a relation R on A is reflexive, if $\ (a,a) \in R, \ for\ every \ a \in A$ symmetric, if $\ (a_1,a_2) \in R \implies (a_2,a_1) \in R,\ for\ all\ a_1,a_2 \in A$ Although I ...
-1
votes
4answers
70 views

Let $g : \Bbb N \times \Bbb N \to\Bbb N \times \Bbb N$ defined as $g(m,n) = (m + n,m - n)$

Determine if $g$ is injective; surjective; bijective. Question on a recent test regarding one-to-one and onto functions. Was very difficult for me, could not even begin to answer either. This is ...
1
vote
4answers
27 views

How can I prove this relation between the images of these two different sets?

If $f : X \to Y$ is surjective, prove that every $A\subset X$ satisfies $$Y\setminus f(A) \subset f(X\setminus A). $$ Show that the claim is false is $f$ is not surjective. I was able to ...
3
votes
3answers
84 views

Let $S$ and $T$ be finite non-empty sets such that $|S| = |T|$. Show that the function $f : S\to T$ is onto if and only if it is one-to-one.

This is a recent homework bonus question assigned in my Proofs and Conjectures class. It (evidently) includes and evaluates our understanding of elementary-set theory and how to determine and prove ...
0
votes
0answers
35 views

Recursive seqence of power set, starting with the empty set

Let $A_0$ be the empty set and $A_n := \mathcal{P}(A_{n-1})$ for $n \in \mathbb{N}$. I have to determine $A_n$ and $|A_n|$. Using the definition of the power set I get \begin{align} A_1 & = ...
3
votes
1answer
34 views

Prove that $\bigcup_{n=2}^{\infty} [1/n, 1 - 1/n] = (0, 1)$

This is an exercise for a set theory class. I already managed to prove $\bigcup_{n=2}^{\infty} [\frac{1}{n}, 1 - \frac{1}{n}] \subseteq (0, 1)$: Let $x \in \bigcup_{n=2}^{\infty} [\frac{1}{n}, 1 - ...
-1
votes
1answer
46 views

Prove or Disprove the following statement. For any sets $A$, $ B$, and $C$, we have $A \cup (B \& C) = (A\cup B) \cup (A\&C)$

Trying to figure this question out in my proofs class (tried venn-diagram the multiple set-notation signs are confusing me). Homework question in the fundamental sets unit.
0
votes
1answer
25 views

Bijection between sets of functions

Let $\left ( B \times C \right )^A=\{f \in \mathcal{P} \left ( \left ( B \times C \right) \times A \right) \big | f \hspace{2mm} \text{is a function and} \hspace{2mm} \text{dom}(f)=B \times C \}$ ...
0
votes
0answers
28 views

How to prove this equation of composition of binary relations?

We have three binary relations $R,S,T$ all from $A$ to $A$. Prove $(R∘S)\cap T=\emptyset$ iff $(R^{-1}∘T)\cap S=\emptyset$ iff $(T∘S^{-1})\cap R=\emptyset$ I don't quite see what's $(R∘S)^{c}$ is ...