This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...

learn more… | top users | synonyms

0
votes
0answers
5 views

Proving a set 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 ...
0
votes
0answers
16 views

A and B are sets. Prove that A=B iff P(A) = P(B) where P is the power set. [duplicate]

Since P(A) = P(B) P(A) is a subset is P(B). A is also an element of P(A). But since P(A) is a subset of P(B) A is almost an element of P(B) which means A is a subset of B. Can I do the same thing to ...
0
votes
2answers
22 views

Is there some kind of right distributivity of the subset predicate over set union?

$X \cup Y \subset Z \leftrightarrow X \subset Z \wedge Y \subset Z$. Is there a similar simple rule for $X \subset Y \cup Z$?
1
vote
2answers
36 views

Are these proofs valid? Which method of proof is better?

I want to prove that S ∪ (T ∩ V) = (S ∪ T) ∩ (S ∪ V) Here's 2 methods of proof, the first one I thought up, the second is from my notes: First method: a. S ∪ (T ∩ V) ⊆ (S ∪ T) ∩ (S ∪ V) x ∈ S ∪ (T ...
0
votes
1answer
26 views

Missing step in proof?

I was just looking over my notes and found that some steps, while obvious, seem to be missing in-between steps. For example: $$x ∈ S \land (x ∈ T \lor x ∈ V) \Rightarrow (x ∈ S \land x ∈ T) \lor (x ∈ ...
0
votes
0answers
31 views

How to prove that for finite, nonempty sets $A,B$ $|A \times B| = |A|\cdot|B|$

With $|A| = a$ and $|B| = b$, bijections $f : A \rightarrow [a]$ and $g : B \rightarrow [b]$ exists. I can't seem to take one definitive action for this problem. Are there inequality cases with $a$ ...
1
vote
1answer
26 views

How do you define computational complexity abstractly?

Let the problem we're studying be $f : X \to Y$. Say, I don't know what I want to define time-complexity with respect to, I just know I have a map $|\cdot| : X \to \Bbb{R}$, such that $|\cdot| \geq ...
0
votes
1answer
19 views

How to prove that a union of a countably infinite set and a finite set is countably infinite with no intersection

I can get my head around this thing... So I can find examples of this using reals and naturals, but the intersection of reals and naturals is naturals. Is there a way to prove that the union of a ...
0
votes
3answers
39 views

How to Prove that a set is uncountably infinite if through bijection

So I know that and know how to find a bijection between a set of infinite binary strings and its power set. I came to a first conclusion that there exists a bijection between set S={0,1}* and P(N). ...
-3
votes
0answers
28 views

Find an example of sets $A,B,C$ such that $A\cap B = B\cap C = C \cap D = \emptyset$ but $A \cap B\cap C \neq\emptyset$ [duplicate]

Find an example of sets A,B,C such that $$A\cap B = B\cap C= C \cap D = \emptyset$$ but $$A \cap B\cap C\neq\emptyset$$
0
votes
0answers
18 views

Equivalence classes of the form (a,b)

https://www.dropbox.com/s/q0w2vwwz5w1b0y8/sets.jpg I can do the proof and under b the class would take the form x=3m +2 and y=2n+1 I know that I need to find the equivalence classes (0,0), (1,0), ...
2
votes
3answers
45 views

Explain “There is a unique function from $\emptyset$ to any set $A$”.

My book says: There is a unique function from $\emptyset$ to any set $A$. I don't understand how that is. Let $A=\{1,2,3\}$. Which element of $A$ do we map $\emptyset$ to? Do we map $\emptyset$ ...
0
votes
0answers
22 views

Bijective function with different domain and co-domain element count

To be bijective is to be both injective and surjective. Which in other words, have to have a one-on-one match right? Then how am I supposed to come up with a bijective function if the domain has a ...
0
votes
0answers
30 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
0answers
25 views

some basic concepts on algebra / measure theory

I'm reading a book in Chinese on measure theory (Introduction on Measure Theory, by Yan Jia-an). In the beginning there are some algebra concepts defined that I'd like to confirm the exact meaning and ...
0
votes
1answer
26 views

prove that if A is a subset of B, B is a subset of C, and C is a subset of A, then A=B and B=C

To prove A=B, I must prove that A is a subset of B and B is a subset of A. A is a subset of B is already given. So all that is left is to prove B is a subset of A. Is it suffice to say that since A ...
-1
votes
0answers
31 views

Uncountably infinite: the set of all infinite binary strings [duplicate]

Given that $S=\{0,1\}^{ \mathbb{N} } $ is the set of all infinite binary strings. Is it possible to find a bijective function $f:S\rightarrow \mathcal P(\mathbb N)$? Thank you.
1
vote
3answers
29 views

Prove that $\{(a,b):a,b\in\mathbb N, a\geq b\}$ is denumerable.

If $S=\{(a,b):a,b\in\mathbb N, a\geq b\}$, how do I prove that $S$ is denumerable? Work: Since $S \subseteq\mathbb{N\times N}$ I know that $S$ is denumerable. But I don't know how to structure the ...
2
votes
2answers
55 views

Proving that (0,1) and [0,1] are numerically equivalent.

as the title suggests, I need help proving that the cardinality of $(0,1)$ and $[0,1]$ are the same. Here is my work: $f:[0,1] \rightarrow (0,1)$ Let $n\in N$ Let $A=\{\frac{1}{2}, \frac{1}{3}, ...
2
votes
1answer
30 views

Is a subset an element of a set?

Given these two sets: A = {c} B = {c} Is B $\in$ A? Or is above wrong and c $\in$ A and B $\subseteq $ A?
0
votes
1answer
33 views

Countably infinite subsets of natural and real numbers

$ \{ x \} : x \in \mathbb{N}, x < 2^{20}$; $ \{ x \} : x \in \mathbb{N}, x > 2^{20}$; $ \{ x \} : x \in \mathbb{R}, x > 2$. Are any of these sets countably infinite? I would have said ...
1
vote
2answers
35 views

cardinality with finite sets

$A,B,C$ are finite sets. Suppose $A\subseteq B \subseteq C$ and $\#A=\#C$. Prove that $\#A=\#B$ and $\#B=\#C$. Should I prove this by showing that there exist an element in $A$ that exist in $B$ and ...
0
votes
0answers
7 views

Mapping indices to evenly use items from sets of different item count.

my problem is the following: Let's say I have 3 sets with different item counts (it might be the same though): Set 1: a a a Set 2: b b b b b Set 3: c c I know ...
0
votes
1answer
54 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 ...
1
vote
1answer
52 views

How to quickly determine which number is bigger than the other?

$$\{1,2,66,99\}\cup\{5,7,9\}=\{1,2,5,7,9,66,99\}$$ But if I have for example $$\{0,2,2\sqrt{2},2\sqrt{3}\}\cup\{\sqrt{5},\sqrt{7},2\sqrt{9}\}$$ Should I first find whose element is bigger than the ...
-1
votes
0answers
20 views

Suppose f:A to B. Suppose that C subset A and D subset B. Prove or give a counter example: f (c) subset D iff C subset f^-1(D) [on hold]

Suppose f:A to B. Suppose that C subset A and D subset B. Prove or give a counter example: f (c) subset C iff C subset f^-1(D)
0
votes
1answer
27 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, ...
2
votes
1answer
65 views

What does $\in$ mean?

I'm reading a textbook on complex analysis and I've come across notation using this ($\in$) symbol. In the context of "an argument of $z = x + iy$ is a number $\phi \in \mathbb R$ such that $x = ...
1
vote
2answers
38 views

Cardinality of $\lim_{k\to\infty}\mathbb N^k$ vs. $\mathbb N^\infty$

My friend and I are having a disagreement over whether the number of terms in the following series is countable or uncountable: $$\sum_{i=1}^\infty a_i + \sum_{i=1}^\infty\sum_{j=1}^\infty a_{ij}+ ...
0
votes
1answer
15 views

showing that if a function is a bijection, then there exists a an identity function

Let f:x-y be a bijection, show that foi =iof =f where i is identity function. I know that a bijection is one which is bith noe to one and onto. The problems is that the question is so trivial that I ...
-4
votes
1answer
60 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
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 ...
0
votes
1answer
41 views

Images of Functions and their Preimages

Suppose that $f: A \to B$ and suppose $C ⊆ A$ and $D ⊆ B$ Prove or give a counterexample: a) $f(C) ⊆ D \iff C ⊆ f^{-1}(D)$. This is true correct? b) If $f$ is injective then $f^{-1}(f(C)) = C$ ...
3
votes
1answer
42 views

Cardinality of of set surjection

Let $A$ and $B$ be finite sets. Prove there exists a surjection $f:A \to B$ iff $\#B ≤ \#A$ For this question, does the pigeonhole principle just prove it, or is there more needed? Edit: Also Can i ...
3
votes
1answer
31 views

Need help proving indexed family of sets questions

Need to prove the equality: $$ (\bigcup_{i\in I} A_i)-(\bigcup_{j\in J} B_j)=\bigcup_{i\in I}(\bigcap_{j\in J}[A_i-B_j]) $$ Any ideas on how to start? Thank you
1
vote
1answer
25 views

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 ...
0
votes
0answers
14 views

$\ K = \{ (1,1) , (2,1) , (3,1) \} f(R) = RK$

$\ M$ is the set of all relations on $\ A = \{1,2,3\}$ $\ K$ is the the following relation on A $\ K=\{(1,1),(2,1),(3,1)\}$ let there be $\ f :M\rightarrow M$ $\ f(R) = RK$ is f injective? ...
-1
votes
1answer
44 views

Symmetric Difference Quesions [on hold]

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
122 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
0answers
9 views

Going down from filters to sets for specific relations

Let $\mathfrak{A}$ be a bounded lattice. I call a $2$-staroid a relation $f\in\mathscr{P}(\mathfrak{A}\times\mathfrak{A})$ such that $i\sqcup j \mathrel{f} b\Leftrightarrow i\mathrel{f} b\vee ...
1
vote
1answer
20 views

Prove that if the relation (R) is symmetric and antisymmetric on the set X, there exists a Y subset of X such that R is the = relation on Y.

Prove that for any relation R on a set X that is both symmetric and antisymmetric, there is subset Y \subseteq X for which R is the relation = on Y. I will tell you what I know. I know that ...
0
votes
2answers
35 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
1answer
16 views

Set composed of operations on a Subset

Let there be a set P, and a set K such that $P\subset K$. Let there be 2 binary operations closed on K written $+$ and $\times$. Is there any way to define K as having only elements composed of ...
0
votes
0answers
11 views

Certain constructs on filters and on principal filters

Let $\mathfrak{X}$ be a lattice. I will call a set $S\in\mathscr{P}\mathfrak{X}$ a free star when the least element of $\mathfrak{X}$ is not in $S$ and $X\sqcup Y\in S\Leftrightarrow X\in S\vee Y\in ...
3
votes
3answers
36 views

union of cartesian products problem!

$$\bigcup_{i \in I}A _{i}\times \bigcup_{j \in J}B _{j} = \bigcup_{(i\times j) \in I\times J}A_{i} \times B_{j}$$ $$\bigcup_{k\in N} \mathbb{N}\times\{k\} = \mathbb{N}\times\mathbb{N}$$ i'm not yet ...
-1
votes
0answers
113 views

Construction of the field of real numbers within $ZF$ [duplicate]

I am interested in a problem whether the field of real numbers can be constructed within $ZF$. I will state the problem more precisely as follows. Definition 1 An ordered field $K$ is called ...
2
votes
0answers
22 views

Intuition - Countable iff Surjection iff Injection [Velleman P310 Thm 7.1.5] [duplicate]

Define $I_n = \{1, 2, ..., n \} $. Let $A$ be a nonempty set. TFAE : (i) $A$ is finite (ie: a bijection $h:A\rightarrow I_{N}$ exists) or A is countably infinite (ie: a bijection ...
1
vote
0answers
45 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|$.
0
votes
1answer
23 views

question about the axiom of choice [duplicate]

We know axiom of choice states that: Given any collection $\{ S_i : i \in I \} $ of nonempty sets, there exists a choice function $f: I \to \bigcup_{i \in I} S_i $ such that $f(i) \in S_i $ for all ...