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
1answer
28 views

Choice function to obtain all elements of an infinite set

I'm following a proof of "Axiom of Choice implies Well Ordering Theorem" (from a not-well-known book we use for class), and the author uses this procedure: First, he takes any non-empty set $X$ and ...
-5
votes
2answers
31 views

How many elements in a set?

Suppose m and n are positive integers with m < n. How many elements does {m, m + 1, . . . , n} have? I know that there is a theorem that says you can figure out how many elements in a given set by ...
1
vote
0answers
17 views

showing that the sets (Banach-Tarski-ish) which comprise $S^1$ are disjoint

Let $S^1$ be the unit circle and consider $S^1 = \cup_{q \in \mathbb{Q}} A_q$ where the sets $A_q$ are constructed as follows: Define the equivalence relation $z \sim w$ if for $z = e^{i\alpha}, w = ...
0
votes
1answer
32 views

What does it mean for a binary relation to be an order on “equivalence classes” under another binary relation

I am a bit confused about this statement in "Introduction to Set Theory" by Hrbackek and Jech. The statement is as follows: "|A| <= |B| behaves like an ordering on the "equvivalence classes" under ...
0
votes
1answer
72 views

What are sets and classes in maths, and how are they related to $O()$ and $o()$ notation?

Are there many definitions of sets and classes in mathematics, as given in Formal definion of the notations used in measuring time complexity? And in particular, why the notation given in Fedja's ...
3
votes
2answers
20 views

Curious identity involving symmetric difference

While studying the properties of measurable null sets, I found the following identity: $\bigcup_i B_k\triangle B_i=\bigcup_i B_i - \bigcap_i B_i $ Or in other words, the value of the expression is ...
1
vote
1answer
38 views

Proof of one instance of the Axiom of Choice from another.

I'm trying to show (i) $\implies$ (ii): (i) For any relation $R$, there exists a function $H\subseteq R$, with $\newcommand{\dom}{\mathrm{dom} \ } \dom H = \dom R$. (ii) For any set $I$ and any ...
-1
votes
3answers
41 views

Elements in $F=\bigcup \limits_{n=1}^\infty \left(\bigcap \limits_{k=n}^\infty E_k\right)$

let S be set with subsets $ E_1,E_2,E_3,....$ Show that: a) $F=\bigcup \limits_{n=1}^\infty \left(\bigcap \limits_{k=n}^\infty E_k\right)$ consists of all elements of S each of which belongs to all ...
0
votes
1answer
26 views

Ordinal multiplication property: $\alpha<\beta$ implies $\alpha\gamma\le\beta\gamma$

I'm having trouble proving the following two ordinal multiplication properties. If $\alpha, \beta$, and $\gamma$ are such that $\alpha \lt \beta$ and $\gamma \gt 0$, then $\alpha\gamma \le ...
1
vote
1answer
35 views

Tails sets are Borel

I am trying to proof a particular case of Kolmogorov's law in the set E of infinite binary sequences. Eventually, I'm supposed to prove that a certain type of subsets of this set is in the Borel sigma ...
0
votes
2answers
35 views

the smallest transfinite ordinal number

My guess is that $\omega$ is the smallest transfinite ordinal number. To prove this, let $\beta$ be any transfinite ordinal number and let $\operatorname{ord}(B, \le)= \beta$. And I need to show that ...
0
votes
0answers
45 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$ ...
2
votes
2answers
47 views

Ordinal numbers addition property: $b<c$ implies $b+a \le c+a$

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
41 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 ...
1
vote
1answer
40 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
92 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
50 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
15 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
60 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
58 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
47 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
75 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
74 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
28 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
28 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
21 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
21 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
62 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
138 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
42 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
54 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
59 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
123 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
54 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
100 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
57 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
43 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 $ ...