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

1
vote
2answers
73 views

Proof Explanation (Zorn's Lemma)

1.13 Theorem The following statements are equivalent: (a) (The Axiom of Choice) Them exists a choice function for every. of sets. (b) (The Well-Ordering Principle) Every set can be ...
0
votes
2answers
24 views

If ${p_{n}}$ is a sequence in a compact metric space $X$, then some subsequence of ${p_{n}}$ converges to a point of $X$.

This has been proved in Rudin, but I am trying a different approach. Please suggest me how to prove this with my approach. I have done till the following. Since $X$ is compact, every open cover of ...
0
votes
0answers
29 views

I am having difficulty solving problem on function

I am having hard time solving this question. I am very weak on functions. If someone can help me in solving this, it would be appreciated.
-4
votes
0answers
29 views

Union and intersection of two pairwise disjoint families of sets [closed]

Let $\mathscr{A}$ and $\mathscr{B}$ be two pairwise disjoint families of sets. Let $\mathscr{C} = (\mathscr{A} \cap \mathscr{B})$ and $\mathscr{D} = (\mathscr{A} \cup \mathscr{B})$. (a) Prove that ...
1
vote
1answer
37 views

Compactness of binary sequences metric space

Define a metric space $(X, d)$ as follows. The points in $X$ are all infinite sequences of $0$s and $1$s. Given two distinct sequences $\{p_n\}$ and $\{q_n\}$ in $X$, $d(\{p_n\}, \{q_n\}) = ...
5
votes
4answers
88 views

Is $[a, a)$ equal to $\{a\}$ or $\varnothing$?

Let us define the set $[a,b) = \{ x \in \mathbb{R}: a\le x <b\}$ Is $[a, a)$ equal to $\{a\}$ or $\varnothing$?
-1
votes
1answer
16 views

Symmetric Difference of a Triplet of Sets

I am doing set theory out of interest and am stuck on the following question: Show that: Z \ (X Δ Y) = [Z \ (X ∪ Y)] ∪ ( X ∩ Y ∩ Z) My approach: Beginning with the RHS: [Z \ (X ∪ Y)] ∪ ( X ...
-4
votes
1answer
21 views

Question about this set determination

I dont have a clue how to approach this question and my book isn't clearing it up either. Also, how would one attempt this if it would be a union instead of intersect?
0
votes
0answers
24 views

How to find union and intersection of events?

I have sample space of experiment $S=\left\{x|-\infty<x<\infty\right\}$. I consider events $$A_i=\left\{x \;\middle|\;\frac{1}{2^{i-1}}\le x<\frac{3}{2^i}\right\};i=1,2...$$ And I want to ...
0
votes
1answer
12 views

Is an image of a function f for Dom(f) always equal to Rg(f)?

Let's look at the definition of an image of some function $f: A\rightarrow B$. An image of a function $f$ for some subset $X\subseteq A$ is $\{b\in B \text{ | }f(x)=b \text{ for some } x \in X\}$. ...
2
votes
2answers
60 views

Can $f:\Bbb{N}\rightarrow\Bbb{N}$ return an empty set?

I have a function $f:\Bbb{N}\rightarrow\Bbb{N}$. An empty set is not a member of $\Bbb{N}$. Can $f$ still return an empty set for some arguments $x\in\Bbb{N}$?
1
vote
2answers
24 views

Cardinality of the set of irrational numbers which is connected subset of rational numbers

Let X be a connected subset of real numbers. If every elements of X is irrational then what is the cardinality of X? We know cardinality of irrational numbers is same as the cardinality of real ...
1
vote
2answers
26 views

One one & Onto functions

Are there one one function from the set $A$ to the set $B$? Are there onto function from the set $A$ to the set $B$? Where $A=\{x^2 :0<x<1\}$ and $B=\{x^3:1<x<2\}$.
1
vote
2answers
76 views

Is everything right in this set-theory problem?

I've got a following homework to solve: $f:\Bbb{N}^\Bbb{N}\rightarrow \mathcal P(\Bbb{N})$ is such a function that $f(\phi)=\phi(\Bbb{N}). $ Is $f$ bijective? Find $f^{-1}(B)$ where $B$ is a set of ...
2
votes
2answers
34 views

What is $\{v_0:(\lnot(v_0=v_0))\}$?

I'm going through this set of notes to try to learn a bit more about set theory, because, while I've often encountered papers that use concepts from set theory, I've never actually studied it. I'm ...
0
votes
4answers
57 views

Cardinality of sets of functions

Show that the set $A$ of all functions $f:\mathbb{Z}^{+} \to \mathbb{Z}^{+}$ and $B$ of all functions $f:\mathbb{Z}^{+} \to \{0,1\}$ have the same cardinality. I am having trouble to define a ...
2
votes
1answer
25 views

I have a question about a proof I am doing with partial ordered sets.

$L$ is a partially ordered set in which every subset has a least upper bound. Suppose that $L$ has a bottom element. Prove that $L$ is a complete lattice. I understand that I need to show that any ...
1
vote
0answers
19 views

If relation $R$ is not well-founded is then at least one of these conditions satisfied?

Let $R$ be a relation (or a class of ordered pairs) and call $R$ well-founded if any nonempty set $B$ contains an element $b\in B$ such that $B\cap\left\{ a\mid aRb\right\} =\emptyset$. Here $aRb$ ...
1
vote
1answer
68 views

Using the Cantor-Bernstein theorem

I'm working through Kolmogorov and Fomin's Introductory Real Analysis text, and I came to a question about showing that some sets have the same power as the continuum. I have seen this question posted ...
0
votes
1answer
70 views

Is every chain a lattice?

I am asked to prove that every chain is a distributive lattice. Is it true that every chain is a lattice? I am told that a chain is a poset where we can compare any two elements. A lattice is a ...
0
votes
0answers
20 views

A question about equivalence relations.

Let $A$ be a non-empty set, and $\rho$ an equivalence relation on $A$. Let $a, b \in A$. Prove that $[a] = [b] \iff a \mathrel\rho b$.
1
vote
1answer
43 views

Comparing cardinalities

Why these two sets are equinumerous? $$[0,1]^\Bbb N\text{ and }\Bbb Q^\Bbb N$$ Here is my reason: The set of rational numbers $\Bbb Q$ is countably infinite. However, $[0, 1]$ is not countable and ...
0
votes
3answers
24 views

Cardinality of Power Functions Question

How many elements does each of these sets have where $a$ and $b$ are distinct elements? $$\wp(\{a,b,\{a, b\}\})$$ and $$\wp(\wp(\wp(\varnothing)))$$ I cannot understand how the power function ...
0
votes
1answer
80 views

Measure Atoms: Definition?

Let $\Omega$ be a measure space with measure $\mu$. (Here, a measure is only meant to be countable additive!) Consider a subset $A\in\Sigma$. Then according to the wikipedia article it is an atom ...
0
votes
1answer
72 views

Basic set theory - discrete mathematics

Please help me with this question! I've always thought that if xy = z, then x or y must be a factor of z and so doesn't that mean all values of n are possible where at least one of the numbers is a ...
0
votes
1answer
40 views

Union of a finite number of open sets is open or not? Proper usage of this fact a proof

I received a homework assignment back and I was given full credit on the following proof: Let $S = \{ (x,y) \in \mathbb{R}^{2} | x \geq 1 $ and $ y \geq 1 \}$. Is $S$ closed? My proof is below ...
1
vote
1answer
54 views

Showing a set is a subset of another set

I need to show that $(A \cup B) \subseteq (A \cup B \cup C)$ My Work So Far: What I really need to show is that $x \in (A \cup B)$ implies $x \in (A \cup B \cup C)$ So I translated my sets into ...
1
vote
1answer
35 views

to count the intervals

A finite set of two or more consecutive natural numbers is called a "co-prime interval" if there is no number in it that is co-prime to all other numbers in the set. Given a range [A, B], I would ...
1
vote
0answers
49 views

Can we have calculus without axiom of choice [duplicate]

Do we need axiom of choice for all the theorems studied in basic courses like calculus 1 and linear albgebra? could we build this theory just by using ZF axioms?
1
vote
0answers
18 views

'Function may not necessarily use all elements of specified range'?

In a textbook on the theory of computation, I encountered a passage which states: The outputs of a function come from a set called its range... In the case of the function abs, if we are working ...
4
votes
8answers
77 views

Null Sets $\{\{\emptyset\}\} \subset\{\emptyset, \{\emptyset\}\}$

Regarding null sets, I'm wondering if anyone can explain this $\{\{\emptyset\}\} \subset \{\emptyset, \{\emptyset\}\}$ I don't understand how the left set is a proper set of the right set. In ...
0
votes
1answer
34 views

$P=(m,n)$, $Q=(h,j)$. Prove that $P\subseteq Q$ iff $h\leq m\leq n\leq j$

$P=(m,n)$, $Q=(h,j)$. Prove that $P⊆Q$ iff $h≤m≤n≤j$ I have no idea about how to prove it, does anyone could help me? Thanks!
5
votes
2answers
398 views

Proving that the empty set is unique

I haven't been able to figure out if the following reasoning is correct, so I'd like to have the opinion of other people on that. The goal is to prove that the empty set is unique. In order to do ...
1
vote
6answers
119 views

What is a “formal definition” of a set?

I'm to find a formal definition of a certain set, but I'm unsure what it means by "formal definition" (in relation to Discrete Maths) A quick google search didn't seem to help me much. Can anyone ...
1
vote
0answers
26 views

Comprehending ordinals: from $\omega^\omega$ through $\omega^{\omega^2}$ to $\varepsilon_0$

I am currently trying to comprehend ordinal numbers by finding an order on some countable set (like natural numbers or tuples of natural numbers) that is isomorphic to some ordinal. For an instance, ...
0
votes
1answer
21 views

Cardinality of the set of all indicator functions

Let's say we have two sets X={A,B,C} and Y={0,1}. We are trying to find the cardinality of the set of all functions from X to Y. From my understanding, this is supposed to be equal to the size of the ...
0
votes
0answers
22 views

Prove that the set is countable [duplicate]

Question: We call a real number $x$ $algebraic$ if $x$ is the root of a polynomial equation $c_{0}+c_{1}x+...+ c_{n}x^{n}$ where all $c_{i}$'s are integers. For example $\pm \sqrt{3}$ are algebraic ...
0
votes
2answers
178 views

Discrete Mathematics Sets. ∀x∀y(xy ∈ nN) =⇒ (x ∈ nN ∨ y ∈ nN).

Let N = {0,1,2,3,...} be the set of natural numbers. For a number n let nN denote the set of all multiples of n, i.e. nN = {nx : x ∈ N}. For each integer n consider the proposition p(n) given by ...
0
votes
0answers
34 views

Lists of small lattices and posets

Does any one know where I can find a table that lists, up to isomorphism, all the lattices for a set with small order? and the same thing for how many posets can be formed from a set with small order. ...
1
vote
1answer
21 views

Property of symmetric set difference

Let $A \Delta B$ represent the symmetric difference of $A$ and $B$ (i.e. $A \Delta B = (A \cap \bar{B}) \cup (\bar{A} \cap B)$). The following property of $\Delta$ is known: If $A \Delta B = A \Delta ...
0
votes
2answers
26 views

Union of Set Differences

I'm trying to think of a counterexample to the equality A \ (B ∩ C) = (A \ B) ∪ (A \ C) I keep drawing various combinations of 3 circles intersecting (or not intersecting) to no avail.
10
votes
6answers
622 views

Can a countable group have uncountably many subgroups?

If $G$ is a countable group,can it have an uncountable number of distinct subgroups?
2
votes
4answers
44 views

Help with Subset Problem

So I'm "supposed to show that": $(A \cup B) \subseteq (A \cup B \cup C)$. For $(A \cup B)$, $x \in A \cup B$ and therefore $x \in A \lor x \in B$. For $(A \cup B \cup C )$ , $x \in A \cup B \cup C$ ...
0
votes
2answers
33 views

Need help in proving combinatorial identity involving unions, intersections and complements over sets using induction

The identity is the following: $$\left(\bigcap_{i=1}^n (A_i\cup B_i)\right)^C = \bigcup_{i=1}^n (A_i^C\cap B_i^C)$$ I must use induction to prove it. Base. Ok, I think I got how to prove base case: ...
0
votes
2answers
27 views

Transitivity of a relation [closed]

Is the relation {(1,2)(3,4)(5,6)} is a transitive relation. I have found in many references and ncert text that it is transitive. Give reason for u r answer.
3
votes
1answer
46 views

Is it possible to define a map from $\aleph_0$?

In an assignment question I am asked to show that the cardinality of the set of all functions from $\mathbb{N}$ to $\mathbb{N}$ is equal to $2^{\aleph_0}$. To proceed with my proof I am trying to ...
0
votes
2answers
27 views

The cardinalities [duplicate]

I have some difficulties to resolve a problem. Could you explain me why this sets: $[a,b]=[c,d]$,where $a,b,c,d \in\mathbb{R}$ with $a<b$ and $c<d$ have the same cardinalities? thanks
3
votes
1answer
50 views

Is the following a semiring?

I have the following problem: Let $f: X' \rightarrow X$ be any map and $\mathcal{H} \subseteq \mathcal{P}(X)$ a semring. Is $f^{-1}(\mathcal{H})$ a semiring? Thanks for your help!
0
votes
1answer
69 views

Geometrical description of cantor set is uncountable

Why is Cantor set uncountable? I would like to intuitively understand the uncountable nature of Cantor set. When I construct Cantor set I do not feel so.
0
votes
1answer
34 views

Prove the following $\neg((A\cap B)\cup (\neg A \cap C)) = (A\cap\neg B)\cup (\neg A\cap \neg C)$ [duplicate]

How can I prove the following statements are equivalent using laws of set theory? $\neg((A\cap B)\cup (\neg A \cap C)) = (A\cap\neg B)\cup (\neg A\cap \neg C)$ Using De Morgans laws to simplify the ...