This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, ...

learn more… | top users | synonyms

2
votes
1answer
64 views

Hartogs space of $\mathbb{N}$

Suppose : $U=\chi(\mathbb{N})$ is the Hartogs space of $\mathbb{N}$. $(M_a)_{a\in U}$ a family of infinite subsets of $\mathbb{N}$ such that $a<b \rightarrow M_b\subseteq M_a$. I'm trying ...
0
votes
1answer
103 views

Use of Cantor Schroder-Bernstein theorem?

Use the Schröder-Bernstein theorem to show that there is a bijection between two intervals $[0,1]\subseteq \Bbb R$ and $[1,\infty)\subseteq \Bbb R$, thus they have the same cardinality. What ...
1
vote
1answer
207 views

Characteristic function of union of two sets formula and intuition

From http://topologicalmusings.wordpress.com/2008/03/20/inclusion-exclusion-principle-counting-all-the-objects-outside-the-oval-regions-2/ Is there an easier proof or way to calculate $1[A \cup ...
1
vote
1answer
29 views

Trying to understand an equality between sets

Consider the following equivalence class: $${[\mathbb{N}]_s} = \{ A \in P(\mathbb{Z}) : |A| = |A \cup \mathbb{N}| \wedge |\mathbb{N}| = |A \cup \mathbb{N}|\} $$ So, $A$ must be infinite set with the ...
1
vote
1answer
276 views

Largest infinite cardinal used in a proof

I've heard before that Knuth holds the record for the largest constant used in a mathematical proof. I was wondering what is the largest cardinal ever explicitly considered in set theory. I presume ...
1
vote
1answer
36 views

Why is it true that Max(X) = Min(-X) for a group X composed of numbers in Z

I'm looking for a formal explanation that won't involve calculus (if possible) that would explain why for every group of numbers X (such that all numbers in X are integers), Max(X) = Min(-X) (where -X ...
1
vote
2answers
46 views

Statements about attributes of given function.

Let $HF(0) = \emptyset$. $HF(n+1) = P_\omega(HF(n))$, where $P_\omega(A)$ - set of all finite subsets of $A$, and $HF = \displaystyle\bigcup_{n\subset\omega}HF(n)$. Are those statements true? ...
1
vote
2answers
68 views

Question about filters.

Conceptually, I am thinking that the existence of an initial finite set on which the entire filter $F$ is built means that every other arbitrary set $B\in F$ contains the initial set $A$. Then it ...
4
votes
2answers
147 views

Induction without base case?

I'm doing a bit of research on set theory. So far it's quite interesting. Right now I'm reading about transfinite induction. The book states the following theorem about induction in a well-ordered ...
1
vote
1answer
88 views

Well ordering of type epsilon one

I have been very interested in the countable ordinals for awhile now, but one thing has eluded me despite my research into the subject. What is a well-ordering of the natural numbers corresponding to ...
2
votes
1answer
173 views

Equivalence relation question with cardinality and countability $A=\mathbb R,\ aSb \iff a-b\in \mathbb Q $

Let $A=\mathbb R,\ aSb \iff a-b\in \mathbb Q $ What is the cardinality of $[\pi]_S$ ? Prove that the quotient group $\mathbb R/S$ is uncountable. Well I think that cardinality is ...
1
vote
1answer
186 views

Countability and uncountability of a set $A$ and the set of equivalence classes $A / R$

Let $A$ be a set and $R$ an equivalence relation on $A$. Prove or disprove: If $A$ is countable then all the equivalence classes of $R$ are countable. If $A$ isn't countable then the ...
3
votes
2answers
141 views

Intuition/How to determine if onto or 1-1, given composition of g and f is identity. [GChart 3e P239 9.72]

9.72. $A,B$ are nonempty sets. $f: A \rightarrow B$ and $g: B \rightarrow A$ are functions. Suppose $g \circ f = $ the identity function on $A$. (♦) Are the following true or false? $1.$ $f$ ...
0
votes
1answer
15 views

A criterion for complete lattice.

Is there an infinite partially ordered set $(X,\le)$, in which for each $A\subseteq X$, either $\inf A$ or $\sup A$ exists but for some $A\subseteq X$ either $\inf A$ or $\sup A$ does not exist.
1
vote
1answer
59 views

How many complete theory extend theory T are there?

$Т$ - theory of signature $\{\le\}$, defined by the axioms А1-А5: А1: $\forall x(x=x)$ А2: $\forall x,y\big((x\le y\land y\le x)\to x=y\big)$ A3: $\forall x,y,z\big((x\le y\land y\le z)\to x\le ...
2
votes
1answer
201 views

Condition For A Set Having A Smallest Element

I am reading the second part of the prolouge of Spivak's Calculus. In the text, he proves the Well-Ordering Principle. Here is a sentence from the book: Suppose that the set A has no least member. ...
5
votes
4answers
381 views

Mustn't a function map every element of its domain to range (but not codomain)? [Richard Hammack, P228]

How to Prove It, D Velleman P226, P228: Suppose $f$ is a relation from $A$ to $B.$ Then $f$ is a function from $A$ to $B$ means: $\forall \; \color{#009900}{a \in A}, \exists \; ! \; b \in ...
1
vote
2answers
71 views

Set of elements that don't belong to any power set of these elements [Chartrand P242 10.22 2nd Ed = 10.30 3rd Ed]

How and why is the answer $B = A_d$ ? I thought : Because $A := \{a, b, c\} \neq \{d, e, f, g, h\}$, thus $B = \bigcup_{i\in \{d, e, f, g, h\}} A_i$. Supplementary dated Dec 12 2013: By the ...
1
vote
1answer
552 views

Proving that $f(A+B)=f(A)+f(B).$

Let $X$ and $Y$ denote magmas, and suppose $f : X \rightarrow Y$ is homomorphism. Then I think that for all $A,B \subseteq X$, we have $f(A+B)=f(A)+f(B).$ However, I'm not happy with my: Proof. The ...
4
votes
1answer
184 views

Writing $(a,b)$ as a disjoint union of closed intervals [duplicate]

I've been thinking about the following question: Is it possible to write $(a,b)$ as a disjoint union of closed intervals? My first guess was no, but then I figured the question might be hiding ...
1
vote
1answer
22 views

Can computing the reflexive closure of the transitive closure of a relation add more properties than just reflexivity?

If we have the transitive closure of R, R+, and we then compute the reflexive transitive closure of R, which is R*, will the resultant set/relation ever have any additional properties other than ...
6
votes
1answer
68 views

Deleting intervals from $(0,1):$ what is the resulting set?

Take the open interval $(0,1)$. Split into thirds and consider only the open intervals at each end. We are left with: $$\big(0,\tfrac13\big)\cup \big(\tfrac23,1\big)$$ For each of these: Split ...
2
votes
1answer
55 views

Why do we need “alphabets” defined?

I'm reading over my computational theory book before quarter starts and it's giving me the following definitions. alphabet: any nonempty finite set symbols: members of the alphabet I ...
2
votes
1answer
54 views

Induced relations

I have question on relations: Let $R \subseteq X \times X$ be any relation on $X$, and define $\sim$ to be the intersection of all equivalence relations in $X \times X$ that contain $R$. Show that ...
1
vote
1answer
35 views

Show that $\mathbb P$ is finitly additive and that $\mathcal A$ is an algebra

Given $\mathcal F=\{A \subset\Omega \mid A \mbox{ or } A^c \mbox{ is finite}\}$, show that $\mathcal F$ is an algebra. Second, set: $\mathbb P(A) = \begin{cases} 0, & \mbox{if } A \mbox{ is ...
2
votes
1answer
76 views

Collection of subsets of Naturals with containment

Question: Let $S$ be a collection of subsets of $\Bbb N$ such that for every $A, B \in S$ we have $A \subset B$ or $B \subset A$. Can $S$ be uncountable?
0
votes
2answers
75 views

how to understand that products and coproducts are dual

I am reading some basic category notes, how can one relate the products to coproducts? If given a product, can one build its dual product? for example, the coordinate product $(x,y)$ : $ R \times R$, ...
2
votes
1answer
57 views

Every woset is an ordinal.

I use this notation: a well ordered set $Y$ is an ordinal if for every $a\in Y$, $Y_a=a$, where $Y_a=\{y\in Y|y< a\}$. Now, I know that for every woset there is an isomorphism from that woset to a ...
2
votes
2answers
251 views

Uncountable family of pairwise disjoint discs/circles

Show that there does not exist an uncountable family of pairwise disjoint discs in the plane. What happens if we replace ‘discs’ by ‘circles’?
1
vote
1answer
55 views

Is a non empty set (not containing $\emptyset$) and its power set disjoint?

Or do there exist sets $x,y\neq \emptyset$ so that $x\in y$ and $x\subseteq y$? I think that such sets do not exist and tried to prove it using the regularity axiom as in another question; this does ...
1
vote
1answer
55 views

Quotient group with functions and relations question

For the set $\mathbb Z/5 \mathbb Z $ (the quotient group of $\mathbb Z$ with the relation R that is defined by $xRy$ if $5|y-x$) We'll define the following operations (both are $\cdot, +$ ...
3
votes
3answers
404 views

Equivalence relation question with functions

We'll define on the set: $A=\Bbb R^{[0,1]}$ the relation $R$ by $fRg$ if $f(0)=g(0)$. Make sure it's an equivilence relation. What is $[\cos x]$ ? Describe all the equivalence classes ...
7
votes
1answer
261 views

How to prove that $\mathbb{Q}$ is not the intersection of a countable collection of open sets.

I am reading chapter 4 of Jech - Set Theory and trying to solve question 4.14, in which we are asked to show that: $\mathbb{Q}$ is not the intersection of a countable collection of open sets. The ...
0
votes
1answer
159 views

Set inclusion relation ⊇ on power set [closed]

I am creating the set inclusion relation ⊇ from a power set, A. If my relation creates tuples with the following format, (x, y), will y ever be the empty set, {}? Example: Set A = {x, y, z} Power ...
0
votes
2answers
1k views

Power Set of set containing the empty set and a set as an element

I'm just a little confused on the nuances of power sets. I'm looking for the power set of the following set: $\{\varnothing, a, \{a\}\}$
0
votes
2answers
72 views

Is this set countable? Verify me. Simple question. Basic set theory

Basic set theory question, I think I have the answer but I would like someone to double check it please. let $R$ be an equivalence relation defined on $\mathbb N^{\mathbb N}$ such that: ...
2
votes
4answers
212 views

Book suggestion on set theory/logic

Can anyone recommend good books/tutorials on set theory/logic with simple explanations for a person with no math background (nothing beyond arithmetic and basic algebra back in school)?
4
votes
4answers
118 views

Is the collection of finite subsets of $\mathbb{Z}$ countable?

The collection of all subsets of $\mathbb{Z}$ is uncountable, due to Cantor's theorem But how can I prove that the collection of all finite subsets of $\mathbb{Z}$ is countable?
3
votes
3answers
325 views

Bijective function between $\mathbb Q$ and $\mathbb Q\ge 0$

I have to prove that $\mathbb Q$ and $\mathbb Q \ge 0$ have the same cardinality. In order to do this I need to create bijective function between these sets. And I need help with this. I can't come up ...
6
votes
5answers
737 views

Is the set of decreasing functions from $\Bbb N$ to $\Bbb N$ countable?

I want to prove the set of decreasing functions from $\Bbb N$ to $\Bbb N$ is countable. I considered a decreasing function, $f$, with a least element, $n$, and let $x$ be the smallest number such ...
1
vote
2answers
65 views

Principle of Proof by Induction on a Well-ordering

Let $(X,\leq)$ be a woset (well ordered set). Let $E$ be a subset of $X$ such that: (i) the smallest element of $X$ is a member of $E$ (ii) for any $x\in X$, if $y<x\rightarrow y\in E$, then ...
1
vote
3answers
90 views

Proof that $(a, b) \mathrel{R} (c, d)$ iff $ad = bc$ is an equivalence relation

Let $X = \{(a,b) \mid a,b \in \Bbb Z; b \ne 0\}$. We define $(a,b)\mathrel R (c,d)$ iff $ad = bc$. Prove that $R$ is an equivalence relation on the set $X$. Which known set do the equivalence classes ...
1
vote
1answer
458 views

Set of increasing/Decreasing functions

A function f : N → N is increasing if f(n + 1) ≥ f(n) for all n and decreasing if f(n + 1) ≤ f(n) for all n Is the set of increasing functions countable or uncountable? What about the set of ...
2
votes
1answer
93 views

prove that $\Bbb{Z \times ((0,1]\cap Q)}$ and $\Bbb Q$ have the same cardinality

I have to prove that $\Bbb{Z \times ((0,1]\cap Q)}$ and $\Bbb Q$ have the same cardinality. I think I have bijective function($f(\langle a,b\rangle)=a-b$) between thse sets, but I don't know how to ...
1
vote
2answers
458 views

Is there an injection from the set of all real sequences to R? [duplicate]

Is there an injection from the set of all real sequences to R?
0
votes
1answer
54 views

Image of the set of natural numbers under any function is denumerable.

Hi everyone I'd like to know if the following reasoning is correct, any suggestion would be great. Thanks. Proposition: Let $Y$ be a set and let $f: \mathbb{N}\rightarrow Y$ be a function. Then ...
2
votes
2answers
77 views

Sets question on intersection of infinite sets

Let $A_1,A_2,\ldots$ be sets such that for each $n$ we have $A_1\cap\ldots\cap A_n \ne\varnothing$. Can we have $$A_1\cap A_2 \cap\ldots = \varnothing\;?$$ This question should be easy as its an ...
0
votes
3answers
52 views

How many of $A\subseteq B$ are true for a set of $n$ elements

Let U be the set $\{1, ,2 ,...,n\}$. This set has $2^n$ subsets. So there are $2^n \cdot 2^n = 2^{2n}$ possible relations of the form $A\subseteq B$. I'm wondering how many of them are true. Since ...
3
votes
2answers
133 views

How to solve such problems ${]}{-}\infty,2{[}\cup{]}{-}3,5{[}$

How to solve such problems ${]}{-}\infty,2{[}\cup{]}{-}3,5{[}$ ? Should I just write the result directly or derive it (how?) ? Also is it sufficient to show that on a number line and then conclude ...
0
votes
1answer
33 views

how many pairs differ in one value from another

Assume I have a family of sets $X=\{X_1,X_2,...,X_m\}$ each set $X_i\in X$ has $n$ elements $\{x^i_1,x^i_2,...,x^i_n\}$. Let $Z$ be the cartesian product of $X$. Let $z^{\downarrow V}$ be the ...