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
36 views

Has this partition a name?

The decomposition in disjoint cycles in $S_n$ was inspiring for this question. I found out (if I did nothing wrong) that more generally a bijection $f:X\rightarrow X$ induces a partition of $X$ ...
0
votes
1answer
28 views

ordinal numbers addition property

I'm having trouble proving the following property of ordinal numbers. If $a, b, c$ are ordinal numbers such that $b \lt c$, then $b+a \le c+a$. I first started by assuming $g$ as an order ...
0
votes
1answer
25 views

Clarify Cartesian Products and Binary Operations

So tell me if I'm saying this write. A Cartesian Product is a function f:X x Y --> Z , where some unknown structural operation on the sets X and Y produces a set Z as its codomain, and Z is a set of ...
0
votes
1answer
29 views

Proving equivalence of Axiom of Choice

I am working on the following question concerning the axiom of choice and one of its many equivalences. Advice as to whether I am on the right track would be appreciated. As a preface, I have looked ...
5
votes
2answers
85 views

Why non-measurable sets exist?

What Is the reason behind the fact that $\Bbb R$ is not a complete measure space? Is it only due to the cardinality of $\Bbb R$? Or other structures on $\Bbb R$ also play a role? Can one make every ...
1
vote
4answers
44 views

The intersection of $3$ set is empty, would the intersection of $4$ sets be empty?

Let me clarify some more. Let's say we have four sets $A,B,C,$ and $D$. If the intersection of any three sets is empty, by default is the intersection of all four sets empty?
0
votes
0answers
15 views

Ingredients for Proving that a set is bounded below

I am having a hard time to really understand the definition of bounded below. The definition states : Let S be a nonempty subset of real numbers, we say S is bounded below if there is a c ∈ ℝ ...
0
votes
0answers
14 views

Fixed element $u \in U$ and subsets difference only at the $u$ point.

I have a task with a tip to it. The task: Let U - is not empty ultimate multitude. Prove, that number of subsets of the multitude U, with even power, same as how many subsets with odd power. ...
1
vote
1answer
41 views

How to show that set of strings of odd length in $\{a,b,c\}^*$ is countable?

Through diagonalization method, can I show that set of strings of odd length in $\{a,b,c\}^*$ is countable?
3
votes
1answer
57 views

If $f$ is injective and $g$ is surjective, is $g\circ f$ bijective?

Let $f:A\rightarrow B$ and $g:B\rightarrow C$. If $f$ is injective and $g$ is surjective, is $g\circ f$ bijective? I believe this is false, and have a counterexample. It was actually easier to ...
0
votes
1answer
57 views

Properties of preimages and intersections of sets

I am working through Bert Mendelson's "Introduction to Topology" and am having some trouble with proofs. The text in well presented but to get a proper understanding I am working through the ...
1
vote
1answer
39 views

Define finite ordered set using nested tuples

My book on set theory has this exercise: Define n-tuples so that 1) $(a_0) = a_0$ 2) $(a_0, a_1,...,a_n) = ((a_0, a_1,...,a_{n-1}), a_n)$ for all $n \geq 1$ I don't understand what I ...
1
vote
1answer
70 views

how to show a function is bijection

I have taken two numbers $p$ and $r$ where $p,r\in A = \{0,1,\ldots,4i + 1\}$ where $i\geq 1$ and $q\in B = \{0,1,\ldots,n-1\}$. Let $X$ contains all elements obtained by cartesian product of $A$ and ...
2
votes
2answers
73 views

Equivalence class for the relation of having the same set of prime divisors

For an integer $n\in \mathbb{N}$ define $P(n) = \{p : p \mid n \text{, where $p$ is a prime} \}$. For example $P(12)=\{2,3\} $ and $P(1)=\emptyset$. Question: Consider the relation $R$ on ...
1
vote
2answers
26 views

Measures: Sigma-Additivity vs. Continuity

Let $R$ be a ring of sets that contains the empty set and $\mu$ be a positive and finite set function on $R$. If $\mu$ is countable additive, then it is continuous from below and above: $$A_n\uparrow ...
-4
votes
0answers
17 views

Let (A,≼A) and (B,≼B) be partially ordered sets. [duplicate]

Let (A,≼A) and (B,≼B) be partially ordered sets. Define C = A×B and define the relation ≼' on C by (a,b)≼'(a′,b′) ⇐⇒ (a≼A a′)∧(b≼B b′). (a) Prove that ≼' is a partial order on C. (b) Prove that if a ...
-1
votes
1answer
23 views

Sets and set operations [on hold]

Answer the following with short explanation. We consider a set $X$. Recall that P(X) is the power-set of X. 1) If the size of $X$ is 5, what is the size of $P(X)$? 2) If the size of $P(X)$ is 1024, ...
1
vote
2answers
20 views

Discussion on Measures: Sigma-Additivity

Disclaimer: Though this thread is written in a Q&A style any new thoughts are really welcome! What reasons are there to restrict measures to countable additivity rather than uncountable ...
0
votes
2answers
20 views

Reflexive relation without mentioning the set it is on

I read from my book something like this: Let $R \subseteq A^2$ be a binary relation. If $R$ is reflexive, then... Saying that some relation is reflexive without mentioning the set it is on ...
3
votes
1answer
31 views

Which of the following are true and which are false? Let A = {0,1,2,3,4} and let B = P(A) (the power set of A) Confirm my answers.

Can someone confirm my answers? (a) 1∈A (c) {1}∈A (e) {1}⊆A (g) A∈B (b) 1∈B (d) {1}∈B (f) {1}⊆B (h) B⊆B ================================================== (a) is true because 1 is an element ...
0
votes
1answer
26 views

Understanding Index Sets

Definition in Wolfram: "A set whose members index (label) members of another set." I was just trying to figure out what index and label actually mean. Thank You
0
votes
1answer
20 views

Notation of list expansion to a tuple

I have a set $S$ that I want to expand to a $|S|$-tuple. How is the notation for that? Currently I have something like that: $$ T = (f(x) : x \in S) $$ An example: $$ S = \{A,B,C\}\\ T = (f(A), f(B), ...
3
votes
1answer
29 views

Direct proof of principle of transfinite induction

This is a problem from the book Set theory by You-Feng Lin. Principle of Transfinite Induction Let $(A,\le)$ be a well-ordered set. For each $x \in A$, let $p(x)$ be a statement about $x$. If for ...
1
vote
1answer
60 views

Countable Set & Formal Grammar

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. I try to summarize my though. I think the following proposition is true. suppose $\Sigma$ is arbitrary ...
2
votes
1answer
124 views

Multiple barber paradox

I'm having a little trouble formalizing the proof for this statement Suppose B is the set of barbers in a town who shave ALL those and ONLY those who DO NOT shave themselves I have to prove that the ...
2
votes
1answer
39 views

Equality of cardinality of $\mathbb{N}$ and $\mathbb{N} - \{0\}$

I have the sets $\mathbb{N}$ and $\mathbb{N}-\{0\}$. Clearly, $\mathbb{N}-\{0\}$ is a proper subset of $\mathbb{N}$, yet they have the same cardinality. That means that there exists a bijective map ...
0
votes
5answers
158 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 ...
1
vote
1answer
41 views

Why is the Kleene star of a null set is an empty string?

The articles and textbooks mention that, $\emptyset^\star = \{\epsilon\}$ The star operation puts together any number of strings from the language to get a string in the result. If the language ...
1
vote
2answers
50 views

Prove an addition property of Natural numbers

Prove: For any $x,y \in \mathbb{N}, y \neq x+y$. I'm only suppose to use the Peano axioms as defined here http://aleph0.clarku.edu/~djoyce/numbers/peano.pdf and the properties of addition in ...
2
votes
1answer
25 views

Sum of combinations of the n by consecutive k

In a book, I found that the sum of combinations: $\binom{n}{k} + \binom{n}{k+1} +\cdots+ \binom{n}{n}$, where k starts from 0, equals $2^n$. It is possible to express this statement via sum: $2 + ...
3
votes
1answer
58 views

Sum of Neighborhoods of Zero

When do two neighborhoods of zero over a topological vector space add up as: $$aN+bN=(a+b)N\quad a,b\geq 0$$ I could imagine something like balanced might suffice... The problem is that I'd like to ...
0
votes
3answers
120 views

Proof that the set of all functions from $\mathbb N$ to $\mathbb N$ is not enumerable

I'm trying to show that the set of all functions from $\mathbb N$ to $\mathbb N$ is not enumerable. Can someone verify my proof below? Proof: Let $\mathcal{F}(\mathbb{N}; \mathbb{N})$ be the set of ...
3
votes
1answer
51 views

What does $F = 2^W$ mean?

I'm reading the book Reasoning about uncertainty and having some problems with the notation. $F = 2^W$ where $W$ is a set and $F$ an algebra. What this mean?
-2
votes
2answers
98 views

How do i construct $C^\infty$?

I'm trying to define $C^\infty$ rigorously and i have a trouble with this. Mathematical Induction should be used, but i dunno where to apply this. I'm going to illustrate what i tried below: Before I ...
1
vote
1answer
55 views

Regarding open subsets in topology

(Probably due to my lack of experience with the subject, I see that my question is horribly written. If you are to answer, a beginner-friendly explanation of the basis of a topology and the topology ...
0
votes
1answer
42 views

How to write the union of sets

This is just a question about notation(and I can not write it pretty well in Latex either). Is $X=(0,+\infty)\subset\Bbb{R}$ and $Y=\Bbb{R}$. Then $X\times Y= (0,+\infty)\times \Bbb{R} =$ ? ...
3
votes
4answers
49 views

Show $P\left(A-B\right)=P\left(A\right)-P\left(A \cap B \right)$

I'm trying to show that, given two events $A,B \in \Omega$ ($\Omega$ is a sample space): $$P\left(A-B\right)=P\left(A\right)-P\left(A \cap B \right)$$ I know $A-B = A \cap B^C$, but I don't know how ...
1
vote
2answers
56 views

About well formed formula

Axiom of specification is schema because it talks about definite condition(or wff) which use notion of finite but this again we define from sets. But in logic we defined wff using consept of tuple and ...
2
votes
3answers
73 views

Is this proof correct? Injective function $ f: A \rightarrow B \iff $ function $ g: B \rightarrow A $ is surjective

I've begun a course in "Real Analysis" recently and I have this trivial exercise. Could someone check if my proof is correct? Proposition: There exists Injective function $ f: A \rightarrow B \iff $ ...
1
vote
1answer
21 views

In general, are subsets of recursively enumerable sets recursive sets?

I recently became interested in the solution to Hilbert's tenth problem, in reading about the succession of results that lead up to the proof I came across the notion of recursive sets and ...
1
vote
1answer
21 views

Composition of Ordered Pair

I'm doing math exercises from a Computer Science book and I am confused as to how the following result (from the solutions manual) is obtained: Given the function f={(a,b), (a,c), (c,d), (a,a), ...
2
votes
1answer
90 views

Defining a partial order on $A\times B$, given partial orders on $A$ and on $B$

Let $(A,\preceq_A)$ and $(B,\preceq_B)$ be partially ordered sets. Define $C = A \times B$ and define the relation $\preccurlyeq$ on $C$ to be $(a,b) \preccurlyeq$ $(a',b')$ if and only if ...
0
votes
0answers
24 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 ...
7
votes
1answer
82 views

Graphs with uncountably many vertices

Let $ \mathcal{H}$ be the class of all graphs with at most $ 2^{\aleph_0}$ vertices not containing a complete subgraph of size $ \aleph_1$. Show that there is no graph $ H \in \mathcal{H}$ such that ...
2
votes
1answer
59 views

Two Definitions of Infinite Cartesian Product

In my one of lecture notes, there are two definitions of infinite Cartesian product, and it reads that we can construct a unique bijection between them. One way to define an infinite Cartesian ...
-1
votes
2answers
46 views

Question regarding cartesian product

Suppose $\bigl\{(x,y)\mid x^2+y^2<1\bigr\}$ is a subset of $\Bbb R\times\Bbb R$, where $\Bbb R$ is the set of real numbers. Is the given set also the cartesian product of two subsets of ...
2
votes
3answers
264 views

Cardinality of the set of all two-element subsets of $\mathbb{N}$

Consider the set $\mathbb{N}$ of all natural numbers; we can assign each natural number a point on a single axis. Let $A$ be the set of all of these points; $A$ is a countable set (we can assign each ...
0
votes
0answers
15 views

Proof of a variation of Hausdorff maximality principle

Let ($A$, $\le$) be a partially ordered set and let $B$ be a totally ordered subset of $A$. Prove that $A$ has a maximal totally ordered subset $C$ such that $B \subset C$. I'm trying to prove this ...
5
votes
5answers
495 views

Why is that *any* union of open sets is open but only *finitely many* intersections of open sets is open?

I understand that when we talk about union of open sets, we introduce an index set which can be countable or uncountable. But could I not do the same for the intersection of open sets too?
0
votes
3answers
77 views

What is $X^{\omega}$ where $X$ is a set?

I fail to find a duplicate. If it exists, please link me in the comments and I will delete the question. In my recently bought topology book, they use $X^{\omega}$ where $X$ is a set. However, this ...