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

2
votes
1answer
118 views

Constructing an order-preserving function between two strict p.o.s that is not one-to-one.

Out of Winfried Just and Martin Weese's Set theory book: Give an example of strict partial orders $\langle X,<_x\rangle$ and $\langle Y,<_y\rangle$ and of a function $\tau : X \to Y$ that is ...
1
vote
4answers
104 views

Cardinality of the set $\{(A, B) \mid A ⊆ B ⊆ S\}$ [duplicate]

If $S$ is a set with $n$ elements, what is the cardinality of the set $\left\{(A, B) \mid A ⊆ B ⊆ S\right\}$
2
votes
2answers
98 views

Is there an infinite sequence AB, BC, CD, DX, …, YZ

Is it possible to construct an infinite set of ordered pairs of form S = {(A, B), (B, C), (C, D), (D, x), ..., (y, Z)}? Every element (B, C...) must appear only once as the first object in one of the ...
23
votes
12answers
3k views

How is the set of all programs countable?

I'm having a hard time seeing how the number of programs is not uncountable, since for every real number, you can create a program that's prints out that number. Doesn't that immediately establish ...
0
votes
1answer
70 views

Problem Help-Proof set

When A,B are set proof that $\left ( A\setminus B \right )^{C}=A^{C}\cup \left ( A\cap B \right )$ 1.What does C mean? 2.Proof that. Thanks in advanced
4
votes
2answers
516 views

Second-countable implies separable/Axiom countable choice

Let $(X,\mathscr T)$ be a topological space, and $(B_n)_{n\ge1}$ a countable basis for X. Under this assumptions, X is separable. The proof of this assertion is as follows: We can assume without ...
0
votes
1answer
188 views

Bijection between $\mathbb{R}$ and $\mathbb{R}^2$ [duplicate]

I have been thinking for a while whether its possible to have bijection between $\mathbb{R}$ and $\mathbb{R}^2$, but I cant think of a solution. So my question is: is there a bijection between ...
1
vote
1answer
42 views

How can I construct in $\Gamma$ an structure of Directed Set?

Suppose $\Gamma$ is a uncountable set. It is possible to give $\Gamma$ an structure of an directed set? For an definition of directed set, see here.
2
votes
1answer
208 views

Set theory problem book?

Is there any online resource or a book which has good questions and solutions on basic to advanced set theory? Topics such as ordered sets relations cardinality indexes stes etc are of interest
9
votes
3answers
262 views

Question about members in sets

Let $A_1,A_2,...,A_n$ be sets with $k$ members in $A_i$ for every $1\le i\le n$. Suppose that the $A_i$ satisfy: 1) $|A_i\cap A_j| = 1$ for all $i\ne j$, 2) $A_1\cap A_2\cdots\cap A_n =\emptyset$. ...
1
vote
2answers
277 views

set theory subsets and inheirtance in Java

I started reading Concepts of Modern Mathematics and naturally, I came across set theory. I was wondering if someone could clarify my understanding for subsets by way of inheritance in Java or any ...
0
votes
3answers
91 views

Countability of the continuum

I googled the word countability of continuum and the first result (Ok, second to this thread!) was from Arxiv. I was wondering how valid this argument is. I would also appreciate any additional ...
1
vote
4answers
182 views

Prove $A\cup (A\cap B) = A$

What I've done so far is stated that $(A \cup A) \cap (A \cup B)$ by distribution $A\cap (A\cup B)$ by 1, definition of $\cup$ $A\cap A$ by 2, definition of $\cup$ $A$ ...
0
votes
2answers
113 views

How to show $A \setminus (V \cap A) = A\cap(X \setminus V)$

Question: Suppose that $A, V$ are subsets of $X$. Prove that $A \setminus (V \cap A) = A\cap(X \setminus V)$ Try: $A \setminus (V \cap A)= (A \setminus V) \cup (A \setminus A) = A \setminus V = ...
12
votes
8answers
2k views

Why do we accept Kuratowski's definition of ordered pairs?

I've been struggling understanding Kuratowski's definition of ordered pairs. I understand what it means but I don't see why I should accept it. I've seen this question and this one, most importantly ...
4
votes
2answers
92 views

Existence of an injection from $\Bbb N$ without the axiom of choice

If you have a set $A$, and it satisfies that for some $x\in A$, there is a bijection between $A$ and $A\setminus\{x\}$. Does that imply that there is an injection from $\Bbb N$ to $A$? It is clearly ...
1
vote
2answers
66 views

Number of unique permutations on an alternating bitstring?

Given an alternating bitstring of length k, how many unique permutations can be made from it? To illustrate, I'll show some examples: $$1 \rightarrow 1$$ $$10 \rightarrow 10,01$$ $$101 \rightarrow ...
1
vote
2answers
199 views

No Bijection from set $X$ to $X - \{x\}$

I want to show that there is no bijection from finite set $X$ to the set $X - \{x\}$. But I don't want to use any of the rules of cardinality or Cantor–Bernstein–Schroeder theorem etc. Is there a ...
2
votes
4answers
128 views

Is there a good visual aid or picture to help understand openness and closedness?

I'm struggling to grasp the idea of open, closed, clopen and not open and not closed sets in a more formal approach like how it's described in a math analysis class. Is there a good picture somewhere ...
3
votes
5answers
339 views

Is $\Bbb Q$ countable or uncountable?

I know how to do the proof in terms of using Analysis but how do you do the proof for someone that does not have that much proof experience: Prove that $\Bbb Q$ is a countable set.
4
votes
1answer
69 views

Verification of a proof involving Hausdorff max. principle and collections

I am given this proposition to prove which is a corollary to HMP(Hausdorff maximality principle). My two concerns are: 1. is my attempted proof correct? and 2. Is HMP applicable even when we're ...
0
votes
3answers
1k views

Show that a map is well-defined and homomorphism

Define a function $f_n:\mathbb{Z}_m \to \mathbb{Z}_m$ as a map $\bar{a}\mapsto n\cdot \bar{a}$. Show that it is both well-defined and a group homomorphism. For the well-defined part, I know that I ...
1
vote
1answer
36 views

Size of the set of palindromic functions

Solve and prove for the size of the the set of functions from k bits to 2x bits where the output bitstrings are palindromic (the first x bits are the reverse bitstring of the last x bits). Because ...
0
votes
2answers
325 views

About the definition of n-tuple

I've read from the theory of sets that the definition of ordered pair is foundational. To define formally the term of $n$-tuple I suppose we need to use the concept of ordered pair as well as the ...
2
votes
2answers
149 views

Properties of Arbitrary Cartesian Products

Let $X_\delta$ and $Y_\delta$ be index families of sets with the index set $\Delta$. Show the following: $$\begin{align} \prod_{\delta \in \Delta} X_\delta \cup \prod_{\delta \in \Delta} Y_\delta ...
3
votes
3answers
111 views

Confusion on understanding a proposition on equivalence classes

I am given to prove this proposition on equivalence classes. Each element of $A$ is an element of one and only one equivalent class. The part that is confusing is one and only one. It sounds ...
1
vote
2answers
75 views

How to understand closed subsets of limit ordinal?

On page 20, Constructibility, K.J.Devlin, (Let $\alpha$ is a limit ordinal)A set $A \subseteq \alpha$ is closed, iff $\bigcup A \cap \gamma \in A$ for all $\gamma < \alpha$. Equivalently, if we ...
3
votes
3answers
151 views

How prove $(A\triangle B)\triangle C=A\triangle(B\triangle C)$ bydefining function from $(A\triangle B)\triangle C$ to $A\triangle(B\triangle C)$

How prove $(A \triangle{}B) \triangle{}C=A \triangle{}(B \triangle{}C)$ by defining function from $(A \triangle{}B) \triangle{}C$ to $A \triangle{}(B \triangle{}C)$? $(A \triangle{}B:=A\cup B-(A\cap ...
0
votes
1answer
119 views

Proof of similarity between well ordered sets

In Naive Set Theory we have a proof that two well ordered sets are either similar to one another or one of them is similar to an initial segment of the other. It goes like this: We assume that ...
0
votes
4answers
128 views

Cardinality of a set $\{A,B\}$ $A$ is a subset of $B$, which is a subset of $S$

Let's say that $A$ is a subset of $B$ and be is a subset of a set $S$ of $n$ elements. How big is the set $\{(A,B)\}$ then.
0
votes
1answer
4k views

Why is the Cartesian product of a set $A$ and empty set an empty set? [duplicate]

Let $A \times \emptyset = \{(x,y)| x\in A, y \in \emptyset \}$. We know there is no element in $\emptyset$. But how does it follow that $A \times \emptyset = \emptyset $?
2
votes
1answer
48 views

A question about isomorphism between orders

Is there an isomorphism between the naturals with the regular order $\le$ and the set $\mathbb{N}\times \mathbb{N}$ with the order $R$ defined to be $\langle k_1,r_1\rangle\mathrel R\langle ...
2
votes
1answer
115 views

No zero divisors in $\mathbb{Z}$

Let $\mathbb{N}$ be natural number with injective successor function $s.$ Define addition $+:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$: $\forall a,b\in\mathbb{N}.\;a+ 0 =0+a= a\;\wedge\;a+ s(b) = ...
5
votes
2answers
444 views

Why are infinite cardinals limit ordinals?

My book states this as obvious, but it isn't so trivial to me. thanks
4
votes
3answers
115 views

In how many ways we can arrange two strings with distinct elements such that the order is intact?

In how many ways we can arrange two strings (with distinct elements) such that the order is intact? For example if the strings are , "aA" and "bk". The valid arrangements are: ...
5
votes
1answer
113 views

Is $\alpha^{\beta}=2^{\beta}$ for all infinite cardinalities $\alpha, \beta$?

Is $\alpha^{\beta}=2^{\beta}$ for all infinite cardinalities $\alpha, \beta$? I was wondering about this since I've encountered examples of times where this holds, but I can't seem to prove it myself ...
3
votes
2answers
133 views

Proof that the even natural numbers are a subset of $\mathbb{N}$

I'm doing some self-studying on discrete mathematics and so far its going well however I came upon a question that whilst I can make sense of and I know that set $A$ is a subset of set $B$, I cannot ...
0
votes
3answers
93 views

Question when proving well-ordering principle

In my text book the proof of well ordering principle goes like this: Let A be an arbitrarily given nonempty set which is to be well-ordered. Consider the family A* of all well-ordered sets ($A_0$, ...
1
vote
0answers
48 views

Selecting the same item from a set without knowing the set's size

I don't know if this is possible or not but I thought I'd ask. Given an ordered list a1,...,an Is it possible that if each element of the list represented numeric indexes that I could consistently ...
2
votes
1answer
291 views

Basic questions on permutation of sets (composition, inverse and signatures)

I am having trouble finding good resources to understand composition of permutation, I was wondering how can you go about multiplying (composition) of two permutations and how do they return the just ...
0
votes
4answers
270 views

The set of all functions from $\mathbb{N} \to \{0, 1\}$ is uncountable?

How can I prove that the set of all functions from $\mathbb{N} \to \{0, 1\}$ is uncountable? Edit: This answer came to mind. Is it correct? This answer just came to mind. By contradiction suppose ...
1
vote
4answers
92 views

Question about bijections

Determine whether or not the following functions from real numbers to real numbers are bijections. If they are bijections, then find the inverse. If they are not bijections, then explain why not. I ...
1
vote
3answers
677 views

What are your favorite proofs using mathematical induction? [closed]

I would like to get a list going of cool proofs using mathematical induction. Im not really interested in the standard proofs, like $1+3+5+...+(2n-1)=n^2$, that can be found in any discrete math ...
1
vote
2answers
392 views

common knowledge and concept of coarsening partition

Here is a proof of the equivalence between my definition and Aumann's for "common knowledge". I'm assuming some familiarity with set partitions. Aumann's definition is in terms of the ...
5
votes
3answers
1k views

Examples of transfinite induction

I know what transfinite induction is, but not sure how it is used to prove something. Can anyone show how transfinite induction is used to prove something? A simple case is OK.
2
votes
2answers
85 views

Addition of cardinalities

"It is impossible to define addition of cardinalities since the resulting operation is not well-defined" The above is the true and false question and what i think the statement above is false and my ...
1
vote
1answer
142 views

Is arbitrary union any different from typical union (set theory)

So suppose that $\bigcup_{i}X_i \, i \in \mathbb{N}$ where $X_i = \{x \, \, | \, x \leq i, x \in \mathbb{N}\}$. So, $X_1 = \{0,1\}$ and so on. Question is, will this arbitrary union result in the ...
1
vote
2answers
389 views

Cardinality of all the functions from $\mathbb N$ to $\{0,1\}$.

Is it true to say that: $$|\{0,1\}^\mathbb N| = |\{0,1\}|^{|\mathbb N|} = 2^{\aleph_0}=\aleph$$ As I know the right part of the equation is true, but I don't know if the equations to it are allowed.
3
votes
4answers
2k views

Empty set does not belong to empty set

Herbert in his book "Elements of set theory" on page no 3 says that we can form the set $ \{ \emptyset \} $ whose only member is $\emptyset $. Note that $ \{ \emptyset \} \neq \emptyset $, ...
3
votes
3answers
90 views

Are $\prod_{i\in I}{X_i^2}$ and $(\prod_{i\in I}{X_i})^2$ the same?

We have: $$\prod_{i\in I}{X_i}=\left\{f:I\to\bigcup_{i\in I}{X_i}~\Big|~ (\forall i\in I)\big(f(i)\in X_i\big)\right\}$$ Is it true: $$\left|\prod_{i\in I}{X_i^2}\right|=\left|\left(\prod_{i\in ...